net/disk_cache/blockfile/bitmap.cc

   1 // Copyright (c) 2009 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/disk_cache/blockfile/bitmap.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/logging.h"
  10
  11 namespace {
  12
  13 // Returns the number of trailing zeros.
  14 int FindLSBSetNonZero(uint32 word) {
  15   // Get the LSB, put it on the exponent of a 32 bit float and remove the
  16   // mantisa and the bias. This code requires IEEE 32 bit float compliance.
  17   float f = static_cast<float>(word & -static_cast<int>(word));
  18
  19   // We use a union to go around strict-aliasing complains.
  20   union {
  21     float ieee_float;
  22     uint32 as_uint;
  23   } x;
  24
  25   x.ieee_float = f;
  26   return (x.as_uint >> 23) - 0x7f;
  27 }
  28
  29 // Returns the index of the first bit set to |value| from |word|. This code
  30 // assumes that we'll be able to find that bit.
  31 int FindLSBNonEmpty(uint32 word, bool value) {
  32   // If we are looking for 0, negate |word| and look for 1.
  33   if (!value)
  34     word = ~word;
  35
  36   return FindLSBSetNonZero(word);
  37 }
  38
  39 }  // namespace
  40
  41 namespace disk_cache {
  42
  43 Bitmap::Bitmap(int num_bits, bool clear_bits)
  44     : num_bits_(num_bits),
  45       array_size_(RequiredArraySize(num_bits)),
  46       alloc_(true) {
  47   map_ = new uint32[array_size_];
  48
  49   // Initialize all of the bits.
  50   if (clear_bits)
  51     Clear();
  52 }
  53
  54 Bitmap::Bitmap(uint32* map, int num_bits, int num_words)
  55     : map_(map),
  56       num_bits_(num_bits),
  57       // If size is larger than necessary, trim because array_size_ is used
  58       // as a bound by various methods.
  59       array_size_(std::min(RequiredArraySize(num_bits), num_words)),
  60       alloc_(false) {
  61 }
  62
  63 Bitmap::~Bitmap() {
  64   if (alloc_)
  65     delete [] map_;
  66 }
  67
  68 void Bitmap::Resize(int num_bits, bool clear_bits) {
  69   DCHECK(alloc_ || !map_);
  70   const int old_maxsize = num_bits_;
  71   const int old_array_size = array_size_;
  72   array_size_ = RequiredArraySize(num_bits);
  73
  74   if (array_size_ != old_array_size) {
  75     uint32* new_map = new uint32[array_size_];
  76     // Always clear the unused bits in the last word.
  77     new_map[array_size_ - 1] = 0;
  78     memcpy(new_map, map_,
  79            sizeof(*map_) * std::min(array_size_, old_array_size));
  80     if (alloc_)
  81       delete[] map_;  // No need to check for NULL.
  82     map_ = new_map;
  83     alloc_ = true;
  84   }
  85
  86   num_bits_ = num_bits;
  87   if (old_maxsize < num_bits_ && clear_bits) {
  88     SetRange(old_maxsize, num_bits_, false);
  89   }
  90 }
  91
  92 void Bitmap::Set(int index, bool value) {
  93   DCHECK_LT(index, num_bits_);
  94   DCHECK_GE(index, 0);
  95   const int i = index & (kIntBits - 1);
  96   const int j = index / kIntBits;
  97   if (value)
  98     map_[j] |= (1 << i);
  99   else
 100     map_[j] &= ~(1 << i);
 101 }
 102
 103 bool Bitmap::Get(int index) const {
 104   DCHECK_LT(index, num_bits_);
 105   DCHECK_GE(index, 0);
 106   const int i = index & (kIntBits-1);
 107   const int j = index / kIntBits;
 108   return ((map_[j] & (1 << i)) != 0);
 109 }
 110
 111 void Bitmap::Toggle(int index) {
 112   DCHECK_LT(index, num_bits_);
 113   DCHECK_GE(index, 0);
 114   const int i = index & (kIntBits - 1);
 115   const int j = index / kIntBits;
 116   map_[j] ^= (1 << i);
 117 }
 118
 119 void Bitmap::SetMapElement(int array_index, uint32 value) {
 120   DCHECK_LT(array_index, array_size_);
 121   DCHECK_GE(array_index, 0);
 122   map_[array_index] = value;
 123 }
 124
 125 uint32 Bitmap::GetMapElement(int array_index) const {
 126   DCHECK_LT(array_index, array_size_);
 127   DCHECK_GE(array_index, 0);
 128   return map_[array_index];
 129 }
 130
 131 void Bitmap::SetMap(const uint32* map, int size) {
 132   memcpy(map_, map, std::min(size, array_size_) * sizeof(*map_));
 133 }
 134
 135 void Bitmap::SetRange(int begin, int end, bool value) {
 136   DCHECK_LE(begin, end);
 137   int start_offset = begin & (kIntBits - 1);
 138   if (start_offset) {
 139     // Set the bits in the first word.
 140     int len = std::min(end - begin, kIntBits - start_offset);
 141     SetWordBits(begin, len, value);
 142     begin += len;
 143   }
 144
 145   if (begin == end)
 146     return;
 147
 148   // Now set the bits in the last word.
 149   int end_offset = end & (kIntBits - 1);
 150   end -= end_offset;
 151   SetWordBits(end, end_offset, value);
 152
 153   // Set all the words in the middle.
 154   memset(map_ + (begin / kIntBits), (value ? 0xFF : 0x00),
 155          ((end / kIntBits) - (begin / kIntBits)) * sizeof(*map_));
 156 }
 157
 158 // Return true if any bit between begin inclusive and end exclusive
 159 // is set.  0 <= begin <= end <= bits() is required.
 160 bool Bitmap::TestRange(int begin, int end, bool value) const {
 161   DCHECK_LT(begin, num_bits_);
 162   DCHECK_LE(end, num_bits_);
 163   DCHECK_LE(begin, end);
 164   DCHECK_GE(begin, 0);
 165   DCHECK_GE(end, 0);
 166
 167   // Return false immediately if the range is empty.
 168   if (begin >= end || end <= 0)
 169     return false;
 170
 171   // Calculate the indices of the words containing the first and last bits,
 172   // along with the positions of the bits within those words.
 173   int word = begin / kIntBits;
 174   int offset = begin & (kIntBits - 1);
 175   int last_word = (end - 1) / kIntBits;
 176   int last_offset = (end - 1) & (kIntBits - 1);
 177
 178   // If we are looking for zeros, negate the data from the map.
 179   uint32 this_word = map_[word];
 180   if (!value)
 181     this_word = ~this_word;
 182
 183   // If the range spans multiple words, discard the extraneous bits of the
 184   // first word by shifting to the right, and then test the remaining bits.
 185   if (word < last_word) {
 186     if (this_word >> offset)
 187       return true;
 188     offset = 0;
 189
 190     word++;
 191     // Test each of the "middle" words that lies completely within the range.
 192     while (word < last_word) {
 193       this_word = map_[word++];
 194       if (!value)
 195         this_word = ~this_word;
 196       if (this_word)
 197         return true;
 198     }
 199   }
 200
 201   // Test the portion of the last word that lies within the range. (This logic
 202   // also handles the case where the entire range lies within a single word.)
 203   const uint32 mask = ((2 << (last_offset - offset)) - 1) << offset;
 204
 205   this_word = map_[last_word];
 206   if (!value)
 207     this_word = ~this_word;
 208
 209   return (this_word & mask) != 0;
 210 }
 211
 212 bool Bitmap::FindNextBit(int* index, int limit, bool value) const {
 213   DCHECK_LT(*index, num_bits_);
 214   DCHECK_LE(limit, num_bits_);
 215   DCHECK_LE(*index, limit);
 216   DCHECK_GE(*index, 0);
 217   DCHECK_GE(limit, 0);
 218
 219   const int bit_index = *index;
 220   if (bit_index >= limit || limit <= 0)
 221     return false;
 222
 223   // From now on limit != 0, since if it was we would have returned false.
 224   int word_index = bit_index >> kLogIntBits;
 225   uint32 one_word = map_[word_index];
 226
 227   // Simple optimization where we can immediately return true if the first
 228   // bit is set.  This helps for cases where many bits are set, and doesn't
 229   // hurt too much if not.
 230   if (Get(bit_index) == value)
 231     return true;
 232
 233   const int first_bit_offset = bit_index & (kIntBits - 1);
 234
 235   // First word is special - we need to mask off leading bits.
 236   uint32 mask = 0xFFFFFFFF << first_bit_offset;
 237   if (value) {
 238     one_word &= mask;
 239   } else {
 240     one_word |= ~mask;
 241   }
 242
 243   uint32 empty_value = value ? 0 : 0xFFFFFFFF;
 244
 245   // Loop through all but the last word.  Note that 'limit' is one
 246   // past the last bit we want to check, and we don't want to read
 247   // past the end of "words".  E.g. if num_bits_ == 32 only words[0] is
 248   // valid, so we want to avoid reading words[1] when limit == 32.
 249   const int last_word_index = (limit - 1) >> kLogIntBits;
 250   while (word_index < last_word_index) {
 251     if (one_word != empty_value) {
 252       *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value);
 253       return true;
 254     }
 255     one_word = map_[++word_index];
 256   }
 257
 258   // Last word is special - we may need to mask off trailing bits.  Note that
 259   // 'limit' is one past the last bit we want to check, and if limit is a
 260   // multiple of 32 we want to check all bits in this word.
 261   const int last_bit_offset = (limit - 1) & (kIntBits - 1);
 262   mask = 0xFFFFFFFE << last_bit_offset;
 263   if (value) {
 264     one_word &= ~mask;
 265   } else {
 266     one_word |= mask;
 267   }
 268   if (one_word != empty_value) {
 269     *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value);
 270     return true;
 271   }
 272   return false;
 273 }
 274
 275 int Bitmap::FindBits(int* index, int limit, bool value) const {
 276   DCHECK_LT(*index, num_bits_);
 277   DCHECK_LE(limit, num_bits_);
 278   DCHECK_LE(*index, limit);
 279   DCHECK_GE(*index, 0);
 280   DCHECK_GE(limit, 0);
 281
 282   if (!FindNextBit(index, limit, value))
 283     return false;
 284
 285   // Now see how many bits have the same value.
 286   int end = *index;
 287   if (!FindNextBit(&end, limit, !value))
 288     return limit - *index;
 289
 290   return end - *index;
 291 }
 292
 293 void Bitmap::SetWordBits(int start, int len, bool value) {
 294   DCHECK_LT(len, kIntBits);
 295   DCHECK_GE(len, 0);
 296   if (!len)
 297     return;
 298
 299   int word = start / kIntBits;
 300   int offset = start % kIntBits;
 301
 302   uint32 to_add = 0xffffffff << len;
 303   to_add = (~to_add) << offset;
 304   if (value) {
 305     map_[word] |= to_add;
 306   } else {
 307     map_[word] &= ~to_add;
 308   }
 309 }
 310
 311 }  // namespace disk_cache