1 /*
2 * Copyright (C) 2022 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "chre/util/intrusive_list.h"
18
19 #include "gtest/gtest.h"
20
21 using chre::IntrusiveList;
22 using chre::ListNode;
23
TEST(IntrusiveList,EmptyByDefault)24 TEST(IntrusiveList, EmptyByDefault) {
25 IntrusiveList<int> testLinkedList;
26 EXPECT_EQ(testLinkedList.size(), 0);
27 EXPECT_TRUE(testLinkedList.empty());
28 }
29
TEST(IntrusiveList,PushReadAndPop)30 TEST(IntrusiveList, PushReadAndPop) {
31 typedef ListNode<int> ListIntNode;
32
33 ListIntNode nodeA(0);
34 ListIntNode nodeB(1);
35 ListIntNode nodeC(2);
36 ListIntNode nodeD(3);
37 IntrusiveList<int> testLinkedList;
38
39 testLinkedList.link_back(&nodeB);
40 testLinkedList.link_back(&nodeC);
41 testLinkedList.link_front(&nodeA);
42 EXPECT_EQ(testLinkedList.size(), 3);
43
44 EXPECT_EQ(testLinkedList.front().item, nodeA.item);
45 EXPECT_EQ(testLinkedList.back().item, nodeC.item);
46
47 testLinkedList.unlink_front();
48 EXPECT_EQ(testLinkedList.size(), 2);
49 EXPECT_EQ(testLinkedList.front().item, nodeB.item);
50
51 testLinkedList.unlink_back();
52 EXPECT_EQ(testLinkedList.size(), 1);
53 EXPECT_EQ(testLinkedList.back().item, nodeB.item);
54
55 testLinkedList.unlink_back();
56 EXPECT_EQ(testLinkedList.size(), 0);
57 EXPECT_TRUE(testLinkedList.empty());
58
59 testLinkedList.link_back(&nodeD);
60 EXPECT_EQ(testLinkedList.size(), 1);
61 EXPECT_EQ(testLinkedList.back().item, nodeD.item);
62 EXPECT_EQ(testLinkedList.front().item, nodeD.item);
63 }
64
TEST(IntrusiveList,CatchInvalidCallToEmptyList)65 TEST(IntrusiveList, CatchInvalidCallToEmptyList) {
66 IntrusiveList<int> testList;
67 ASSERT_DEATH(testList.front(), "");
68 ASSERT_DEATH(testList.back(), "");
69 ASSERT_DEATH(testList.unlink_front(), "");
70 ASSERT_DEATH(testList.unlink_back(), "");
71 }
72
TEST(IntrusiveList,DestructorCleanUpLink)73 TEST(IntrusiveList, DestructorCleanUpLink) {
74 typedef ListNode<int> ListIntNode;
75
76 ListIntNode testInput[]{
77 ListIntNode(0), ListIntNode(1), ListIntNode(2),
78 ListIntNode(3), ListIntNode(4),
79 };
80
81 {
82 IntrusiveList<int> testLinkedList;
83 for (auto &node : testInput) {
84 testLinkedList.link_back(&node);
85 }
86
87 int idx = 0;
88 for (auto const &node : testLinkedList) {
89 EXPECT_EQ(node.item, idx++);
90 }
91 }
92
93 for (auto &node : testInput) {
94 EXPECT_EQ(node.node.next, nullptr);
95 EXPECT_EQ(node.node.prev, nullptr);
96 }
97 }
98
TEST(IntrusiveList,AccessMiddleTest)99 TEST(IntrusiveList, AccessMiddleTest) {
100 typedef ListNode<int> ListIntNode;
101
102 ListIntNode testListIntNodes[]{
103 ListIntNode(0), ListIntNode(1), ListIntNode(2),
104 ListIntNode(3), ListIntNode(4),
105 };
106
107 IntrusiveList<int> testLinkedList;
108
109 for (auto &node : testListIntNodes) {
110 testLinkedList.link_back(&node);
111 }
112
113 testLinkedList.unlink_node(&testListIntNodes[1]); // removes ListIntNode(1)
114 EXPECT_EQ(testListIntNodes[0].node.next, &testListIntNodes[2].node);
115 EXPECT_EQ(testLinkedList.size(), 4);
116
117 testLinkedList.link_after(&testListIntNodes[0],
118 &testListIntNodes[1]); // add back ListIntNode(1)
119 EXPECT_EQ(testListIntNodes[0].node.next, &testListIntNodes[1].node);
120 EXPECT_EQ(testLinkedList.size(), 5);
121 }
122
TEST(IntrusiveList,LinkFront)123 TEST(IntrusiveList, LinkFront) {
124 typedef ListNode<int> ListIntNode;
125 ListIntNode nodeA(0);
126 ListIntNode nodeB(1);
127
128 IntrusiveList<int> testLinkedList;
129 testLinkedList.link_front(&nodeA);
130 EXPECT_EQ(testLinkedList.size(), 1);
131 EXPECT_EQ(testLinkedList.front().item, nodeA.item);
132 EXPECT_EQ(testLinkedList.back().item, nodeA.item);
133
134 testLinkedList.link_front(&nodeB);
135 EXPECT_EQ(testLinkedList.size(), 2);
136 EXPECT_EQ(testLinkedList.front().item, nodeB.item);
137 EXPECT_EQ(testLinkedList.back().item, nodeA.item);
138 EXPECT_EQ(nodeB.node.next, &nodeA.node);
139 EXPECT_EQ(nodeA.node.prev, &nodeB.node);
140 }
141