cssText should use shorthand notations
[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 ensureSizeAndSet(size_t bit, size_t size)
151     {
152         ensureSize(size);
153         quickSet(bit);
154     }
155
156     void clear(size_t bit)
157     {
158         if (bit >= size())
159             return;
160         quickClear(bit);
161     }
162     
163     void set(size_t bit, bool value)
164     {
165         if (value)
166             set(bit);
167         else
168             clear(bit);
169     }
170     
171     void dump(FILE* out);
172     
173 private:
174     static unsigned bitsInPointer()
175     {
176         return sizeof(void*) << 3;
177     }
178     
179     static unsigned maxInlineBits()
180     {
181         return bitsInPointer() - 1;
182     }
183     
184     static size_t byteCount(size_t bitCount)
185     {
186         return (bitCount + 7) >> 3;
187     }
188     
189     static uintptr_t makeInlineBits(uintptr_t bits)
190     {
191         ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
192         return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
193     }
194     
195     class OutOfLineBits {
196     public:
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); }
201         
202         static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
203         
204         static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
205
206     private:
207         OutOfLineBits(size_t numBits)
208             : m_numBits(numBits)
209         {
210         }
211         
212         size_t m_numBits;
213     };
214     
215     bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
216     
217     const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
218     OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
219     
220     WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
221     WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
222     
223     uintptr_t* bits()
224     {
225         if (isInline())
226             return &m_bitsOrPointer;
227         return outOfLineBits()->bits();
228     }
229     
230     const uintptr_t* bits() const
231     {
232         if (isInline())
233             return &m_bitsOrPointer;
234         return outOfLineBits()->bits();
235     }
236     
237     uintptr_t m_bitsOrPointer;
238 };
239
240 } // namespace WTF
241
242 using WTF::BitVector;
243
244 #endif // BitVector_h