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#include "source/util/bit_vector.h"
16
17#include <cassert>
18#include <iostream>
19
20namespace spvtools {
21namespace utils {
22
23void BitVector::ReportDensity(std::ostream& out) {
24 uint32_t count = 0;
25
26 for (BitContainer e : bits_) {
27 while (e != 0) {
28 if ((e & 1) != 0) {
29 ++count;
30 }
31 e = e >> 1;
32 }
33 }
34
35 out << "count=" << count
36 << ", total size (bytes)=" << bits_.size() * sizeof(BitContainer)
37 << ", bytes per element="
38 << (double)(bits_.size() * sizeof(BitContainer)) / (double)(count);
39}
40
41bool BitVector::Or(const BitVector& other) {
42 auto this_it = this->bits_.begin();
43 auto other_it = other.bits_.begin();
44 bool modified = false;
45
46 while (this_it != this->bits_.end() && other_it != other.bits_.end()) {
47 auto temp = *this_it | *other_it;
48 if (temp != *this_it) {
49 modified = true;
50 *this_it = temp;
51 }
52 ++this_it;
53 ++other_it;
54 }
55
56 if (other_it != other.bits_.end()) {
57 modified = true;
58 this->bits_.insert(this->bits_.end(), other_it, other.bits_.end());
59 }
60
61 return modified;
62}
63
64std::ostream& operator<<(std::ostream& out, const BitVector& bv) {
65 out << "{";
66 for (uint32_t i = 0; i < bv.bits_.size(); ++i) {
67 BitVector::BitContainer b = bv.bits_[i];
68 uint32_t j = 0;
69 while (b != 0) {
70 if (b & 1) {
71 out << ' ' << i * BitVector::kBitContainerSize + j;
72 }
73 ++j;
74 b = b >> 1;
75 }
76 }
77 out << "}";
78 return out;
79}
80
81} // namespace utils
82} // namespace spvtools
83