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