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 13struct ListItem { 14 ListItem *Next; 15 ListItem *Prev; 16}; 17 18static ListItem Items[6]; 19static ListItem *X = &Items[0]; 20static ListItem *Y = &Items[1]; 21static ListItem *Z = &Items[2]; 22static ListItem *A = &Items[3]; 23static ListItem *B = &Items[4]; 24static ListItem *C = &Items[5]; 25 26typedef scudo::SinglyLinkedList<ListItem> SLList; 27typedef scudo::DoublyLinkedList<ListItem> DLList; 28 29template <typename ListT> 30static 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 41template <typename ListT> 42static 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 72template <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 128TEST(ScudoListTest, LinkedListCommon) { 129 testListCommon<SLList>(); 130 testListCommon<DLList>(); 131} 132 133TEST(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 183TEST(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} 217