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
36 namespace WTF {
37
setSlow(const BitVector & other)38 void 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
resize(size_t numBits)53 void 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
clearAll()68 void BitVector::clearAll()
69 {
70 if (isInline())
71 m_bitsOrPointer = makeInlineBits(0);
72 else
73 memset(outOfLineBits()->bits(), 0, byteCount(size()));
74 }
75
create(size_t numBits)76 BitVector::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
destroy(OutOfLineBits * outOfLineBits)88 void BitVector::OutOfLineBits::destroy(OutOfLineBits* outOfLineBits)
89 {
90 partitionFreeGeneric(Partitions::getBufferPartition(), outOfLineBits);
91 }
92
resizeOutOfLine(size_t numBits)93 void 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
dump(PrintStream & out)114 void 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