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