// 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 <algorithm>
#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 {
Bitmap::Bitmap(int num_bits, bool clear_bits)
: num_bits_(num_bits),
array_size_(RequiredArraySize(num_bits)),
alloc_(true) {
map_ = new uint32[array_size_];
// Initialize all of the bits.
if (clear_bits)
Clear();
}
Bitmap::Bitmap(uint32* map, int num_bits, int num_words)
: map_(map),
num_bits_(num_bits),
// If size is larger than necessary, trim because array_size_ is used
// as a bound by various methods.
array_size_(std::min(RequiredArraySize(num_bits), num_words)),
alloc_(false) {
}
Bitmap::~Bitmap() {
if (alloc_)
delete [] map_;
}
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::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;
}
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;
}
}
} // namespace disk_cache