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 bool isEmpty() const
240 {
241 if (isInline())
242 return !cleanseInlineBits(m_bitsOrPointer);
243 return isEmptySlow();
244 }
245
246 size_t findBit(size_t index, bool value) const
247 {
248 size_t result = findBitFast(index, value);
249 if (!ASSERT_DISABLED) {
250 size_t expectedResult = findBitSimple(index, value);
251 if (result != expectedResult) {
252 dataLog("findBit(", index, ", ", value, ") on ", *this, " should have gotten ", expectedResult, " but got ", result, "\n");
253 ASSERT_NOT_REACHED();
254 }
255 }
256 return result;
257 }
258
259 WTF_EXPORT_PRIVATE void dump(PrintStream& out) const;
260
261 enum EmptyValueTag { EmptyValue };
262 enum DeletedValueTag { DeletedValue };
263
264 BitVector(EmptyValueTag)
265 : m_bitsOrPointer(0)
266 {
267 }
268
269 BitVector(DeletedValueTag)
270 : m_bitsOrPointer(1)
271 {
272 }
273
274 bool isEmptyValue() const { return !m_bitsOrPointer; }
275 bool isDeletedValue() const { return m_bitsOrPointer == 1; }
276
277 bool isEmptyOrDeletedValue() const { return m_bitsOrPointer <= 1; }
278
279 bool operator==(const BitVector& other) const
280 {
281 if (isInline() && other.isInline())
282 return m_bitsOrPointer == other.m_bitsOrPointer;
283 return equalsSlowCase(other);
284 }
285
286 unsigned hash() const
287 {
288 // This is a very simple hash. Just xor together the words that hold the various
289 // bits and then compute the hash. This makes it very easy to deal with bitvectors
290 // that have a lot of trailing zero's.
291 uintptr_t value;
292 if (isInline())
293 value = cleanseInlineBits(m_bitsOrPointer);
294 else
295 value = hashSlowCase();
296 return IntHash<uintptr_t>::hash(value);
297 }
298
299 class iterator {
300 public:
301 iterator()
302 : m_bitVector(nullptr)
303 , m_index(0)
304 {
305 }
306
307 iterator(const BitVector& bitVector, size_t index)
308 : m_bitVector(&bitVector)
309 , m_index(index)
310 {
311 }
312
313 size_t operator*() const { return m_index; }
314
315 iterator& operator++()
316 {
317 m_index = m_bitVector->findBit(m_index + 1, true);
318 return *this;
319 }
320
321 iterator operator++(int)
322 {
323 iterator result = *this;
324 ++(*this);
325 return result;
326 }
327
328 bool isAtEnd() const
329 {
330 return m_index >= m_bitVector->size();
331 }
332
333 bool operator==(const iterator& other) const
334 {
335 return m_index == other.m_index;
336 }
337
338 bool operator!=(const iterator& other) const
339 {
340 return !(*this == other);
341 }
342 private:
343 const BitVector* m_bitVector;
344 size_t m_index;
345 };
346
347 // Use this to iterate over set bits.
348 iterator begin() const { return iterator(*this, findBit(0, true)); }
349 iterator end() const { return iterator(*this, size()); }
350
351private:
352 friend class JSC::CachedBitVector;
353
354 static unsigned bitsInPointer()
355 {
356 return sizeof(void*) << 3;
357 }
358
359 static unsigned maxInlineBits()
360 {
361 return bitsInPointer() - 1;
362 }
363
364 static size_t byteCount(size_t bitCount)
365 {
366 return (bitCount + 7) >> 3;
367 }
368
369 static uintptr_t makeInlineBits(uintptr_t bits)
370 {
371 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
372 return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
373 }
374
375 static uintptr_t cleanseInlineBits(uintptr_t bits)
376 {
377 return bits & ~(static_cast<uintptr_t>(1) << maxInlineBits());
378 }
379
380 static size_t bitCount(uintptr_t bits)
381 {
382 if (sizeof(uintptr_t) == 4)
383 return WTF::bitCount(static_cast<unsigned>(bits));
384 return WTF::bitCount(static_cast<uint64_t>(bits));
385 }
386
387 size_t findBitFast(size_t startIndex, bool value) const
388 {
389 if (isInline()) {
390 size_t index = startIndex;
391 findBitInWord(m_bitsOrPointer, index, maxInlineBits(), value);
392 return index;
393 }
394
395 const OutOfLineBits* bits = outOfLineBits();
396
397 // value = true: casts to 1, then xors to 0, then negates to 0.
398 // value = false: casts to 0, then xors to 1, then negates to -1 (i.e. all one bits).
399 uintptr_t skipValue = -(static_cast<uintptr_t>(value) ^ 1);
400 size_t numWords = bits->numWords();
401
402 size_t wordIndex = startIndex / bitsInPointer();
403 size_t startIndexInWord = startIndex - wordIndex * bitsInPointer();
404
405 while (wordIndex < numWords) {
406 uintptr_t word = bits->bits()[wordIndex];
407 if (word != skipValue) {
408 size_t index = startIndexInWord;
409 if (findBitInWord(word, index, bitsInPointer(), value))
410 return wordIndex * bitsInPointer() + index;
411 }
412
413 wordIndex++;
414 startIndexInWord = 0;
415 }
416
417 return bits->numBits();
418 }
419
420 size_t findBitSimple(size_t index, bool value) const
421 {
422 while (index < size()) {
423 if (get(index) == value)
424 return index;
425 index++;
426 }
427 return size();
428 }
429
430 class OutOfLineBits {
431 public:
432 size_t numBits() const { return m_numBits; }
433 size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
434 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
435 const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
436
437 static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
438
439 static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
440
441 private:
442 OutOfLineBits(size_t numBits)
443 : m_numBits(numBits)
444 {
445 }
446
447 size_t m_numBits;
448 };
449
450 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
451
452 const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
453 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
454
455 WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
456 WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
457
458 WTF_EXPORT_PRIVATE void mergeSlow(const BitVector& other);
459 WTF_EXPORT_PRIVATE void filterSlow(const BitVector& other);
460 WTF_EXPORT_PRIVATE void excludeSlow(const BitVector& other);
461
462 WTF_EXPORT_PRIVATE size_t bitCountSlow() const;
463 WTF_EXPORT_PRIVATE bool isEmptySlow() const;
464
465 WTF_EXPORT_PRIVATE bool equalsSlowCase(const BitVector& other) const;
466 bool equalsSlowCaseFast(const BitVector& other) const;
467 bool equalsSlowCaseSimple(const BitVector& other) const;
468 WTF_EXPORT_PRIVATE uintptr_t hashSlowCase() const;
469
470 uintptr_t* bits()
471 {
472 if (isInline())
473 return &m_bitsOrPointer;
474 return outOfLineBits()->bits();
475 }
476
477 const uintptr_t* bits() const
478 {
479 if (isInline())
480 return &m_bitsOrPointer;
481 return outOfLineBits()->bits();
482 }
483
484 uintptr_t m_bitsOrPointer;
485};
486
487struct BitVectorHash {
488 static unsigned hash(const BitVector& vector) { return vector.hash(); }
489 static bool equal(const BitVector& a, const BitVector& b) { return a == b; }
490 static const bool safeToCompareToEmptyOrDeleted = false;
491};
492
493template<typename T> struct DefaultHash;
494template<> struct DefaultHash<BitVector> {
495 typedef BitVectorHash Hash;
496};
497
498template<> struct HashTraits<BitVector> : public CustomHashTraits<BitVector> { };
499
500} // namespace WTF
501
502using WTF::BitVector;
503