wtf/Bitmap.h

   1 /*
   2  *  Copyright (C) 2010 Apple Inc. All rights reserved.
   3  *
   4  *  This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU Lesser General Public
   6  *  License as published by the Free Software Foundation; either
   7  *  version 2 of the License, or (at your option) any later version.
   8  *
   9  *  This library is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  *  Lesser General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU Lesser General Public
  15  *  License along with this library; if not, write to the Free Software
  16  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  17  *
  18  */
  19 #ifndef Bitmap_h
  20 #define Bitmap_h
  21
  22 #include "FixedArray.h"
  23 #include "StdLibExtras.h"
  24 #include <stdint.h>
  25 #include <string.h>
  26
  27 namespace WTF {
  28
  29 template<size_t size>
  30 class Bitmap {
  31 private:
  32     typedef uint32_t WordType;
  33
  34 public:
  35     Bitmap();
  36
  37     bool get(size_t) const;
  38     void set(size_t);
  39     bool testAndSet(size_t);
  40     size_t nextPossiblyUnset(size_t) const;
  41     void clear(size_t);
  42     void clearAll();
  43     int64_t findRunOfZeros(size_t) const;
  44     size_t count(size_t = 0) const;
  45     size_t isEmpty() const;
  46     size_t isFull() const;
  47
  48 private:
  49     static const WordType wordSize = sizeof(WordType) * 8;
  50     static const WordType words = (size + wordSize - 1) / wordSize;
  51
  52     // the literal '1' is of type signed int.  We want to use an unsigned
  53     // version of the correct size when doing the calculations because if
  54     // WordType is larger than int, '1 << 31' will first be sign extended
  55     // and then casted to unsigned, meaning that set(31) when WordType is
  56     // a 64 bit unsigned int would give 0xffff8000
  57     static const WordType one = 1;
  58
  59     FixedArray<WordType, words> bits;
  60 };
  61
  62 template<size_t size>
  63 inline Bitmap<size>::Bitmap()
  64 {
  65     clearAll();
  66 }
  67
  68 template<size_t size>
  69 inline bool Bitmap<size>::get(size_t n) const
  70 {
  71     return !!(bits[n / wordSize] & (one << (n % wordSize)));
  72 }
  73
  74 template<size_t size>
  75 inline void Bitmap<size>::set(size_t n)
  76 {
  77     bits[n / wordSize] |= (one << (n % wordSize));
  78 }
  79
  80 template<size_t size>
  81 inline bool Bitmap<size>::testAndSet(size_t n)
  82 {
  83     WordType mask = one << (n % wordSize);
  84     size_t index = n / wordSize;
  85     bool result = bits[index] & mask;
  86     bits[index] |= mask;
  87     return result;
  88 }
  89
  90 template<size_t size>
  91 inline void Bitmap<size>::clear(size_t n)
  92 {
  93     bits[n / wordSize] &= ~(one << (n % wordSize));
  94 }
  95
  96 template<size_t size>
  97 inline void Bitmap<size>::clearAll()
  98 {
  99     memset(bits.data(), 0, sizeof(bits));
 100 }
 101
 102 template<size_t size>
 103 inline size_t Bitmap<size>::nextPossiblyUnset(size_t start) const
 104 {
 105     if (!~bits[start / wordSize])
 106         return ((start / wordSize) + 1) * wordSize;
 107     return start + 1;
 108 }
 109
 110 template<size_t size>
 111 inline int64_t Bitmap<size>::findRunOfZeros(size_t runLength) const
 112 {
 113     if (!runLength)
 114         runLength = 1;
 115
 116     for (size_t i = 0; i <= (size - runLength) ; i++) {
 117         bool found = true;
 118         for (size_t j = i; j <= (i + runLength - 1) ; j++) {
 119             if (get(j)) {
 120                 found = false;
 121                 break;
 122             }
 123         }
 124         if (found)
 125             return i;
 126     }
 127     return -1;
 128 }
 129
 130 template<size_t size>
 131 inline size_t Bitmap<size>::count(size_t start) const
 132 {
 133     size_t result = 0;
 134     for ( ; (start % wordSize); ++start) {
 135         if (get(start))
 136             ++result;
 137     }
 138     for (size_t i = start / wordSize; i < words; ++i)
 139         result += WTF::bitCount(bits[i]);
 140     return result;
 141 }
 142
 143 template<size_t size>
 144 inline size_t Bitmap<size>::isEmpty() const
 145 {
 146     for (size_t i = 0; i < words; ++i)
 147         if (bits[i])
 148             return false;
 149     return true;
 150 }
 151
 152 template<size_t size>
 153 inline size_t Bitmap<size>::isFull() const
 154 {
 155     for (size_t i = 0; i < words; ++i)
 156         if (~bits[i])
 157             return false;
 158     return true;
 159 }
 160
 161 }
 162 #endif