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> 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 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 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 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 162 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate4) { 163 populate_and_iterate<4, 4, false>(); 164 } 165 166 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate8) { 167 populate_and_iterate<4, 8, false>(); 168 } 169 170 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate10) { 171 populate_and_iterate<4, 10, false>(); 172 } 173 174 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse4) { 175 populate_and_iterate<4, 4, true>(); 176 } 177 178 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse8) { 179 populate_and_iterate<4, 8, true>(); 180 } 181 182 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse10) { 183 populate_and_iterate<4, 10, true>(); 184 } 185 186 TEST_F(LlvmLibcBlockStoreTest, Back) { 187 back_test<false>(); 188 back_test<true>(); 189 } 190 191 TEST_F(LlvmLibcBlockStoreTest, Empty) { 192 empty_test<false>(); 193 empty_test<true>(); 194 } 195 196 TEST_F(LlvmLibcBlockStoreTest, Erase) { 197 erase_test<false>(); 198 erase_test<true>(); 199 } 200