1 //===-- Unittests for BlockStore ------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "src/__support/blockstore.h"
10 #include "test/UnitTest/Test.h"
11
12 struct Element {
13 int a;
14 long b;
15 unsigned c;
16 };
17
18 class LlvmLibcBlockStoreTest : public LIBC_NAMESPACE::testing::Test {
19 public:
20 template <size_t BLOCK_SIZE, size_t ELEMENT_COUNT, bool REVERSE>
populate_and_iterate()21 void populate_and_iterate() {
22 LIBC_NAMESPACE::BlockStore<Element, BLOCK_SIZE, REVERSE> block_store;
23 for (int i = 0; i < int(ELEMENT_COUNT); ++i)
24 ASSERT_TRUE(block_store.push_back({i, 2 * i, 3 * unsigned(i)}));
25 auto end = block_store.end();
26 int i = 0;
27 for (auto iter = block_store.begin(); iter != end; ++iter, ++i) {
28 Element &e = *iter;
29 if (REVERSE) {
30 int j = ELEMENT_COUNT - 1 - i;
31 ASSERT_EQ(e.a, j);
32 ASSERT_EQ(e.b, long(j * 2));
33 ASSERT_EQ(e.c, unsigned(j * 3));
34 } else {
35 ASSERT_EQ(e.a, i);
36 ASSERT_EQ(e.b, long(i * 2));
37 ASSERT_EQ(e.c, unsigned(i * 3));
38 }
39 }
40 ASSERT_EQ(i, int(ELEMENT_COUNT));
41 LIBC_NAMESPACE::BlockStore<Element, BLOCK_SIZE, REVERSE>::destroy(
42 &block_store);
43 }
44
back_test()45 template <bool REVERSE> void back_test() {
46 using LIBC_NAMESPACE::BlockStore;
47 BlockStore<int, 4, REVERSE> block_store;
48 for (int i = 0; i < 20; i++)
49 ASSERT_TRUE(block_store.push_back(i));
50 for (int i = 19; i >= 0; i--, block_store.pop_back())
51 ASSERT_EQ(block_store.back(), i);
52 block_store.destroy(&block_store);
53 }
54
empty_test()55 template <bool REVERSE> void empty_test() {
56 using LIBC_NAMESPACE::BlockStore;
57 BlockStore<int, 2, REVERSE> block_store;
58
59 ASSERT_TRUE(block_store.empty());
60 ASSERT_TRUE(block_store.push_back(1));
61 for (int i = 0; i < 10; i++) {
62 ASSERT_FALSE(block_store.empty());
63 ASSERT_TRUE(block_store.push_back(1));
64 }
65 block_store.destroy(&block_store);
66 }
67
erase_test()68 template <bool REVERSE> void erase_test() {
69 using LIBC_NAMESPACE::BlockStore;
70 BlockStore<int, 2, REVERSE> block_store;
71 int i;
72
73 constexpr int ARR_SIZE = 6;
74
75 ASSERT_TRUE(block_store.empty());
76 for (int i = 0; i < ARR_SIZE; i++) {
77 ASSERT_TRUE(block_store.push_back(i + 1));
78 }
79
80 // block_store state should be {1,2,3,4,5,6}
81
82 block_store.erase(block_store.begin());
83
84 // FORWARD: block_store state should be {2,3,4,5,6}
85 // REVERSE: block_store state should be {1,2,3,4,5}
86
87 auto iter = block_store.begin();
88 for (i = 0; iter != block_store.end(); ++i, ++iter) {
89 if (!REVERSE) {
90 ASSERT_EQ(*iter, i + 2);
91 } else {
92 ASSERT_EQ(*iter, (ARR_SIZE - 1) - i);
93 }
94 }
95
96 // Assert that there were the correct number of elements
97 ASSERT_EQ(i, ARR_SIZE - 1);
98
99 block_store.erase(block_store.end());
100
101 // BOTH: block_store state should be {2,3,4,5}
102
103 iter = block_store.begin();
104 for (i = 0; iter != block_store.end(); ++i, ++iter) {
105 if (!REVERSE) {
106 ASSERT_EQ(*iter, i + 2);
107 } else {
108 ASSERT_EQ(*iter, (ARR_SIZE - 1) - i);
109 }
110 }
111
112 ASSERT_EQ(i, ARR_SIZE - 2);
113
114 block_store.erase(block_store.begin() + 1);
115
116 // FORWARD: block_store state should be {2,4,5}
117 // REVERSE: block_store state should be {2,3,5}
118
119 const int FORWARD_RESULTS[] = {2, 4, 5};
120 const int REVERSE_RESULTS[] = {2, 3, 5};
121
122 iter = block_store.begin();
123 for (i = 0; iter != block_store.end(); ++i, ++iter) {
124 if (!REVERSE) {
125 ASSERT_EQ(*iter, FORWARD_RESULTS[i]);
126 } else {
127 ASSERT_EQ(*iter, REVERSE_RESULTS[ARR_SIZE - 4 - i]); // reversed
128 }
129 }
130
131 ASSERT_EQ(i, ARR_SIZE - 3);
132
133 block_store.erase(block_store.begin() + 1);
134 // BOTH: block_store state should be {2,5}
135
136 iter = block_store.begin();
137 if (!REVERSE) {
138 ASSERT_EQ(*iter, 2);
139 ASSERT_EQ(*(iter + 1), 5);
140 } else {
141 ASSERT_EQ(*iter, 5);
142 ASSERT_EQ(*(iter + 1), 2);
143 }
144
145 block_store.erase(block_store.begin());
146 // FORWARD: block_store state should be {5}
147 // REVERSE: block_store state should be {2}
148 iter = block_store.begin();
149 if (!REVERSE) {
150 ASSERT_EQ(*iter, 5);
151 } else {
152 ASSERT_EQ(*iter, 2);
153 }
154
155 block_store.erase(block_store.begin());
156 // BOTH: block_store state should be {}
157
158 block_store.destroy(&block_store);
159 }
160 };
161
TEST_F(LlvmLibcBlockStoreTest,PopulateAndIterate4)162 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate4) {
163 populate_and_iterate<4, 4, false>();
164 }
165
TEST_F(LlvmLibcBlockStoreTest,PopulateAndIterate8)166 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate8) {
167 populate_and_iterate<4, 8, false>();
168 }
169
TEST_F(LlvmLibcBlockStoreTest,PopulateAndIterate10)170 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate10) {
171 populate_and_iterate<4, 10, false>();
172 }
173
TEST_F(LlvmLibcBlockStoreTest,PopulateAndIterateReverse4)174 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse4) {
175 populate_and_iterate<4, 4, true>();
176 }
177
TEST_F(LlvmLibcBlockStoreTest,PopulateAndIterateReverse8)178 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse8) {
179 populate_and_iterate<4, 8, true>();
180 }
181
TEST_F(LlvmLibcBlockStoreTest,PopulateAndIterateReverse10)182 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse10) {
183 populate_and_iterate<4, 10, true>();
184 }
185
TEST_F(LlvmLibcBlockStoreTest,Back)186 TEST_F(LlvmLibcBlockStoreTest, Back) {
187 back_test<false>();
188 back_test<true>();
189 }
190
TEST_F(LlvmLibcBlockStoreTest,Empty)191 TEST_F(LlvmLibcBlockStoreTest, Empty) {
192 empty_test<false>();
193 empty_test<true>();
194 }
195
TEST_F(LlvmLibcBlockStoreTest,Erase)196 TEST_F(LlvmLibcBlockStoreTest, Erase) {
197 erase_test<false>();
198 erase_test<true>();
199 }
200