| 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 |
| (...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 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 } | 61 } |
| 62 | 62 |
| 63 Bitmap::~Bitmap() { | 63 Bitmap::~Bitmap() { |
| 64 if (alloc_) | 64 if (alloc_) |
| 65 delete [] map_; | 65 delete[] map_; |
| 66 } | 66 } |
| 67 | 67 |
| 68 void Bitmap::Resize(int num_bits, bool clear_bits) { | 68 void Bitmap::Resize(int num_bits, bool clear_bits) { |
| 69 DCHECK(alloc_ || !map_); | 69 DCHECK(alloc_ || !map_); |
| 70 const int old_maxsize = num_bits_; | 70 const int old_maxsize = num_bits_; |
| 71 const int old_array_size = array_size_; | 71 const int old_array_size = array_size_; |
| 72 array_size_ = RequiredArraySize(num_bits); | 72 array_size_ = RequiredArraySize(num_bits); |
| 73 | 73 |
| 74 if (array_size_ != old_array_size) { | 74 if (array_size_ != old_array_size) { |
| 75 uint32* new_map = new uint32[array_size_]; | 75 uint32* new_map = new uint32[array_size_]; |
| 76 // Always clear the unused bits in the last word. | 76 // Always clear the unused bits in the last word. |
| 77 new_map[array_size_ - 1] = 0; | 77 new_map[array_size_ - 1] = 0; |
| 78 memcpy(new_map, map_, | 78 memcpy( |
| 79 sizeof(*map_) * std::min(array_size_, old_array_size)); | 79 new_map, map_, sizeof(*map_) * std::min(array_size_, old_array_size)); |
| 80 if (alloc_) | 80 if (alloc_) |
| 81 delete[] map_; // No need to check for NULL. | 81 delete[] map_; // No need to check for NULL. |
| 82 map_ = new_map; | 82 map_ = new_map; |
| 83 alloc_ = true; | 83 alloc_ = true; |
| 84 } | 84 } |
| 85 | 85 |
| 86 num_bits_ = num_bits; | 86 num_bits_ = num_bits; |
| 87 if (old_maxsize < num_bits_ && clear_bits) { | 87 if (old_maxsize < num_bits_ && clear_bits) { |
| 88 SetRange(old_maxsize, num_bits_, false); | 88 SetRange(old_maxsize, num_bits_, false); |
| 89 } | 89 } |
| 90 } | 90 } |
| 91 | 91 |
| 92 void Bitmap::Set(int index, bool value) { | 92 void Bitmap::Set(int index, bool value) { |
| 93 DCHECK_LT(index, num_bits_); | 93 DCHECK_LT(index, num_bits_); |
| 94 DCHECK_GE(index, 0); | 94 DCHECK_GE(index, 0); |
| 95 const int i = index & (kIntBits - 1); | 95 const int i = index & (kIntBits - 1); |
| 96 const int j = index / kIntBits; | 96 const int j = index / kIntBits; |
| 97 if (value) | 97 if (value) |
| 98 map_[j] |= (1 << i); | 98 map_[j] |= (1 << i); |
| 99 else | 99 else |
| 100 map_[j] &= ~(1 << i); | 100 map_[j] &= ~(1 << i); |
| 101 } | 101 } |
| 102 | 102 |
| 103 bool Bitmap::Get(int index) const { | 103 bool Bitmap::Get(int index) const { |
| 104 DCHECK_LT(index, num_bits_); | 104 DCHECK_LT(index, num_bits_); |
| 105 DCHECK_GE(index, 0); | 105 DCHECK_GE(index, 0); |
| 106 const int i = index & (kIntBits-1); | 106 const int i = index & (kIntBits - 1); |
| 107 const int j = index / kIntBits; | 107 const int j = index / kIntBits; |
| 108 return ((map_[j] & (1 << i)) != 0); | 108 return ((map_[j] & (1 << i)) != 0); |
| 109 } | 109 } |
| 110 | 110 |
| 111 void Bitmap::Toggle(int index) { | 111 void Bitmap::Toggle(int index) { |
| 112 DCHECK_LT(index, num_bits_); | 112 DCHECK_LT(index, num_bits_); |
| 113 DCHECK_GE(index, 0); | 113 DCHECK_GE(index, 0); |
| 114 const int i = index & (kIntBits - 1); | 114 const int i = index & (kIntBits - 1); |
| 115 const int j = index / kIntBits; | 115 const int j = index / kIntBits; |
| 116 map_[j] ^= (1 << i); | 116 map_[j] ^= (1 << i); |
| (...skipping 27 matching lines...) Expand all Loading... |
| 144 | 144 |
| 145 if (begin == end) | 145 if (begin == end) |
| 146 return; | 146 return; |
| 147 | 147 |
| 148 // Now set the bits in the last word. | 148 // Now set the bits in the last word. |
| 149 int end_offset = end & (kIntBits - 1); | 149 int end_offset = end & (kIntBits - 1); |
| 150 end -= end_offset; | 150 end -= end_offset; |
| 151 SetWordBits(end, end_offset, value); | 151 SetWordBits(end, end_offset, value); |
| 152 | 152 |
| 153 // Set all the words in the middle. | 153 // Set all the words in the middle. |
| 154 memset(map_ + (begin / kIntBits), (value ? 0xFF : 0x00), | 154 memset(map_ + (begin / kIntBits), |
| 155 (value ? 0xFF : 0x00), |
| 155 ((end / kIntBits) - (begin / kIntBits)) * sizeof(*map_)); | 156 ((end / kIntBits) - (begin / kIntBits)) * sizeof(*map_)); |
| 156 } | 157 } |
| 157 | 158 |
| 158 // Return true if any bit between begin inclusive and end exclusive | 159 // Return true if any bit between begin inclusive and end exclusive |
| 159 // is set. 0 <= begin <= end <= bits() is required. | 160 // is set. 0 <= begin <= end <= bits() is required. |
| 160 bool Bitmap::TestRange(int begin, int end, bool value) const { | 161 bool Bitmap::TestRange(int begin, int end, bool value) const { |
| 161 DCHECK_LT(begin, num_bits_); | 162 DCHECK_LT(begin, num_bits_); |
| 162 DCHECK_LE(end, num_bits_); | 163 DCHECK_LE(end, num_bits_); |
| 163 DCHECK_LE(begin, end); | 164 DCHECK_LE(begin, end); |
| 164 DCHECK_GE(begin, 0); | 165 DCHECK_GE(begin, 0); |
| (...skipping 137 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 302 uint32 to_add = 0xffffffff << len; | 303 uint32 to_add = 0xffffffff << len; |
| 303 to_add = (~to_add) << offset; | 304 to_add = (~to_add) << offset; |
| 304 if (value) { | 305 if (value) { |
| 305 map_[word] |= to_add; | 306 map_[word] |= to_add; |
| 306 } else { | 307 } else { |
| 307 map_[word] &= ~to_add; | 308 map_[word] &= ~to_add; |
| 308 } | 309 } |
| 309 } | 310 } |
| 310 | 311 |
| 311 } // namespace disk_cache | 312 } // namespace disk_cache |
| OLD | NEW |