diff options
Diffstat (limited to 'Source/WTF/wtf/BitVector.h')
| -rw-r--r-- | Source/WTF/wtf/BitVector.h | 162 |
1 files changed, 142 insertions, 20 deletions
diff --git a/Source/WTF/wtf/BitVector.h b/Source/WTF/wtf/BitVector.h index 77d95f6df..762cc0460 100644 --- a/Source/WTF/wtf/BitVector.h +++ b/Source/WTF/wtf/BitVector.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2011 Apple Inc. All rights reserved. + * Copyright (C) 2011, 2014, 2016 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -28,6 +28,7 @@ #include <stdio.h> #include <wtf/Assertions.h> +#include <wtf/DataLog.h> #include <wtf/HashFunctions.h> #include <wtf/HashTraits.h> #include <wtf/PrintStream.h> @@ -117,24 +118,31 @@ public: return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)))); } - void quickSet(size_t bit) + bool quickSet(size_t bit) { ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); - bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))); + uintptr_t& word = bits()[bit / bitsInPointer()]; + uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)); + bool result = !!(word & mask); + word |= mask; + return result; } - void quickClear(size_t bit) + bool quickClear(size_t bit) { ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); - bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))); + uintptr_t& word = bits()[bit / bitsInPointer()]; + uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)); + bool result = !!(word & mask); + word &= ~mask; + return result; } - void quickSet(size_t bit, bool value) + bool quickSet(size_t bit, bool value) { if (value) - quickSet(bit); - else - quickClear(bit); + return quickSet(bit); + return quickClear(bit); } bool get(size_t bit) const @@ -143,32 +151,48 @@ public: return false; return quickGet(bit); } + + bool contains(size_t bit) const + { + return get(bit); + } - void set(size_t bit) + bool set(size_t bit) { ensureSize(bit + 1); - quickSet(bit); + return quickSet(bit); + } + + // This works like the add methods of sets. Instead of returning the previous value, like set(), + // it returns whether the bit transitioned from false to true. + bool add(size_t bit) + { + return !set(bit); } - void ensureSizeAndSet(size_t bit, size_t size) + bool ensureSizeAndSet(size_t bit, size_t size) { ensureSize(size); - quickSet(bit); + return quickSet(bit); } - void clear(size_t bit) + bool clear(size_t bit) { if (bit >= size()) - return; - quickClear(bit); + return false; + return quickClear(bit); + } + + bool remove(size_t bit) + { + return clear(bit); } - void set(size_t bit, bool value) + bool set(size_t bit, bool value) { if (value) - set(bit); - else - clear(bit); + return set(bit); + return clear(bit); } void merge(const BitVector& other) @@ -209,6 +233,19 @@ public: return bitCountSlow(); } + size_t findBit(size_t index, bool value) const + { + size_t result = findBitFast(index, value); + if (!ASSERT_DISABLED) { + size_t expectedResult = findBitSimple(index, value); + if (result != expectedResult) { + dataLog("findBit(", index, ", ", value, ") on ", *this, " should have gotten ", expectedResult, " but got ", result, "\n"); + ASSERT_NOT_REACHED(); + } + } + return result; + } + WTF_EXPORT_PRIVATE void dump(PrintStream& out) const; enum EmptyValueTag { EmptyValue }; @@ -249,6 +286,46 @@ public: return IntHash<uintptr_t>::hash(value); } + class iterator { + public: + iterator() + : m_bitVector(nullptr) + , m_index(0) + { + } + + iterator(const BitVector& bitVector, size_t index) + : m_bitVector(&bitVector) + , m_index(index) + { + } + + size_t operator*() const { return m_index; } + + iterator& operator++() + { + m_index = m_bitVector->findBit(m_index + 1, true); + return *this; + } + + bool operator==(const iterator& other) const + { + return m_index == other.m_index; + } + + bool operator!=(const iterator& other) const + { + return !(*this == other); + } + private: + const BitVector* m_bitVector; + size_t m_index; + }; + + // Use this to iterate over set bits. + iterator begin() const { return iterator(*this, findBit(0, true)); } + iterator end() const { return iterator(*this, size()); } + private: static unsigned bitsInPointer() { @@ -283,6 +360,49 @@ private: return WTF::bitCount(static_cast<uint64_t>(bits)); } + size_t findBitFast(size_t startIndex, bool value) const + { + if (isInline()) { + size_t index = startIndex; + findBitInWord(m_bitsOrPointer, index, maxInlineBits(), value); + return index; + } + + const OutOfLineBits* bits = outOfLineBits(); + + // value = true: casts to 1, then xors to 0, then negates to 0. + // value = false: casts to 0, then xors to 1, then negates to -1 (i.e. all one bits). + uintptr_t skipValue = -(static_cast<uintptr_t>(value) ^ 1); + size_t numWords = bits->numWords(); + + size_t wordIndex = startIndex / bitsInPointer(); + size_t startIndexInWord = startIndex - wordIndex * bitsInPointer(); + + while (wordIndex < numWords) { + uintptr_t word = bits->bits()[wordIndex]; + if (word != skipValue) { + size_t index = startIndexInWord; + if (findBitInWord(word, index, bitsInPointer(), value)) + return wordIndex * bitsInPointer() + index; + } + + wordIndex++; + startIndexInWord = 0; + } + + return bits->numBits(); + } + + size_t findBitSimple(size_t index, bool value) const + { + while (index < size()) { + if (get(index) == value) + return index; + index++; + } + return size(); + } + class OutOfLineBits { public: size_t numBits() const { return m_numBits; } @@ -318,6 +438,8 @@ private: WTF_EXPORT_PRIVATE size_t bitCountSlow() const; WTF_EXPORT_PRIVATE bool equalsSlowCase(const BitVector& other) const; + bool equalsSlowCaseFast(const BitVector& other) const; + bool equalsSlowCaseSimple(const BitVector& other) const; WTF_EXPORT_PRIVATE uintptr_t hashSlowCase() const; uintptr_t* bits() |