libc/test/src/__support/blockstore_test.cpp

   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 }