summaryrefslogtreecommitdiffstats
path: root/net/disk_cache/bitmap.cc
diff options
context:
space:
mode:
Diffstat (limited to 'net/disk_cache/bitmap.cc')
-rw-r--r--net/disk_cache/bitmap.cc272
1 files changed, 0 insertions, 272 deletions
diff --git a/net/disk_cache/bitmap.cc b/net/disk_cache/bitmap.cc
deleted file mode 100644
index 7c507b8..0000000
--- a/net/disk_cache/bitmap.cc
+++ /dev/null
@@ -1,272 +0,0 @@
-// 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.
- float f = static_cast<float>(word & -static_cast<int>(word));
- return (*reinterpret_cast<uint32*>(&f) >> 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_];
- 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
generated by cgit v1.1 at 2025-02-01 11:32:34 +0000