123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120 |
- // 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_
|