OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 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 #ifndef NET_DISK_CACHE_BLOCKFILE_BITMAP_H_ | 5 #ifndef NET_DISK_CACHE_BLOCKFILE_BITMAP_H_ |
6 #define NET_DISK_CACHE_BLOCKFILE_BITMAP_H_ | 6 #define NET_DISK_CACHE_BLOCKFILE_BITMAP_H_ |
7 | 7 |
8 #include "base/basictypes.h" | 8 #include <stdint.h> |
| 9 |
| 10 #include "base/macros.h" |
9 #include "net/base/net_export.h" | 11 #include "net/base/net_export.h" |
10 | 12 |
11 namespace disk_cache { | 13 namespace disk_cache { |
12 | 14 |
13 // This class provides support for simple maps of bits. | 15 // This class provides support for simple maps of bits. |
14 class NET_EXPORT_PRIVATE Bitmap { | 16 class NET_EXPORT_PRIVATE Bitmap { |
15 public: | 17 public: |
16 Bitmap() : map_(NULL), num_bits_(0), array_size_(0), alloc_(false) {} | 18 Bitmap() : map_(NULL), num_bits_(0), array_size_(0), alloc_(false) {} |
17 | 19 |
18 // This constructor will allocate on a uint32 boundary. If |clear_bits| is | 20 // This constructor will allocate on a uint32_t boundary. If |clear_bits| is |
19 // false, the bitmap bits will not be initialized. | 21 // false, the bitmap bits will not be initialized. |
20 Bitmap(int num_bits, bool clear_bits); | 22 Bitmap(int num_bits, bool clear_bits); |
21 | 23 |
22 // Constructs a Bitmap with the actual storage provided by the caller. |map| | 24 // Constructs a Bitmap with the actual storage provided by the caller. |map| |
23 // has to be valid until this object destruction. |num_bits| is the number of | 25 // has to be valid until this object destruction. |num_bits| is the number of |
24 // bits in the bitmap, and |num_words| is the size of |map| in 32-bit words. | 26 // bits in the bitmap, and |num_words| is the size of |map| in 32-bit words. |
25 Bitmap(uint32* map, int num_bits, int num_words); | 27 Bitmap(uint32_t* map, int num_bits, int num_words); |
26 | 28 |
27 ~Bitmap(); | 29 ~Bitmap(); |
28 | 30 |
29 // Resizes the bitmap. | 31 // Resizes the bitmap. |
30 // If |num_bits| < Size(), the extra bits will be discarded. | 32 // If |num_bits| < Size(), the extra bits will be discarded. |
31 // If |num_bits| > Size(), the extra bits will be filled with zeros if | 33 // If |num_bits| > Size(), the extra bits will be filled with zeros if |
32 // |clear_bits| is true. | 34 // |clear_bits| is true. |
33 // This object cannot be using memory provided during construction. | 35 // This object cannot be using memory provided during construction. |
34 void Resize(int num_bits, bool clear_bits); | 36 void Resize(int num_bits, bool clear_bits); |
35 | 37 |
(...skipping 11 matching lines...) Expand all Loading... |
47 // Clears all bits in the bitmap | 49 // Clears all bits in the bitmap |
48 void Clear() { SetAll(false); } | 50 void Clear() { SetAll(false); } |
49 | 51 |
50 // Sets the value, gets the value or toggles the value of a given bit. | 52 // Sets the value, gets the value or toggles the value of a given bit. |
51 void Set(int index, bool value); | 53 void Set(int index, bool value); |
52 bool Get(int index) const; | 54 bool Get(int index) const; |
53 void Toggle(int index); | 55 void Toggle(int index); |
54 | 56 |
55 // Directly sets an element of the internal map. Requires |array_index| < | 57 // Directly sets an element of the internal map. Requires |array_index| < |
56 // ArraySize(); | 58 // ArraySize(); |
57 void SetMapElement(int array_index, uint32 value); | 59 void SetMapElement(int array_index, uint32_t value); |
58 | 60 |
59 // Gets an entry of the internal map. Requires array_index < | 61 // Gets an entry of the internal map. Requires array_index < |
60 // ArraySize() | 62 // ArraySize() |
61 uint32 GetMapElement(int array_index) const; | 63 uint32_t GetMapElement(int array_index) const; |
62 | 64 |
63 // Directly sets the whole internal map. |size| is the number of 32-bit words | 65 // Directly sets the whole internal map. |size| is the number of 32-bit words |
64 // to set from |map|. If |size| > array_size(), it ignores the end of |map|. | 66 // to set from |map|. If |size| > array_size(), it ignores the end of |map|. |
65 void SetMap(const uint32* map, int size); | 67 void SetMap(const uint32_t* map, int size); |
66 | 68 |
67 // Gets a pointer to the internal map. | 69 // Gets a pointer to the internal map. |
68 const uint32* GetMap() const { return map_; } | 70 const uint32_t* GetMap() const { return map_; } |
69 | 71 |
70 // Sets a range of bits to |value|. | 72 // Sets a range of bits to |value|. |
71 void SetRange(int begin, int end, bool value); | 73 void SetRange(int begin, int end, bool value); |
72 | 74 |
73 // Returns true if any bit between begin inclusive and end exclusive is set. | 75 // Returns true if any bit between begin inclusive and end exclusive is set. |
74 // 0 <= |begin| <= |end| <= Size() is required. | 76 // 0 <= |begin| <= |end| <= Size() is required. |
75 bool TestRange(int begin, int end, bool value) const; | 77 bool TestRange(int begin, int end, bool value) const; |
76 | 78 |
77 // Scans bits starting at bit *|index|, looking for a bit set to |value|. If | 79 // Scans bits starting at bit *|index|, looking for a bit set to |value|. If |
78 // it finds that bit before reaching bit index |limit|, sets *|index| to the | 80 // it finds that bit before reaching bit index |limit|, sets *|index| to the |
(...skipping 30 matching lines...) Expand all Loading... |
109 // Returns number of allocated words required for a bitmap of size |num_bits|. | 111 // Returns number of allocated words required for a bitmap of size |num_bits|. |
110 static int RequiredArraySize(int num_bits) { | 112 static int RequiredArraySize(int num_bits) { |
111 // Force at least one allocated word. | 113 // Force at least one allocated word. |
112 if (num_bits <= kIntBits) | 114 if (num_bits <= kIntBits) |
113 return 1; | 115 return 1; |
114 | 116 |
115 return (num_bits + kIntBits - 1) >> kLogIntBits; | 117 return (num_bits + kIntBits - 1) >> kLogIntBits; |
116 } | 118 } |
117 | 119 |
118 private: | 120 private: |
119 static const int kIntBits = sizeof(uint32) * 8; | 121 static const int kIntBits = sizeof(uint32_t) * 8; |
120 static const int kLogIntBits = 5; // 2^5 == 32 bits per word. | 122 static const int kLogIntBits = 5; // 2^5 == 32 bits per word. |
121 | 123 |
122 // Sets |len| bits from |start| to |value|. All the bits to be set should be | 124 // Sets |len| bits from |start| to |value|. All the bits to be set should be |
123 // stored in the same word, and len < kIntBits. | 125 // stored in the same word, and len < kIntBits. |
124 void SetWordBits(int start, int len, bool value); | 126 void SetWordBits(int start, int len, bool value); |
125 | 127 |
126 uint32* map_; // The bitmap. | 128 uint32_t* map_; // The bitmap. |
127 int num_bits_; // The upper bound of the bitmap. | 129 int num_bits_; // The upper bound of the bitmap. |
128 int array_size_; // The physical size (in uint32s) of the bitmap. | 130 int array_size_; // The physical size (in uint32s) of the bitmap. |
129 bool alloc_; // Whether or not we allocated the memory. | 131 bool alloc_; // Whether or not we allocated the memory. |
130 | 132 |
131 DISALLOW_COPY_AND_ASSIGN(Bitmap); | 133 DISALLOW_COPY_AND_ASSIGN(Bitmap); |
132 }; | 134 }; |
133 | 135 |
134 } // namespace disk_cache | 136 } // namespace disk_cache |
135 | 137 |
136 #endif // NET_DISK_CACHE_BLOCKFILE_BITMAP_H_ | 138 #endif // NET_DISK_CACHE_BLOCKFILE_BITMAP_H_ |
OLD | NEW |