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