| //===-- list_test.cpp -------------------------------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "scudo/standalone/list.h" |
| #include "gtest/gtest.h" |
| |
| struct ListItem { |
| ListItem *Next; |
| }; |
| |
| typedef scudo::IntrusiveList<ListItem> List; |
| |
| static List StaticList; |
| |
| static void setList(List *L, ListItem *X = nullptr, ListItem *Y = nullptr, |
| ListItem *Z = nullptr) { |
| L->clear(); |
| if (X) |
| L->push_back(X); |
| if (Y) |
| L->push_back(Y); |
| if (Z) |
| L->push_back(Z); |
| } |
| |
| static void checkList(List *L, ListItem *I1, ListItem *I2 = nullptr, |
| ListItem *I3 = nullptr, ListItem *I4 = nullptr, |
| ListItem *I5 = nullptr, ListItem *I6 = nullptr) { |
| if (I1) { |
| EXPECT_EQ(L->front(), I1); |
| L->pop_front(); |
| } |
| if (I2) { |
| EXPECT_EQ(L->front(), I2); |
| L->pop_front(); |
| } |
| if (I3) { |
| EXPECT_EQ(L->front(), I3); |
| L->pop_front(); |
| } |
| if (I4) { |
| EXPECT_EQ(L->front(), I4); |
| L->pop_front(); |
| } |
| if (I5) { |
| EXPECT_EQ(L->front(), I5); |
| L->pop_front(); |
| } |
| if (I6) { |
| EXPECT_EQ(L->front(), I6); |
| L->pop_front(); |
| } |
| EXPECT_TRUE(L->empty()); |
| } |
| |
| TEST(ScudoListTest, IntrusiveList) { |
| ListItem Items[6]; |
| EXPECT_EQ(StaticList.size(), 0U); |
| |
| List L; |
| L.clear(); |
| |
| ListItem *X = &Items[0]; |
| ListItem *Y = &Items[1]; |
| ListItem *Z = &Items[2]; |
| ListItem *A = &Items[3]; |
| ListItem *B = &Items[4]; |
| ListItem *C = &Items[5]; |
| |
| EXPECT_EQ(L.size(), 0U); |
| L.push_back(X); |
| EXPECT_EQ(L.size(), 1U); |
| EXPECT_EQ(L.back(), X); |
| EXPECT_EQ(L.front(), X); |
| L.pop_front(); |
| EXPECT_TRUE(L.empty()); |
| L.checkConsistency(); |
| |
| L.push_front(X); |
| EXPECT_EQ(L.size(), 1U); |
| EXPECT_EQ(L.back(), X); |
| EXPECT_EQ(L.front(), X); |
| L.pop_front(); |
| EXPECT_TRUE(L.empty()); |
| L.checkConsistency(); |
| |
| L.push_front(X); |
| L.push_front(Y); |
| L.push_front(Z); |
| EXPECT_EQ(L.size(), 3U); |
| EXPECT_EQ(L.front(), Z); |
| EXPECT_EQ(L.back(), X); |
| L.checkConsistency(); |
| |
| L.pop_front(); |
| EXPECT_EQ(L.size(), 2U); |
| EXPECT_EQ(L.front(), Y); |
| EXPECT_EQ(L.back(), X); |
| L.pop_front(); |
| L.pop_front(); |
| EXPECT_TRUE(L.empty()); |
| L.checkConsistency(); |
| |
| L.push_back(X); |
| L.push_back(Y); |
| L.push_back(Z); |
| EXPECT_EQ(L.size(), 3U); |
| EXPECT_EQ(L.front(), X); |
| EXPECT_EQ(L.back(), Z); |
| L.checkConsistency(); |
| |
| L.pop_front(); |
| EXPECT_EQ(L.size(), 2U); |
| EXPECT_EQ(L.front(), Y); |
| EXPECT_EQ(L.back(), Z); |
| L.pop_front(); |
| L.pop_front(); |
| EXPECT_TRUE(L.empty()); |
| L.checkConsistency(); |
| |
| L.push_back(X); |
| L.push_back(Y); |
| L.push_back(Z); |
| L.extract(X, Y); |
| EXPECT_EQ(L.size(), 2U); |
| EXPECT_EQ(L.front(), X); |
| EXPECT_EQ(L.back(), Z); |
| L.checkConsistency(); |
| L.extract(X, Z); |
| EXPECT_EQ(L.size(), 1U); |
| EXPECT_EQ(L.front(), X); |
| EXPECT_EQ(L.back(), X); |
| L.checkConsistency(); |
| L.pop_front(); |
| EXPECT_TRUE(L.empty()); |
| |
| List L1, L2; |
| L1.clear(); |
| L2.clear(); |
| |
| L1.append_front(&L2); |
| EXPECT_TRUE(L1.empty()); |
| EXPECT_TRUE(L2.empty()); |
| |
| L1.append_back(&L2); |
| EXPECT_TRUE(L1.empty()); |
| EXPECT_TRUE(L2.empty()); |
| |
| setList(&L1, X); |
| checkList(&L1, X); |
| |
| setList(&L1, X, Y, Z); |
| setList(&L2, A, B, C); |
| L1.append_back(&L2); |
| checkList(&L1, X, Y, Z, A, B, C); |
| EXPECT_TRUE(L2.empty()); |
| |
| setList(&L1, X, Y); |
| setList(&L2); |
| L1.append_front(&L2); |
| checkList(&L1, X, Y); |
| EXPECT_TRUE(L2.empty()); |
| } |
| |
| TEST(ScudoListTest, IntrusiveListAppendEmpty) { |
| ListItem I; |
| List L; |
| L.clear(); |
| L.push_back(&I); |
| List L2; |
| L2.clear(); |
| L.append_back(&L2); |
| EXPECT_EQ(L.back(), &I); |
| EXPECT_EQ(L.front(), &I); |
| EXPECT_EQ(L.size(), 1U); |
| L.append_front(&L2); |
| EXPECT_EQ(L.back(), &I); |
| EXPECT_EQ(L.front(), &I); |
| EXPECT_EQ(L.size(), 1U); |
| } |