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