compiler-rt/lib/scudo/standalone/tests/list_test.cpp

   1 //===-- list_test.cpp -------------------------------------------*- C++ -*-===//
   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 "tests/scudo_unit_test.h"
  10
  11 #include "list.h"
  12
  13 #include <array>
  14
  15 struct ListItemLinkedWithPtr {
  16   ListItemLinkedWithPtr *Next;
  17   ListItemLinkedWithPtr *Prev;
  18 };
  19
  20 struct ListItemLinkedWithIndex {
  21   scudo::uptr Next;
  22   scudo::uptr Prev;
  23   static constexpr scudo::uptr EndOfListVal = 1ULL << 30;
  24 };
  25
  26 template <typename ListT, typename ListItemTy>
  27 static void setList(ListT *L, ListItemTy *I1 = nullptr,
  28                     ListItemTy *I2 = nullptr, ListItemTy *I3 = nullptr) {
  29   L->clear();
  30   if (I1)
  31     L->push_back(I1);
  32   if (I2)
  33     L->push_back(I2);
  34   if (I3)
  35     L->push_back(I3);
  36 }
  37
  38 template <typename ListT, typename ListItemTy>
  39 static void checkList(ListT *L, ListItemTy *I1, ListItemTy *I2 = nullptr,
  40                       ListItemTy *I3 = nullptr, ListItemTy *I4 = nullptr,
  41                       ListItemTy *I5 = nullptr, ListItemTy *I6 = nullptr) {
  42   if (I1) {
  43     EXPECT_EQ(L->front(), I1);
  44     L->pop_front();
  45   }
  46   if (I2) {
  47     EXPECT_EQ(L->front(), I2);
  48     L->pop_front();
  49   }
  50   if (I3) {
  51     EXPECT_EQ(L->front(), I3);
  52     L->pop_front();
  53   }
  54   if (I4) {
  55     EXPECT_EQ(L->front(), I4);
  56     L->pop_front();
  57   }
  58   if (I5) {
  59     EXPECT_EQ(L->front(), I5);
  60     L->pop_front();
  61   }
  62   if (I6) {
  63     EXPECT_EQ(L->front(), I6);
  64     L->pop_front();
  65   }
  66   EXPECT_TRUE(L->empty());
  67 }
  68
  69 template <template <typename> class ListTy, typename ListItemTy>
  70 static void testListCommon(void) {
  71   ListItemTy Items[3];
  72   ListItemTy *X = &Items[0];
  73   ListItemTy *Y = &Items[1];
  74   ListItemTy *Z = &Items[2];
  75
  76   ListTy<ListItemTy> L;
  77   L.clear();
  78   L.init(Items, sizeof(Items));
  79
  80   EXPECT_EQ(L.size(), 0U);
  81   L.push_back(X);
  82   EXPECT_EQ(L.size(), 1U);
  83   EXPECT_EQ(L.back(), X);
  84   EXPECT_EQ(L.front(), X);
  85   L.pop_front();
  86   EXPECT_TRUE(L.empty());
  87   L.checkConsistency();
  88
  89   L.push_front(X);
  90   EXPECT_EQ(L.size(), 1U);
  91   EXPECT_EQ(L.back(), X);
  92   EXPECT_EQ(L.front(), X);
  93   L.pop_front();
  94   EXPECT_TRUE(L.empty());
  95   L.checkConsistency();
  96
  97   L.push_front(X);
  98   L.push_front(Y);
  99   L.push_front(Z);
 100   EXPECT_EQ(L.size(), 3U);
 101   EXPECT_EQ(L.front(), Z);
 102   EXPECT_EQ(L.back(), X);
 103   L.checkConsistency();
 104
 105   L.pop_front();
 106   EXPECT_EQ(L.size(), 2U);
 107   EXPECT_EQ(L.front(), Y);
 108   EXPECT_EQ(L.back(), X);
 109   L.pop_front();
 110   L.pop_front();
 111   EXPECT_TRUE(L.empty());
 112   L.checkConsistency();
 113
 114   L.push_back(X);
 115   L.push_back(Y);
 116   L.push_back(Z);
 117   EXPECT_EQ(L.size(), 3U);
 118   EXPECT_EQ(L.front(), X);
 119   EXPECT_EQ(L.back(), Z);
 120   L.checkConsistency();
 121
 122   L.pop_front();
 123   EXPECT_EQ(L.size(), 2U);
 124   EXPECT_EQ(L.front(), Y);
 125   EXPECT_EQ(L.back(), Z);
 126   L.pop_front();
 127   L.pop_front();
 128   EXPECT_TRUE(L.empty());
 129   L.checkConsistency();
 130
 131   L.push_back(X);
 132   L.push_back(Y);
 133   L.push_back(Z);
 134
 135   // Verify the iterator
 136   std::array<ListItemTy *, 3> visitOrder{X, Y, Z};
 137   auto Iter = visitOrder.begin();
 138   for (const auto &Item : L) {
 139     EXPECT_EQ(&Item, *Iter);
 140     ++Iter;
 141   }
 142 }
 143
 144 TEST(ScudoListTest, LinkedListCommon) {
 145   testListCommon<scudo::SinglyLinkedList, ListItemLinkedWithPtr>();
 146   testListCommon<scudo::SinglyLinkedList, ListItemLinkedWithIndex>();
 147   testListCommon<scudo::DoublyLinkedList, ListItemLinkedWithPtr>();
 148   testListCommon<scudo::DoublyLinkedList, ListItemLinkedWithIndex>();
 149 }
 150
 151 template <template <typename> class ListTy, typename ListItemTy>
 152 static void testSinglyLinkedList() {
 153   ListItemTy Items[6];
 154   ListItemTy *X = &Items[0];
 155   ListItemTy *Y = &Items[1];
 156   ListItemTy *Z = &Items[2];
 157   ListItemTy *A = &Items[3];
 158   ListItemTy *B = &Items[4];
 159   ListItemTy *C = &Items[5];
 160
 161   ListTy<ListItemTy> L;
 162   L.clear();
 163   L.init(Items, sizeof(Items));
 164
 165   L.push_back(X);
 166   L.push_back(Y);
 167   L.push_back(Z);
 168   L.extract(X, Y);
 169   EXPECT_EQ(L.size(), 2U);
 170   EXPECT_EQ(L.front(), X);
 171   EXPECT_EQ(L.back(), Z);
 172   L.checkConsistency();
 173   L.extract(X, Z);
 174   EXPECT_EQ(L.size(), 1U);
 175   EXPECT_EQ(L.front(), X);
 176   EXPECT_EQ(L.back(), X);
 177   L.checkConsistency();
 178   L.pop_front();
 179   EXPECT_TRUE(L.empty());
 180
 181   ListTy<ListItemTy> L1, L2;
 182   L1.clear();
 183   L2.clear();
 184   L1.init(Items, sizeof(Items));
 185   L2.init(Items, sizeof(Items));
 186
 187   L1.append_back(&L2);
 188   EXPECT_TRUE(L1.empty());
 189   EXPECT_TRUE(L2.empty());
 190
 191   setList(&L1, X);
 192   checkList(&L1, X);
 193
 194   setList(&L1, X, Y);
 195   L1.insert(X, Z);
 196   checkList(&L1, X, Z, Y);
 197
 198   setList(&L1, X, Y, Z);
 199   setList(&L2, A, B, C);
 200   L1.append_back(&L2);
 201   checkList(&L1, X, Y, Z, A, B, C);
 202   EXPECT_TRUE(L2.empty());
 203
 204   L1.clear();
 205   L2.clear();
 206   L1.push_back(X);
 207   L1.append_back(&L2);
 208   EXPECT_EQ(L1.back(), X);
 209   EXPECT_EQ(L1.front(), X);
 210   EXPECT_EQ(L1.size(), 1U);
 211 }
 212
 213 TEST(ScudoListTest, SinglyLinkedList) {
 214   testSinglyLinkedList<scudo::SinglyLinkedList, ListItemLinkedWithPtr>();
 215   testSinglyLinkedList<scudo::SinglyLinkedList, ListItemLinkedWithIndex>();
 216 }
 217
 218 template <template <typename> class ListTy, typename ListItemTy>
 219 static void testDoublyLinkedList() {
 220   ListItemTy Items[3];
 221   ListItemTy *X = &Items[0];
 222   ListItemTy *Y = &Items[1];
 223   ListItemTy *Z = &Items[2];
 224
 225   ListTy<ListItemTy> L;
 226   L.clear();
 227   L.init(Items, sizeof(Items));
 228
 229   L.push_back(X);
 230   L.push_back(Y);
 231   L.push_back(Z);
 232   L.remove(Y);
 233   EXPECT_EQ(L.size(), 2U);
 234   EXPECT_EQ(L.front(), X);
 235   EXPECT_EQ(L.back(), Z);
 236   L.checkConsistency();
 237   L.remove(Z);
 238   EXPECT_EQ(L.size(), 1U);
 239   EXPECT_EQ(L.front(), X);
 240   EXPECT_EQ(L.back(), X);
 241   L.checkConsistency();
 242   L.pop_front();
 243   EXPECT_TRUE(L.empty());
 244
 245   L.push_back(X);
 246   L.insert(Y, X);
 247   EXPECT_EQ(L.size(), 2U);
 248   EXPECT_EQ(L.front(), Y);
 249   EXPECT_EQ(L.back(), X);
 250   L.checkConsistency();
 251   L.remove(Y);
 252   EXPECT_EQ(L.size(), 1U);
 253   EXPECT_EQ(L.front(), X);
 254   EXPECT_EQ(L.back(), X);
 255   L.checkConsistency();
 256   L.pop_front();
 257   EXPECT_TRUE(L.empty());
 258 }
 259
 260 TEST(ScudoListTest, DoublyLinkedList) {
 261   testDoublyLinkedList<scudo::DoublyLinkedList, ListItemLinkedWithPtr>();
 262   testDoublyLinkedList<scudo::DoublyLinkedList, ListItemLinkedWithIndex>();
 263 }