Cache bytecode to disk
[WebKit-https.git] / Source / WTF / wtf / BitVector.h
1 /*
2  * Copyright (C) 2011, 2014, 2016 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 #pragma once
27
28 #include <stdio.h>
29 #include <wtf/Assertions.h>
30 #include <wtf/DataLog.h>
31 #include <wtf/HashFunctions.h>
32 #include <wtf/HashTraits.h>
33 #include <wtf/PrintStream.h>
34 #include <wtf/StdLibExtras.h>
35
36 namespace JSC {
37 class CachedBitVector;
38 }
39
40 namespace WTF {
41
42 // This is a space-efficient, resizeable bitvector class. In the common case it
43 // occupies one word, but if necessary, it will inflate this one word to point
44 // to a single chunk of out-of-line allocated storage to store an arbitrary number
45 // of bits.
46 //
47 // - The bitvector remembers the bound of how many bits can be stored, but this
48 //   may be slightly greater (by as much as some platform-specific constant)
49 //   than the last argument passed to ensureSize().
50 //
51 // - The bitvector can resize itself automatically (set, clear, get) or can be used
52 //   in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize).
53 //
54 // - Accesses ASSERT that you are within bounds.
55 //
56 // - Bits are automatically initialized to zero.
57 //
58 // On the other hand, this BitVector class may not be the fastest around, since
59 // it does conditionals on every get/set/clear. But it is great if you need to
60 // juggle a lot of variable-length BitVectors and you're worried about wasting
61 // space.
62
63 class BitVector {
64 public: 
65     BitVector()
66         : m_bitsOrPointer(makeInlineBits(0))
67     {
68     }
69     
70     explicit BitVector(size_t numBits)
71         : m_bitsOrPointer(makeInlineBits(0))
72     {
73         ensureSize(numBits);
74     }
75     
76     BitVector(const BitVector& other)
77         : m_bitsOrPointer(makeInlineBits(0))
78     {
79         (*this) = other;
80     }
81
82     
83     ~BitVector()
84     {
85         if (isInline())
86             return;
87         OutOfLineBits::destroy(outOfLineBits());
88     }
89     
90     BitVector& operator=(const BitVector& other)
91     {
92         if (isInline() && other.isInline())
93             m_bitsOrPointer = other.m_bitsOrPointer;
94         else
95             setSlow(other);
96         return *this;
97     }
98
99     size_t size() const
100     {
101         if (isInline())
102             return maxInlineBits();
103         return outOfLineBits()->numBits();
104     }
105
106     void ensureSize(size_t numBits)
107     {
108         if (numBits <= size())
109             return;
110         resizeOutOfLine(numBits);
111     }
112     
113     // Like ensureSize(), but supports reducing the size of the bitvector.
114     WTF_EXPORT_PRIVATE void resize(size_t numBits);
115     
116     WTF_EXPORT_PRIVATE void clearAll();
117
118     bool quickGet(size_t bit) const
119     {
120         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
121         return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
122     }
123     
124     bool quickSet(size_t bit)
125     {
126         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
127         uintptr_t& word = bits()[bit / bitsInPointer()];
128         uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
129         bool result = !!(word & mask);
130         word |= mask;
131         return result;
132     }
133     
134     bool quickClear(size_t bit)
135     {
136         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
137         uintptr_t& word = bits()[bit / bitsInPointer()];
138         uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
139         bool result = !!(word & mask);
140         word &= ~mask;
141         return result;
142     }
143     
144     bool quickSet(size_t bit, bool value)
145     {
146         if (value)
147             return quickSet(bit);
148         return quickClear(bit);
149     }
150     
151     bool get(size_t bit) const
152     {
153         if (bit >= size())
154             return false;
155         return quickGet(bit);
156     }
157
158     bool contains(size_t bit) const
159     {
160         return get(bit);
161     }
162     
163     bool set(size_t bit)
164     {
165         ensureSize(bit + 1);
166         return quickSet(bit);
167     }
168
169     // This works like the add methods of sets. Instead of returning the previous value, like set(),
170     // it returns whether the bit transitioned from false to true.
171     bool add(size_t bit)
172     {
173         return !set(bit);
174     }
175
176     bool ensureSizeAndSet(size_t bit, size_t size)
177     {
178         ensureSize(size);
179         return quickSet(bit);
180     }
181
182     bool clear(size_t bit)
183     {
184         if (bit >= size())
185             return false;
186         return quickClear(bit);
187     }
188
189     bool remove(size_t bit)
190     {
191         return clear(bit);
192     }
193     
194     bool set(size_t bit, bool value)
195     {
196         if (value)
197             return set(bit);
198         return clear(bit);
199     }
200     
201     void merge(const BitVector& other)
202     {
203         if (!isInline() || !other.isInline()) {
204             mergeSlow(other);
205             return;
206         }
207         m_bitsOrPointer |= other.m_bitsOrPointer;
208         ASSERT(isInline());
209     }
210     
211     void filter(const BitVector& other)
212     {
213         if (!isInline() || !other.isInline()) {
214             filterSlow(other);
215             return;
216         }
217         m_bitsOrPointer &= other.m_bitsOrPointer;
218         ASSERT(isInline());
219     }
220     
221     void exclude(const BitVector& other)
222     {
223         if (!isInline() || !other.isInline()) {
224             excludeSlow(other);
225             return;
226         }
227         m_bitsOrPointer &= ~other.m_bitsOrPointer;
228         m_bitsOrPointer |= (static_cast<uintptr_t>(1) << maxInlineBits());
229         ASSERT(isInline());
230     }
231     
232     size_t bitCount() const
233     {
234         if (isInline())
235             return bitCount(cleanseInlineBits(m_bitsOrPointer));
236         return bitCountSlow();
237     }
238     
239     size_t findBit(size_t index, bool value) const
240     {
241         size_t result = findBitFast(index, value);
242         if (!ASSERT_DISABLED) {
243             size_t expectedResult = findBitSimple(index, value);
244             if (result != expectedResult) {
245                 dataLog("findBit(", index, ", ", value, ") on ", *this, " should have gotten ", expectedResult, " but got ", result, "\n");
246                 ASSERT_NOT_REACHED();
247             }
248         }
249         return result;
250     }
251     
252     WTF_EXPORT_PRIVATE void dump(PrintStream& out) const;
253     
254     enum EmptyValueTag { EmptyValue };
255     enum DeletedValueTag { DeletedValue };
256     
257     BitVector(EmptyValueTag)
258         : m_bitsOrPointer(0)
259     {
260     }
261     
262     BitVector(DeletedValueTag)
263         : m_bitsOrPointer(1)
264     {
265     }
266     
267     bool isEmptyValue() const { return !m_bitsOrPointer; }
268     bool isDeletedValue() const { return m_bitsOrPointer == 1; }
269     
270     bool isEmptyOrDeletedValue() const { return m_bitsOrPointer <= 1; }
271     
272     bool operator==(const BitVector& other) const
273     {
274         if (isInline() && other.isInline())
275             return m_bitsOrPointer == other.m_bitsOrPointer;
276         return equalsSlowCase(other);
277     }
278     
279     unsigned hash() const
280     {
281         // This is a very simple hash. Just xor together the words that hold the various
282         // bits and then compute the hash. This makes it very easy to deal with bitvectors
283         // that have a lot of trailing zero's.
284         uintptr_t value;
285         if (isInline())
286             value = cleanseInlineBits(m_bitsOrPointer);
287         else
288             value = hashSlowCase();
289         return IntHash<uintptr_t>::hash(value);
290     }
291     
292     class iterator {
293     public:
294         iterator()
295             : m_bitVector(nullptr)
296             , m_index(0)
297         {
298         }
299         
300         iterator(const BitVector& bitVector, size_t index)
301             : m_bitVector(&bitVector)
302             , m_index(index)
303         {
304         }
305         
306         size_t operator*() const { return m_index; }
307         
308         iterator& operator++()
309         {
310             m_index = m_bitVector->findBit(m_index + 1, true);
311             return *this;
312         }
313
314         iterator operator++(int)
315         {
316             iterator result = *this;
317             ++(*this);
318             return result;
319         }
320
321         bool isAtEnd() const
322         {
323             return m_index >= m_bitVector->size();
324         }
325         
326         bool operator==(const iterator& other) const
327         {
328             return m_index == other.m_index;
329         }
330         
331         bool operator!=(const iterator& other) const
332         {
333             return !(*this == other);
334         }
335     private:
336         const BitVector* m_bitVector;
337         size_t m_index;
338     };
339
340     // Use this to iterate over set bits.
341     iterator begin() const { return iterator(*this, findBit(0, true)); }
342     iterator end() const { return iterator(*this, size()); }
343         
344 private:
345     friend class JSC::CachedBitVector;
346
347     static unsigned bitsInPointer()
348     {
349         return sizeof(void*) << 3;
350     }
351
352     static unsigned maxInlineBits()
353     {
354         return bitsInPointer() - 1;
355     }
356
357     static size_t byteCount(size_t bitCount)
358     {
359         return (bitCount + 7) >> 3;
360     }
361
362     static uintptr_t makeInlineBits(uintptr_t bits)
363     {
364         ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
365         return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
366     }
367     
368     static uintptr_t cleanseInlineBits(uintptr_t bits)
369     {
370         return bits & ~(static_cast<uintptr_t>(1) << maxInlineBits());
371     }
372     
373     static size_t bitCount(uintptr_t bits)
374     {
375         if (sizeof(uintptr_t) == 4)
376             return WTF::bitCount(static_cast<unsigned>(bits));
377         return WTF::bitCount(static_cast<uint64_t>(bits));
378     }
379     
380     size_t findBitFast(size_t startIndex, bool value) const
381     {
382         if (isInline()) {
383             size_t index = startIndex;
384             findBitInWord(m_bitsOrPointer, index, maxInlineBits(), value);
385             return index;
386         }
387         
388         const OutOfLineBits* bits = outOfLineBits();
389         
390         // value = true: casts to 1, then xors to 0, then negates to 0.
391         // value = false: casts to 0, then xors to 1, then negates to -1 (i.e. all one bits).
392         uintptr_t skipValue = -(static_cast<uintptr_t>(value) ^ 1);
393         size_t numWords = bits->numWords();
394         
395         size_t wordIndex = startIndex / bitsInPointer();
396         size_t startIndexInWord = startIndex - wordIndex * bitsInPointer();
397         
398         while (wordIndex < numWords) {
399             uintptr_t word = bits->bits()[wordIndex];
400             if (word != skipValue) {
401                 size_t index = startIndexInWord;
402                 if (findBitInWord(word, index, bitsInPointer(), value))
403                     return wordIndex * bitsInPointer() + index;
404             }
405             
406             wordIndex++;
407             startIndexInWord = 0;
408         }
409         
410         return bits->numBits();
411     }
412     
413     size_t findBitSimple(size_t index, bool value) const
414     {
415         while (index < size()) {
416             if (get(index) == value)
417                 return index;
418             index++;
419         }
420         return size();
421     }
422     
423     class OutOfLineBits {
424     public:
425         size_t numBits() const { return m_numBits; }
426         size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
427         uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
428         const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
429         
430         static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
431         
432         static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
433
434     private:
435         OutOfLineBits(size_t numBits)
436             : m_numBits(numBits)
437         {
438         }
439         
440         size_t m_numBits;
441     };
442     
443     bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
444     
445     const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
446     OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
447     
448     WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
449     WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
450     
451     WTF_EXPORT_PRIVATE void mergeSlow(const BitVector& other);
452     WTF_EXPORT_PRIVATE void filterSlow(const BitVector& other);
453     WTF_EXPORT_PRIVATE void excludeSlow(const BitVector& other);
454     
455     WTF_EXPORT_PRIVATE size_t bitCountSlow() const;
456     
457     WTF_EXPORT_PRIVATE bool equalsSlowCase(const BitVector& other) const;
458     bool equalsSlowCaseFast(const BitVector& other) const;
459     bool equalsSlowCaseSimple(const BitVector& other) const;
460     WTF_EXPORT_PRIVATE uintptr_t hashSlowCase() const;
461     
462     uintptr_t* bits()
463     {
464         if (isInline())
465             return &m_bitsOrPointer;
466         return outOfLineBits()->bits();
467     }
468     
469     const uintptr_t* bits() const
470     {
471         if (isInline())
472             return &m_bitsOrPointer;
473         return outOfLineBits()->bits();
474     }
475     
476     uintptr_t m_bitsOrPointer;
477 };
478
479 struct BitVectorHash {
480     static unsigned hash(const BitVector& vector) { return vector.hash(); }
481     static bool equal(const BitVector& a, const BitVector& b) { return a == b; }
482     static const bool safeToCompareToEmptyOrDeleted = false;
483 };
484
485 template<typename T> struct DefaultHash;
486 template<> struct DefaultHash<BitVector> {
487     typedef BitVectorHash Hash;
488 };
489
490 template<> struct HashTraits<BitVector> : public CustomHashTraits<BitVector> { };
491
492 } // namespace WTF
493
494 using WTF::BitVector;