1/* 2 * Copyright (C) 2011 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 BitVector_h 27#define BitVector_h 28 29#include <stdio.h> 30#include <wtf/Assertions.h> 31#include <wtf/HashFunctions.h> 32#include <wtf/HashTraits.h> 33#include <wtf/PrintStream.h> 34#include <wtf/StdLibExtras.h> 35 36namespace WTF { 37 38// This is a space-efficient, resizeable bitvector class. In the common case it 39// occupies one word, but if necessary, it will inflate this one word to point 40// to a single chunk of out-of-line allocated storage to store an arbitrary number 41// of bits. 42// 43// - The bitvector remembers the bound of how many bits can be stored, but this 44// may be slightly greater (by as much as some platform-specific constant) 45// than the last argument passed to ensureSize(). 46// 47// - The bitvector can resize itself automatically (set, clear, get) or can be used 48// in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize). 49// 50// - Accesses ASSERT that you are within bounds. 51// 52// - Bits are automatically initialized to zero. 53// 54// On the other hand, this BitVector class may not be the fastest around, since 55// it does conditionals on every get/set/clear. But it is great if you need to 56// juggle a lot of variable-length BitVectors and you're worried about wasting 57// space. 58 59class BitVector { 60public: 61 BitVector() 62 : m_bitsOrPointer(makeInlineBits(0)) 63 { 64 } 65 66 explicit BitVector(size_t numBits) 67 : m_bitsOrPointer(makeInlineBits(0)) 68 { 69 ensureSize(numBits); 70 } 71 72 BitVector(const BitVector& other) 73 : m_bitsOrPointer(makeInlineBits(0)) 74 { 75 (*this) = other; 76 } 77 78 79 ~BitVector() 80 { 81 if (isInline()) 82 return; 83 OutOfLineBits::destroy(outOfLineBits()); 84 } 85 86 BitVector& operator=(const BitVector& other) 87 { 88 if (isInline() && other.isInline()) 89 m_bitsOrPointer = other.m_bitsOrPointer; 90 else 91 setSlow(other); 92 return *this; 93 } 94 95 size_t size() const 96 { 97 if (isInline()) 98 return maxInlineBits(); 99 return outOfLineBits()->numBits(); 100 } 101 102 void ensureSize(size_t numBits) 103 { 104 if (numBits <= size()) 105 return; 106 resizeOutOfLine(numBits); 107 } 108 109 // Like ensureSize(), but supports reducing the size of the bitvector. 110 WTF_EXPORT_PRIVATE void resize(size_t numBits); 111 112 WTF_EXPORT_PRIVATE void clearAll(); 113 114 bool quickGet(size_t bit) const 115 { 116 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); 117 return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)))); 118 } 119 120 void quickSet(size_t bit) 121 { 122 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); 123 bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))); 124 } 125 126 void quickClear(size_t bit) 127 { 128 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); 129 bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))); 130 } 131 132 void quickSet(size_t bit, bool value) 133 { 134 if (value) 135 quickSet(bit); 136 else 137 quickClear(bit); 138 } 139 140 bool get(size_t bit) const 141 { 142 if (bit >= size()) 143 return false; 144 return quickGet(bit); 145 } 146 147 void set(size_t bit) 148 { 149 ensureSize(bit + 1); 150 quickSet(bit); 151 } 152 153 void ensureSizeAndSet(size_t bit, size_t size) 154 { 155 ensureSize(size); 156 quickSet(bit); 157 } 158 159 void clear(size_t bit) 160 { 161 if (bit >= size()) 162 return; 163 quickClear(bit); 164 } 165 166 void set(size_t bit, bool value) 167 { 168 if (value) 169 set(bit); 170 else 171 clear(bit); 172 } 173 174 void merge(const BitVector& other) 175 { 176 if (!isInline() || !other.isInline()) { 177 mergeSlow(other); 178 return; 179 } 180 m_bitsOrPointer |= other.m_bitsOrPointer; 181 ASSERT(isInline()); 182 } 183 184 void filter(const BitVector& other) 185 { 186 if (!isInline() || !other.isInline()) { 187 filterSlow(other); 188 return; 189 } 190 m_bitsOrPointer &= other.m_bitsOrPointer; 191 ASSERT(isInline()); 192 } 193 194 void exclude(const BitVector& other) 195 { 196 if (!isInline() || !other.isInline()) { 197 excludeSlow(other); 198 return; 199 } 200 m_bitsOrPointer &= ~other.m_bitsOrPointer; 201 m_bitsOrPointer |= (static_cast<uintptr_t>(1) << maxInlineBits()); 202 ASSERT(isInline()); 203 } 204 205 size_t bitCount() const 206 { 207 if (isInline()) 208 return bitCount(cleanseInlineBits(m_bitsOrPointer)); 209 return bitCountSlow(); 210 } 211 212 WTF_EXPORT_PRIVATE void dump(PrintStream& out) const; 213 214 enum EmptyValueTag { EmptyValue }; 215 enum DeletedValueTag { DeletedValue }; 216 217 BitVector(EmptyValueTag) 218 : m_bitsOrPointer(0) 219 { 220 } 221 222 BitVector(DeletedValueTag) 223 : m_bitsOrPointer(1) 224 { 225 } 226 227 bool isEmptyValue() const { return !m_bitsOrPointer; } 228 bool isDeletedValue() const { return m_bitsOrPointer == 1; } 229 230 bool isEmptyOrDeletedValue() const { return m_bitsOrPointer <= 1; } 231 232 bool operator==(const BitVector& other) const 233 { 234 if (isInline() && other.isInline()) 235 return m_bitsOrPointer == other.m_bitsOrPointer; 236 return equalsSlowCase(other); 237 } 238 239 unsigned hash() const 240 { 241 // This is a very simple hash. Just xor together the words that hold the various 242 // bits and then compute the hash. This makes it very easy to deal with bitvectors 243 // that have a lot of trailing zero's. 244 uintptr_t value; 245 if (isInline()) 246 value = cleanseInlineBits(m_bitsOrPointer); 247 else 248 value = hashSlowCase(); 249 return IntHash<uintptr_t>::hash(value); 250 } 251 252private: 253 static unsigned bitsInPointer() 254 { 255 return sizeof(void*) << 3; 256 } 257 258 static unsigned maxInlineBits() 259 { 260 return bitsInPointer() - 1; 261 } 262 263 static size_t byteCount(size_t bitCount) 264 { 265 return (bitCount + 7) >> 3; 266 } 267 268 static uintptr_t makeInlineBits(uintptr_t bits) 269 { 270 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits()))); 271 return bits | (static_cast<uintptr_t>(1) << maxInlineBits()); 272 } 273 274 static uintptr_t cleanseInlineBits(uintptr_t bits) 275 { 276 return bits & ~(static_cast<uintptr_t>(1) << maxInlineBits()); 277 } 278 279 static size_t bitCount(uintptr_t bits) 280 { 281 if (sizeof(uintptr_t) == 4) 282 return WTF::bitCount(static_cast<unsigned>(bits)); 283 return WTF::bitCount(static_cast<uint64_t>(bits)); 284 } 285 286 class OutOfLineBits { 287 public: 288 size_t numBits() const { return m_numBits; } 289 size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); } 290 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); } 291 const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); } 292 293 static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits); 294 295 static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*); 296 297 private: 298 OutOfLineBits(size_t numBits) 299 : m_numBits(numBits) 300 { 301 } 302 303 size_t m_numBits; 304 }; 305 306 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); } 307 308 const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); } 309 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); } 310 311 WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits); 312 WTF_EXPORT_PRIVATE void setSlow(const BitVector& other); 313 314 WTF_EXPORT_PRIVATE void mergeSlow(const BitVector& other); 315 WTF_EXPORT_PRIVATE void filterSlow(const BitVector& other); 316 WTF_EXPORT_PRIVATE void excludeSlow(const BitVector& other); 317 318 WTF_EXPORT_PRIVATE size_t bitCountSlow() const; 319 320 WTF_EXPORT_PRIVATE bool equalsSlowCase(const BitVector& other) const; 321 WTF_EXPORT_PRIVATE uintptr_t hashSlowCase() const; 322 323 uintptr_t* bits() 324 { 325 if (isInline()) 326 return &m_bitsOrPointer; 327 return outOfLineBits()->bits(); 328 } 329 330 const uintptr_t* bits() const 331 { 332 if (isInline()) 333 return &m_bitsOrPointer; 334 return outOfLineBits()->bits(); 335 } 336 337 uintptr_t m_bitsOrPointer; 338}; 339 340struct BitVectorHash { 341 static unsigned hash(const BitVector& vector) { return vector.hash(); } 342 static bool equal(const BitVector& a, const BitVector& b) { return a == b; } 343 static const bool safeToCompareToEmptyOrDeleted = false; 344}; 345 346template<typename T> struct DefaultHash; 347template<> struct DefaultHash<BitVector> { 348 typedef BitVectorHash Hash; 349}; 350 351template<typename T> struct HashTraits; 352template<> struct HashTraits<BitVector> : public CustomHashTraits<BitVector> { }; 353 354} // namespace WTF 355 356using WTF::BitVector; 357 358#endif // BitVector_h 359