1// Copyright (c) 2017 Google Inc.
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 <vector>
16
17#include "gmock/gmock.h"
18
19#include "source/util/bit_vector.h"
20
21namespace spvtools {
22namespace utils {
23namespace {
24
25using BitVectorTest = ::testing::Test;
26
27TEST(BitVectorTest, Initialize) {
28  BitVector bvec;
29
30  // Checks that all values are 0.  Also tests checking a  bit past the end of
31  // the vector containing the bits.
32  for (int i = 1; i < 10000; i *= 2) {
33    EXPECT_FALSE(bvec.Get(i));
34  }
35}
36
37TEST(BitVectorTest, Set) {
38  BitVector bvec;
39
40  // Since 10,000 is larger than the initial size, this tests the resizing
41  // code.
42  for (int i = 3; i < 10000; i *= 2) {
43    bvec.Set(i);
44  }
45
46  // Check that bits that were not set are 0.
47  for (int i = 1; i < 10000; i *= 2) {
48    EXPECT_FALSE(bvec.Get(i));
49  }
50
51  // Check that bits that were set are 1.
52  for (int i = 3; i < 10000; i *= 2) {
53    EXPECT_TRUE(bvec.Get(i));
54  }
55}
56
57TEST(BitVectorTest, SetReturnValue) {
58  BitVector bvec;
59
60  // Make sure |Set| returns false when the bit was not set.
61  for (int i = 3; i < 10000; i *= 2) {
62    EXPECT_FALSE(bvec.Set(i));
63  }
64
65  // Make sure |Set| returns true when the bit was already set.
66  for (int i = 3; i < 10000; i *= 2) {
67    EXPECT_TRUE(bvec.Set(i));
68  }
69}
70
71TEST(BitVectorTest, Clear) {
72  BitVector bvec;
73  for (int i = 3; i < 10000; i *= 2) {
74    bvec.Set(i);
75  }
76
77  // Check that the bits were properly set.
78  for (int i = 3; i < 10000; i *= 2) {
79    EXPECT_TRUE(bvec.Get(i));
80  }
81
82  // Clear all of the bits except for bit 3.
83  for (int i = 6; i < 10000; i *= 2) {
84    bvec.Clear(i);
85  }
86
87  // Make sure bit 3 was not cleared.
88  EXPECT_TRUE(bvec.Get(3));
89
90  // Make sure all of the other bits that were set have been cleared.
91  for (int i = 6; i < 10000; i *= 2) {
92    EXPECT_FALSE(bvec.Get(i));
93  }
94}
95
96TEST(BitVectorTest, ClearReturnValue) {
97  BitVector bvec;
98  for (int i = 3; i < 10000; i *= 2) {
99    bvec.Set(i);
100  }
101
102  // Make sure |Clear| returns true if the bit was set.
103  for (int i = 3; i < 10000; i *= 2) {
104    EXPECT_TRUE(bvec.Clear(i));
105  }
106
107  // Make sure |Clear| returns false if the bit was not set.
108  for (int i = 3; i < 10000; i *= 2) {
109    EXPECT_FALSE(bvec.Clear(i));
110  }
111}
112
113TEST(BitVectorTest, SimpleOrTest) {
114  BitVector bvec1;
115  bvec1.Set(3);
116  bvec1.Set(4);
117
118  BitVector bvec2;
119  bvec2.Set(2);
120  bvec2.Set(4);
121
122  // Check that |bvec1| changed when doing the |Or| operation.
123  EXPECT_TRUE(bvec1.Or(bvec2));
124
125  // Check that the values are all correct.
126  EXPECT_FALSE(bvec1.Get(0));
127  EXPECT_FALSE(bvec1.Get(1));
128  EXPECT_TRUE(bvec1.Get(2));
129  EXPECT_TRUE(bvec1.Get(3));
130  EXPECT_TRUE(bvec1.Get(4));
131}
132
133TEST(BitVectorTest, ResizingOrTest) {
134  BitVector bvec1;
135  bvec1.Set(3);
136  bvec1.Set(4);
137
138  BitVector bvec2;
139  bvec2.Set(10000);
140
141  // Similar to above except with a large value to test resizing.
142  EXPECT_TRUE(bvec1.Or(bvec2));
143  EXPECT_FALSE(bvec1.Get(0));
144  EXPECT_FALSE(bvec1.Get(1));
145  EXPECT_FALSE(bvec1.Get(2));
146  EXPECT_TRUE(bvec1.Get(3));
147  EXPECT_TRUE(bvec1.Get(10000));
148}
149
150TEST(BitVectorTest, SubsetOrTest) {
151  BitVector bvec1;
152  bvec1.Set(3);
153  bvec1.Set(4);
154
155  BitVector bvec2;
156  bvec2.Set(3);
157
158  // |Or| returns false if |bvec1| does not change.
159  EXPECT_FALSE(bvec1.Or(bvec2));
160}
161
162}  // namespace
163}  // namespace utils
164}  // namespace spvtools
165