wtf/BitVector.h has a variety of bugs which manifest when the
[WebKit-https.git] / Source / JavaScriptCore / 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 <wtf/Assertions.h>
30 #include <wtf/StdLibExtras.h>
31
32 namespace WTF {
33
34 // This is a space-efficient, resizeable bitvector class. In the common case it
35 // occupies one word, but if necessary, it will inflate this one word to point
36 // to a single chunk of out-of-line allocated storage to store an arbitrary number
37 // of bits.
38 //
39 // - The bitvector needs to be resized manually (just call ensureSize()).
40 //
41 // - The bitvector remembers the bound of how many bits can be stored, but this
42 //   may be slightly greater (by as much as some platform-specific constant)
43 //   than the last argument passed to ensureSize().
44 //
45 // - Accesses ASSERT that you are within bounds.
46 //
47 // - Bits are not automatically initialized to zero.
48 //
49 // On the other hand, this BitVector class may not be the fastest around, since
50 // it does conditionals on every get/set/clear. But it is great if you need to
51 // juggle a lot of variable-length BitVectors and you're worried about wasting
52 // space.
53
54 class BitVector {
55 public: 
56     BitVector()
57         : m_bitsOrPointer(makeInlineBits(0))
58     {
59     }
60     
61     BitVector(const BitVector& other);
62     
63     ~BitVector()
64     {
65         if (isInline())
66             return;
67         OutOfLineBits::destroy(outOfLineBits());
68     }
69     
70     BitVector& operator=(const BitVector& other);
71
72     size_t size() const
73     {
74         if (isInline())
75             return maxInlineBits();
76         return outOfLineBits()->numBits();
77     }
78
79     void ensureSize(size_t numBits)
80     {
81         if (numBits <= size())
82             return;
83         resizeOutOfLine(numBits);
84     }
85     
86     // Like ensureSize(), but supports reducing the size of the bitvector.
87     void resize(size_t numBits);
88     
89     void clearAll();
90
91     bool get(size_t bit) const
92     {
93         ASSERT(bit < size());
94         return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
95     }
96     
97     void set(size_t bit)
98     {
99         ASSERT(bit < size());
100         bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
101     }
102     
103     void clear(size_t bit)
104     {
105         ASSERT(bit < size());
106         bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
107     }
108     
109     void set(size_t bit, bool value)
110     {
111         if (value)
112             set(bit);
113         else
114             clear(bit);
115     }
116     
117 private:
118     static unsigned bitsInPointer()
119     {
120         return sizeof(void*) << 3;
121     }
122     
123     static unsigned maxInlineBits()
124     {
125         return bitsInPointer() - 1;
126     }
127     
128     static size_t byteCount(size_t bitCount)
129     {
130         return (bitCount + 7) >> 3;
131     }
132     
133     static uintptr_t makeInlineBits(uintptr_t bits)
134     {
135         ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
136         return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
137     }
138     
139     class OutOfLineBits {
140     public:
141         size_t numBits() const { return m_numBits; }
142         size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
143         uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
144         const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
145         
146         static OutOfLineBits* create(size_t numBits);
147         
148         static void destroy(OutOfLineBits*);
149
150     private:
151         OutOfLineBits(size_t numBits)
152             : m_numBits(numBits)
153         {
154         }
155         
156         size_t m_numBits;
157     };
158     
159     bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
160     
161     const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer); }
162     OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer); }
163     
164     void resizeOutOfLine(size_t numBits);
165     
166     uintptr_t* bits()
167     {
168         if (isInline())
169             return &m_bitsOrPointer;
170         return outOfLineBits()->bits();
171     }
172     
173     const uintptr_t* bits() const
174     {
175         if (isInline())
176             return &m_bitsOrPointer;
177         return outOfLineBits()->bits();
178     }
179     
180     uintptr_t m_bitsOrPointer;
181 };
182
183 } // namespace WTF
184
185 using WTF::BitVector;
186
187 #endif // BitVector_h