forked from facebook/hermes
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBitArrayTest.cpp
More file actions
139 lines (122 loc) · 3.96 KB
/
BitArrayTest.cpp
File metadata and controls
139 lines (122 loc) · 3.96 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/*
* Copyright (c) Facebook, Inc. and its affiliates.
*
* This source code is licensed under the MIT license found in the
* LICENSE file in the root directory of this source tree.
*/
#include "hermes/ADT/BitArray.h"
#include "gtest/gtest.h"
#include <deque>
namespace {
using namespace hermes;
template <typename SIZE>
struct BitArrayTest : public ::testing::Test {
protected:
std::vector<std::deque<size_t>> getTestIndices() {
std::vector<std::deque<size_t>> testIndices;
// Use a mix of word-aligned and non-word-aligned values. Set the first and
// last bits to check that those edge cases are handled correctly.
testIndices.push_back({0,
1,
2,
128,
234,
436,
789,
1099,
SIZE::value - 65,
SIZE::value - 2,
SIZE::value - 1});
// Test the case where there are no set bits at the start/end.
testIndices.push_back({128, 234, 436, 789, 1099, SIZE::value - 100});
// Test the case where set bits occur at word boundaries.
testIndices.push_back({63, 127, 1023, 1024, SIZE::value - 1});
return testIndices;
}
};
// Use a mix of word-aligned and non-word-aligned sizes. Also have a mix of
// different numbers of words.
using TestSizes = testing::Types<
std::integral_constant<size_t, 1571>,
std::integral_constant<size_t, 2047>,
std::integral_constant<size_t, 2048>>;
TYPED_TEST_CASE(BitArrayTest, TestSizes);
TYPED_TEST(BitArrayTest, NextSetBit) {
constexpr size_t N = TypeParam::value;
BitArray<N> ba;
auto testIndices = this->getTestIndices();
for (auto &indices : testIndices) {
ba.reset();
// Empty case: No marked bits
EXPECT_EQ(N, ba.findNextSetBitFrom(0));
for (size_t idx : indices) {
ba.set(idx, true);
}
// Use the same style of loop we use elsewhere for scanning the array.
for (size_t from = ba.findNextSetBitFrom(0); from < N;
from = ba.findNextSetBitFrom(from + 1)) {
EXPECT_EQ(indices.front(), from);
indices.pop_front();
}
EXPECT_EQ(0, indices.size());
}
}
TYPED_TEST(BitArrayTest, NextZeroBit) {
constexpr size_t N = TypeParam::value;
BitArray<N> ba;
auto testIndices = this->getTestIndices();
for (auto &indices : testIndices) {
ba.set();
// Full case: No unmarked bits
EXPECT_EQ(N, ba.findNextZeroBitFrom(0));
for (auto idx : indices) {
ba.set(idx, false);
}
// Use the same style of loop we use elsewhere for scanning the array.
for (size_t from = ba.findNextZeroBitFrom(0); from < N;
from = ba.findNextZeroBitFrom(from + 1)) {
EXPECT_EQ(indices.front(), from);
indices.pop_front();
}
EXPECT_EQ(0, indices.size());
}
}
TYPED_TEST(BitArrayTest, PrevSetBit) {
constexpr size_t N = TypeParam::value;
BitArray<N> ba;
auto testIndices = this->getTestIndices();
for (auto &indices : testIndices) {
ba.reset();
// Empty case: No marked bits
EXPECT_EQ(N, ba.findPrevSetBitFrom(N));
for (auto idx : indices) {
ba.set(idx, true);
}
for (size_t from = ba.findPrevSetBitFrom(N); from != N;
from = ba.findPrevSetBitFrom(from)) {
EXPECT_EQ(indices.back(), from);
indices.pop_back();
}
EXPECT_EQ(0, indices.size());
}
}
TYPED_TEST(BitArrayTest, PrevZeroBit) {
constexpr size_t N = TypeParam::value;
BitArray<N> ba;
auto testIndices = this->getTestIndices();
for (auto &indices : testIndices) {
ba.set();
// Full case: No unmarked bits
EXPECT_EQ(N, ba.findPrevZeroBitFrom(N));
for (auto idx : indices) {
ba.set(idx, false);
}
for (size_t from = ba.findPrevZeroBitFrom(N); from != N;
from = ba.findPrevZeroBitFrom(from)) {
EXPECT_EQ(indices.back(), from);
indices.pop_back();
}
EXPECT_EQ(0, indices.size());
}
}
} // namespace