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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
/*
* Copyright (C) 2011 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "bit_vector.h"
namespace art {
// TODO: profile to make sure this is still a win relative to just using shifted masks.
static uint32_t check_masks[32] = {
0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010,
0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200,
0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000,
0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000,
0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
0x40000000, 0x80000000 };
static inline uint32_t BitsToWords(uint32_t bits) {
return (bits + 31) >> 5;
}
// TODO: replace excessive argument defaulting when we are at gcc 4.7
// or later on host with delegating constructor support. Specifically,
// starts_bits and storage_size/storage are mutually exclusive.
BitVector::BitVector(uint32_t start_bits,
bool expandable,
Allocator* allocator,
uint32_t storage_size,
uint32_t* storage)
: allocator_(allocator),
expandable_(expandable),
storage_size_(storage_size),
storage_(storage) {
DCHECK_EQ(sizeof(storage_[0]), 4U); // Assuming 32-bit units.
if (storage_ == NULL) {
storage_size_ = BitsToWords(start_bits);
storage_ = static_cast<uint32_t*>(allocator_->Alloc(storage_size_ * sizeof(uint32_t)));
}
}
BitVector::~BitVector() {
allocator_->Free(storage_);
}
/*
* Determine whether or not the specified bit is set.
*/
bool BitVector::IsBitSet(uint32_t num) const {
DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
uint32_t val = storage_[num >> 5] & check_masks[num & 0x1f];
return (val != 0);
}
// Mark all bits bit as "clear".
void BitVector::ClearAllBits() {
memset(storage_, 0, storage_size_ * sizeof(uint32_t));
}
// Mark the specified bit as "set".
/*
* TUNING: this could have pathologically bad growth/expand behavior. Make sure we're
* not using it badly or change resize mechanism.
*/
void BitVector::SetBit(uint32_t num) {
if (num >= storage_size_ * sizeof(uint32_t) * 8) {
DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << num;
/* Round up to word boundaries for "num+1" bits */
uint32_t new_size = BitsToWords(num + 1);
DCHECK_GT(new_size, storage_size_);
uint32_t *new_storage =
static_cast<uint32_t*>(allocator_->Alloc(new_size * sizeof(uint32_t)));
memcpy(new_storage, storage_, storage_size_ * sizeof(uint32_t));
// Zero out the new storage words.
memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * sizeof(uint32_t));
// TOTO: collect stats on space wasted because of resize.
storage_ = new_storage;
storage_size_ = new_size;
}
storage_[num >> 5] |= check_masks[num & 0x1f];
}
// Mark the specified bit as "unset".
void BitVector::ClearBit(uint32_t num) {
DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
storage_[num >> 5] &= ~check_masks[num & 0x1f];
}
// Intersect with another bit vector. Sizes and expandability must be the same.
void BitVector::Intersect(const BitVector* src) {
DCHECK_EQ(storage_size_, src->GetStorageSize());
DCHECK_EQ(expandable_, src->IsExpandable());
for (uint32_t idx = 0; idx < storage_size_; idx++) {
storage_[idx] &= src->GetRawStorageWord(idx);
}
}
/*
* Union with another bit vector. Sizes and expandability must be the same.
*/
void BitVector::Union(const BitVector* src) {
DCHECK_EQ(storage_size_, src->GetStorageSize());
DCHECK_EQ(expandable_, src->IsExpandable());
for (uint32_t idx = 0; idx < storage_size_; idx++) {
storage_[idx] |= src->GetRawStorageWord(idx);
}
}
// Count the number of bits that are set.
uint32_t BitVector::NumSetBits() const {
uint32_t count = 0;
for (uint32_t word = 0; word < storage_size_; word++) {
count += __builtin_popcount(storage_[word]);
}
return count;
}
// Count the number of bits that are set up through and including num.
uint32_t BitVector::NumSetBits(uint32_t num) const {
DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
uint32_t last_word = num >> 5;
uint32_t partial_word_bits = num & 0x1f;
// partial_word_bits | # | | | partial_word_mask
// 00000 | 0 | 0xffffffff >> (31 - 0) | (1 << (0 + 1)) - 1 | 0x00000001
// 00001 | 1 | 0xffffffff >> (31 - 1) | (1 << (1 + 1)) - 1 | 0x00000003
// 00010 | 2 | 0xffffffff >> (31 - 2) | (1 << (2 + 1)) - 1 | 0x00000007
// ..... |
// 11110 | 30 | 0xffffffff >> (31 - 30) | (1 << (30 + 1)) - 1 | 0x7fffffff
// 11111 | 31 | 0xffffffff >> (31 - 31) | last_full_word++ | 0xffffffff
uint32_t partial_word_mask = 0xffffffff >> (0x1f - partial_word_bits);
uint32_t count = 0;
for (uint32_t word = 0; word < last_word; word++) {
count += __builtin_popcount(storage_[word]);
}
count += __builtin_popcount(storage_[last_word] & partial_word_mask);
return count;
}
BitVector::Iterator* BitVector::GetIterator() const {
return new (allocator_) Iterator(this);
}
/*
* Mark specified number of bits as "set". Cannot set all bits like ClearAll
* since there might be unused bits - setting those to one will confuse the
* iterator.
*/
void BitVector::SetInitialBits(uint32_t num_bits) {
DCHECK_LE(BitsToWords(num_bits), storage_size_);
uint32_t idx;
for (idx = 0; idx < (num_bits >> 5); idx++) {
storage_[idx] = -1;
}
uint32_t rem_num_bits = num_bits & 0x1f;
if (rem_num_bits) {
storage_[idx] = (1 << rem_num_bits) - 1;
}
}
} // namespace art
|
