1/*
2 * Copyright (C) 2011-2019 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 final {
64 WTF_MAKE_FAST_ALLOCATED;
65public:
66 BitVector()
67 : m_bitsOrPointer(makeInlineBits(0))
68 {
69 }
70
71 explicit BitVector(size_t numBits)
72 : m_bitsOrPointer(makeInlineBits(0))
73 {
74 ensureSize(numBits);
75 }
76
77 BitVector(const BitVector& other)
78 : m_bitsOrPointer(makeInlineBits(0))
79 {
80 (*this) = other;
81 }
82
83
84 ~BitVector()
85 {
86 if (isInline())
87 return;
88 OutOfLineBits::destroy(outOfLineBits());
89 }
90
91 BitVector& operator=(const BitVector& other)
92 {
93 if (isInline() && other.isInline())
94 m_bitsOrPointer = other.m_bitsOrPointer;
95 else
96 setSlow(other);
97 return *this;
98 }
99
100 size_t size() const
101 {
102 if (isInline())
103 return maxInlineBits();
104 return outOfLineBits()->numBits();
105 }
106
107 void ensureSize(size_t numBits)
108 {
109 if (numBits <= size())
110 return;
111 resizeOutOfLine(numBits);
112 }
113
114 // Like ensureSize(), but supports reducing the size of the bitvector.
115 WTF_EXPORT_PRIVATE void resize(size_t numBits);
116
117 WTF_EXPORT_PRIVATE void clearAll();
118
119 bool quickGet(size_t bit) const
120 {
121 ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
122 return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
123 }
124
125 bool quickSet(size_t bit)
126 {
127 ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
128 uintptr_t& word = bits()[bit / bitsInPointer()];
129 uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
130 bool result = !!(word & mask);
131 word |= mask;
132 return result;
133 }
134
135 bool quickClear(size_t bit)
136 {
137 ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
138 uintptr_t& word = bits()[bit / bitsInPointer()];
139 uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
140 bool result = !!(word & mask);
141 word &= ~mask;
142 return result;
143 }
144
145 bool quickSet(size_t bit, bool value)
146 {
147 if (value)
148 return quickSet(bit);
149 return quickClear(bit);
150 }
151
152 bool get(size_t bit) const
153 {
154 if (bit >= size())
155 return false;
156 return quickGet(bit);
157 }
158
159 bool contains(size_t bit) const
160 {
161 return get(bit);
162 }
163
164 bool set(size_t bit)
165 {
166 ensureSize(bit + 1);
167 return quickSet(bit);
168 }
169
170 // This works like the add methods of sets. Instead of returning the previous value, like set(),
171 // it returns whether the bit transitioned from false to true.
172 bool add(size_t bit)
173 {
174 return !set(bit);
175 }
176
177 bool ensureSizeAndSet(size_t bit, size_t size)
178 {
179 ensureSize(size);
180 return quickSet(bit);
181 }
182
183 bool clear(size_t bit)
184 {
185 if (bit >= size())
186 return false;
187 return quickClear(bit);
188 }
189
190 bool remove(size_t bit)
191 {
192 return clear(bit);
193 }
194
195 bool set(size_t bit, bool value)
196 {
197 if (value)
198 return set(bit);
199 return clear(bit);
200 }
201
202 void merge(const BitVector& other)
203 {
204 if (!isInline() || !other.isInline()) {
205 mergeSlow(other);
206 return;
207 }
208 m_bitsOrPointer |= other.m_bitsOrPointer;
209 ASSERT(isInline());
210 }
211
212 void filter(const BitVector& other)
213 {
214 if (!isInline() || !other.isInline()) {
215 filterSlow(other);
216 return;
217 }
218 m_bitsOrPointer &= other.m_bitsOrPointer;
219 ASSERT(isInline());
220 }
221
222 void exclude(const BitVector& other)
223 {
224 if (!isInline() || !other.isInline()) {
225 excludeSlow(other);
226 return;
227 }
228 m_bitsOrPointer &= ~other.m_bitsOrPointer;
229 m_bitsOrPointer |= (static_cast<uintptr_t>(1) << maxInlineBits());
230 ASSERT(isInline());
231 }
232
233 size_t bitCount() const
234 {
235 if (isInline())
236 return bitCount(cleanseInlineBits(m_bitsOrPointer));
237 return bitCountSlow();
238 }
239
240 bool isEmpty() const
241 {
242 if (isInline())
243 return !cleanseInlineBits(m_bitsOrPointer);
244 return isEmptySlow();
245 }
246
247 size_t findBit(size_t index, bool value) const
248 {
249 size_t result = findBitFast(index, value);
250 if (!ASSERT_DISABLED) {
251 size_t expectedResult = findBitSimple(index, value);
252 if (result != expectedResult) {
253 dataLog("findBit(", index, ", ", value, ") on ", *this, " should have gotten ", expectedResult, " but got ", result, "\n");
254 ASSERT_NOT_REACHED();
255 }
256 }
257 return result;
258 }
259
260 WTF_EXPORT_PRIVATE void dump(PrintStream& out) const;
261
262 enum EmptyValueTag { EmptyValue };
263 enum DeletedValueTag { DeletedValue };
264
265 BitVector(EmptyValueTag)
266 : m_bitsOrPointer(0)
267 {
268 }
269
270 BitVector(DeletedValueTag)
271 : m_bitsOrPointer(1)
272 {
273 }
274
275 bool isEmptyValue() const { return !m_bitsOrPointer; }
276 bool isDeletedValue() const { return m_bitsOrPointer == 1; }
277
278 bool isEmptyOrDeletedValue() const { return m_bitsOrPointer <= 1; }
279
280 bool operator==(const BitVector& other) const
281 {
282 if (isInline() && other.isInline())
283 return m_bitsOrPointer == other.m_bitsOrPointer;
284 return equalsSlowCase(other);
285 }
286
287 unsigned hash() const
288 {
289 // This is a very simple hash. Just xor together the words that hold the various
290 // bits and then compute the hash. This makes it very easy to deal with bitvectors
291 // that have a lot of trailing zero's.
292 uintptr_t value;
293 if (isInline())
294 value = cleanseInlineBits(m_bitsOrPointer);
295 else
296 value = hashSlowCase();
297 return IntHash<uintptr_t>::hash(value);
298 }
299
300 class iterator {
301 WTF_MAKE_FAST_ALLOCATED;
302 public:
303 iterator()
304 : m_bitVector(nullptr)
305 , m_index(0)
306 {
307 }
308
309 iterator(const BitVector& bitVector, size_t index)
310 : m_bitVector(&bitVector)
311 , m_index(index)
312 {
313 }
314
315 size_t operator*() const { return m_index; }
316
317 iterator& operator++()
318 {
319 m_index = m_bitVector->findBit(m_index + 1, true);
320 return *this;
321 }
322
323 iterator operator++(int)
324 {
325 iterator result = *this;
326 ++(*this);
327 return result;
328 }
329
330 bool isAtEnd() const
331 {
332 return m_index >= m_bitVector->size();
333 }
334
335 bool operator==(const iterator& other) const
336 {
337 return m_index == other.m_index;
338 }
339
340 bool operator!=(const iterator& other) const
341 {
342 return !(*this == other);
343 }
344 private:
345 const BitVector* m_bitVector;
346 size_t m_index;
347 };
348
349 // Use this to iterate over set bits.
350 iterator begin() const { return iterator(*this, findBit(0, true)); }
351 iterator end() const { return iterator(*this, size()); }
352
353private:
354 friend class JSC::CachedBitVector;
355
356 static unsigned bitsInPointer()
357 {
358 return sizeof(void*) << 3;
359 }
360
361 static unsigned maxInlineBits()
362 {
363 return bitsInPointer() - 1;
364 }
365
366 static size_t byteCount(size_t bitCount)
367 {
368 return (bitCount + 7) >> 3;
369 }
370
371 static uintptr_t makeInlineBits(uintptr_t bits)
372 {
373 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
374 return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
375 }
376
377 static uintptr_t cleanseInlineBits(uintptr_t bits)
378 {
379 return bits & ~(static_cast<uintptr_t>(1) << maxInlineBits());
380 }
381
382 static size_t bitCount(uintptr_t bits)
383 {
384 if (sizeof(uintptr_t) == 4)
385 return WTF::bitCount(static_cast<unsigned>(bits));
386 return WTF::bitCount(static_cast<uint64_t>(bits));
387 }
388
389 size_t findBitFast(size_t startIndex, bool value) const
390 {
391 if (isInline()) {
392 size_t index = startIndex;
393 findBitInWord(m_bitsOrPointer, index, maxInlineBits(), value);
394 return index;
395 }
396
397 const OutOfLineBits* bits = outOfLineBits();
398
399 // value = true: casts to 1, then xors to 0, then negates to 0.
400 // value = false: casts to 0, then xors to 1, then negates to -1 (i.e. all one bits).
401 uintptr_t skipValue = -(static_cast<uintptr_t>(value) ^ 1);
402 size_t numWords = bits->numWords();
403
404 size_t wordIndex = startIndex / bitsInPointer();
405 size_t startIndexInWord = startIndex - wordIndex * bitsInPointer();
406
407 while (wordIndex < numWords) {
408 uintptr_t word = bits->bits()[wordIndex];
409 if (word != skipValue) {
410 size_t index = startIndexInWord;
411 if (findBitInWord(word, index, bitsInPointer(), value))
412 return wordIndex * bitsInPointer() + index;
413 }
414
415 wordIndex++;
416 startIndexInWord = 0;
417 }
418
419 return bits->numBits();
420 }
421
422 size_t findBitSimple(size_t index, bool value) const
423 {
424 while (index < size()) {
425 if (get(index) == value)
426 return index;
427 index++;
428 }
429 return size();
430 }
431
432 class OutOfLineBits {
433 public:
434 size_t numBits() const { return m_numBits; }
435 size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
436 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
437 const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
438
439 static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
440
441 static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
442
443 private:
444 OutOfLineBits(size_t numBits)
445 : m_numBits(numBits)
446 {
447 }
448
449 size_t m_numBits;
450 };
451
452 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
453
454 const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
455 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
456
457 WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
458 WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
459
460 WTF_EXPORT_PRIVATE void mergeSlow(const BitVector& other);
461 WTF_EXPORT_PRIVATE void filterSlow(const BitVector& other);
462 WTF_EXPORT_PRIVATE void excludeSlow(const BitVector& other);
463
464 WTF_EXPORT_PRIVATE size_t bitCountSlow() const;
465 WTF_EXPORT_PRIVATE bool isEmptySlow() const;
466
467 WTF_EXPORT_PRIVATE bool equalsSlowCase(const BitVector& other) const;
468 bool equalsSlowCaseFast(const BitVector& other) const;
469 bool equalsSlowCaseSimple(const BitVector& other) const;
470 WTF_EXPORT_PRIVATE uintptr_t hashSlowCase() const;
471
472 uintptr_t* bits()
473 {
474 if (isInline())
475 return &m_bitsOrPointer;
476 return outOfLineBits()->bits();
477 }
478
479 const uintptr_t* bits() const
480 {
481 if (isInline())
482 return &m_bitsOrPointer;
483 return outOfLineBits()->bits();
484 }
485
486 uintptr_t m_bitsOrPointer;
487};
488
489struct BitVectorHash {
490 static unsigned hash(const BitVector& vector) { return vector.hash(); }
491 static bool equal(const BitVector& a, const BitVector& b) { return a == b; }
492 static constexpr bool safeToCompareToEmptyOrDeleted = false;
493};
494
495template<typename T> struct DefaultHash;
496template<> struct DefaultHash<BitVector> {
497 typedef BitVectorHash Hash;
498};
499
500template<> struct HashTraits<BitVector> : public CustomHashTraits<BitVector> { };
501
502} // namespace WTF
503
504using WTF::BitVector;
505