Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(268)

Side by Side Diff: net/disk_cache/blockfile/bitmap.cc

Issue 1535363003: Switch to standard integer types in net/. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: stddef Created 5 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « net/disk_cache/blockfile/bitmap.h ('k') | net/disk_cache/blockfile/bitmap_unittest.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
OLDNEW
« no previous file with comments | « net/disk_cache/blockfile/bitmap.h ('k') | net/disk_cache/blockfile/bitmap_unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698