net/disk_cache/blockfile/bitmap.h

   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
  11 namespace disk_cache {
  12
  13 // This class provides support for simple maps of bits.
  14 class 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_