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
|
// Copyright (c) 2018 Google LLC
//
// 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.
#ifndef SOURCE_UTIL_BIT_VECTOR_H_
#define SOURCE_UTIL_BIT_VECTOR_H_
#include <cstdint>
#include <iosfwd>
#include <vector>
namespace spvtools {
namespace utils {
// Implements a bit vector class.
//
// All bits default to zero, and the upper bound is 2^32-1.
class BitVector {
private:
using BitContainer = uint64_t;
enum { kBitContainerSize = 64 };
enum { kInitialNumBits = 1024 };
public:
// Creates a bit vector contianing 0s.
BitVector(uint32_t reserved_size = kInitialNumBits)
: bits_((reserved_size - 1) / kBitContainerSize + 1, 0) {}
// Sets the |i|th bit to 1. Returns the |i|th bit before it was set.
bool Set(uint32_t i) {
uint32_t element_index = i / kBitContainerSize;
uint32_t bit_in_element = i % kBitContainerSize;
if (element_index >= bits_.size()) {
bits_.resize(element_index + 1, 0);
}
BitContainer original = bits_[element_index];
BitContainer ith_bit = static_cast<BitContainer>(1) << bit_in_element;
if ((original & ith_bit) != 0) {
return true;
} else {
bits_[element_index] = original | ith_bit;
return false;
}
}
// Sets the |i|th bit to 0. Return the |i|th bit before it was cleared.
bool Clear(uint32_t i) {
uint32_t element_index = i / kBitContainerSize;
uint32_t bit_in_element = i % kBitContainerSize;
if (element_index >= bits_.size()) {
return false;
}
BitContainer original = bits_[element_index];
BitContainer ith_bit = static_cast<BitContainer>(1) << bit_in_element;
if ((original & ith_bit) == 0) {
return false;
} else {
bits_[element_index] = original & (~ith_bit);
return true;
}
}
// Returns the |i|th bit.
bool Get(uint32_t i) const {
uint32_t element_index = i / kBitContainerSize;
uint32_t bit_in_element = i % kBitContainerSize;
if (element_index >= bits_.size()) {
return false;
}
return (bits_[element_index] &
(static_cast<BitContainer>(1) << bit_in_element)) != 0;
}
// Returns true if every bit is 0.
bool Empty() const {
for (BitContainer b : bits_) {
if (b != 0) {
return false;
}
}
return true;
}
// Print a report on the densicy of the bit vector, number of 1 bits, number
// of bytes, and average bytes for 1 bit, to |out|.
void ReportDensity(std::ostream& out);
friend std::ostream& operator<<(std::ostream&, const BitVector&);
// Performs a bitwise-or operation on |this| and |that|, storing the result in
// |this|. Return true if |this| changed.
bool Or(const BitVector& that);
private:
std::vector<BitContainer> bits_;
};
} // namespace utils
} // namespace spvtools
#endif // SOURCE_UTIL_BIT_VECTOR_H_
|
