2 * Copyright (C) 2011 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
30 #include <wtf/Assertions.h>
31 #include <wtf/StdLibExtras.h>
35 // This is a space-efficient, resizeable bitvector class. In the common case it
36 // occupies one word, but if necessary, it will inflate this one word to point
37 // to a single chunk of out-of-line allocated storage to store an arbitrary number
40 // - The bitvector remembers the bound of how many bits can be stored, but this
41 // may be slightly greater (by as much as some platform-specific constant)
42 // than the last argument passed to ensureSize().
44 // - The bitvector can resize itself automatically (set, clear, get) or can be used
45 // in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize).
47 // - Accesses ASSERT that you are within bounds.
49 // - Bits are automatically initialized to zero.
51 // On the other hand, this BitVector class may not be the fastest around, since
52 // it does conditionals on every get/set/clear. But it is great if you need to
53 // juggle a lot of variable-length BitVectors and you're worried about wasting
59 : m_bitsOrPointer(makeInlineBits(0))
63 explicit BitVector(size_t numBits)
64 : m_bitsOrPointer(makeInlineBits(0))
69 BitVector(const BitVector& other)
70 : m_bitsOrPointer(makeInlineBits(0))
80 OutOfLineBits::destroy(outOfLineBits());
83 BitVector& operator=(const BitVector& other)
85 if (isInline() && other.isInline())
86 m_bitsOrPointer = other.m_bitsOrPointer;
95 return maxInlineBits();
96 return outOfLineBits()->numBits();
99 void ensureSize(size_t numBits)
101 if (numBits <= size())
103 resizeOutOfLine(numBits);
106 // Like ensureSize(), but supports reducing the size of the bitvector.
107 WTF_EXPORT_PRIVATE void resize(size_t numBits);
109 WTF_EXPORT_PRIVATE void clearAll();
111 bool quickGet(size_t bit) const
113 ASSERT(bit < size());
114 return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
117 void quickSet(size_t bit)
119 ASSERT(bit < size());
120 bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
123 void quickClear(size_t bit)
125 ASSERT(bit < size());
126 bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
129 void quickSet(size_t bit, bool value)
137 bool get(size_t bit) const
141 return quickGet(bit);
150 void ensureSizeAndSet(size_t bit, size_t size)
156 void clear(size_t bit)
163 void set(size_t bit, bool value)
171 void dump(FILE* out);
174 static unsigned bitsInPointer()
176 return sizeof(void*) << 3;
179 static unsigned maxInlineBits()
181 return bitsInPointer() - 1;
184 static size_t byteCount(size_t bitCount)
186 return (bitCount + 7) >> 3;
189 static uintptr_t makeInlineBits(uintptr_t bits)
191 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
192 return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
195 class OutOfLineBits {
197 size_t numBits() const { return m_numBits; }
198 size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
199 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
200 const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
202 static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
204 static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
207 OutOfLineBits(size_t numBits)
215 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
217 const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
218 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
220 WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
221 WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
226 return &m_bitsOrPointer;
227 return outOfLineBits()->bits();
230 const uintptr_t* bits() const
233 return &m_bitsOrPointer;
234 return outOfLineBits()->bits();
237 uintptr_t m_bitsOrPointer;
242 using WTF::BitVector;
244 #endif // BitVector_h