1/*
2 * Copyright (C) 2011 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#ifndef BitVector_h
27#define BitVector_h
28
29#include "wtf/Assertions.h"
30#include "wtf/StdLibExtras.h"
31#include "wtf/WTFExport.h"
32
33namespace WTF {
34
35class PrintStream;
36
37// This is a space-efficient, resizeable bitvector class. In the common case it
38// occupies one word, but if necessary, it will inflate this one word to point
39// to a single chunk of out-of-line allocated storage to store an arbitrary number
40// of bits.
41//
42// - The bitvector remembers the bound of how many bits can be stored, but this
43//   may be slightly greater (by as much as some platform-specific constant)
44//   than the last argument passed to ensureSize().
45//
46// - The bitvector can resize itself automatically (set, clear, get) or can be used
47//   in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize).
48//
49// - Accesses ASSERT that you are within bounds.
50//
51// - Bits are automatically initialized to zero.
52//
53// On the other hand, this BitVector class may not be the fastest around, since
54// it does conditionals on every get/set/clear. But it is great if you need to
55// juggle a lot of variable-length BitVectors and you're worried about wasting
56// space.
57
58class WTF_EXPORT BitVector {
59public:
60    BitVector()
61        : m_bitsOrPointer(makeInlineBits(0))
62    {
63    }
64
65    explicit BitVector(size_t numBits)
66        : m_bitsOrPointer(makeInlineBits(0))
67    {
68        ensureSize(numBits);
69    }
70
71    BitVector(const BitVector& other)
72        : m_bitsOrPointer(makeInlineBits(0))
73    {
74        (*this) = other;
75    }
76
77
78    ~BitVector()
79    {
80        if (isInline())
81            return;
82        OutOfLineBits::destroy(outOfLineBits());
83    }
84
85    BitVector& operator=(const BitVector& other)
86    {
87        if (isInline() && other.isInline())
88            m_bitsOrPointer = other.m_bitsOrPointer;
89        else
90            setSlow(other);
91        return *this;
92    }
93
94    size_t size() const
95    {
96        if (isInline())
97            return maxInlineBits();
98        return outOfLineBits()->numBits();
99    }
100
101    void ensureSize(size_t numBits)
102    {
103        if (numBits <= size())
104            return;
105        resizeOutOfLine(numBits);
106    }
107
108    // Like ensureSize(), but supports reducing the size of the bitvector.
109    void resize(size_t numBits);
110
111    void clearAll();
112
113    bool quickGet(size_t bit) const
114    {
115        ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
116        return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
117    }
118
119    void quickSet(size_t bit)
120    {
121        ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
122        bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
123    }
124
125    void quickClear(size_t bit)
126    {
127        ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
128        bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
129    }
130
131    void quickSet(size_t bit, bool value)
132    {
133        if (value)
134            quickSet(bit);
135        else
136            quickClear(bit);
137    }
138
139    bool get(size_t bit) const
140    {
141        if (bit >= size())
142            return false;
143        return quickGet(bit);
144    }
145
146    void set(size_t bit)
147    {
148        ensureSize(bit + 1);
149        quickSet(bit);
150    }
151
152    void ensureSizeAndSet(size_t bit, size_t size)
153    {
154        ensureSize(size);
155        quickSet(bit);
156    }
157
158    void clear(size_t bit)
159    {
160        if (bit >= size())
161            return;
162        quickClear(bit);
163    }
164
165    void set(size_t bit, bool value)
166    {
167        if (value)
168            set(bit);
169        else
170            clear(bit);
171    }
172
173    void dump(PrintStream& out);
174
175private:
176    static unsigned bitsInPointer()
177    {
178        return sizeof(void*) << 3;
179    }
180
181    static unsigned maxInlineBits()
182    {
183        return bitsInPointer() - 1;
184    }
185
186    static size_t byteCount(size_t bitCount)
187    {
188        return (bitCount + 7) >> 3;
189    }
190
191    static uintptr_t makeInlineBits(uintptr_t bits)
192    {
193        ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
194        return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
195    }
196
197    class WTF_EXPORT OutOfLineBits {
198    public:
199        size_t numBits() const { return m_numBits; }
200        size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
201        uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
202        const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
203
204        static OutOfLineBits* create(size_t numBits);
205
206        static void destroy(OutOfLineBits*);
207
208    private:
209        OutOfLineBits(size_t numBits)
210            : m_numBits(numBits)
211        {
212        }
213
214        size_t m_numBits;
215    };
216
217    bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
218
219    const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
220    OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
221
222    void resizeOutOfLine(size_t numBits);
223    void setSlow(const BitVector& other);
224
225    uintptr_t* bits()
226    {
227        if (isInline())
228            return &m_bitsOrPointer;
229        return outOfLineBits()->bits();
230    }
231
232    const uintptr_t* bits() const
233    {
234        if (isInline())
235            return &m_bitsOrPointer;
236        return outOfLineBits()->bits();
237    }
238
239    uintptr_t m_bitsOrPointer;
240};
241
242} // namespace WTF
243
244using WTF::BitVector;
245
246#endif // BitVector_h
247