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#include "config.h" 27#include "BitVector.h" 28 29#include <algorithm> 30#include <string.h> 31#include <wtf/Assertions.h> 32#include <wtf/FastMalloc.h> 33#include <wtf/StdLibExtras.h> 34 35namespace WTF { 36 37void BitVector::setSlow(const BitVector& other) 38{ 39 uintptr_t newBitsOrPointer; 40 if (other.isInline() || other.isEmptyOrDeletedValue()) 41 newBitsOrPointer = other.m_bitsOrPointer; 42 else { 43 OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(other.size()); 44 memcpy(newOutOfLineBits->bits(), other.bits(), byteCount(other.size())); 45 newBitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits) >> 1; 46 } 47 if (!isInline() && !isEmptyOrDeletedValue()) 48 OutOfLineBits::destroy(outOfLineBits()); 49 m_bitsOrPointer = newBitsOrPointer; 50} 51 52void BitVector::resize(size_t numBits) 53{ 54 if (numBits <= maxInlineBits()) { 55 if (isInline()) 56 return; 57 58 OutOfLineBits* myOutOfLineBits = outOfLineBits(); 59 m_bitsOrPointer = makeInlineBits(*myOutOfLineBits->bits()); 60 OutOfLineBits::destroy(myOutOfLineBits); 61 return; 62 } 63 64 resizeOutOfLine(numBits); 65} 66 67void BitVector::clearAll() 68{ 69 if (isInline()) 70 m_bitsOrPointer = makeInlineBits(0); 71 else 72 memset(outOfLineBits()->bits(), 0, byteCount(size())); 73} 74 75BitVector::OutOfLineBits* BitVector::OutOfLineBits::create(size_t numBits) 76{ 77 numBits = (numBits + bitsInPointer() - 1) & ~(bitsInPointer() - 1); 78 size_t size = sizeof(OutOfLineBits) + sizeof(uintptr_t) * (numBits / bitsInPointer()); 79 OutOfLineBits* result = new (NotNull, fastMalloc(size)) OutOfLineBits(numBits); 80 return result; 81} 82 83void BitVector::OutOfLineBits::destroy(OutOfLineBits* outOfLineBits) 84{ 85 fastFree(outOfLineBits); 86} 87 88void BitVector::resizeOutOfLine(size_t numBits) 89{ 90 ASSERT(numBits > maxInlineBits()); 91 OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(numBits); 92 size_t newNumWords = newOutOfLineBits->numWords(); 93 if (isInline()) { 94 // Make sure that all of the bits are zero in case we do a no-op resize. 95 *newOutOfLineBits->bits() = m_bitsOrPointer & ~(static_cast<uintptr_t>(1) << maxInlineBits()); 96 memset(newOutOfLineBits->bits() + 1, 0, (newNumWords - 1) * sizeof(void*)); 97 } else { 98 if (numBits > size()) { 99 size_t oldNumWords = outOfLineBits()->numWords(); 100 memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(), oldNumWords * sizeof(void*)); 101 memset(newOutOfLineBits->bits() + oldNumWords, 0, (newNumWords - oldNumWords) * sizeof(void*)); 102 } else 103 memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(), newOutOfLineBits->numWords() * sizeof(void*)); 104 OutOfLineBits::destroy(outOfLineBits()); 105 } 106 m_bitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits) >> 1; 107} 108 109void BitVector::mergeSlow(const BitVector& other) 110{ 111 if (other.isInline()) { 112 ASSERT(!isInline()); 113 *bits() |= cleanseInlineBits(other.m_bitsOrPointer); 114 return; 115 } 116 117 ensureSize(other.size()); 118 ASSERT(!isInline()); 119 ASSERT(!other.isInline()); 120 121 OutOfLineBits* a = outOfLineBits(); 122 const OutOfLineBits* b = other.outOfLineBits(); 123 for (unsigned i = a->numWords(); i--;) 124 a->bits()[i] |= b->bits()[i]; 125} 126 127void BitVector::filterSlow(const BitVector& other) 128{ 129 if (other.isInline()) { 130 ASSERT(!isInline()); 131 *bits() &= cleanseInlineBits(other.m_bitsOrPointer); 132 return; 133 } 134 135 if (isInline()) { 136 ASSERT(!other.isInline()); 137 m_bitsOrPointer &= *other.outOfLineBits()->bits(); 138 m_bitsOrPointer |= (static_cast<uintptr_t>(1) << maxInlineBits()); 139 ASSERT(isInline()); 140 return; 141 } 142 143 OutOfLineBits* a = outOfLineBits(); 144 const OutOfLineBits* b = other.outOfLineBits(); 145 for (unsigned i = std::min(a->numWords(), b->numWords()); i--;) 146 a->bits()[i] &= b->bits()[i]; 147 148 for (unsigned i = b->numWords(); i < a->numWords(); ++i) 149 a->bits()[i] = 0; 150} 151 152void BitVector::excludeSlow(const BitVector& other) 153{ 154 if (other.isInline()) { 155 ASSERT(!isInline()); 156 *bits() &= ~cleanseInlineBits(other.m_bitsOrPointer); 157 return; 158 } 159 160 if (isInline()) { 161 ASSERT(!other.isInline()); 162 m_bitsOrPointer &= ~*other.outOfLineBits()->bits(); 163 m_bitsOrPointer |= (static_cast<uintptr_t>(1) << maxInlineBits()); 164 ASSERT(isInline()); 165 return; 166 } 167 168 OutOfLineBits* a = outOfLineBits(); 169 const OutOfLineBits* b = other.outOfLineBits(); 170 for (unsigned i = std::min(a->numWords(), b->numWords()); i--;) 171 a->bits()[i] &= ~b->bits()[i]; 172} 173 174size_t BitVector::bitCountSlow() const 175{ 176 ASSERT(!isInline()); 177 const OutOfLineBits* bits = outOfLineBits(); 178 size_t result = 0; 179 for (unsigned i = bits->numWords(); i--;) 180 result += bitCount(bits->bits()[i]); 181 return result; 182} 183 184bool BitVector::equalsSlowCase(const BitVector& other) const 185{ 186 // This is really cheesy, but probably good enough for now. 187 for (unsigned i = std::max(size(), other.size()); i--;) { 188 if (get(i) != other.get(i)) 189 return false; 190 } 191 return true; 192} 193 194uintptr_t BitVector::hashSlowCase() const 195{ 196 ASSERT(!isInline()); 197 const OutOfLineBits* bits = outOfLineBits(); 198 uintptr_t result = 0; 199 for (unsigned i = bits->numWords(); i--;) 200 result ^= bits->bits()[i]; 201 return result; 202} 203 204void BitVector::dump(PrintStream& out) const 205{ 206 for (size_t i = 0; i < size(); ++i) { 207 if (get(i)) 208 out.printf("1"); 209 else 210 out.printf("-"); 211 } 212} 213 214} // namespace WTF 215