1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
/*
* Copyright (C) 2011 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "wtf/BitVector.h"
#include "wtf/LeakAnnotations.h"
#include "wtf/PrintStream.h"
#include "wtf/allocator/Partitions.h"
#include <algorithm>
#include <string.h>
namespace WTF {
void BitVector::setSlow(const BitVector& other) {
uintptr_t newBitsOrPointer;
if (other.isInline()) {
newBitsOrPointer = other.m_bitsOrPointer;
} else {
OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(other.size());
memcpy(newOutOfLineBits->bits(), other.bits(), byteCount(other.size()));
newBitsOrPointer = bitwiseCast<uintptr_t>(newOutOfLineBits) >> 1;
}
if (!isInline())
OutOfLineBits::destroy(outOfLineBits());
m_bitsOrPointer = newBitsOrPointer;
}
void BitVector::resize(size_t numBits) {
if (numBits <= maxInlineBits()) {
if (isInline())
return;
OutOfLineBits* myOutOfLineBits = outOfLineBits();
m_bitsOrPointer = makeInlineBits(*myOutOfLineBits->bits());
OutOfLineBits::destroy(myOutOfLineBits);
return;
}
resizeOutOfLine(numBits);
}
void BitVector::clearAll() {
if (isInline())
m_bitsOrPointer = makeInlineBits(0);
else
memset(outOfLineBits()->bits(), 0, byteCount(size()));
}
BitVector::OutOfLineBits* BitVector::OutOfLineBits::create(size_t numBits) {
// Because of the way BitVector stores the pointer, memory tools
// will erroneously report a leak here.
WTF_INTERNAL_LEAK_SANITIZER_DISABLED_SCOPE;
numBits = (numBits + bitsInPointer() - 1) &
~(bitsInPointer() - static_cast<size_t>(1));
size_t size =
sizeof(OutOfLineBits) + sizeof(uintptr_t) * (numBits / bitsInPointer());
void* allocation = Partitions::bufferMalloc(
size, WTF_HEAP_PROFILER_TYPE_NAME(OutOfLineBits));
OutOfLineBits* result = new (NotNull, allocation) OutOfLineBits(numBits);
return result;
}
void BitVector::OutOfLineBits::destroy(OutOfLineBits* outOfLineBits) {
Partitions::bufferFree(outOfLineBits);
}
void BitVector::resizeOutOfLine(size_t numBits) {
DCHECK_GT(numBits, maxInlineBits());
OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(numBits);
size_t newNumWords = newOutOfLineBits->numWords();
if (isInline()) {
// Make sure that all of the bits are zero in case we do a no-op resize.
*newOutOfLineBits->bits() =
m_bitsOrPointer & ~(static_cast<uintptr_t>(1) << maxInlineBits());
memset(newOutOfLineBits->bits() + 1, 0, (newNumWords - 1) * sizeof(void*));
} else {
if (numBits > size()) {
size_t oldNumWords = outOfLineBits()->numWords();
memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(),
oldNumWords * sizeof(void*));
memset(newOutOfLineBits->bits() + oldNumWords, 0,
(newNumWords - oldNumWords) * sizeof(void*));
} else {
memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(),
newOutOfLineBits->numWords() * sizeof(void*));
}
OutOfLineBits::destroy(outOfLineBits());
}
m_bitsOrPointer = bitwiseCast<uintptr_t>(newOutOfLineBits) >> 1;
}
void BitVector::dump(PrintStream& out) {
for (size_t i = 0; i < size(); ++i) {
if (get(i))
out.printf("1");
else
out.printf("-");
}
}
} // namespace WTF
|
