OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2011 Apple Inc. All rights reserved. | 2 * Copyright (C) 2011 Apple Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
6 * are met: | 6 * are met: |
7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
11 * documentation and/or other materials provided with the distribution. | 11 * documentation and/or other materials provided with the distribution. |
12 * | 12 * |
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY | 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR | 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
24 */ | 24 */ |
25 | 25 |
26 #ifndef BitVector_h | 26 #ifndef BitVector_h |
27 #define BitVector_h | 27 #define BitVector_h |
28 | 28 |
29 #include <stdio.h> | 29 #include <stdio.h> |
30 #include "wtf/Assertions.h" | 30 #include "wtf/Assertions.h" |
31 #include "wtf/PrintStream.h" | 31 #include "wtf/PrintStream.h" |
32 #include "wtf/StdLibExtras.h" | 32 #include "wtf/StdLibExtras.h" |
33 #include "wtf/WTFExport.h" | 33 #include "wtf/WTFExport.h" |
(...skipping 15 matching lines...) Expand all Loading... |
49 // - Accesses ASSERT that you are within bounds. | 49 // - Accesses ASSERT that you are within bounds. |
50 // | 50 // |
51 // - Bits are automatically initialized to zero. | 51 // - Bits are automatically initialized to zero. |
52 // | 52 // |
53 // On the other hand, this BitVector class may not be the fastest around, since | 53 // On the other hand, this BitVector class may not be the fastest around, since |
54 // it does conditionals on every get/set/clear. But it is great if you need to | 54 // it does conditionals on every get/set/clear. But it is great if you need to |
55 // juggle a lot of variable-length BitVectors and you're worried about wasting | 55 // juggle a lot of variable-length BitVectors and you're worried about wasting |
56 // space. | 56 // space. |
57 | 57 |
58 class WTF_EXPORT BitVector { | 58 class WTF_EXPORT BitVector { |
59 public: | 59 public: |
60 BitVector() | 60 BitVector() |
61 : m_bitsOrPointer(makeInlineBits(0)) | 61 : m_bitsOrPointer(makeInlineBits(0)) |
62 { | 62 { |
63 } | 63 } |
64 | 64 |
65 explicit BitVector(size_t numBits) | 65 explicit BitVector(size_t numBits) |
66 : m_bitsOrPointer(makeInlineBits(0)) | 66 : m_bitsOrPointer(makeInlineBits(0)) |
67 { | 67 { |
68 ensureSize(numBits); | 68 ensureSize(numBits); |
69 } | 69 } |
70 | 70 |
71 BitVector(const BitVector& other) | 71 BitVector(const BitVector& other) |
72 : m_bitsOrPointer(makeInlineBits(0)) | 72 : m_bitsOrPointer(makeInlineBits(0)) |
73 { | 73 { |
74 (*this) = other; | 74 (*this) = other; |
75 } | 75 } |
76 | 76 |
77 | 77 |
78 ~BitVector() | 78 ~BitVector() |
79 { | 79 { |
80 if (isInline()) | 80 if (isInline()) |
81 return; | 81 return; |
82 OutOfLineBits::destroy(outOfLineBits()); | 82 OutOfLineBits::destroy(outOfLineBits()); |
83 } | 83 } |
84 | 84 |
85 BitVector& operator=(const BitVector& other) | 85 BitVector& operator=(const BitVector& other) |
86 { | 86 { |
87 if (isInline() && other.isInline()) | 87 if (isInline() && other.isInline()) |
88 m_bitsOrPointer = other.m_bitsOrPointer; | 88 m_bitsOrPointer = other.m_bitsOrPointer; |
89 else | 89 else |
90 setSlow(other); | 90 setSlow(other); |
91 return *this; | 91 return *this; |
92 } | 92 } |
93 | 93 |
94 size_t size() const | 94 size_t size() const |
95 { | 95 { |
96 if (isInline()) | 96 if (isInline()) |
97 return maxInlineBits(); | 97 return maxInlineBits(); |
98 return outOfLineBits()->numBits(); | 98 return outOfLineBits()->numBits(); |
99 } | 99 } |
100 | 100 |
101 void ensureSize(size_t numBits) | 101 void ensureSize(size_t numBits) |
102 { | 102 { |
103 if (numBits <= size()) | 103 if (numBits <= size()) |
104 return; | 104 return; |
105 resizeOutOfLine(numBits); | 105 resizeOutOfLine(numBits); |
106 } | 106 } |
107 | 107 |
108 // Like ensureSize(), but supports reducing the size of the bitvector. | 108 // Like ensureSize(), but supports reducing the size of the bitvector. |
109 void resize(size_t numBits); | 109 void resize(size_t numBits); |
110 | 110 |
111 void clearAll(); | 111 void clearAll(); |
112 | 112 |
113 bool quickGet(size_t bit) const | 113 bool quickGet(size_t bit) const |
114 { | 114 { |
115 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); | 115 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
116 return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) <<
(bit & (bitsInPointer() - 1)))); | 116 return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) <<
(bit & (bitsInPointer() - 1)))); |
117 } | 117 } |
118 | 118 |
119 void quickSet(size_t bit) | 119 void quickSet(size_t bit) |
120 { | 120 { |
121 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); | 121 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
122 bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (b
itsInPointer() - 1))); | 122 bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (b
itsInPointer() - 1))); |
123 } | 123 } |
124 | 124 |
125 void quickClear(size_t bit) | 125 void quickClear(size_t bit) |
126 { | 126 { |
127 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); | 127 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
128 bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (
bitsInPointer() - 1))); | 128 bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (
bitsInPointer() - 1))); |
129 } | 129 } |
130 | 130 |
131 void quickSet(size_t bit, bool value) | 131 void quickSet(size_t bit, bool value) |
132 { | 132 { |
133 if (value) | 133 if (value) |
134 quickSet(bit); | 134 quickSet(bit); |
135 else | 135 else |
136 quickClear(bit); | 136 quickClear(bit); |
137 } | 137 } |
138 | 138 |
139 bool get(size_t bit) const | 139 bool get(size_t bit) const |
140 { | 140 { |
141 if (bit >= size()) | 141 if (bit >= size()) |
142 return false; | 142 return false; |
143 return quickGet(bit); | 143 return quickGet(bit); |
144 } | 144 } |
145 | 145 |
146 void set(size_t bit) | 146 void set(size_t bit) |
147 { | 147 { |
148 ensureSize(bit + 1); | 148 ensureSize(bit + 1); |
149 quickSet(bit); | 149 quickSet(bit); |
150 } | 150 } |
151 | 151 |
152 void ensureSizeAndSet(size_t bit, size_t size) | 152 void ensureSizeAndSet(size_t bit, size_t size) |
153 { | 153 { |
154 ensureSize(size); | 154 ensureSize(size); |
155 quickSet(bit); | 155 quickSet(bit); |
156 } | 156 } |
157 | 157 |
158 void clear(size_t bit) | 158 void clear(size_t bit) |
159 { | 159 { |
160 if (bit >= size()) | 160 if (bit >= size()) |
161 return; | 161 return; |
162 quickClear(bit); | 162 quickClear(bit); |
163 } | 163 } |
164 | 164 |
165 void set(size_t bit, bool value) | 165 void set(size_t bit, bool value) |
166 { | 166 { |
167 if (value) | 167 if (value) |
168 set(bit); | 168 set(bit); |
169 else | 169 else |
170 clear(bit); | 170 clear(bit); |
171 } | 171 } |
172 | 172 |
173 void dump(PrintStream& out); | 173 void dump(PrintStream& out); |
174 | 174 |
175 private: | 175 private: |
176 static unsigned bitsInPointer() | 176 static unsigned bitsInPointer() |
177 { | 177 { |
178 return sizeof(void*) << 3; | 178 return sizeof(void*) << 3; |
179 } | 179 } |
180 | 180 |
181 static unsigned maxInlineBits() | 181 static unsigned maxInlineBits() |
182 { | 182 { |
183 return bitsInPointer() - 1; | 183 return bitsInPointer() - 1; |
184 } | 184 } |
185 | 185 |
186 static size_t byteCount(size_t bitCount) | 186 static size_t byteCount(size_t bitCount) |
187 { | 187 { |
188 return (bitCount + 7) >> 3; | 188 return (bitCount + 7) >> 3; |
189 } | 189 } |
190 | 190 |
191 static uintptr_t makeInlineBits(uintptr_t bits) | 191 static uintptr_t makeInlineBits(uintptr_t bits) |
192 { | 192 { |
193 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits()))); | 193 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits()))); |
194 return bits | (static_cast<uintptr_t>(1) << maxInlineBits()); | 194 return bits | (static_cast<uintptr_t>(1) << maxInlineBits()); |
195 } | 195 } |
196 | 196 |
197 class OutOfLineBits { | 197 class OutOfLineBits { |
198 public: | 198 public: |
199 size_t numBits() const { return m_numBits; } | 199 size_t numBits() const { return m_numBits; } |
200 size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bit
sInPointer(); } | 200 size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bit
sInPointer(); } |
201 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); } | 201 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); } |
202 const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(th
is + 1); } | 202 const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(th
is + 1); } |
203 | 203 |
204 static OutOfLineBits* create(size_t numBits); | 204 static OutOfLineBits* create(size_t numBits); |
205 | 205 |
206 static void destroy(OutOfLineBits*); | 206 static void destroy(OutOfLineBits*); |
207 | 207 |
208 private: | 208 private: |
209 OutOfLineBits(size_t numBits) | 209 OutOfLineBits(size_t numBits) |
210 : m_numBits(numBits) | 210 : m_numBits(numBits) |
211 { | 211 { |
212 } | 212 } |
213 | 213 |
214 size_t m_numBits; | 214 size_t m_numBits; |
215 }; | 215 }; |
216 | 216 |
217 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); } | 217 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); } |
218 | 218 |
219 const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOf
LineBits*>(m_bitsOrPointer << 1); } | 219 const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOf
LineBits*>(m_bitsOrPointer << 1); } |
220 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsO
rPointer << 1); } | 220 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsO
rPointer << 1); } |
221 | 221 |
222 void resizeOutOfLine(size_t numBits); | 222 void resizeOutOfLine(size_t numBits); |
223 void setSlow(const BitVector& other); | 223 void setSlow(const BitVector& other); |
224 | 224 |
225 uintptr_t* bits() | 225 uintptr_t* bits() |
226 { | 226 { |
227 if (isInline()) | 227 if (isInline()) |
228 return &m_bitsOrPointer; | 228 return &m_bitsOrPointer; |
229 return outOfLineBits()->bits(); | 229 return outOfLineBits()->bits(); |
230 } | 230 } |
231 | 231 |
232 const uintptr_t* bits() const | 232 const uintptr_t* bits() const |
233 { | 233 { |
234 if (isInline()) | 234 if (isInline()) |
235 return &m_bitsOrPointer; | 235 return &m_bitsOrPointer; |
236 return outOfLineBits()->bits(); | 236 return outOfLineBits()->bits(); |
237 } | 237 } |
238 | 238 |
239 uintptr_t m_bitsOrPointer; | 239 uintptr_t m_bitsOrPointer; |
240 }; | 240 }; |
241 | 241 |
242 } // namespace WTF | 242 } // namespace WTF |
243 | 243 |
244 using WTF::BitVector; | 244 using WTF::BitVector; |
245 | 245 |
246 #endif // BitVector_h | 246 #endif // BitVector_h |
OLD | NEW |