Initial source checkin.

The source files were determined by building net_unittests in chromium's source
tree. Some of the obvious libraries were left out (v8, gmock, gtest).

The Android.mk file has all the sources (minus unittests and tools) that were
used during net_unittests compilation. Nothing builds yet because of STL but
that is the next task. The .cpp files will most likely not compile anyways
because of the LOCAL_CPP_EXTENSION mod. I will have to break this into multiple
projects to get around that limitation.

1 files changed, 284 insertions, 0 deletions

diff --git a/net/disk_cache/bitmap.cc b/net/disk_cache/bitmap.cc
new file mode 100644
index 0000000..e025090
--- /dev/null
+++ b/net/disk_cache/bitmap.cc
@@ -0,0 +1,284 @@
+// 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);
+  DCHECK_GE(len, 0);
+  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) {
+  DCHECK_LE(begin, end);
+  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