Implement Array key, value and entries iterators
[WebKit-https.git] / Source / WTF / wtf / FastBitVector.h
1 /*
2  * Copyright (C) 2012 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 FastBitVector_h
27 #define FastBitVector_h
28
29 #include <wtf/FastMalloc.h>
30 #include <wtf/StdLibExtras.h>
31
32 namespace WTF {
33
34 class FastBitVector {
35 public:
36     FastBitVector()
37         : m_array(0)
38         , m_numBits(0)
39     {
40     }
41     
42     FastBitVector(const FastBitVector& other)
43         : m_array(0)
44         , m_numBits(0)
45     {
46         *this = other;
47     }
48     
49     ~FastBitVector()
50     {
51         if (m_array)
52             fastFree(m_array);
53     }
54     
55     FastBitVector& operator=(const FastBitVector& other)
56     {
57         size_t length = other.arrayLength();
58         uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(length, 4));
59         memcpy(newArray, other.m_array, length * 4);
60         if (m_array)
61             fastFree(m_array);
62         m_array = newArray;
63         m_numBits = other.m_numBits;
64         return *this;
65     }
66     
67     size_t numBits() const { return m_numBits; }
68     
69     void resize(size_t numBits)
70     {
71         // Use fastCalloc instead of fastRealloc because we expect the common
72         // use case for this method to be initializing the size of the bitvector.
73         
74         size_t newLength = (numBits + 31) >> 5;
75         uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(newLength, 4));
76         memcpy(newArray, m_array, arrayLength() * 4);
77         if (m_array)
78             fastFree(m_array);
79         m_array = newArray;
80         m_numBits = numBits;
81     }
82     
83     void setAll()
84     {
85         memset(m_array, 255, arrayLength() * 4);
86     }
87     
88     void clearAll()
89     {
90         memset(m_array, 0, arrayLength() * 4);
91     }
92     
93     void set(const FastBitVector& other)
94     {
95         ASSERT(m_numBits == other.m_numBits);
96         memcpy(m_array, other.m_array, arrayLength() * 4);
97     }
98     
99     bool setAndCheck(const FastBitVector& other)
100     {
101         bool changed = false;
102         ASSERT(m_numBits == other.m_numBits);
103         for (unsigned i = arrayLength(); i--;) {
104             if (m_array[i] == other.m_array[i])
105                 continue;
106             m_array[i] = other.m_array[i];
107             changed = true;
108         }
109         return changed;
110     }
111     
112     bool equals(const FastBitVector& other) const
113     {
114         ASSERT(m_numBits == other.m_numBits);
115         // Use my own comparison loop because memcmp does more than what I want
116         // and bcmp is not as standard.
117         for (unsigned i = arrayLength(); i--;) {
118             if (m_array[i] != other.m_array[i])
119                 return false;
120         }
121         return true;
122     }
123     
124     void merge(const FastBitVector& other)
125     {
126         ASSERT(m_numBits == other.m_numBits);
127         for (unsigned i = arrayLength(); i--;)
128             m_array[i] |= other.m_array[i];
129     }
130     
131     void filter(const FastBitVector& other)
132     {
133         ASSERT(m_numBits == other.m_numBits);
134         for (unsigned i = arrayLength(); i--;)
135             m_array[i] &= other.m_array[i];
136     }
137     
138     void exclude(const FastBitVector& other)
139     {
140         ASSERT(m_numBits == other.m_numBits);
141         for (unsigned i = arrayLength(); i--;)
142             m_array[i] &= ~other.m_array[i];
143     }
144     
145     void set(size_t i)
146     {
147         ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
148         m_array[i >> 5] |= (1 << (i & 31));
149     }
150     
151     void clear(size_t i)
152     {
153         ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
154         m_array[i >> 5] &= ~(1 << (i & 31));
155     }
156     
157     void set(size_t i, bool value)
158     {
159         if (value)
160             set(i);
161         else
162             clear(i);
163     }
164     
165     bool get(size_t i) const
166     {
167         ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
168         return !!(m_array[i >> 5] & (1 << (i & 31)));
169     }
170 private:
171     size_t arrayLength() const { return (m_numBits + 31) >> 5; }
172     
173     uint32_t* m_array; // No, this can't be an std::unique_ptr<uint32_t[]>.
174     size_t m_numBits;
175 };
176
177 } // namespace WTF
178
179 using WTF::FastBitVector;
180
181 #endif // FastBitVector_h
182