1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #define LOG_TAG "BitSet_test" 18 19 #include <utils/BitSet.h> 20 #include <cutils/log.h> 21 #include <gtest/gtest.h> 22 #include <unistd.h> 23 24 namespace android { 25 26 class BitSet32Test : public testing::Test { 27 protected: 28 BitSet32 b1; 29 BitSet32 b2; 30 virtual void TearDown() { 31 b1.clear(); 32 b2.clear(); 33 } 34 }; 35 36 37 TEST_F(BitSet32Test, BitWiseOr) { 38 b1.markBit(2); 39 b2.markBit(4); 40 41 BitSet32 tmp = b1 | b2; 42 EXPECT_EQ(tmp.count(), 2u); 43 EXPECT_TRUE(tmp.hasBit(2) && tmp.hasBit(4)); 44 // Check that the operator is symmetric 45 EXPECT_TRUE((b2 | b1) == (b1 | b2)); 46 47 b1 |= b2; 48 EXPECT_EQ(b1.count(), 2u); 49 EXPECT_TRUE(b1.hasBit(2) && b1.hasBit(4)); 50 EXPECT_TRUE(b2.hasBit(4) && b2.count() == 1u); 51 } 52 TEST_F(BitSet32Test, BitWiseAnd_Disjoint) { 53 b1.markBit(2); 54 b1.markBit(4); 55 b1.markBit(6); 56 57 BitSet32 tmp = b1 & b2; 58 EXPECT_TRUE(tmp.isEmpty()); 59 // Check that the operator is symmetric 60 EXPECT_TRUE((b2 & b1) == (b1 & b2)); 61 62 b2 &= b1; 63 EXPECT_TRUE(b2.isEmpty()); 64 EXPECT_EQ(b1.count(), 3u); 65 EXPECT_TRUE(b1.hasBit(2) && b1.hasBit(4) && b1.hasBit(6)); 66 } 67 68 TEST_F(BitSet32Test, BitWiseAnd_NonDisjoint) { 69 b1.markBit(2); 70 b1.markBit(4); 71 b1.markBit(6); 72 b2.markBit(3); 73 b2.markBit(6); 74 b2.markBit(9); 75 76 BitSet32 tmp = b1 & b2; 77 EXPECT_EQ(tmp.count(), 1u); 78 EXPECT_TRUE(tmp.hasBit(6)); 79 // Check that the operator is symmetric 80 EXPECT_TRUE((b2 & b1) == (b1 & b2)); 81 82 b1 &= b2; 83 EXPECT_EQ(b1.count(), 1u); 84 EXPECT_EQ(b2.count(), 3u); 85 EXPECT_TRUE(b2.hasBit(3) && b2.hasBit(6) && b2.hasBit(9)); 86 } 87 88 TEST_F(BitSet32Test, MarkFirstUnmarkedBit) { 89 b1.markBit(1); 90 91 b1.markFirstUnmarkedBit(); 92 EXPECT_EQ(b1.count(), 2u); 93 EXPECT_TRUE(b1.hasBit(0) && b1.hasBit(1)); 94 95 b1.markFirstUnmarkedBit(); 96 EXPECT_EQ(b1.count(), 3u); 97 EXPECT_TRUE(b1.hasBit(0) && b1.hasBit(1) && b1.hasBit(2)); 98 } 99 100 TEST_F(BitSet32Test, ClearFirstMarkedBit) { 101 b1.markBit(0); 102 b1.markBit(10); 103 104 b1.clearFirstMarkedBit(); 105 EXPECT_EQ(b1.count(), 1u); 106 EXPECT_TRUE(b1.hasBit(10)); 107 108 b1.markBit(30); 109 b1.clearFirstMarkedBit(); 110 EXPECT_EQ(b1.count(), 1u); 111 EXPECT_TRUE(b1.hasBit(30)); 112 } 113 114 TEST_F(BitSet32Test, ClearLastMarkedBit) { 115 b1.markBit(10); 116 b1.markBit(31); 117 118 b1.clearLastMarkedBit(); 119 EXPECT_EQ(b1.count(), 1u); 120 EXPECT_TRUE(b1.hasBit(10)); 121 122 b1.markBit(5); 123 b1.clearLastMarkedBit(); 124 EXPECT_EQ(b1.count(), 1u); 125 EXPECT_TRUE(b1.hasBit(5)); 126 } 127 128 TEST_F(BitSet32Test, FillAndClear) { 129 EXPECT_TRUE(b1.isEmpty()); 130 for (size_t i = 0; i < 32; i++) { 131 b1.markFirstUnmarkedBit(); 132 } 133 EXPECT_TRUE(b1.isFull()); 134 b1.clear(); 135 EXPECT_TRUE(b1.isEmpty()); 136 } 137 138 TEST_F(BitSet32Test, GetIndexOfBit) { 139 b1.markBit(1); 140 b1.markBit(4); 141 EXPECT_EQ(b1.getIndexOfBit(1), 0); 142 EXPECT_EQ(b1.getIndexOfBit(4), 1); 143 b1.markFirstUnmarkedBit(); 144 EXPECT_EQ(b1.getIndexOfBit(1), 1); 145 EXPECT_EQ(b1.getIndexOfBit(4), 2); 146 } 147 148 class BitSet64Test : public testing::Test { 149 protected: 150 BitSet64 b1; 151 BitSet64 b2; 152 virtual void TearDown() { 153 b1.clear(); 154 b2.clear(); 155 } 156 }; 157 158 159 TEST_F(BitSet64Test, BitWiseOr) { 160 b1.markBit(20); 161 b2.markBit(40); 162 163 BitSet64 tmp = b1 | b2; 164 EXPECT_EQ(tmp.count(), 2u); 165 EXPECT_TRUE(tmp.hasBit(20) && tmp.hasBit(40)); 166 // Check that the operator is symmetric 167 EXPECT_TRUE((b2 | b1) == (b1 | b2)); 168 169 b1 |= b2; 170 EXPECT_EQ(b1.count(), 2u); 171 EXPECT_TRUE(b1.hasBit(20) && b1.hasBit(40)); 172 EXPECT_TRUE(b2.hasBit(40) && b2.count() == 1u); 173 } 174 TEST_F(BitSet64Test, BitWiseAnd_Disjoint) { 175 b1.markBit(20); 176 b1.markBit(40); 177 b1.markBit(60); 178 179 BitSet64 tmp = b1 & b2; 180 EXPECT_TRUE(tmp.isEmpty()); 181 // Check that the operator is symmetric 182 EXPECT_TRUE((b2 & b1) == (b1 & b2)); 183 184 b2 &= b1; 185 EXPECT_TRUE(b2.isEmpty()); 186 EXPECT_EQ(b1.count(), 3u); 187 EXPECT_TRUE(b1.hasBit(20) && b1.hasBit(40) && b1.hasBit(60)); 188 } 189 190 TEST_F(BitSet64Test, BitWiseAnd_NonDisjoint) { 191 b1.markBit(20); 192 b1.markBit(40); 193 b1.markBit(60); 194 b2.markBit(30); 195 b2.markBit(60); 196 b2.markBit(63); 197 198 BitSet64 tmp = b1 & b2; 199 EXPECT_EQ(tmp.count(), 1u); 200 EXPECT_TRUE(tmp.hasBit(60)); 201 // Check that the operator is symmetric 202 EXPECT_TRUE((b2 & b1) == (b1 & b2)); 203 204 b1 &= b2; 205 EXPECT_EQ(b1.count(), 1u); 206 EXPECT_EQ(b2.count(), 3u); 207 EXPECT_TRUE(b2.hasBit(30) && b2.hasBit(60) && b2.hasBit(63)); 208 } 209 210 TEST_F(BitSet64Test, MarkFirstUnmarkedBit) { 211 b1.markBit(1); 212 213 b1.markFirstUnmarkedBit(); 214 EXPECT_EQ(b1.count(), 2u); 215 EXPECT_TRUE(b1.hasBit(0) && b1.hasBit(1)); 216 217 b1.markFirstUnmarkedBit(); 218 EXPECT_EQ(b1.count(), 3u); 219 EXPECT_TRUE(b1.hasBit(0) && b1.hasBit(1) && b1.hasBit(2)); 220 } 221 222 TEST_F(BitSet64Test, ClearFirstMarkedBit) { 223 b1.markBit(0); 224 b1.markBit(10); 225 226 b1.clearFirstMarkedBit(); 227 EXPECT_EQ(b1.count(), 1u); 228 EXPECT_TRUE(b1.hasBit(10)); 229 230 b1.markBit(50); 231 b1.clearFirstMarkedBit(); 232 EXPECT_EQ(b1.count(), 1u); 233 EXPECT_TRUE(b1.hasBit(50)); 234 } 235 236 TEST_F(BitSet64Test, ClearLastMarkedBit) { 237 b1.markBit(10); 238 b1.markBit(63); 239 240 b1.clearLastMarkedBit(); 241 EXPECT_EQ(b1.count(), 1u); 242 EXPECT_TRUE(b1.hasBit(10)); 243 244 b1.markBit(5); 245 b1.clearLastMarkedBit(); 246 EXPECT_EQ(b1.count(), 1u); 247 EXPECT_TRUE(b1.hasBit(5)); 248 } 249 250 TEST_F(BitSet64Test, FillAndClear) { 251 EXPECT_TRUE(b1.isEmpty()); 252 for (size_t i = 0; i < 64; i++) { 253 b1.markFirstUnmarkedBit(); 254 } 255 EXPECT_TRUE(b1.isFull()); 256 b1.clear(); 257 EXPECT_TRUE(b1.isEmpty()); 258 } 259 260 TEST_F(BitSet64Test, GetIndexOfBit) { 261 b1.markBit(10); 262 b1.markBit(40); 263 EXPECT_EQ(b1.getIndexOfBit(10), 0); 264 EXPECT_EQ(b1.getIndexOfBit(40), 1); 265 b1.markFirstUnmarkedBit(); 266 EXPECT_EQ(b1.getIndexOfBit(10), 1); 267 EXPECT_EQ(b1.getIndexOfBit(40), 2); 268 } 269 270 } // namespace android 271