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 22 namespace spvtools { 23 namespace utils { 24 25 // Implements a bit vector class. 26 // 27 // All bits default to zero, and the upper bound is 2^32-1. 28 class BitVector { 29 private: 30 using BitContainer = uint64_t; 31 enum { kBitContainerSize = 64 }; 32 enum { kInitialNumBits = 1024 }; 33 34 public: 35 // Creates a bit vector containing 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. Set(uint32_t i)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. Clear(uint32_t i)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. Get(uint32_t i)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. Empty()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