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 "wtf/LeakAnnotations.h"
30#include "wtf/PartitionAlloc.h"
31#include "wtf/PrintStream.h"
32#include "wtf/WTF.h"
33#include <algorithm>
34#include <string.h>
35
36namespace WTF {
37
38void BitVector::setSlow(const BitVector& other)
39{
40    uintptr_t newBitsOrPointer;
41    if (other.isInline())
42        newBitsOrPointer = other.m_bitsOrPointer;
43    else {
44        OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(other.size());
45        memcpy(newOutOfLineBits->bits(), other.bits(), byteCount(other.size()));
46        newBitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits) >> 1;
47    }
48    if (!isInline())
49        OutOfLineBits::destroy(outOfLineBits());
50    m_bitsOrPointer = newBitsOrPointer;
51}
52
53void BitVector::resize(size_t numBits)
54{
55    if (numBits <= maxInlineBits()) {
56        if (isInline())
57            return;
58
59        OutOfLineBits* myOutOfLineBits = outOfLineBits();
60        m_bitsOrPointer = makeInlineBits(*myOutOfLineBits->bits());
61        OutOfLineBits::destroy(myOutOfLineBits);
62        return;
63    }
64
65    resizeOutOfLine(numBits);
66}
67
68void BitVector::clearAll()
69{
70    if (isInline())
71        m_bitsOrPointer = makeInlineBits(0);
72    else
73        memset(outOfLineBits()->bits(), 0, byteCount(size()));
74}
75
76BitVector::OutOfLineBits* BitVector::OutOfLineBits::create(size_t numBits)
77{
78    // Because of the way BitVector stores the pointer, memory tools
79    // will erroneously report a leak here.
80    WTF_ANNOTATE_SCOPED_MEMORY_LEAK;
81    numBits = (numBits + bitsInPointer() - 1) & ~(bitsInPointer() - 1);
82    size_t size = sizeof(OutOfLineBits) + sizeof(uintptr_t) * (numBits / bitsInPointer());
83    void* allocation = partitionAllocGeneric(Partitions::getBufferPartition(), size);
84    OutOfLineBits* result = new (NotNull, allocation) OutOfLineBits(numBits);
85    return result;
86}
87
88void BitVector::OutOfLineBits::destroy(OutOfLineBits* outOfLineBits)
89{
90    partitionFreeGeneric(Partitions::getBufferPartition(), outOfLineBits);
91}
92
93void BitVector::resizeOutOfLine(size_t numBits)
94{
95    ASSERT(numBits > maxInlineBits());
96    OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(numBits);
97    size_t newNumWords = newOutOfLineBits->numWords();
98    if (isInline()) {
99        // Make sure that all of the bits are zero in case we do a no-op resize.
100        *newOutOfLineBits->bits() = m_bitsOrPointer & ~(static_cast<uintptr_t>(1) << maxInlineBits());
101        memset(newOutOfLineBits->bits() + 1, 0, (newNumWords - 1) * sizeof(void*));
102    } else {
103        if (numBits > size()) {
104            size_t oldNumWords = outOfLineBits()->numWords();
105            memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(), oldNumWords * sizeof(void*));
106            memset(newOutOfLineBits->bits() + oldNumWords, 0, (newNumWords - oldNumWords) * sizeof(void*));
107        } else
108            memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(), newOutOfLineBits->numWords() * sizeof(void*));
109        OutOfLineBits::destroy(outOfLineBits());
110    }
111    m_bitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits) >> 1;
112}
113
114void BitVector::dump(PrintStream& out)
115{
116    for (size_t i = 0; i < size(); ++i) {
117        if (get(i))
118            out.printf("1");
119        else
120            out.printf("-");
121    }
122}
123
124} // namespace WTF
125