DFG should support continuous optimization
[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 <algorithm>
30 #include <string.h>
31 #include <wtf/Assertions.h>
32 #include <wtf/FastMalloc.h>
33 #include <wtf/StdLibExtras.h>
34
35 namespace WTF {
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 needs to be resized manually (just call ensureSize()).
43 //
44 // - The bitvector remembers the bound of how many bits can be stored, but this
45 //   may be slightly greater (by as much as some platform-specific constant)
46 //   than the last argument passed to ensureSize().
47 //
48 // - Accesses ASSERT that you are within bounds.
49 //
50 // - Bits are not automatically initialized to zero.
51 //
52 // On the other hand, this BitVector class may not be the fastest around, since
53 // it does conditionals on every get/set/clear. But it is great if you need to
54 // juggle a lot of variable-length BitVectors and you're worried about wasting
55 // space.
56
57 class BitVector {
58 public: 
59     BitVector()
60         : m_bitsOrPointer(makeInlineBits(0))
61     {
62     }
63     
64     BitVector(const BitVector& other)
65         : m_bitsOrPointer(makeInlineBits(0))
66     {
67         (*this) = other;
68     }
69     
70     ~BitVector()
71     {
72         if (isInline())
73             return;
74         OutOfLineBits::destroy(outOfLineBits());
75     }
76     
77     BitVector& operator=(const BitVector& other)
78     {
79         uintptr_t newBitsOrPointer;
80         if (other.isInline())
81             newBitsOrPointer = other.m_bitsOrPointer;
82         else {
83             OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(other.size());
84             memcpy(newOutOfLineBits->bits(), other.bits(), byteCount(other.size()));
85             newBitsOrPointer = reinterpret_cast<uintptr_t>(newOutOfLineBits);
86         }
87         if (!isInline())
88             OutOfLineBits::destroy(outOfLineBits());
89         m_bitsOrPointer = newBitsOrPointer;
90         return *this;
91     }
92
93     size_t size() const
94     {
95         if (isInline())
96             return maxInlineBits();
97         return outOfLineBits()->numBits();
98     }
99
100     void ensureSize(size_t numBits)
101     {
102         if (numBits <= size())
103             return;
104         resizeOutOfLine(numBits);
105     }
106     
107     // Like ensureSize(), but supports reducing the size of the bitvector.
108     void resize(size_t numBits)
109     {
110         if (isInline())
111             return;
112         
113         if (numBits <= maxInlineBits()) {
114             OutOfLineBits* myOutOfLineBits = outOfLineBits();
115             m_bitsOrPointer = makeInlineBits(*myOutOfLineBits->bits());
116             OutOfLineBits::destroy(myOutOfLineBits);
117             return;
118         }
119         
120         resizeOutOfLine(numBits);
121     }
122     
123     void clearAll()
124     {
125         if (isInline())
126             m_bitsOrPointer = makeInlineBits(0);
127         else
128             memset(outOfLineBits()->bits(), 0, byteCount(size()));
129     }
130
131     bool get(size_t bit) const
132     {
133         ASSERT(bit < size());
134         return !!(bits()[bit >> bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
135     }
136     
137     void set(size_t bit)
138     {
139         ASSERT(bit < size());
140         bits()[bit >> bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
141     }
142     
143     void clear(size_t bit)
144     {
145         ASSERT(bit < size());
146         bits()[bit >> bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
147     }
148     
149     void set(size_t bit, bool value)
150     {
151         if (value)
152             set(bit);
153         else
154             clear(bit);
155     }
156     
157 private:
158     static unsigned bitsInPointer()
159     {
160         return sizeof(void*) << 3;
161     }
162     
163     static unsigned maxInlineBits()
164     {
165         return bitsInPointer() - 1;
166     }
167     
168     // This function relies on bitCount being a multiple of bitsInPointer()
169     static size_t byteCount(size_t bitCount)
170     {
171         ASSERT(!(bitCount & (bitsInPointer() - 1)));
172         return bitCount >> 3;
173     }
174     
175     static uintptr_t makeInlineBits(uintptr_t bits)
176     {
177         ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
178         return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
179     }
180     
181     class OutOfLineBits {
182     public:
183         size_t numBits() const { return m_numBits; }
184         size_t numWords() const { return (m_numBits + bitsInPointer() - 1) >> bitsInPointer(); }
185         uintptr_t* bits() { return reinterpret_cast<uintptr_t*>(this + 1); }
186         const uintptr_t* bits() const { return reinterpret_cast<const uintptr_t*>(this + 1); }
187         
188         static OutOfLineBits* create(size_t numBits)
189         {
190             numBits = (numBits + bitsInPointer() - 1) & ~bitsInPointer();
191             return new (fastMalloc(sizeof(OutOfLineBits) + (numBits >> bitsInPointer()))) OutOfLineBits(numBits);
192         }
193         
194         static void destroy(OutOfLineBits* outOfLineBits)
195         {
196             fastFree(outOfLineBits);
197         }
198
199     private:
200         OutOfLineBits(size_t numBits)
201             : m_numBits(numBits)
202         {
203         }
204         
205         size_t m_numBits;
206     };
207     
208     bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
209     
210     const OutOfLineBits* outOfLineBits() const { return reinterpret_cast<const OutOfLineBits*>(m_bitsOrPointer); }
211     OutOfLineBits* outOfLineBits() { return reinterpret_cast<OutOfLineBits*>(m_bitsOrPointer); }
212     
213     void resizeOutOfLine(size_t numBits)
214     {
215         ASSERT(numBits > maxInlineBits());
216         OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(numBits);
217         memcpy(newOutOfLineBits->bits(), bits(), byteCount(std::min(size(), numBits)));
218         if (!isInline())
219             OutOfLineBits::destroy(outOfLineBits());
220         m_bitsOrPointer = reinterpret_cast<uintptr_t>(newOutOfLineBits);
221     }
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