322 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// PagedVector unit tests.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/ADT/PagedVector.h"14#include "gtest/gtest.h"15#include <iterator>16 17namespace llvm {18TEST(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#endif31}32 33TEST(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 44TEST(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 62TEST(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#endif78}79 80TEST(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 94TEST(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 111TEST(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 vector123 // 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 else130 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 pages137// will allocate all of them138TEST(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 else151 EXPECT_EQ(V[I], 0);152}153 154struct TestHelper {155 int A = -1;156};157 158// Use this to count how many times the constructor / destructor are called159struct TestHelper2 {160 int A = -1;161 static int constructed;162 static int destroyed;163 164 TestHelper2() { constructed++; }165 ~TestHelper2() { destroyed++; }166};167 168int TestHelper2::constructed = 0;169int TestHelper2::destroyed = 0;170 171TEST(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 expect184// the number of constructed / destructed elements to be a multiple of the185// page size and the constructor is invoked when the page is actually accessed186// the first time.187TEST(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 part212 // 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 destructor221 // is called only for the materialized pages222 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 231TEST(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#endif256}257 258TEST(PagedVectorTest, FunctionalityTest) {259 PagedVector<int, 10> V;260 EXPECT_EQ(V.empty(), true);261 262 // Next ten numbers are 10..19263 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 llvm322