Disk cache: First pass to add support for sparse entries.

Adding Read/Write support.

BUG=12258
TEST=unittests.

original review: http://codereview.chromium.org/126179

Review URL: http://codereview.chromium.org/132031

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@18772 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 282 insertions, 0 deletions

diff --git a/net/disk_cache/bitmap.cc b/net/disk_cache/bitmap.cc
new file mode 100644
index 0000000..79606c5
--- /dev/null
+++ b/net/disk_cache/bitmap.cc
@@ -0,0 +1,282 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/disk_cache/bitmap.h"
+
+#include "base/logging.h"
+
+namespace {
+
+// Returns the number of trailing zeros.
+int FindLSBSetNonZero(uint32 word) {
+  // Get the LSB, put it on the exponent of a 32 bit float and remove the
+  // mantisa and the bias. This code requires IEEE 32 bit float compliance.
+  float f = static_cast<float>(word & -static_cast<int>(word));
+
+  // We use a union to go around strict-aliasing complains.
+  union {
+    float ieee_float;
+    uint32 as_uint;
+  } x;
+
+  x.ieee_float = f;
+  return (x.as_uint >> 23) - 0x7f;
+}
+
+// Returns the index of the first bit set to |value| from |word|. This code
+// assumes that we'll be able to find that bit.
+int FindLSBNonEmpty(uint32 word, bool value) {
+  // If we are looking for 0, negate |word| and look for 1.
+  if (!value)
+    word = ~word;
+
+  return FindLSBSetNonZero(word);
+}
+
+}
+
+namespace disk_cache {
+
+void Bitmap::Resize(int num_bits, bool clear_bits) {
+  DCHECK(alloc_ || !map_);
+  const int old_maxsize = num_bits_;
+  const int old_array_size = array_size_;
+  array_size_ = RequiredArraySize(num_bits);
+
+  if (array_size_ != old_array_size) {
+    uint32* new_map = new uint32[array_size_];
+    // Always clear the unused bits in the last word.
+    new_map[array_size_ - 1] = 0;
+    memcpy(new_map, map_,
+           sizeof(*map_) * std::min(array_size_, old_array_size));
+    if (alloc_)
+      delete[] map_;  // No need to check for NULL.
+    map_ = new_map;
+    alloc_ = true;
+  }
+
+  num_bits_ = num_bits;
+  if (old_maxsize < num_bits_ && clear_bits) {
+    SetRange(old_maxsize, num_bits_, false);
+  }
+}
+
+void Bitmap::Set(int index, bool value) {
+  DCHECK_LT(index, num_bits_);
+  DCHECK_GE(index, 0);
+  const int i = index & (kIntBits - 1);
+  const int j = index / kIntBits;
+  if (value)
+    map_[j] |= (1 << i);
+  else
+    map_[j] &= ~(1 << i);
+}
+
+bool Bitmap::Get(int index) const {
+  DCHECK_LT(index, num_bits_);
+  DCHECK_GE(index, 0);
+  const int i = index & (kIntBits-1);
+  const int j = index / kIntBits;
+  return map_[j] & (1 << i) ? true : false;
+}
+
+void Bitmap::Toggle(int index) {
+  DCHECK_LT(index, num_bits_);
+  DCHECK_GE(index, 0);
+  const int i = index & (kIntBits - 1);
+  const int j = index / kIntBits;
+  map_[j] ^= (1 << i);
+}
+
+void Bitmap::SetMapElement(int array_index, uint32 value) {
+  DCHECK_LT(array_index, array_size_);
+  DCHECK_GE(array_index, 0);
+  map_[array_index] = value;
+}
+
+uint32 Bitmap::GetMapElement(int array_index) const {
+  DCHECK_LT(array_index, array_size_);
+  DCHECK_GE(array_index, 0);
+  return map_[array_index];
+}
+
+void Bitmap::SetMap(const uint32* map, int size) {
+  memcpy(map_, map, std::min(size, array_size_) * sizeof(*map_));
+}
+
+void Bitmap::SetWordBits(int start, int len, bool value) {
+  DCHECK_LT(len, kIntBits);
+  if (!len)
+    return;
+
+  int word = start / kIntBits;
+  int offset = start % kIntBits;
+
+  uint32 to_add = 0xffffffff << len;
+  to_add = (~to_add) << offset;
+  if (value) {
+    map_[word] |= to_add;
+  } else {
+    map_[word] &= ~to_add;
+  }
+}
+
+void Bitmap::SetRange(int begin, int end, bool value) {
+  int start_offset = begin & (kIntBits - 1);
+  if (start_offset) {
+    // Set the bits in the first word.
+    int len = std::min(end - begin, kIntBits - start_offset);
+    SetWordBits(begin, len, value);
+    begin += len;
+  }
+
+  if (begin == end)
+    return;
+
+  // Now set the bits in the last word.
+  int end_offset = end & (kIntBits - 1);
+  end -= end_offset;
+  SetWordBits(end, end_offset, value);
+
+  // Set all the words in the middle.
+  memset(map_ + (begin / kIntBits), (value ? 0xFF : 0x00),
+         ((end / kIntBits) - (begin / kIntBits)) * sizeof(*map_));
+}
+
+// Return true if any bit between begin inclusive and end exclusive
+// is set.  0 <= begin <= end <= bits() is required.
+bool Bitmap::TestRange(int begin, int end, bool value) const {
+  DCHECK_LT(begin, num_bits_);
+  DCHECK_LE(end, num_bits_);
+  DCHECK_LE(begin, end);
+  DCHECK_GE(begin, 0);
+  DCHECK_GE(end, 0);
+
+  // Return false immediately if the range is empty.
+  if (begin >= end || end <= 0)
+    return false;
+
+  // Calculate the indices of the words containing the first and last bits,
+  // along with the positions of the bits within those words.
+  int word = begin / kIntBits;
+  int offset = begin & (kIntBits - 1);
+  int last_word = (end - 1) / kIntBits;
+  int last_offset = (end - 1) & (kIntBits - 1);
+
+  // If we are looking for zeros, negate the data from the map.
+  uint32 this_word = map_[word];
+  if (!value)
+    this_word = ~this_word;
+
+  // If the range spans multiple words, discard the extraneous bits of the
+  // first word by shifting to the right, and then test the remaining bits.
+  if (word < last_word) {
+    if (this_word >> offset)
+      return true;
+    offset = 0;
+
+    word++;
+    // Test each of the "middle" words that lies completely within the range.
+    while (word < last_word) {
+      this_word = map_[word++];
+      if (!value)
+        this_word = ~this_word;
+      if (this_word)
+        return true;
+    }
+  }
+
+  // Test the portion of the last word that lies within the range. (This logic
+  // also handles the case where the entire range lies within a single word.)
+  const uint32 mask = ((2 << (last_offset - offset)) - 1) << offset;
+
+  this_word = map_[last_word];
+  if (!value)
+    this_word = ~this_word;
+
+  return (this_word & mask) != 0;
+}
+
+bool Bitmap::FindNextBit(int* index, int limit, bool value) const {
+  DCHECK_LT(*index, num_bits_);
+  DCHECK_LE(limit, num_bits_);
+  DCHECK_LE(*index, limit);
+  DCHECK_GE(*index, 0);
+  DCHECK_GE(limit, 0);
+
+  const int bit_index = *index;
+  if (bit_index >= limit || limit <= 0)
+    return false;
+
+  // From now on limit != 0, since if it was we would have returned false.
+  int word_index = bit_index >> kLogIntBits;
+  uint32 one_word = map_[word_index];
+
+  // Simple optimization where we can immediately return true if the first
+  // bit is set.  This helps for cases where many bits are set, and doesn't
+  // hurt too much if not.
+  if (Get(bit_index) == value)
+    return true;
+
+  const int first_bit_offset = bit_index & (kIntBits - 1);
+
+  // First word is special - we need to mask off leading bits.
+  uint32 mask = 0xFFFFFFFF << first_bit_offset;
+  if (value) {
+    one_word &= mask;
+  } else {
+    one_word |= ~mask;
+  }
+
+  uint32 empty_value = value ? 0 : 0xFFFFFFFF;
+
+  // Loop through all but the last word.  Note that 'limit' is one
+  // past the last bit we want to check, and we don't want to read
+  // past the end of "words".  E.g. if num_bits_ == 32 only words[0] is
+  // valid, so we want to avoid reading words[1] when limit == 32.
+  const int last_word_index = (limit - 1) >> kLogIntBits;
+  while (word_index < last_word_index) {
+    if (one_word != empty_value) {
+      *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value);
+      return true;
+    }
+    one_word = map_[++word_index];
+  }
+
+  // Last word is special - we may need to mask off trailing bits.  Note that
+  // 'limit' is one past the last bit we want to check, and if limit is a
+  // multiple of 32 we want to check all bits in this word.
+  const int last_bit_offset = (limit - 1) & (kIntBits - 1);
+  mask = 0xFFFFFFFE << last_bit_offset;
+  if (value) {
+    one_word &= ~mask;
+  } else {
+    one_word |= mask;
+  }
+  if (one_word != empty_value) {
+    *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value);
+    return true;
+  }
+  return false;
+}
+
+int Bitmap::FindBits(int* index, int limit, bool value) const {
+  DCHECK_LT(*index, num_bits_);
+  DCHECK_LE(limit, num_bits_);
+  DCHECK_LE(*index, limit);
+  DCHECK_GE(*index, 0);
+  DCHECK_GE(limit, 0);
+
+  if (!FindNextBit(index, limit, value))
+    return false;
+
+  // Now see how many bits have the same value.
+  int end = *index;
+  if (!FindNextBit(&end, limit, !value))
+    return limit - *index;
+
+  return end - *index;
+}
+
+}  // namespace disk_cache