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 #ifndef NET_DISK_CACHE_BITMAP_H_ 6 #define NET_DISK_CACHE_BITMAP_H_ 7 8 #include <algorithm> 9 10 #include "base/basictypes.h" 11 12 namespace disk_cache { 13 14 // This class provides support for simple maps of bits. 15 class Bitmap { 16 public: 17 Bitmap() : map_(NULL), num_bits_(0), array_size_(0), alloc_(false) {} 18 19 // This constructor will allocate on a uint32 boundary. If |clear_bits| is 20 // false, the bitmap bits will not be initialized. 21 Bitmap(int num_bits, bool clear_bits) 22 : num_bits_(num_bits), array_size_(RequiredArraySize(num_bits)), 23 alloc_(true) { 24 map_ = new uint32[array_size_]; 25 26 // Initialize all of the bits. 27 if (clear_bits) 28 Clear(); 29 } 30 31 // Constructs a Bitmap with the actual storage provided by the caller. |map| 32 // has to be valid until this object destruction. |num_bits| is the number of 33 // bits in the bitmap, and |num_words| is the size of |map| in 32-bit words. 34 Bitmap(uint32* map, int num_bits, int num_words) 35 : map_(map), num_bits_(num_bits), 36 // If size is larger than necessary, trim because array_size_ is used 37 // as a bound by various methods. 38 array_size_(std::min(RequiredArraySize(num_bits), num_words)), 39 alloc_(false) {} 40 41 ~Bitmap() { 42 if (alloc_) 43 delete[] map_; 44 } 45 46 // Resizes the bitmap. 47 // If |num_bits| < Size(), the extra bits will be discarded. 48 // If |num_bits| > Size(), the extra bits will be filled with zeros if 49 // |clear_bits| is true. 50 // This object cannot be using memory provided during construction. 51 void Resize(int num_bits, bool clear_bits); 52 53 // Returns the number of bits in the bitmap. 54 int Size() const { return num_bits_; } 55 56 // Returns the number of 32-bit words in the bitmap. 57 int ArraySize() const { return array_size_; } 58 59 // Sets all the bits to true or false. 60 void SetAll(bool value) { 61 memset(map_, (value ? 0xFF : 0x00), array_size_ * sizeof(*map_)); 62 } 63 64 // Clears all bits in the bitmap 65 void Clear() { SetAll(false); } 66 67 // Sets the value, gets the value or toggles the value of a given bit. 68 void Set(int index, bool value); 69 bool Get(int index) const; 70 void Toggle(int index); 71 72 // Directly sets an element of the internal map. Requires |array_index| < 73 // ArraySize(); 74 void SetMapElement(int array_index, uint32 value); 75 76 // Gets an entry of the internal map. Requires array_index < 77 // ArraySize() 78 uint32 GetMapElement(int array_index) const; 79 80 // Directly sets the whole internal map. |size| is the number of 32-bit words 81 // to set from |map|. If |size| > array_size(), it ignores the end of |map|. 82 void SetMap(const uint32* map, int size); 83 84 // Gets a pointer to the internal map. 85 const uint32* GetMap() const { return map_; } 86 87 // Sets a range of bits to |value|. 88 void SetRange(int begin, int end, bool value); 89 90 // Returns true if any bit between begin inclusive and end exclusive is set. 91 // 0 <= |begin| <= |end| <= Size() is required. 92 bool TestRange(int begin, int end, bool value) const; 93 94 // Scans bits starting at bit *|index|, looking for a bit set to |value|. If 95 // it finds that bit before reaching bit index |limit|, sets *|index| to the 96 // bit index and returns true. Otherwise returns false. 97 // Requires |limit| <= Size(). 98 // 99 // Note that to use these methods in a loop you must increment the index 100 // after each use, as in: 101 // 102 // for (int index = 0 ; map.FindNextBit(&index, limit, value) ; ++index) { 103 // DoSomethingWith(index); 104 // } 105 bool FindNextBit(int* index, int limit, bool value) const; 106 107 // Finds the first offset >= *|index| and < |limit| that has its bit set. 108 // See FindNextBit() for more info. 109 bool FindNextSetBitBeforeLimit(int* index, int limit) const { 110 return FindNextBit(index, limit, true); 111 } 112 113 // Finds the first offset >= *|index| that has its bit set. 114 // See FindNextBit() for more info. 115 bool FindNextSetBit(int *index) const { 116 return FindNextSetBitBeforeLimit(index, num_bits_); 117 } 118 119 // Scans bits starting at bit *|index|, looking for a bit set to |value|. If 120 // it finds that bit before reaching bit index |limit|, sets *|index| to the 121 // bit index and then counts the number of consecutive bits set to |value| 122 // (before reaching |limit|), and returns that count. If no bit is found 123 // returns 0. Requires |limit| <= Size(). 124 int FindBits(int* index, int limit, bool value) const; 125 126 // Returns number of allocated words required for a bitmap of size |num_bits|. 127 static int RequiredArraySize(int num_bits) { 128 // Force at least one allocated word. 129 if (num_bits <= kIntBits) 130 return 1; 131 132 return (num_bits + kIntBits - 1) >> kLogIntBits; 133 } 134 135 private: 136 static const int kIntBits = sizeof(uint32) * 8; 137 static const int kLogIntBits = 5; // 2^5 == 32 bits per word. 138 139 // Sets |len| bits from |start| to |value|. All the bits to be set should be 140 // stored in the same word, and len < kIntBits. 141 void SetWordBits(int start, int len, bool value); 142 143 uint32* map_; // The bitmap. 144 int num_bits_; // The upper bound of the bitmap. 145 int array_size_; // The physical size (in uint32s) of the bitmap. 146 bool alloc_; // Whether or not we allocated the memory. 147 148 DISALLOW_COPY_AND_ASSIGN(Bitmap); 149 }; 150 151 } // namespace disk_cache 152 153 #endif // NET_DISK_CACHE_BITMAP_H_ 154
