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