1 /*
2 * Copyright 2011 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "src/base/SkRandom.h"
9 #include "src/utils/SkBitSet.h"
10 #include "tests/Test.h"
11
12 #include <vector>
13
DEF_TEST(BitSet,reporter)14 DEF_TEST(BitSet, reporter) {
15 SkBitSet set0(65536);
16 REPORTER_ASSERT(reporter, set0.size() == 65536);
17 REPORTER_ASSERT(reporter, set0.test(0) == false);
18 REPORTER_ASSERT(reporter, set0.test(32767) == false);
19 REPORTER_ASSERT(reporter, set0.test(65535) == false);
20 REPORTER_ASSERT(reporter, !set0.findFirst());
21
22 set0.set(22);
23 REPORTER_ASSERT(reporter, set0.test(22) == true);
24 REPORTER_ASSERT(reporter, set0.findFirst());
25 REPORTER_ASSERT(reporter, *set0.findFirst() == 22);
26 set0.set(24);
27 REPORTER_ASSERT(reporter, set0.test(24) == true);
28 REPORTER_ASSERT(reporter, *set0.findFirst() == 22);
29 set0.set(35); // on a different DWORD
30 REPORTER_ASSERT(reporter, set0.test(35) == true);
31 REPORTER_ASSERT(reporter, *set0.findFirst() == 22);
32 REPORTER_ASSERT(reporter, set0.test(24) == true);
33 REPORTER_ASSERT(reporter, set0.test(35) == true);
34 set0.set(21);
35 REPORTER_ASSERT(reporter, set0.test(21) == true);
36 REPORTER_ASSERT(reporter, *set0.findFirst() == 21);
37 set0.reset(21);
38 REPORTER_ASSERT(reporter, set0.test(21) == false);
39 REPORTER_ASSERT(reporter, *set0.findFirst() == 22);
40
41 std::vector<unsigned int> data;
42 set0.forEachSetIndex([&data](unsigned v) { data.push_back(v); });
43
44 REPORTER_ASSERT(reporter, data.size() == 3);
45 REPORTER_ASSERT(reporter, data[0] == 22);
46 REPORTER_ASSERT(reporter, data[1] == 24);
47 REPORTER_ASSERT(reporter, data[2] == 35);
48
49 SkBitSet set1(65536);
50 set1.set(12345);
51 REPORTER_ASSERT(reporter, set0.test(12345) == false);
52 REPORTER_ASSERT(reporter, set1.test(12345) == true);
53 REPORTER_ASSERT(reporter, set1.test(22) == false);
54 REPORTER_ASSERT(reporter, set0.test(35) == true);
55
56 set0.reset();
57 REPORTER_ASSERT(reporter, !set0.findFirst());
58 REPORTER_ASSERT(reporter, set0.test(1234) == false);
59
60 set0.set();
61 REPORTER_ASSERT(reporter, !set0.findFirstUnset());
62 REPORTER_ASSERT(reporter, set0.test(5678) == true);
63 }
64
DEF_TEST(BitSetComparisonSizeMatching,reporter)65 DEF_TEST(BitSetComparisonSizeMatching, reporter) {
66 // Verify that bitsets of differing sizes are never equal, even if the contents match.
67 SkBitSet bitsetA(123);
68 SkBitSet bitsetB(123);
69 REPORTER_ASSERT(reporter, bitsetA == bitsetB);
70 REPORTER_ASSERT(reporter, !(bitsetA != bitsetB));
71
72 SkBitSet bitsetC(345);
73 REPORTER_ASSERT(reporter, bitsetA != bitsetC);
74 REPORTER_ASSERT(reporter, !(bitsetA == bitsetC));
75
76 SkBitSet bitsetD(67);
77 REPORTER_ASSERT(reporter, bitsetA != bitsetD);
78 REPORTER_ASSERT(reporter, !(bitsetA == bitsetD));
79 }
80
DEF_TEST(BitSetComparisonBitMatching,reporter)81 DEF_TEST(BitSetComparisonBitMatching, reporter) {
82 SkRandom random;
83 for (int trial = 0; trial < 500; ++trial) {
84 // Make two identical bitsets.
85 int size = random.nextRangeU(1, 1000);
86 SkBitSet bitsetA(size);
87 SkBitSet bitsetB(size);
88
89 for (int index = 0; index < size; ++index) {
90 if (random.nextBool()) {
91 bitsetA.set(index);
92 bitsetB.set(index);
93 }
94 }
95
96 // Verify that the sets are equal.
97 REPORTER_ASSERT(reporter, bitsetA == bitsetB);
98 REPORTER_ASSERT(reporter, !(bitsetA != bitsetB));
99
100 // Flip some bits randomly. Always flip an odd number of bits to ensure that our random bit
101 // flips don't all cancel each other out.
102 int numBitsToFlip = random.nextULessThan(size) | 1;
103 for (int index = 0; index < numBitsToFlip; ++index) {
104 int bitToFlip = random.nextULessThan(size);
105 if (bitsetA.test(bitToFlip)) {
106 bitsetA.reset(bitToFlip);
107 } else {
108 bitsetA.set(bitToFlip);
109 }
110 }
111
112 // Verify that the sets are no longer equal.
113 REPORTER_ASSERT(reporter, bitsetA != bitsetB);
114 REPORTER_ASSERT(reporter, !(bitsetA == bitsetB));
115 }
116 }
117