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
  25 #include <stdint.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     void clear(size_t);
  40     void clearAll();
  41     void advanceToNextFreeBit(size_t&) const;
  42     size_t count(size_t = 0) const;
  43     size_t isEmpty() const;
  44     size_t isFull() const;
  45
  46 private:
  47     static const WordType wordSize = sizeof(WordType) * 8;
  48     static const WordType words = (size + wordSize - 1) / wordSize;
  49
  50     // the literal '1' is of type signed int.  We want to use an unsigned
  51     // version of the correct size when doing the calculations because if
  52     // WordType is larger than int, '1 << 31' will first be sign extended
  53     // and then casted to unsigned, meaning that set(31) when WordType is
  54     // a 64 bit unsigned int would give 0xffff8000
  55     static const WordType one = 1;
  56
  57     FixedArray<WordType, words> bits;
  58 };
  59
  60 template<size_t size>
  61 inline Bitmap<size>::Bitmap()
  62 {
  63     clearAll();
  64 }
  65
  66 template<size_t size>
  67 inline bool Bitmap<size>::get(size_t n) const
  68 {
  69     return !!(bits[n / wordSize] & (one << (n % wordSize)));
  70 }
  71
  72 template<size_t size>
  73 inline void Bitmap<size>::set(size_t n)
  74 {
  75     bits[n / wordSize] |= (one << (n % wordSize));
  76 }
  77
  78 template<size_t size>
  79 inline void Bitmap<size>::clear(size_t n)
  80 {
  81     bits[n / wordSize] &= ~(one << (n % wordSize));
  82 }
  83
  84 template<size_t size>
  85 inline void Bitmap<size>::clearAll()
  86 {
  87     memset(bits.data(), 0, sizeof(bits));
  88 }
  89
  90 template<size_t size>
  91 inline void Bitmap<size>::advanceToNextFreeBit(size_t& start) const
  92 {
  93     if (!~bits[start / wordSize])
  94         start = ((start / wordSize) + 1) * wordSize;
  95     else
  96         ++start;
  97 }
  98
  99 template<size_t size>
 100 inline size_t Bitmap<size>::count(size_t start) const
 101 {
 102     size_t result = 0;
 103     for ( ; (start % wordSize); ++start) {
 104         if (get(start))
 105             ++result;
 106     }
 107     for (size_t i = start / wordSize; i < words; ++i)
 108         result += WTF::bitCount(bits[i]);
 109     return result;
 110 }
 111
 112 template<size_t size>
 113 inline size_t Bitmap<size>::isEmpty() const
 114 {
 115     for (size_t i = 0; i < words; ++i)
 116         if (bits[i])
 117             return false;
 118     return true;
 119 }
 120
 121 template<size_t size>
 122 inline size_t Bitmap<size>::isFull() const
 123 {
 124     for (size_t i = 0; i < words; ++i)
 125         if (~bits[i])
 126             return false;
 127     return true;
 128 }
 129
 130 }
 131 #endif