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 } 264