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