1/*
2 * Copyright (C) 2011, 2014, 2016 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
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.
24 */
25
26#pragma once
27
28#include <stdio.h>
29#include <wtf/Assertions.h>
30#include <wtf/DataLog.h>
31#include <wtf/HashFunctions.h>
32#include <wtf/HashTraits.h>
33#include <wtf/PrintStream.h>
34#include <wtf/StdLibExtras.h>
35
36namespace JSC {
37class CachedBitVector;
38}
39
40namespace WTF {
41
42// This is a space-efficient, resizeable bitvector class. In the common case it
43// occupies one word, but if necessary, it will inflate this one word to point
44// to a single chunk of out-of-line allocated storage to store an arbitrary number
45// of bits.
46//
47// - The bitvector remembers the bound of how many bits can be stored, but this
48// may be slightly greater (by as much as some platform-specific constant)
49// than the last argument passed to ensureSize().
50//
51// - The bitvector can resize itself automatically (set, clear, get) or can be used
52// in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize).
53//
54// - Accesses ASSERT that you are within bounds.
55//
56// - Bits are automatically initialized to zero.
57//
58// On the other hand, this BitVector class may not be the fastest around, since
59// it does conditionals on every get/set/clear. But it is great if you need to
60// juggle a lot of variable-length BitVectors and you're worried about wasting
61// space.
62
63class BitVector {
64public:
65 BitVector()
66 : m_bitsOrPointer(makeInlineBits(0))
67 {
68 }
69
70 explicit BitVector(size_t numBits)
71 : m_bitsOrPointer(makeInlineBits(0))
72 {
73 ensureSize(numBits);
74 }
75
76 BitVector(const BitVector& other)
77 : m_bitsOrPointer(makeInlineBits(0))
78 {
79 (*this) = other;
80 }
81
82
83 ~BitVector()
84 {
85 if (isInline())
86 return;
87 OutOfLineBits::destroy(outOfLineBits());
88 }
89
90 BitVector& operator=(const BitVector& other)
91 {
92 if (isInline() && other.isInline())
93 m_bitsOrPointer = other.m_bitsOrPointer;
94 else
95 setSlow(other);
96 return *this;
97 }
98
99 size_t size() const
100 {
101 if (isInline())
102 return maxInlineBits();
103 return outOfLineBits()->numBits();
104 }
105
106 void ensureSize(size_t numBits)
107 {
108 if (numBits <= size())
109 return;
110 resizeOutOfLine(numBits);
111 }
112
113 // Like ensureSize(), but supports reducing the size of the bitvector.
114 WTF_EXPORT_PRIVATE void resize(size_t numBits);
115
116 WTF_EXPORT_PRIVATE void clearAll();
117
118 bool quickGet(size_t bit) const
119 {
120 ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
121 return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
122 }
123
124 bool quickSet(size_t bit)
125 {
126 ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
127 uintptr_t& word = bits()[bit / bitsInPointer()];
128 uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
129 bool result = !!(word & mask);
130 word |= mask;
131 return result;
132 }
133
134 bool quickClear(size_t bit)
135 {
136 ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
137 uintptr_t& word = bits()[bit / bitsInPointer()];
138 uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
139 bool result = !!(word & mask);
140 word &= ~mask;
141 return result;
142 }
143
144 bool quickSet(size_t bit, bool value)
145 {
146 if (value)
147 return quickSet(bit);
148 return quickClear(bit);
149 }
150
151 bool get(size_t bit) const
152 {
153 if (bit >= size())
154 return false;
155 return quickGet(bit);
156 }
157
158 bool contains(size_t bit) const
159 {
160 return get(bit);
161 }
162
163 bool set(size_t bit)
164 {
165 ensureSize(bit + 1);
166 return quickSet(bit);
167 }
168
169 // This works like the add methods of sets. Instead of returning the previous value, like set(),
170 // it returns whether the bit transitioned from false to true.
171 bool add(size_t bit)
172 {
173 return !set(bit);
174 }
175
176 bool ensureSizeAndSet(size_t bit, size_t size)
177 {
178 ensureSize(size);
179 return quickSet(bit);
180 }
181
182 bool clear(size_t bit)
183 {
184 if (bit >= size())
185 return false;
186 return quickClear(bit);
187 }
188
189 bool remove(size_t bit)
190 {
191 return clear(bit);
192 }
193
194 bool set(size_t bit, bool value)
195 {
196 if (value)
197 return set(bit);
198 return clear(bit);
199 }
200
201 void merge(const BitVector& other)
202 {
203 if (!isInline() || !other.isInline()) {
204 mergeSlow(other);
205 return;
206 }
207 m_bitsOrPointer |= other.m_bitsOrPointer;
208 ASSERT(isInline());
209 }
210
211 void filter(const BitVector& other)
212 {
213 if (!isInline() || !other.isInline()) {
214 filterSlow(other);
215 return;
216 }
217 m_bitsOrPointer &= other.m_bitsOrPointer;
218 ASSERT(isInline());
219 }
220
221 void exclude(const BitVector& other)
222 {
223 if (!isInline() || !other.isInline()) {
224 excludeSlow(other);
225 return;
226 }
227 m_bitsOrPointer &= ~other.m_bitsOrPointer;
228 m_bitsOrPointer |= (static_cast<uintptr_t>(1) << maxInlineBits());
229 ASSERT(isInline());
230 }
231
232 size_t bitCount() const
233 {
234 if (isInline())
235 return bitCount(cleanseInlineBits(m_bitsOrPointer));
236 return bitCountSlow();
237 }
238
239 size_t findBit(size_t index, bool value) const
240 {
241 size_t result = findBitFast(index, value);
242 if (!ASSERT_DISABLED) {
243 size_t expectedResult = findBitSimple(index, value);
244 if (result != expectedResult) {
245 dataLog("findBit(", index, ", ", value, ") on ", *this, " should have gotten ", expectedResult, " but got ", result, "\n");
246 ASSERT_NOT_REACHED();
247 }
248 }
249 return result;
250 }
251
252 WTF_EXPORT_PRIVATE void dump(PrintStream& out) const;
253
254 enum EmptyValueTag { EmptyValue };
255 enum DeletedValueTag { DeletedValue };
256
257 BitVector(EmptyValueTag)
258 : m_bitsOrPointer(0)
259 {
260 }
261
262 BitVector(DeletedValueTag)
263 : m_bitsOrPointer(1)
264 {
265 }
266
267 bool isEmptyValue() const { return !m_bitsOrPointer; }
268 bool isDeletedValue() const { return m_bitsOrPointer == 1; }
269
270 bool isEmptyOrDeletedValue() const { return m_bitsOrPointer <= 1; }
271
272 bool operator==(const BitVector& other) const
273 {
274 if (isInline() && other.isInline())
275 return m_bitsOrPointer == other.m_bitsOrPointer;
276 return equalsSlowCase(other);
277 }
278
279 unsigned hash() const
280 {
281 // This is a very simple hash. Just xor together the words that hold the various
282 // bits and then compute the hash. This makes it very easy to deal with bitvectors
283 // that have a lot of trailing zero's.
284 uintptr_t value;
285 if (isInline())
286 value = cleanseInlineBits(m_bitsOrPointer);
287 else
288 value = hashSlowCase();
289 return IntHash<uintptr_t>::hash(value);
290 }
291
292 class iterator {
293 public:
294 iterator()
295 : m_bitVector(nullptr)
296 , m_index(0)
297 {
298 }
299
300 iterator(const BitVector& bitVector, size_t index)
301 : m_bitVector(&bitVector)
302 , m_index(index)
303 {
304 }
305
306 size_t operator*() const { return m_index; }
307
308 iterator& operator++()
309 {
310 m_index = m_bitVector->findBit(m_index + 1, true);
311 return *this;
312 }
313
314 iterator operator++(int)
315 {
316 iterator result = *this;
317 ++(*this);
318 return result;
319 }
320
321 bool isAtEnd() const
322 {
323 return m_index >= m_bitVector->size();
324 }
325
326 bool operator==(const iterator& other) const
327 {
328 return m_index == other.m_index;
329 }
330
331 bool operator!=(const iterator& other) const
332 {
333 return !(*this == other);
334 }
335 private:
336 const BitVector* m_bitVector;
337 size_t m_index;
338 };
339
340 // Use this to iterate over set bits.
341 iterator begin() const { return iterator(*this, findBit(0, true)); }
342 iterator end() const { return iterator(*this, size()); }
343
344private:
345 friend class JSC::CachedBitVector;
346
347 static unsigned bitsInPointer()
348 {
349 return sizeof(void*) << 3;
350 }
351
352 static unsigned maxInlineBits()
353 {
354 return bitsInPointer() - 1;
355 }
356
357 static size_t byteCount(size_t bitCount)
358 {
359 return (bitCount + 7) >> 3;
360 }
361
362 static uintptr_t makeInlineBits(uintptr_t bits)
363 {
364 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
365 return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
366 }
367
368 static uintptr_t cleanseInlineBits(uintptr_t bits)
369 {
370 return bits & ~(static_cast<uintptr_t>(1) << maxInlineBits());
371 }
372
373 static size_t bitCount(uintptr_t bits)
374 {
375 if (sizeof(uintptr_t) == 4)
376 return WTF::bitCount(static_cast<unsigned>(bits));
377 return WTF::bitCount(static_cast<uint64_t>(bits));
378 }
379
380 size_t findBitFast(size_t startIndex, bool value) const
381 {
382 if (isInline()) {
383 size_t index = startIndex;
384 findBitInWord(m_bitsOrPointer, index, maxInlineBits(), value);
385 return index;
386 }
387
388 const OutOfLineBits* bits = outOfLineBits();
389
390 // value = true: casts to 1, then xors to 0, then negates to 0.
391 // value = false: casts to 0, then xors to 1, then negates to -1 (i.e. all one bits).
392 uintptr_t skipValue = -(static_cast<uintptr_t>(value) ^ 1);
393 size_t numWords = bits->numWords();
394
395 size_t wordIndex = startIndex / bitsInPointer();
396 size_t startIndexInWord = startIndex - wordIndex * bitsInPointer();
397
398 while (wordIndex < numWords) {
399 uintptr_t word = bits->bits()[wordIndex];
400 if (word != skipValue) {
401 size_t index = startIndexInWord;
402 if (findBitInWord(word, index, bitsInPointer(), value))
403 return wordIndex * bitsInPointer() + index;
404 }
405
406 wordIndex++;
407 startIndexInWord = 0;
408 }
409
410 return bits->numBits();
411 }
412
413 size_t findBitSimple(size_t index, bool value) const
414 {
415 while (index < size()) {
416 if (get(index) == value)
417 return index;
418 index++;
419 }
420 return size();
421 }
422
423 class OutOfLineBits {
424 public:
425 size_t numBits() const { return m_numBits; }
426 size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
427 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
428 const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
429
430 static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
431
432 static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
433
434 private:
435 OutOfLineBits(size_t numBits)
436 : m_numBits(numBits)
437 {
438 }
439
440 size_t m_numBits;
441 };
442
443 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
444
445 const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
446 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
447
448 WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
449 WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
450
451 WTF_EXPORT_PRIVATE void mergeSlow(const BitVector& other);
452 WTF_EXPORT_PRIVATE void filterSlow(const BitVector& other);
453 WTF_EXPORT_PRIVATE void excludeSlow(const BitVector& other);
454
455 WTF_EXPORT_PRIVATE size_t bitCountSlow() const;
456
457 WTF_EXPORT_PRIVATE bool equalsSlowCase(const BitVector& other) const;
458 bool equalsSlowCaseFast(const BitVector& other) const;
459 bool equalsSlowCaseSimple(const BitVector& other) const;
460 WTF_EXPORT_PRIVATE uintptr_t hashSlowCase() const;
461
462 uintptr_t* bits()
463 {
464 if (isInline())
465 return &m_bitsOrPointer;
466 return outOfLineBits()->bits();
467 }
468
469 const uintptr_t* bits() const
470 {
471 if (isInline())
472 return &m_bitsOrPointer;
473 return outOfLineBits()->bits();
474 }
475
476 uintptr_t m_bitsOrPointer;
477};
478
479struct BitVectorHash {
480 static unsigned hash(const BitVector& vector) { return vector.hash(); }
481 static bool equal(const BitVector& a, const BitVector& b) { return a == b; }
482 static const bool safeToCompareToEmptyOrDeleted = false;
483};
484
485template<typename T> struct DefaultHash;
486template<> struct DefaultHash<BitVector> {
487 typedef BitVectorHash Hash;
488};
489
490template<> struct HashTraits<BitVector> : public CustomHashTraits<BitVector> { };
491
492} // namespace WTF
493
494using WTF::BitVector;
495