264 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "tests/scudo_unit_test.h"10 11#include "list.h"12 13#include <array>14 15struct ListItemLinkedWithPtr {16 ListItemLinkedWithPtr *Next;17 ListItemLinkedWithPtr *Prev;18};19 20struct ListItemLinkedWithIndex {21 scudo::uptr Next;22 scudo::uptr Prev;23 static constexpr scudo::uptr EndOfListVal = 1ULL << 30;24};25 26template <typename ListT, typename ListItemTy>27static 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 38template <typename ListT, typename ListItemTy>39static 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 69template <template <typename> class ListTy, typename ListItemTy>70static 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 iterator136 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 144TEST(ScudoListTest, LinkedListCommon) {145 testListCommon<scudo::SinglyLinkedList, ListItemLinkedWithPtr>();146 testListCommon<scudo::SinglyLinkedList, ListItemLinkedWithIndex>();147 testListCommon<scudo::DoublyLinkedList, ListItemLinkedWithPtr>();148 testListCommon<scudo::DoublyLinkedList, ListItemLinkedWithIndex>();149}150 151template <template <typename> class ListTy, typename ListItemTy>152static 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 213TEST(ScudoListTest, SinglyLinkedList) {214 testSinglyLinkedList<scudo::SinglyLinkedList, ListItemLinkedWithPtr>();215 testSinglyLinkedList<scudo::SinglyLinkedList, ListItemLinkedWithIndex>();216}217 218template <template <typename> class ListTy, typename ListItemTy>219static 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 260TEST(ScudoListTest, DoublyLinkedList) {261 testDoublyLinkedList<scudo::DoublyLinkedList, ListItemLinkedWithPtr>();262 testDoublyLinkedList<scudo::DoublyLinkedList, ListItemLinkedWithIndex>();263}264