a5371cc849a925911a20653029fe66138118901f
[WebKit-https.git] / Source / WTF / wtf / BitVector.h
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/StdLibExtras.h>
32
33 namespace WTF {
34
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
38 // of bits.
39 //
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().
43 //
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).
46 //
47 // - Accesses ASSERT that you are within bounds.
48 //
49 // - Bits are automatically initialized to zero.
50 //
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
54 // space.
55
56 class BitVector {
57 public: 
58     BitVector()
59         : m_bitsOrPointer(makeInlineBits(0))
60     {
61     }
62     
63     explicit BitVector(size_t numBits)
64         : m_bitsOrPointer(makeInlineBits(0))
65     {
66         ensureSize(numBits);
67     }
68     
69     BitVector(const BitVector& other)
70         : m_bitsOrPointer(makeInlineBits(0))
71     {
72         (*this) = other;
73     }
74
75     
76     ~BitVector()
77     {
78         if (isInline())
79             return;
80         OutOfLineBits::destroy(outOfLineBits());
81     }
82     
83     BitVector& operator=(const BitVector& other)
84     {
85         if (isInline() && other.isInline())
86             m_bitsOrPointer = other.m_bitsOrPointer;
87         else
88             setSlow(other);
89         return *this;
90     }
91
92     size_t size() const
93     {
94         if (isInline())
95             return maxInlineBits();
96         return outOfLineBits()->numBits();
97     }
98
99     void ensureSize(size_t numBits)
100     {
101         if (numBits <= size())
102             return;
103         resizeOutOfLine(numBits);
104     }
105     
106     // Like ensureSize(), but supports reducing the size of the bitvector.
107     WTF_EXPORT_PRIVATE void resize(size_t numBits);
108     
109     WTF_EXPORT_PRIVATE void clearAll();
110
111     bool quickGet(size_t bit) const
112     {
113         ASSERT(bit < size());
114         return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
115     }
116     
117     void quickSet(size_t bit)
118     {
119         ASSERT(bit < size());
120         bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
121     }
122     
123     void quickClear(size_t bit)
124     {
125         ASSERT(bit < size());
126         bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
127     }
128     
129     void quickSet(size_t bit, bool value)
130     {
131         if (value)
132             quickSet(bit);
133         else
134             quickClear(bit);
135     }
136     
137     bool get(size_t bit) const
138     {
139         if (bit >= size())
140             return false;
141         return quickGet(bit);
142     }
143     
144     void set(size_t bit)
145     {
146         ensureSize(bit + 1);
147         quickSet(bit);
148     }
149     
150     void clear(size_t bit)
151     {
152         if (bit >= size())
153             return;
154         quickClear(bit);
155     }
156     
157     void set(size_t bit, bool value)
158     {
159         if (value)
160             set(bit);
161         else
162             clear(bit);
163     }
164     
165     void dump(FILE* out);
166     
167 private:
168     static unsigned bitsInPointer()
169     {
170         return sizeof(void*) << 3;
171     }
172     
173     static unsigned maxInlineBits()
174     {
175         return bitsInPointer() - 1;
176     }
177     
178     static size_t byteCount(size_t bitCount)
179     {
180         return (bitCount + 7) >> 3;
181     }
182     
183     static uintptr_t makeInlineBits(uintptr_t bits)
184     {
185         ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
186         return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
187     }
188     
189     class OutOfLineBits {
190     public:
191         size_t numBits() const { return m_numBits; }
192         size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
193         uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
194         const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
195         
196         static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
197         
198         static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
199
200     private:
201         OutOfLineBits(size_t numBits)
202             : m_numBits(numBits)
203         {
204         }
205         
206         size_t m_numBits;
207     };
208     
209     bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
210     
211     const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
212     OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
213     
214     WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
215     WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
216     
217     uintptr_t* bits()
218     {
219         if (isInline())
220             return &m_bitsOrPointer;
221         return outOfLineBits()->bits();
222     }
223     
224     const uintptr_t* bits() const
225     {
226         if (isInline())
227             return &m_bitsOrPointer;
228         return outOfLineBits()->bits();
229     }
230     
231     uintptr_t m_bitsOrPointer;
232 };
233
234 } // namespace WTF
235
236 using WTF::BitVector;
237
238 #endif // BitVector_h