Source/WTF/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 <wtf/Atomics.h>
  23 #include <wtf/FixedArray.h>
  24 #include <wtf/StdLibExtras.h>
  25 #include <stdint.h>
  26 #include <string.h>
  27
  28 namespace WTF {
  29
  30 enum BitmapAtomicMode {
  31     // This makes concurrentTestAndSet behave just like testAndSet.
  32     BitmapNotAtomic,
  33
  34     // This makes concurrentTestAndSet use compareAndSwap, so that it's
  35     // atomic even when used concurrently.
  36     BitmapAtomic
  37 };
  38
  39 template<size_t size, BitmapAtomicMode atomicMode = BitmapNotAtomic>
  40 class Bitmap {
  41 private:
  42     typedef uint32_t WordType;
  43
  44 public:
  45     Bitmap();
  46
  47     bool get(size_t) const;
  48     void set(size_t);
  49     bool testAndSet(size_t);
  50     bool testAndClear(size_t);
  51     bool concurrentTestAndSet(size_t);
  52     bool concurrentTestAndClear(size_t);
  53     size_t nextPossiblyUnset(size_t) const;
  54     void clear(size_t);
  55     void clearAll();
  56     int64_t findRunOfZeros(size_t) const;
  57     size_t count(size_t = 0) const;
  58     size_t isEmpty() const;
  59     size_t isFull() const;
  60
  61 private:
  62     static const WordType wordSize = sizeof(WordType) * 8;
  63     static const WordType words = (size + wordSize - 1) / wordSize;
  64
  65     // the literal '1' is of type signed int.  We want to use an unsigned
  66     // version of the correct size when doing the calculations because if
  67     // WordType is larger than int, '1 << 31' will first be sign extended
  68     // and then casted to unsigned, meaning that set(31) when WordType is
  69     // a 64 bit unsigned int would give 0xffff8000
  70     static const WordType one = 1;
  71
  72     FixedArray<WordType, words> bits;
  73 };
  74
  75 template<size_t size, BitmapAtomicMode atomicMode>
  76 inline Bitmap<size, atomicMode>::Bitmap()
  77 {
  78     clearAll();
  79 }
  80
  81 template<size_t size, BitmapAtomicMode atomicMode>
  82 inline bool Bitmap<size, atomicMode>::get(size_t n) const
  83 {
  84     return !!(bits[n / wordSize] & (one << (n % wordSize)));
  85 }
  86
  87 template<size_t size, BitmapAtomicMode atomicMode>
  88 inline void Bitmap<size, atomicMode>::set(size_t n)
  89 {
  90     bits[n / wordSize] |= (one << (n % wordSize));
  91 }
  92
  93 template<size_t size, BitmapAtomicMode atomicMode>
  94 inline bool Bitmap<size, atomicMode>::testAndSet(size_t n)
  95 {
  96     WordType mask = one << (n % wordSize);
  97     size_t index = n / wordSize;
  98     bool result = bits[index] & mask;
  99     bits[index] |= mask;
 100     return result;
 101 }
 102
 103 template<size_t size, BitmapAtomicMode atomicMode>
 104 inline bool Bitmap<size, atomicMode>::testAndClear(size_t n)
 105 {
 106     WordType mask = one << (n % wordSize);
 107     size_t index = n / wordSize;
 108     bool result = bits[index] & mask;
 109     bits[index] &= ~mask;
 110     return result;
 111 }
 112
 113 template<size_t size, BitmapAtomicMode atomicMode>
 114 inline bool Bitmap<size, atomicMode>::concurrentTestAndSet(size_t n)
 115 {
 116     if (atomicMode == BitmapNotAtomic)
 117         return testAndSet(n);
 118
 119     ASSERT(atomicMode == BitmapAtomic);
 120
 121     WordType mask = one << (n % wordSize);
 122     size_t index = n / wordSize;
 123     WordType* wordPtr = bits.data() + index;
 124     WordType oldValue;
 125     do {
 126         oldValue = *wordPtr;
 127         if (oldValue & mask)
 128             return true;
 129     } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue | mask));
 130     return false;
 131 }
 132
 133 template<size_t size, BitmapAtomicMode atomicMode>
 134 inline bool Bitmap<size, atomicMode>::concurrentTestAndClear(size_t n)
 135 {
 136     if (atomicMode == BitmapNotAtomic)
 137         return testAndClear(n);
 138
 139     ASSERT(atomicMode == BitmapAtomic);
 140
 141     WordType mask = one << (n % wordSize);
 142     size_t index = n / wordSize;
 143     WordType* wordPtr = bits.data() + index;
 144     WordType oldValue;
 145     do {
 146         oldValue = *wordPtr;
 147         if (!(oldValue & mask))
 148             return false;
 149     } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue & ~mask));
 150     return true;
 151 }
 152
 153 template<size_t size, BitmapAtomicMode atomicMode>
 154 inline void Bitmap<size, atomicMode>::clear(size_t n)
 155 {
 156     bits[n / wordSize] &= ~(one << (n % wordSize));
 157 }
 158
 159 template<size_t size, BitmapAtomicMode atomicMode>
 160 inline void Bitmap<size, atomicMode>::clearAll()
 161 {
 162     memset(bits.data(), 0, sizeof(bits));
 163 }
 164
 165 template<size_t size, BitmapAtomicMode atomicMode>
 166 inline size_t Bitmap<size, atomicMode>::nextPossiblyUnset(size_t start) const
 167 {
 168     if (!~bits[start / wordSize])
 169         return ((start / wordSize) + 1) * wordSize;
 170     return start + 1;
 171 }
 172
 173 template<size_t size, BitmapAtomicMode atomicMode>
 174 inline int64_t Bitmap<size, atomicMode>::findRunOfZeros(size_t runLength) const
 175 {
 176     if (!runLength)
 177         runLength = 1;
 178
 179     for (size_t i = 0; i <= (size - runLength) ; i++) {
 180         bool found = true;
 181         for (size_t j = i; j <= (i + runLength - 1) ; j++) {
 182             if (get(j)) {
 183                 found = false;
 184                 break;
 185             }
 186         }
 187         if (found)
 188             return i;
 189     }
 190     return -1;
 191 }
 192
 193 template<size_t size, BitmapAtomicMode atomicMode>
 194 inline size_t Bitmap<size, atomicMode>::count(size_t start) const
 195 {
 196     size_t result = 0;
 197     for ( ; (start % wordSize); ++start) {
 198         if (get(start))
 199             ++result;
 200     }
 201     for (size_t i = start / wordSize; i < words; ++i)
 202         result += WTF::bitCount(bits[i]);
 203     return result;
 204 }
 205
 206 template<size_t size, BitmapAtomicMode atomicMode>
 207 inline size_t Bitmap<size, atomicMode>::isEmpty() const
 208 {
 209     for (size_t i = 0; i < words; ++i)
 210         if (bits[i])
 211             return false;
 212     return true;
 213 }
 214
 215 template<size_t size, BitmapAtomicMode atomicMode>
 216 inline size_t Bitmap<size, atomicMode>::isFull() const
 217 {
 218     for (size_t i = 0; i < words; ++i)
 219         if (~bits[i])
 220             return false;
 221     return true;
 222 }
 223
 224 }
 225 #endif