1// Copyright (c) 2018 Google LLC
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef SOURCE_UTIL_BIT_VECTOR_H_
16#define SOURCE_UTIL_BIT_VECTOR_H_
17
18#include <cstdint>
19#include <iosfwd>
20#include <vector>
21
22namespace spvtools {
23namespace utils {
24
25// Implements a bit vector class.
26//
27// All bits default to zero, and the upper bound is 2^32-1.
28class BitVector {
29 private:
30 using BitContainer = uint64_t;
31 enum { kBitContainerSize = 64 };
32 enum { kInitialNumBits = 1024 };
33
34 public:
35 // Creates a bit vector contianing 0s.
36 BitVector(uint32_t reserved_size = kInitialNumBits)
37 : bits_((reserved_size - 1) / kBitContainerSize + 1, 0) {}
38
39 // Sets the |i|th bit to 1. Returns the |i|th bit before it was set.
40 bool Set(uint32_t i) {
41 uint32_t element_index = i / kBitContainerSize;
42 uint32_t bit_in_element = i % kBitContainerSize;
43
44 if (element_index >= bits_.size()) {
45 bits_.resize(element_index + 1, 0);
46 }
47
48 BitContainer original = bits_[element_index];
49 BitContainer ith_bit = static_cast<BitContainer>(1) << bit_in_element;
50
51 if ((original & ith_bit) != 0) {
52 return true;
53 } else {
54 bits_[element_index] = original | ith_bit;
55 return false;
56 }
57 }
58
59 // Sets the |i|th bit to 0. Return the |i|th bit before it was cleared.
60 bool Clear(uint32_t i) {
61 uint32_t element_index = i / kBitContainerSize;
62 uint32_t bit_in_element = i % kBitContainerSize;
63
64 if (element_index >= bits_.size()) {
65 return false;
66 }
67
68 BitContainer original = bits_[element_index];
69 BitContainer ith_bit = static_cast<BitContainer>(1) << bit_in_element;
70
71 if ((original & ith_bit) == 0) {
72 return false;
73 } else {
74 bits_[element_index] = original & (~ith_bit);
75 return true;
76 }
77 }
78
79 // Returns the |i|th bit.
80 bool Get(uint32_t i) const {
81 uint32_t element_index = i / kBitContainerSize;
82 uint32_t bit_in_element = i % kBitContainerSize;
83
84 if (element_index >= bits_.size()) {
85 return false;
86 }
87
88 return (bits_[element_index] &
89 (static_cast<BitContainer>(1) << bit_in_element)) != 0;
90 }
91
92 // Returns true if every bit is 0.
93 bool Empty() const {
94 for (BitContainer b : bits_) {
95 if (b != 0) {
96 return false;
97 }
98 }
99 return true;
100 }
101
102 // Print a report on the densicy of the bit vector, number of 1 bits, number
103 // of bytes, and average bytes for 1 bit, to |out|.
104 void ReportDensity(std::ostream& out);
105
106 friend std::ostream& operator<<(std::ostream&, const BitVector&);
107
108 // Performs a bitwise-or operation on |this| and |that|, storing the result in
109 // |this|. Return true if |this| changed.
110 bool Or(const BitVector& that);
111
112 private:
113 std::vector<BitContainer> bits_;
114};
115
116} // namespace utils
117} // namespace spvtools
118
119#endif // SOURCE_UTIL_BIT_VECTOR_H_
120