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 struct ListItem {
  14   ListItem *Next;
  15   ListItem *Prev;
  16 };
  17
  18 static ListItem Items[6];
  19 static ListItem *X = &Items[0];
  20 static ListItem *Y = &Items[1];
  21 static ListItem *Z = &Items[2];
  22 static ListItem *A = &Items[3];
  23 static ListItem *B = &Items[4];
  24 static ListItem *C = &Items[5];
  25
  26 typedef scudo::SinglyLinkedList<ListItem> SLList;
  27 typedef scudo::DoublyLinkedList<ListItem> DLList;
  28
  29 template <typename ListT>
  30 static void setList(ListT *L, ListItem *I1 = nullptr, ListItem *I2 = nullptr,
  31                     ListItem *I3 = nullptr) {
  32   L->clear();
  33   if (I1)
  34     L->push_back(I1);
  35   if (I2)
  36     L->push_back(I2);
  37   if (I3)
  38     L->push_back(I3);
  39 }
  40
  41 template <typename ListT>
  42 static void checkList(ListT *L, ListItem *I1, ListItem *I2 = nullptr,
  43                       ListItem *I3 = nullptr, ListItem *I4 = nullptr,
  44                       ListItem *I5 = nullptr, ListItem *I6 = nullptr) {
  45   if (I1) {
  46     EXPECT_EQ(L->front(), I1);
  47     L->pop_front();
  48   }
  49   if (I2) {
  50     EXPECT_EQ(L->front(), I2);
  51     L->pop_front();
  52   }
  53   if (I3) {
  54     EXPECT_EQ(L->front(), I3);
  55     L->pop_front();
  56   }
  57   if (I4) {
  58     EXPECT_EQ(L->front(), I4);
  59     L->pop_front();
  60   }
  61   if (I5) {
  62     EXPECT_EQ(L->front(), I5);
  63     L->pop_front();
  64   }
  65   if (I6) {
  66     EXPECT_EQ(L->front(), I6);
  67     L->pop_front();
  68   }
  69   EXPECT_TRUE(L->empty());
  70 }
  71
  72 template <typename ListT> static void testListCommon(void) {
  73   ListT L;
  74   L.clear();
  75
  76   EXPECT_EQ(L.size(), 0U);
  77   L.push_back(X);
  78   EXPECT_EQ(L.size(), 1U);
  79   EXPECT_EQ(L.back(), X);
  80   EXPECT_EQ(L.front(), X);
  81   L.pop_front();
  82   EXPECT_TRUE(L.empty());
  83   L.checkConsistency();
  84
  85   L.push_front(X);
  86   EXPECT_EQ(L.size(), 1U);
  87   EXPECT_EQ(L.back(), X);
  88   EXPECT_EQ(L.front(), X);
  89   L.pop_front();
  90   EXPECT_TRUE(L.empty());
  91   L.checkConsistency();
  92
  93   L.push_front(X);
  94   L.push_front(Y);
  95   L.push_front(Z);
  96   EXPECT_EQ(L.size(), 3U);
  97   EXPECT_EQ(L.front(), Z);
  98   EXPECT_EQ(L.back(), X);
  99   L.checkConsistency();
 100
 101   L.pop_front();
 102   EXPECT_EQ(L.size(), 2U);
 103   EXPECT_EQ(L.front(), Y);
 104   EXPECT_EQ(L.back(), X);
 105   L.pop_front();
 106   L.pop_front();
 107   EXPECT_TRUE(L.empty());
 108   L.checkConsistency();
 109
 110   L.push_back(X);
 111   L.push_back(Y);
 112   L.push_back(Z);
 113   EXPECT_EQ(L.size(), 3U);
 114   EXPECT_EQ(L.front(), X);
 115   EXPECT_EQ(L.back(), Z);
 116   L.checkConsistency();
 117
 118   L.pop_front();
 119   EXPECT_EQ(L.size(), 2U);
 120   EXPECT_EQ(L.front(), Y);
 121   EXPECT_EQ(L.back(), Z);
 122   L.pop_front();
 123   L.pop_front();
 124   EXPECT_TRUE(L.empty());
 125   L.checkConsistency();
 126 }
 127
 128 TEST(ScudoListTest, LinkedListCommon) {
 129   testListCommon<SLList>();
 130   testListCommon<DLList>();
 131 }
 132
 133 TEST(ScudoListTest, SinglyLinkedList) {
 134   SLList L;
 135   L.clear();
 136
 137   L.push_back(X);
 138   L.push_back(Y);
 139   L.push_back(Z);
 140   L.extract(X, Y);
 141   EXPECT_EQ(L.size(), 2U);
 142   EXPECT_EQ(L.front(), X);
 143   EXPECT_EQ(L.back(), Z);
 144   L.checkConsistency();
 145   L.extract(X, Z);
 146   EXPECT_EQ(L.size(), 1U);
 147   EXPECT_EQ(L.front(), X);
 148   EXPECT_EQ(L.back(), X);
 149   L.checkConsistency();
 150   L.pop_front();
 151   EXPECT_TRUE(L.empty());
 152
 153   SLList L1, L2;
 154   L1.clear();
 155   L2.clear();
 156
 157   L1.append_back(&L2);
 158   EXPECT_TRUE(L1.empty());
 159   EXPECT_TRUE(L2.empty());
 160
 161   setList(&L1, X);
 162   checkList(&L1, X);
 163
 164   setList(&L1, X, Y);
 165   L1.insert(X, Z);
 166   checkList(&L1, X, Z, Y);
 167
 168   setList(&L1, X, Y, Z);
 169   setList(&L2, A, B, C);
 170   L1.append_back(&L2);
 171   checkList(&L1, X, Y, Z, A, B, C);
 172   EXPECT_TRUE(L2.empty());
 173
 174   L1.clear();
 175   L2.clear();
 176   L1.push_back(X);
 177   L1.append_back(&L2);
 178   EXPECT_EQ(L1.back(), X);
 179   EXPECT_EQ(L1.front(), X);
 180   EXPECT_EQ(L1.size(), 1U);
 181 }
 182
 183 TEST(ScudoListTest, DoublyLinkedList) {
 184   DLList L;
 185   L.clear();
 186
 187   L.push_back(X);
 188   L.push_back(Y);
 189   L.push_back(Z);
 190   L.remove(Y);
 191   EXPECT_EQ(L.size(), 2U);
 192   EXPECT_EQ(L.front(), X);
 193   EXPECT_EQ(L.back(), Z);
 194   L.checkConsistency();
 195   L.remove(Z);
 196   EXPECT_EQ(L.size(), 1U);
 197   EXPECT_EQ(L.front(), X);
 198   EXPECT_EQ(L.back(), X);
 199   L.checkConsistency();
 200   L.pop_front();
 201   EXPECT_TRUE(L.empty());
 202
 203   L.push_back(X);
 204   L.insert(Y, X);
 205   EXPECT_EQ(L.size(), 2U);
 206   EXPECT_EQ(L.front(), Y);
 207   EXPECT_EQ(L.back(), X);
 208   L.checkConsistency();
 209   L.remove(Y);
 210   EXPECT_EQ(L.size(), 1U);
 211   EXPECT_EQ(L.front(), X);
 212   EXPECT_EQ(L.back(), X);
 213   L.checkConsistency();
 214   L.pop_front();
 215   EXPECT_TRUE(L.empty());
 216 }