TestBitSet.cpp (9775B)
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */ 3 /* This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this file, 5 * You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #include "mozilla/Assertions.h" 8 #include "mozilla/Atomics.h" 9 #include "mozilla/BitSet.h" 10 11 using mozilla::Atomic; 12 using mozilla::BitSet; 13 14 template <typename Storage> 15 class BitSetSuite { 16 template <size_t N> 17 using TestBitSet = BitSet<N, Storage>; 18 19 using Word = typename TestBitSet<1>::Word; 20 21 static constexpr size_t kBitsPerWord = sizeof(Storage) * 8; 22 23 static constexpr Word kAllBitsSet = ~Word{0}; 24 25 public: 26 void testLength() { 27 MOZ_RELEASE_ASSERT(TestBitSet<1>().Storage().LengthBytes() == 28 sizeof(Storage)); 29 30 MOZ_RELEASE_ASSERT(TestBitSet<1>().Storage().Length() == 1); 31 MOZ_RELEASE_ASSERT(TestBitSet<kBitsPerWord>().Storage().Length() == 1); 32 MOZ_RELEASE_ASSERT(TestBitSet<kBitsPerWord + 1>().Storage().Length() == 2); 33 } 34 35 void testConstructAndAssign() { 36 MOZ_RELEASE_ASSERT(TestBitSet<1>().Storage()[0] == 0); 37 MOZ_RELEASE_ASSERT(TestBitSet<kBitsPerWord>().Storage()[0] == 0); 38 MOZ_RELEASE_ASSERT(TestBitSet<kBitsPerWord + 1>().Storage()[0] == 0); 39 MOZ_RELEASE_ASSERT(TestBitSet<kBitsPerWord + 1>().Storage()[1] == 0); 40 41 TestBitSet<1> bitset1; 42 bitset1.SetAll(); 43 TestBitSet<kBitsPerWord> bitsetW; 44 bitsetW.SetAll(); 45 TestBitSet<kBitsPerWord + 1> bitsetW1; 46 bitsetW1.SetAll(); 47 48 MOZ_RELEASE_ASSERT(bitset1.Storage()[0] == 1); 49 MOZ_RELEASE_ASSERT(bitsetW.Storage()[0] == kAllBitsSet); 50 MOZ_RELEASE_ASSERT(bitsetW1.Storage()[0] == kAllBitsSet); 51 MOZ_RELEASE_ASSERT(bitsetW1.Storage()[1] == 1); 52 53 MOZ_RELEASE_ASSERT(TestBitSet<1>(bitset1).Storage()[0] == 1); 54 MOZ_RELEASE_ASSERT(TestBitSet<kBitsPerWord>(bitsetW).Storage()[0] == 55 kAllBitsSet); 56 MOZ_RELEASE_ASSERT(TestBitSet<kBitsPerWord + 1>(bitsetW1).Storage()[0] == 57 kAllBitsSet); 58 MOZ_RELEASE_ASSERT(TestBitSet<kBitsPerWord + 1>(bitsetW1).Storage()[1] == 59 1); 60 61 MOZ_RELEASE_ASSERT(TestBitSet<1>(bitset1.Storage()).Storage()[0] == 1); 62 MOZ_RELEASE_ASSERT( 63 TestBitSet<kBitsPerWord>(bitsetW.Storage()).Storage()[0] == 64 kAllBitsSet); 65 MOZ_RELEASE_ASSERT( 66 TestBitSet<kBitsPerWord + 1>(bitsetW1.Storage()).Storage()[0] == 67 kAllBitsSet); 68 MOZ_RELEASE_ASSERT( 69 TestBitSet<kBitsPerWord + 1>(bitsetW1.Storage()).Storage()[1] == 1); 70 71 TestBitSet<1> bitset1Copy; 72 bitset1Copy = bitset1; 73 TestBitSet<kBitsPerWord> bitsetWCopy; 74 bitsetWCopy = bitsetW; 75 TestBitSet<kBitsPerWord + 1> bitsetW1Copy; 76 bitsetW1Copy = bitsetW1; 77 78 MOZ_RELEASE_ASSERT(bitset1Copy.Storage()[0] == 1); 79 MOZ_RELEASE_ASSERT(bitsetWCopy.Storage()[0] == kAllBitsSet); 80 MOZ_RELEASE_ASSERT(bitsetW1Copy.Storage()[0] == kAllBitsSet); 81 MOZ_RELEASE_ASSERT(bitsetW1Copy.Storage()[1] == 1); 82 } 83 84 void testSetBit() { 85 TestBitSet<kBitsPerWord + 2> bitset; 86 MOZ_RELEASE_ASSERT(!bitset.test(3)); 87 MOZ_RELEASE_ASSERT(!bitset[3]); 88 MOZ_RELEASE_ASSERT(!bitset.test(kBitsPerWord + 1)); 89 MOZ_RELEASE_ASSERT(!bitset[kBitsPerWord + 1]); 90 91 bitset[3] = true; 92 MOZ_RELEASE_ASSERT(bitset.test(3)); 93 MOZ_RELEASE_ASSERT(bitset[3]); 94 95 bitset[kBitsPerWord + 1] = true; 96 MOZ_RELEASE_ASSERT(bitset.test(3)); 97 MOZ_RELEASE_ASSERT(bitset[3]); 98 MOZ_RELEASE_ASSERT(bitset.test(kBitsPerWord + 1)); 99 MOZ_RELEASE_ASSERT(bitset[kBitsPerWord + 1]); 100 101 bitset.ResetAll(); 102 for (size_t i = 0; i < decltype(bitset)::size(); i++) { 103 MOZ_RELEASE_ASSERT(!bitset[i]); 104 } 105 106 bitset.SetAll(); 107 for (size_t i = 0; i < decltype(bitset)::size(); i++) { 108 MOZ_RELEASE_ASSERT(bitset[i]); 109 } 110 111 // Test trailing unused bits are not set by SetAll(). 112 MOZ_RELEASE_ASSERT(bitset.Storage()[1] == 3); 113 114 bitset.ResetAll(); 115 for (size_t i = 0; i < decltype(bitset)::size(); i++) { 116 MOZ_RELEASE_ASSERT(!bitset[i]); 117 } 118 } 119 120 void testFindBits() { 121 TestBitSet<kBitsPerWord * 5 + 2> bitset; 122 size_t size = bitset.size(); 123 MOZ_RELEASE_ASSERT(bitset.IsEmpty()); 124 MOZ_RELEASE_ASSERT(bitset.FindFirst() == SIZE_MAX); 125 MOZ_RELEASE_ASSERT(bitset.FindLast() == SIZE_MAX); 126 MOZ_RELEASE_ASSERT(bitset.FindNext(0) == SIZE_MAX); 127 MOZ_RELEASE_ASSERT(bitset.FindNext(size - 1) == SIZE_MAX); 128 MOZ_RELEASE_ASSERT(bitset.FindPrev(0) == SIZE_MAX); 129 MOZ_RELEASE_ASSERT(bitset.FindPrev(size - 1) == SIZE_MAX); 130 131 // Test with single bit set. 132 for (size_t i = 0; i < size; i += 5) { 133 bitset[i] = true; 134 MOZ_RELEASE_ASSERT(bitset.FindFirst() == i); 135 MOZ_RELEASE_ASSERT(bitset.FindLast() == i); 136 MOZ_RELEASE_ASSERT(bitset.FindNext(i) == i); 137 MOZ_RELEASE_ASSERT(bitset.FindPrev(i) == i); 138 MOZ_RELEASE_ASSERT(bitset.FindNext(0) == i); 139 MOZ_RELEASE_ASSERT(bitset.FindPrev(size - 1) == i); 140 if (i != 0) { 141 MOZ_RELEASE_ASSERT(bitset.FindNext(i - 1) == i); 142 MOZ_RELEASE_ASSERT(bitset.FindPrev(i - 1) == SIZE_MAX); 143 } 144 if (i != size - 1) { 145 MOZ_RELEASE_ASSERT(bitset.FindNext(i + 1) == SIZE_MAX); 146 MOZ_RELEASE_ASSERT(bitset.FindPrev(i + 1) == i); 147 } 148 bitset[i] = false; 149 } 150 151 // Test with multiple bits set. 152 // 153 // This creates bits pattern with every |i|th bit set and checks the result 154 // of calling FindNext/FindPrev at and around each set bit. 155 for (size_t i = 3; i < size; i += 5) { 156 bitset.ResetAll(); 157 for (size_t j = 0; j < size; j += i) { 158 bitset[j] = true; 159 } 160 for (size_t j = 0; j < size; j += i) { 161 // Test FindNext/FindPrev on the current bit. 162 MOZ_RELEASE_ASSERT(bitset[j]); 163 MOZ_RELEASE_ASSERT(bitset.FindNext(j) == j); 164 MOZ_RELEASE_ASSERT(bitset.FindPrev(j) == j); 165 // Test FindNext/FindPrev on the previous bit. 166 if (j != 0) { 167 MOZ_RELEASE_ASSERT(bitset[j - i]); 168 MOZ_RELEASE_ASSERT(bitset.FindNext(j - 1) == j); 169 MOZ_RELEASE_ASSERT(bitset.FindPrev(j - 1) == j - i); 170 } 171 // Test FindNext/FindPrev on the next bit. 172 if (j + i < size) { 173 MOZ_RELEASE_ASSERT(bitset[j + i]); 174 MOZ_RELEASE_ASSERT(bitset.FindNext(j + 1) == j + i); 175 MOZ_RELEASE_ASSERT(bitset.FindPrev(j + 1) == j); 176 } 177 } 178 } 179 } 180 181 void testCount() { 182 testCountForSize<1>(); 183 testCountForSize<kBitsPerWord>(); 184 testCountForSize<kBitsPerWord + 1>(); 185 } 186 187 template <size_t N> 188 void testCountForSize() { 189 TestBitSet<N> bits; 190 MOZ_RELEASE_ASSERT(bits.Count() == 0); 191 bits.SetAll(); 192 MOZ_RELEASE_ASSERT(bits.Count() == N); 193 bits.ResetAll(); 194 bits[0] = true; 195 MOZ_RELEASE_ASSERT(bits.Count() == 1); 196 bits[0] = false; 197 bits[N - 1] = true; 198 MOZ_RELEASE_ASSERT(bits.Count() == 1); 199 } 200 201 void testComparison() { 202 testComparisonForSize<1>(); 203 testComparisonForSize<kBitsPerWord>(); 204 testComparisonForSize<kBitsPerWord + 1>(); 205 } 206 207 template <size_t N> 208 void testComparisonForSize() { 209 TestBitSet<N> a; 210 TestBitSet<N> b; 211 MOZ_RELEASE_ASSERT(a == b); 212 MOZ_RELEASE_ASSERT(!(a != b)); 213 a[0] = true; 214 MOZ_RELEASE_ASSERT(a != b); 215 MOZ_RELEASE_ASSERT(!(a == b)); 216 b[0] = true; 217 MOZ_RELEASE_ASSERT(a == b); 218 MOZ_RELEASE_ASSERT(!(a != b)); 219 a.SetAll(); 220 b.SetAll(); 221 MOZ_RELEASE_ASSERT(a == b); 222 MOZ_RELEASE_ASSERT(!(a != b)); 223 a[N - 1] = false; 224 MOZ_RELEASE_ASSERT(a != b); 225 MOZ_RELEASE_ASSERT(!(a == b)); 226 b[N - 1] = false; 227 MOZ_RELEASE_ASSERT(a == b); 228 MOZ_RELEASE_ASSERT(!(a != b)); 229 } 230 231 void testLogical() { 232 testLogicalForSize<2>(); 233 testLogicalForSize<kBitsPerWord>(); 234 testLogicalForSize<kBitsPerWord + 1>(); 235 } 236 237 template <size_t N> 238 void testLogicalForSize() { 239 TestBitSet<N> none; 240 TestBitSet<N> all; 241 all.SetAll(); 242 TestBitSet<N> some; 243 for (size_t i = 0; i < N; i += 2) { 244 some[i] = true; 245 } 246 247 // operator& is implemented in terms of operator&= (and likewise for 248 // operator|) so this tests both. 249 250 MOZ_RELEASE_ASSERT(none.Count() == 0); 251 MOZ_RELEASE_ASSERT(all.Count() == N); 252 MOZ_RELEASE_ASSERT(some.Count() == (N + 1) / 2); 253 254 MOZ_RELEASE_ASSERT((none & none) == none); 255 MOZ_RELEASE_ASSERT((none & all) == none); 256 MOZ_RELEASE_ASSERT((none & some) == none); 257 258 MOZ_RELEASE_ASSERT((all & none) == none); 259 MOZ_RELEASE_ASSERT((all & all) == all); 260 MOZ_RELEASE_ASSERT((all & some) == some); 261 262 MOZ_RELEASE_ASSERT((some & none) == none); 263 MOZ_RELEASE_ASSERT((some & all) == some); 264 MOZ_RELEASE_ASSERT((some & some) == some); 265 266 MOZ_RELEASE_ASSERT((none | none) == none); 267 MOZ_RELEASE_ASSERT((none | all) == all); 268 MOZ_RELEASE_ASSERT((none | some) == some); 269 270 MOZ_RELEASE_ASSERT((all | none) == all); 271 MOZ_RELEASE_ASSERT((all | all) == all); 272 MOZ_RELEASE_ASSERT((all | some) == all); 273 274 MOZ_RELEASE_ASSERT((some | none) == some); 275 MOZ_RELEASE_ASSERT((some | all) == all); 276 MOZ_RELEASE_ASSERT((some | some) == some); 277 278 MOZ_RELEASE_ASSERT(~none == all); 279 MOZ_RELEASE_ASSERT(~all == none); 280 MOZ_RELEASE_ASSERT(~some != some); 281 MOZ_RELEASE_ASSERT(~some != all); 282 MOZ_RELEASE_ASSERT(~some != none); 283 } 284 285 void runTests() { 286 testLength(); 287 testConstructAndAssign(); 288 testSetBit(); 289 testFindBits(); 290 testCount(); 291 testComparison(); 292 testLogical(); 293 } 294 }; 295 296 int main() { 297 BitSetSuite<uint8_t>().runTests(); 298 BitSetSuite<uint32_t>().runTests(); 299 BitSetSuite<uint64_t>().runTests(); 300 BitSetSuite<Atomic<uint32_t>>().runTests(); 301 BitSetSuite<Atomic<uint64_t>>().runTests(); 302 303 return 0; 304 }