Home | History | Annotate | Download | only in wtf 
      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
    163