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>
Bitmap()63 inline Bitmap<size>::Bitmap()
64 {
65 clearAll();
66 }
67
68 template<size_t size>
get(size_t n)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>
set(size_t n)75 inline void Bitmap<size>::set(size_t n)
76 {
77 bits[n / wordSize] |= (one << (n % wordSize));
78 }
79
80 template<size_t size>
testAndSet(size_t n)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>
clear(size_t n)91 inline void Bitmap<size>::clear(size_t n)
92 {
93 bits[n / wordSize] &= ~(one << (n % wordSize));
94 }
95
96 template<size_t size>
clearAll()97 inline void Bitmap<size>::clearAll()
98 {
99 memset(bits.data(), 0, sizeof(bits));
100 }
101
102 template<size_t size>
nextPossiblyUnset(size_t start)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>
findRunOfZeros(size_t runLength)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>
count(size_t start)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>
isEmpty()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>
isFull()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