code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/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     bool testAndClear(size_t);
  41     size_t nextPossiblyUnset(size_t) const;
  42     void clear(size_t);
  43     void clearAll();
  44     int64_t findRunOfZeros(size_t) const;
  45     size_t count(size_t = 0) const;
  46     size_t isEmpty() const;
  47     size_t isFull() const;
  48
  49 private:
  50     static const WordType wordSize = sizeof(WordType) * 8;
  51     static const WordType words = (size + wordSize - 1) / wordSize;
  52
  53     // the literal '1' is of type signed int.  We want to use an unsigned
  54     // version of the correct size when doing the calculations because if
  55     // WordType is larger than int, '1 << 31' will first be sign extended
  56     // and then casted to unsigned, meaning that set(31) when WordType is
  57     // a 64 bit unsigned int would give 0xffff8000
  58     static const WordType one = 1;
  59
  60     FixedArray<WordType, words> bits;
  61 };
  62
  63 template<size_t size>
  64 inline Bitmap<size>::Bitmap()
  65 {
  66     clearAll();
  67 }
  68
  69 template<size_t size>
  70 inline bool Bitmap<size>::get(size_t n) const
  71 {
  72     return !!(bits[n / wordSize] & (one << (n % wordSize)));
  73 }
  74
  75 template<size_t size>
  76 inline void Bitmap<size>::set(size_t n)
  77 {
  78     bits[n / wordSize] |= (one << (n % wordSize));
  79 }
  80
  81 template<size_t size>
  82 inline bool Bitmap<size>::testAndSet(size_t n)
  83 {
  84     WordType mask = one << (n % wordSize);
  85     size_t index = n / wordSize;
  86     bool result = bits[index] & mask;
  87     bits[index] |= mask;
  88     return result;
  89 }
  90
  91 template<size_t size>
  92 inline bool Bitmap<size>::testAndClear(size_t n)
  93 {
  94     WordType mask = one << (n % wordSize);
  95     size_t index = n / wordSize;
  96     bool result = bits[index] & mask;
  97     bits[index] &= ~mask;
  98     return result;
  99 }
 100
 101 template<size_t size>
 102 inline void Bitmap<size>::clear(size_t n)
 103 {
 104     bits[n / wordSize] &= ~(one << (n % wordSize));
 105 }
 106
 107 template<size_t size>
 108 inline void Bitmap<size>::clearAll()
 109 {
 110     memset(bits.data(), 0, sizeof(bits));
 111 }
 112
 113 template<size_t size>
 114 inline size_t Bitmap<size>::nextPossiblyUnset(size_t start) const
 115 {
 116     if (!~bits[start / wordSize])
 117         return ((start / wordSize) + 1) * wordSize;
 118     return start + 1;
 119 }
 120
 121 template<size_t size>
 122 inline int64_t Bitmap<size>::findRunOfZeros(size_t runLength) const
 123 {
 124     if (!runLength)
 125         runLength = 1;
 126
 127     for (size_t i = 0; i <= (size - runLength) ; i++) {
 128         bool found = true;
 129         for (size_t j = i; j <= (i + runLength - 1) ; j++) {
 130             if (get(j)) {
 131                 found = false;
 132                 break;
 133             }
 134         }
 135         if (found)
 136             return i;
 137     }
 138     return -1;
 139 }
 140
 141 template<size_t size>
 142 inline size_t Bitmap<size>::count(size_t start) const
 143 {
 144     size_t result = 0;
 145     for ( ; (start % wordSize); ++start) {
 146         if (get(start))
 147             ++result;
 148     }
 149     for (size_t i = start / wordSize; i < words; ++i)
 150         result += WTF::bitCount(bits[i]);
 151     return result;
 152 }
 153
 154 template<size_t size>
 155 inline size_t Bitmap<size>::isEmpty() const
 156 {
 157     for (size_t i = 0; i < words; ++i)
 158         if (bits[i])
 159             return false;
 160     return true;
 161 }
 162
 163 template<size_t size>
 164 inline size_t Bitmap<size>::isFull() const
 165 {
 166     for (size_t i = 0; i < words; ++i)
 167         if (~bits[i])
 168             return false;
 169     return true;
 170 }
 171
 172 }
 173 #endif