Index: Source/WTF/wtf/BitVector.h |
diff --git a/Source/WTF/wtf/BitVector.h b/Source/WTF/wtf/BitVector.h |
deleted file mode 100644 |
index f42bc0b91a7d64c199e34f48558e945a02fbf7ed..0000000000000000000000000000000000000000 |
--- a/Source/WTF/wtf/BitVector.h |
+++ /dev/null |
@@ -1,245 +0,0 @@ |
-/* |
- * Copyright (C) 2011 Apple Inc. All rights reserved. |
- * |
- * Redistribution and use in source and binary forms, with or without |
- * modification, are permitted provided that the following conditions |
- * are met: |
- * 1. Redistributions of source code must retain the above copyright |
- * notice, this list of conditions and the following disclaimer. |
- * 2. Redistributions in binary form must reproduce the above copyright |
- * notice, this list of conditions and the following disclaimer in the |
- * documentation and/or other materials provided with the distribution. |
- * |
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
- * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
- */ |
- |
-#ifndef BitVector_h |
-#define BitVector_h |
- |
-#include <stdio.h> |
-#include <wtf/Assertions.h> |
-#include <wtf/PrintStream.h> |
-#include <wtf/StdLibExtras.h> |
- |
-namespace WTF { |
- |
-// This is a space-efficient, resizeable bitvector class. In the common case it |
-// occupies one word, but if necessary, it will inflate this one word to point |
-// to a single chunk of out-of-line allocated storage to store an arbitrary number |
-// of bits. |
-// |
-// - The bitvector remembers the bound of how many bits can be stored, but this |
-// may be slightly greater (by as much as some platform-specific constant) |
-// than the last argument passed to ensureSize(). |
-// |
-// - The bitvector can resize itself automatically (set, clear, get) or can be used |
-// in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize). |
-// |
-// - Accesses ASSERT that you are within bounds. |
-// |
-// - Bits are automatically initialized to zero. |
-// |
-// On the other hand, this BitVector class may not be the fastest around, since |
-// it does conditionals on every get/set/clear. But it is great if you need to |
-// juggle a lot of variable-length BitVectors and you're worried about wasting |
-// space. |
- |
-class BitVector { |
-public: |
- BitVector() |
- : m_bitsOrPointer(makeInlineBits(0)) |
- { |
- } |
- |
- explicit BitVector(size_t numBits) |
- : m_bitsOrPointer(makeInlineBits(0)) |
- { |
- ensureSize(numBits); |
- } |
- |
- BitVector(const BitVector& other) |
- : m_bitsOrPointer(makeInlineBits(0)) |
- { |
- (*this) = other; |
- } |
- |
- |
- ~BitVector() |
- { |
- if (isInline()) |
- return; |
- OutOfLineBits::destroy(outOfLineBits()); |
- } |
- |
- BitVector& operator=(const BitVector& other) |
- { |
- if (isInline() && other.isInline()) |
- m_bitsOrPointer = other.m_bitsOrPointer; |
- else |
- setSlow(other); |
- return *this; |
- } |
- |
- size_t size() const |
- { |
- if (isInline()) |
- return maxInlineBits(); |
- return outOfLineBits()->numBits(); |
- } |
- |
- void ensureSize(size_t numBits) |
- { |
- if (numBits <= size()) |
- return; |
- resizeOutOfLine(numBits); |
- } |
- |
- // Like ensureSize(), but supports reducing the size of the bitvector. |
- WTF_EXPORT_PRIVATE void resize(size_t numBits); |
- |
- WTF_EXPORT_PRIVATE void clearAll(); |
- |
- bool quickGet(size_t bit) const |
- { |
- ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
- return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)))); |
- } |
- |
- void quickSet(size_t bit) |
- { |
- ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
- bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))); |
- } |
- |
- void quickClear(size_t bit) |
- { |
- ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
- bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))); |
- } |
- |
- void quickSet(size_t bit, bool value) |
- { |
- if (value) |
- quickSet(bit); |
- else |
- quickClear(bit); |
- } |
- |
- bool get(size_t bit) const |
- { |
- if (bit >= size()) |
- return false; |
- return quickGet(bit); |
- } |
- |
- void set(size_t bit) |
- { |
- ensureSize(bit + 1); |
- quickSet(bit); |
- } |
- |
- void ensureSizeAndSet(size_t bit, size_t size) |
- { |
- ensureSize(size); |
- quickSet(bit); |
- } |
- |
- void clear(size_t bit) |
- { |
- if (bit >= size()) |
- return; |
- quickClear(bit); |
- } |
- |
- void set(size_t bit, bool value) |
- { |
- if (value) |
- set(bit); |
- else |
- clear(bit); |
- } |
- |
- void dump(PrintStream& out); |
- |
-private: |
- static unsigned bitsInPointer() |
- { |
- return sizeof(void*) << 3; |
- } |
- |
- static unsigned maxInlineBits() |
- { |
- return bitsInPointer() - 1; |
- } |
- |
- static size_t byteCount(size_t bitCount) |
- { |
- return (bitCount + 7) >> 3; |
- } |
- |
- static uintptr_t makeInlineBits(uintptr_t bits) |
- { |
- ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits()))); |
- return bits | (static_cast<uintptr_t>(1) << maxInlineBits()); |
- } |
- |
- class OutOfLineBits { |
- public: |
- size_t numBits() const { return m_numBits; } |
- size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); } |
- uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); } |
- const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); } |
- |
- static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits); |
- |
- static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*); |
- |
- private: |
- OutOfLineBits(size_t numBits) |
- : m_numBits(numBits) |
- { |
- } |
- |
- size_t m_numBits; |
- }; |
- |
- bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); } |
- |
- const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); } |
- OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); } |
- |
- WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits); |
- WTF_EXPORT_PRIVATE void setSlow(const BitVector& other); |
- |
- uintptr_t* bits() |
- { |
- if (isInline()) |
- return &m_bitsOrPointer; |
- return outOfLineBits()->bits(); |
- } |
- |
- const uintptr_t* bits() const |
- { |
- if (isInline()) |
- return &m_bitsOrPointer; |
- return outOfLineBits()->bits(); |
- } |
- |
- uintptr_t m_bitsOrPointer; |
-}; |
- |
-} // namespace WTF |
- |
-using WTF::BitVector; |
- |
-#endif // BitVector_h |