2 * Copyright (C) 2012 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
26 #ifndef FastBitVector_h
27 #define FastBitVector_h
29 #include <wtf/FastMalloc.h>
30 #include <wtf/OwnArrayPtr.h>
31 #include <wtf/PassOwnArrayPtr.h>
32 #include <wtf/StdLibExtras.h>
44 FastBitVector(const FastBitVector& other)
57 FastBitVector& operator=(const FastBitVector& other)
59 size_t length = other.arrayLength();
60 uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(length, 4));
61 memcpy(newArray, other.m_array, length * 4);
65 m_numBits = other.m_numBits;
69 size_t numBits() const { return m_numBits; }
71 void resize(size_t numBits)
73 // Use fastCalloc instead of fastRealloc because we expect the common
74 // use case for this method to be initializing the size of the bitvector.
76 size_t newLength = (numBits + 31) >> 5;
77 uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(newLength, 4));
78 memcpy(newArray, m_array, arrayLength() * 4);
87 memset(m_array, 255, arrayLength() * 4);
92 memset(m_array, 0, arrayLength() * 4);
95 void set(const FastBitVector& other)
97 ASSERT(m_numBits == other.m_numBits);
98 memcpy(m_array, other.m_array, arrayLength() * 4);
101 bool setAndCheck(const FastBitVector& other)
103 bool changed = false;
104 ASSERT(m_numBits == other.m_numBits);
105 for (unsigned i = arrayLength(); i--;) {
106 if (m_array[i] == other.m_array[i])
108 m_array[i] = other.m_array[i];
114 bool equals(const FastBitVector& other) const
116 ASSERT(m_numBits == other.m_numBits);
117 // Use my own comparison loop because memcmp does more than what I want
118 // and bcmp is not as standard.
119 for (unsigned i = arrayLength(); i--;) {
120 if (m_array[i] != other.m_array[i])
126 void merge(const FastBitVector& other)
128 ASSERT(m_numBits == other.m_numBits);
129 for (unsigned i = arrayLength(); i--;)
130 m_array[i] |= other.m_array[i];
133 void filter(const FastBitVector& other)
135 ASSERT(m_numBits == other.m_numBits);
136 for (unsigned i = arrayLength(); i--;)
137 m_array[i] &= other.m_array[i];
140 void exclude(const FastBitVector& other)
142 ASSERT(m_numBits == other.m_numBits);
143 for (unsigned i = arrayLength(); i--;)
144 m_array[i] &= ~other.m_array[i];
149 ASSERT(i < m_numBits);
150 m_array[i >> 5] |= (1 << (i & 31));
155 ASSERT(i < m_numBits);
156 m_array[i >> 5] &= ~(1 << (i & 31));
159 void set(size_t i, bool value)
167 bool get(size_t i) const
169 ASSERT(i < m_numBits);
170 return !!(m_array[i >> 5] & (1 << (i & 31)));
173 size_t arrayLength() const { return (m_numBits + 31) >> 5; }
175 uint32_t* m_array; // No, this can't be an OwnArrayPtr.
181 using WTF::FastBitVector;
183 #endif // FastBitVector_h