llvm/unittests/ADT/PagedVectorTest.cpp

   1 //===- llvm/unittest/ADT/PagedVectorTest.cpp ------------------------------===//
   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 // PagedVector unit tests.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/ADT/PagedVector.h"
  14 #include "gtest/gtest.h"
  15 #include <iterator>
  16
  17 namespace llvm {
  18 TEST(PagedVectorTest, EmptyTest) {
  19   PagedVector<int, 10> V;
  20   EXPECT_EQ(V.empty(), true);
  21   EXPECT_EQ(V.size(), 0ULL);
  22   EXPECT_EQ(V.capacity(), 0ULL);
  23   EXPECT_EQ(V.materialized_begin().getIndex(), 0ULL);
  24   EXPECT_EQ(V.materialized_end().getIndex(), 0ULL);
  25   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
  26
  27 #if GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
  28   EXPECT_DEATH(V[0], "Index < Size");
  29   EXPECT_DEATH(PagedVector<int>(nullptr), "Allocator cannot be null");
  30 #endif
  31 }
  32
  33 TEST(PagedVectorTest, ExpandTest) {
  34   PagedVector<int, 10> V;
  35   V.resize(2);
  36   EXPECT_EQ(V.empty(), false);
  37   EXPECT_EQ(V.size(), 2ULL);
  38   EXPECT_EQ(V.capacity(), 10ULL);
  39   EXPECT_EQ(V.materialized_begin().getIndex(), 2ULL);
  40   EXPECT_EQ(V.materialized_end().getIndex(), 2ULL);
  41   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
  42 }
  43
  44 TEST(PagedVectorTest, FullPageFillingTest) {
  45   PagedVector<int, 10> V;
  46   V.resize(10);
  47   EXPECT_EQ(V.empty(), false);
  48   EXPECT_EQ(V.size(), 10ULL);
  49   EXPECT_EQ(V.capacity(), 10ULL);
  50   for (int I = 0; I < 10; ++I)
  51     V[I] = I;
  52   EXPECT_EQ(V.empty(), false);
  53   EXPECT_EQ(V.size(), 10ULL);
  54   EXPECT_EQ(V.capacity(), 10ULL);
  55   EXPECT_EQ(V.materialized_begin().getIndex(), 0ULL);
  56   EXPECT_EQ(V.materialized_end().getIndex(), 10ULL);
  57   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL);
  58   for (int I = 0; I < 10; ++I)
  59     EXPECT_EQ(V[I], I);
  60 }
  61
  62 TEST(PagedVectorTest, HalfPageFillingTest) {
  63   PagedVector<int, 10> V;
  64   V.resize(5);
  65   EXPECT_EQ(V.empty(), false);
  66   EXPECT_EQ(V.size(), 5ULL);
  67   EXPECT_EQ(V.capacity(), 10ULL);
  68   for (int I = 0; I < 5; ++I)
  69     V[I] = I;
  70   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 5LL);
  71   for (int I = 0; I < 5; ++I)
  72     EXPECT_EQ(V[I], I);
  73
  74 #if GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
  75   for (int I = 5; I < 10; ++I)
  76     EXPECT_DEATH(V[I], "Index < Size");
  77 #endif
  78 }
  79
  80 TEST(PagedVectorTest, FillFullMultiPageTest) {
  81   PagedVector<int, 10> V;
  82   V.resize(20);
  83   EXPECT_EQ(V.empty(), false);
  84   EXPECT_EQ(V.size(), 20ULL);
  85   EXPECT_EQ(V.capacity(), 20ULL);
  86   for (int I = 0; I < 20; ++I)
  87     V[I] = I;
  88   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL);
  89   for (auto MI = V.materialized_begin(), ME = V.materialized_end(); MI != ME;
  90        ++MI)
  91     EXPECT_EQ(*MI, std::distance(V.materialized_begin(), MI));
  92 }
  93
  94 TEST(PagedVectorTest, FillHalfMultiPageTest) {
  95   PagedVector<int, 10> V;
  96   V.resize(20);
  97   EXPECT_EQ(V.empty(), false);
  98   EXPECT_EQ(V.size(), 20ULL);
  99   EXPECT_EQ(V.capacity(), 20ULL);
 100   for (int I = 0; I < 5; ++I)
 101     V[I] = I;
 102   for (int I = 10; I < 15; ++I)
 103     V[I] = I;
 104   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL);
 105   for (int I = 0; I < 5; ++I)
 106     EXPECT_EQ(V[I], I);
 107   for (int I = 10; I < 15; ++I)
 108     EXPECT_EQ(V[I], I);
 109 }
 110
 111 TEST(PagedVectorTest, FillLastMultiPageTest) {
 112   PagedVector<int, 10> V;
 113   V.resize(20);
 114   EXPECT_EQ(V.empty(), false);
 115   EXPECT_EQ(V.size(), 20ULL);
 116   EXPECT_EQ(V.capacity(), 20ULL);
 117   for (int I = 10; I < 15; ++I)
 118     V[I] = I;
 119   for (int I = 10; I < 15; ++I)
 120     EXPECT_EQ(V[I], I);
 121
 122   // Since we fill the last page only, the materialized vector
 123   // should contain only the last page.
 124   int J = 10;
 125   for (auto MI = V.materialized_begin(), ME = V.materialized_end(); MI != ME;
 126        ++MI) {
 127     if (J < 15)
 128       EXPECT_EQ(*MI, J);
 129     else
 130       EXPECT_EQ(*MI, 0);
 131     ++J;
 132   }
 133   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL);
 134 }
 135
 136 // Filling the first element of all the pages
 137 // will allocate all of them
 138 TEST(PagedVectorTest, FillSparseMultiPageTest) {
 139   PagedVector<int, 10> V;
 140   V.resize(100);
 141   EXPECT_EQ(V.empty(), false);
 142   EXPECT_EQ(V.size(), 100ULL);
 143   EXPECT_EQ(V.capacity(), 100ULL);
 144   for (int I = 0; I < 10; ++I)
 145     V[I * 10] = I;
 146   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 100LL);
 147   for (int I = 0; I < 100; ++I)
 148     if (I % 10 == 0)
 149       EXPECT_EQ(V[I], I / 10);
 150     else
 151       EXPECT_EQ(V[I], 0);
 152 }
 153
 154 struct TestHelper {
 155   int A = -1;
 156 };
 157
 158 // Use this to count how many times the constructor / destructor are called
 159 struct TestHelper2 {
 160   int A = -1;
 161   static int constructed;
 162   static int destroyed;
 163
 164   TestHelper2() { constructed++; }
 165   ~TestHelper2() { destroyed++; }
 166 };
 167
 168 int TestHelper2::constructed = 0;
 169 int TestHelper2::destroyed = 0;
 170
 171 TEST(PagedVectorTest, FillNonTrivialConstructor) {
 172   PagedVector<TestHelper, 10> V;
 173   V.resize(10);
 174   EXPECT_EQ(V.empty(), false);
 175   EXPECT_EQ(V.size(), 10ULL);
 176   EXPECT_EQ(V.capacity(), 10ULL);
 177   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
 178   for (int I = 0; I < 10; ++I)
 179     EXPECT_EQ(V[I].A, -1);
 180   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL);
 181 }
 182
 183 // Elements are constructed, destructed in pages, so we expect
 184 // the number of constructed / destructed elements to be a multiple of the
 185 // page size and the constructor is invoked when the page is actually accessed
 186 // the first time.
 187 TEST(PagedVectorTest, FillNonTrivialConstructorDestructor) {
 188   PagedVector<TestHelper2, 10> V;
 189   V.resize(19);
 190   EXPECT_EQ(TestHelper2::constructed, 0);
 191   EXPECT_EQ(V.empty(), false);
 192   EXPECT_EQ(V.size(), 19ULL);
 193   EXPECT_EQ(V.capacity(), 20ULL);
 194   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
 195   EXPECT_EQ(V[0].A, -1);
 196   EXPECT_EQ(TestHelper2::constructed, 10);
 197
 198   for (int I = 0; I < 10; ++I) {
 199     EXPECT_EQ(V[I].A, -1);
 200     EXPECT_EQ(TestHelper2::constructed, 10);
 201   }
 202   for (int I = 10; I < 11; ++I) {
 203     EXPECT_EQ(V[I].A, -1);
 204     EXPECT_EQ(TestHelper2::constructed, 20);
 205   }
 206   for (int I = 0; I < 19; ++I) {
 207     EXPECT_EQ(V[I].A, -1);
 208     EXPECT_EQ(TestHelper2::constructed, 20);
 209   }
 210   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 19LL);
 211   // We initialize the whole page, not just the materialized part
 212   // EXPECT_EQ(TestHelper2::constructed, 20);
 213   V.resize(18);
 214   EXPECT_EQ(TestHelper2::destroyed, 0);
 215   V.resize(1);
 216   EXPECT_EQ(TestHelper2::destroyed, 10);
 217   V.resize(0);
 218   EXPECT_EQ(TestHelper2::destroyed, 20);
 219
 220   // Add a few empty pages so that we can test that the destructor
 221   // is called only for the materialized pages
 222   V.resize(50);
 223   V[49].A = 0;
 224   EXPECT_EQ(TestHelper2::constructed, 30);
 225   EXPECT_EQ(TestHelper2::destroyed, 20);
 226   EXPECT_EQ(V[49].A, 0);
 227   V.resize(0);
 228   EXPECT_EQ(TestHelper2::destroyed, 30);
 229 }
 230
 231 TEST(PagedVectorTest, ShrinkTest) {
 232   PagedVector<int, 10> V;
 233   V.resize(20);
 234   EXPECT_EQ(V.empty(), false);
 235   EXPECT_EQ(V.size(), 20ULL);
 236   EXPECT_EQ(V.capacity(), 20ULL);
 237   for (int I = 0; I < 20; ++I)
 238     V[I] = I;
 239   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL);
 240   V.resize(9);
 241   EXPECT_EQ(V.empty(), false);
 242   EXPECT_EQ(V.size(), 9ULL);
 243   EXPECT_EQ(V.capacity(), 10ULL);
 244   for (int I = 0; I < 9; ++I)
 245     EXPECT_EQ(V[I], I);
 246   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 9LL);
 247   V.resize(0);
 248   EXPECT_EQ(V.empty(), true);
 249   EXPECT_EQ(V.size(), 0ULL);
 250   EXPECT_EQ(V.capacity(), 0ULL);
 251   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
 252
 253 #if GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
 254   EXPECT_DEATH(V[0], "Index < Size");
 255 #endif
 256 }
 257
 258 TEST(PagedVectorTest, FunctionalityTest) {
 259   PagedVector<int, 10> V;
 260   EXPECT_EQ(V.empty(), true);
 261
 262   // Next ten numbers are 10..19
 263   V.resize(2);
 264   EXPECT_EQ(V.empty(), false);
 265   V.resize(10);
 266   V.resize(20);
 267   V.resize(30);
 268   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
 269
 270   EXPECT_EQ(V.size(), 30ULL);
 271   for (int I = 0; I < 10; ++I)
 272     V[I] = I;
 273   for (int I = 0; I < 10; ++I)
 274     EXPECT_EQ(V[I], I);
 275   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL);
 276   for (int I = 20; I < 30; ++I)
 277     V[I] = I;
 278   for (int I = 20; I < 30; ++I)
 279     EXPECT_EQ(V[I], I);
 280   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL);
 281
 282   for (int I = 10; I < 20; ++I)
 283     V[I] = I;
 284   for (int I = 10; I < 20; ++I)
 285     EXPECT_EQ(V[I], I);
 286   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 30LL);
 287   V.resize(35);
 288   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 30LL);
 289   for (int I = 30; I < 35; ++I)
 290     V[I] = I;
 291   EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 35LL);
 292   EXPECT_EQ(V.size(), 35ULL);
 293   EXPECT_EQ(V.capacity(), 40ULL);
 294   V.resize(37);
 295   for (int I = 30; I < 37; ++I)
 296     V[I] = I;
 297   EXPECT_EQ(V.size(), 37ULL);
 298   EXPECT_EQ(V.capacity(), 40ULL);
 299   for (int I = 0; I < 37; ++I)
 300     EXPECT_EQ(V[I], I);
 301
 302   V.resize(41);
 303   V[40] = 40;
 304   EXPECT_EQ(V.size(), 41ULL);
 305   EXPECT_EQ(V.capacity(), 50ULL);
 306   for (int I = 0; I < 36; ++I)
 307     EXPECT_EQ(V[I], I);
 308
 309   for (int I = 37; I < 40; ++I)
 310     EXPECT_EQ(V[I], 0);
 311
 312   V.resize(50);
 313   EXPECT_EQ(V.capacity(), 50ULL);
 314   EXPECT_EQ(V.size(), 50ULL);
 315   EXPECT_EQ(V[40], 40);
 316   V.resize(50ULL);
 317   V.clear();
 318   EXPECT_EQ(V.size(), 0ULL);
 319   EXPECT_EQ(V.capacity(), 0ULL);
 320 }
 321 } // namespace llvm