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