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