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 <stdio.h>
30#include <wtf/Assertions.h>
31#include <wtf/HashFunctions.h>
32#include <wtf/HashTraits.h>
33#include <wtf/PrintStream.h>
34#include <wtf/StdLibExtras.h>
35
36namespace WTF {
37
38// This is a space-efficient, resizeable bitvector class. In the common case it
39// occupies one word, but if necessary, it will inflate this one word to point
40// to a single chunk of out-of-line allocated storage to store an arbitrary number
41// of bits.
42//
43// - The bitvector remembers the bound of how many bits can be stored, but this
44//   may be slightly greater (by as much as some platform-specific constant)
45//   than the last argument passed to ensureSize().
46//
47// - The bitvector can resize itself automatically (set, clear, get) or can be used
48//   in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize).
49//
50// - Accesses ASSERT that you are within bounds.
51//
52// - Bits are automatically initialized to zero.
53//
54// On the other hand, this BitVector class may not be the fastest around, since
55// it does conditionals on every get/set/clear. But it is great if you need to
56// juggle a lot of variable-length BitVectors and you're worried about wasting
57// space.
58
59class BitVector {
60public:
61    BitVector()
62        : m_bitsOrPointer(makeInlineBits(0))
63    {
64    }
65
66    explicit BitVector(size_t numBits)
67        : m_bitsOrPointer(makeInlineBits(0))
68    {
69        ensureSize(numBits);
70    }
71
72    BitVector(const BitVector& other)
73        : m_bitsOrPointer(makeInlineBits(0))
74    {
75        (*this) = other;
76    }
77
78
79    ~BitVector()
80    {
81        if (isInline())
82            return;
83        OutOfLineBits::destroy(outOfLineBits());
84    }
85
86    BitVector& operator=(const BitVector& other)
87    {
88        if (isInline() && other.isInline())
89            m_bitsOrPointer = other.m_bitsOrPointer;
90        else
91            setSlow(other);
92        return *this;
93    }
94
95    size_t size() const
96    {
97        if (isInline())
98            return maxInlineBits();
99        return outOfLineBits()->numBits();
100    }
101
102    void ensureSize(size_t numBits)
103    {
104        if (numBits <= size())
105            return;
106        resizeOutOfLine(numBits);
107    }
108
109    // Like ensureSize(), but supports reducing the size of the bitvector.
110    WTF_EXPORT_PRIVATE void resize(size_t numBits);
111
112    WTF_EXPORT_PRIVATE void clearAll();
113
114    bool quickGet(size_t bit) const
115    {
116        ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
117        return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
118    }
119
120    void quickSet(size_t bit)
121    {
122        ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
123        bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
124    }
125
126    void quickClear(size_t bit)
127    {
128        ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
129        bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
130    }
131
132    void quickSet(size_t bit, bool value)
133    {
134        if (value)
135            quickSet(bit);
136        else
137            quickClear(bit);
138    }
139
140    bool get(size_t bit) const
141    {
142        if (bit >= size())
143            return false;
144        return quickGet(bit);
145    }
146
147    void set(size_t bit)
148    {
149        ensureSize(bit + 1);
150        quickSet(bit);
151    }
152
153    void ensureSizeAndSet(size_t bit, size_t size)
154    {
155        ensureSize(size);
156        quickSet(bit);
157    }
158
159    void clear(size_t bit)
160    {
161        if (bit >= size())
162            return;
163        quickClear(bit);
164    }
165
166    void set(size_t bit, bool value)
167    {
168        if (value)
169            set(bit);
170        else
171            clear(bit);
172    }
173
174    void merge(const BitVector& other)
175    {
176        if (!isInline() || !other.isInline()) {
177            mergeSlow(other);
178            return;
179        }
180        m_bitsOrPointer |= other.m_bitsOrPointer;
181        ASSERT(isInline());
182    }
183
184    void filter(const BitVector& other)
185    {
186        if (!isInline() || !other.isInline()) {
187            filterSlow(other);
188            return;
189        }
190        m_bitsOrPointer &= other.m_bitsOrPointer;
191        ASSERT(isInline());
192    }
193
194    void exclude(const BitVector& other)
195    {
196        if (!isInline() || !other.isInline()) {
197            excludeSlow(other);
198            return;
199        }
200        m_bitsOrPointer &= ~other.m_bitsOrPointer;
201        m_bitsOrPointer |= (static_cast<uintptr_t>(1) << maxInlineBits());
202        ASSERT(isInline());
203    }
204
205    size_t bitCount() const
206    {
207        if (isInline())
208            return bitCount(cleanseInlineBits(m_bitsOrPointer));
209        return bitCountSlow();
210    }
211
212    WTF_EXPORT_PRIVATE void dump(PrintStream& out) const;
213
214    enum EmptyValueTag { EmptyValue };
215    enum DeletedValueTag { DeletedValue };
216
217    BitVector(EmptyValueTag)
218        : m_bitsOrPointer(0)
219    {
220    }
221
222    BitVector(DeletedValueTag)
223        : m_bitsOrPointer(1)
224    {
225    }
226
227    bool isEmptyValue() const { return !m_bitsOrPointer; }
228    bool isDeletedValue() const { return m_bitsOrPointer == 1; }
229
230    bool isEmptyOrDeletedValue() const { return m_bitsOrPointer <= 1; }
231
232    bool operator==(const BitVector& other) const
233    {
234        if (isInline() && other.isInline())
235            return m_bitsOrPointer == other.m_bitsOrPointer;
236        return equalsSlowCase(other);
237    }
238
239    unsigned hash() const
240    {
241        // This is a very simple hash. Just xor together the words that hold the various
242        // bits and then compute the hash. This makes it very easy to deal with bitvectors
243        // that have a lot of trailing zero's.
244        uintptr_t value;
245        if (isInline())
246            value = cleanseInlineBits(m_bitsOrPointer);
247        else
248            value = hashSlowCase();
249        return IntHash<uintptr_t>::hash(value);
250    }
251
252private:
253    static unsigned bitsInPointer()
254    {
255        return sizeof(void*) << 3;
256    }
257
258    static unsigned maxInlineBits()
259    {
260        return bitsInPointer() - 1;
261    }
262
263    static size_t byteCount(size_t bitCount)
264    {
265        return (bitCount + 7) >> 3;
266    }
267
268    static uintptr_t makeInlineBits(uintptr_t bits)
269    {
270        ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
271        return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
272    }
273
274    static uintptr_t cleanseInlineBits(uintptr_t bits)
275    {
276        return bits & ~(static_cast<uintptr_t>(1) << maxInlineBits());
277    }
278
279    static size_t bitCount(uintptr_t bits)
280    {
281        if (sizeof(uintptr_t) == 4)
282            return WTF::bitCount(static_cast<unsigned>(bits));
283        return WTF::bitCount(static_cast<uint64_t>(bits));
284    }
285
286    class OutOfLineBits {
287    public:
288        size_t numBits() const { return m_numBits; }
289        size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
290        uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
291        const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
292
293        static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
294
295        static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
296
297    private:
298        OutOfLineBits(size_t numBits)
299            : m_numBits(numBits)
300        {
301        }
302
303        size_t m_numBits;
304    };
305
306    bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
307
308    const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
309    OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
310
311    WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
312    WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
313
314    WTF_EXPORT_PRIVATE void mergeSlow(const BitVector& other);
315    WTF_EXPORT_PRIVATE void filterSlow(const BitVector& other);
316    WTF_EXPORT_PRIVATE void excludeSlow(const BitVector& other);
317
318    WTF_EXPORT_PRIVATE size_t bitCountSlow() const;
319
320    WTF_EXPORT_PRIVATE bool equalsSlowCase(const BitVector& other) const;
321    WTF_EXPORT_PRIVATE uintptr_t hashSlowCase() const;
322
323    uintptr_t* bits()
324    {
325        if (isInline())
326            return &m_bitsOrPointer;
327        return outOfLineBits()->bits();
328    }
329
330    const uintptr_t* bits() const
331    {
332        if (isInline())
333            return &m_bitsOrPointer;
334        return outOfLineBits()->bits();
335    }
336
337    uintptr_t m_bitsOrPointer;
338};
339
340struct BitVectorHash {
341    static unsigned hash(const BitVector& vector) { return vector.hash(); }
342    static bool equal(const BitVector& a, const BitVector& b) { return a == b; }
343    static const bool safeToCompareToEmptyOrDeleted = false;
344};
345
346template<typename T> struct DefaultHash;
347template<> struct DefaultHash<BitVector> {
348    typedef BitVectorHash Hash;
349};
350
351template<typename T> struct HashTraits;
352template<> struct HashTraits<BitVector> : public CustomHashTraits<BitVector> { };
353
354} // namespace WTF
355
356using WTF::BitVector;
357
358#endif // BitVector_h
359