| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 992733002:
Remove //net (except for Android test stuff) and sdch (Closed)
Base URL: git@github.com:domokit/mojo.git@master