1 //===-- Unittests for insque ----------------------------------------------===//
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 "src/search/insque.h"
10 #include "src/search/remque.h"
11 #include "test/UnitTest/Test.h"
12
13 namespace {
14
15 struct Node {
16 Node *next;
17 Node *prev;
18 };
19
make_linear_links(Node (& nodes)[N])20 template <unsigned N> void make_linear_links(Node (&nodes)[N]) {
21 for (unsigned i = 0; i < N; ++i) {
22 if (i == N - 1)
23 nodes[i].next = nullptr;
24 else
25 nodes[i].next = &nodes[i + 1];
26
27 if (i == 0)
28 nodes[i].prev = nullptr;
29 else
30 nodes[i].prev = &nodes[i - 1];
31 }
32 }
33
make_circular_links(Node (& nodes)[N])34 template <unsigned N> void make_circular_links(Node (&nodes)[N]) {
35 for (unsigned i = 0; i < N; ++i) {
36 nodes[i].next = &nodes[(i + 1) % N];
37 nodes[i].prev = &nodes[(i + N - 1) % N];
38 }
39 }
40
41 } // namespace
42
43 class LlvmLibcInsqueTest : public LIBC_NAMESPACE::testing::Test {
44 protected:
45 template <unsigned N>
check_linear(const Node * head,const Node * const (& nodes)[N])46 void check_linear(const Node *head, const Node *const (&nodes)[N]) {
47 // First make sure that the given N nodes form a valid linear list.
48 for (unsigned i = 0; i < N; ++i) {
49 const Node *next = nullptr;
50 if (i + 1 < N)
51 next = nodes[i + 1];
52
53 const Node *prev = nullptr;
54 if (i > 0)
55 prev = nodes[i - 1];
56
57 EXPECT_EQ(static_cast<const Node *>(nodes[i]->next), next);
58 EXPECT_EQ(static_cast<const Node *>(nodes[i]->prev), prev);
59 }
60
61 // Then check the list nodes match.
62 for (unsigned i = 0; i < N; ++i) {
63 EXPECT_EQ(head, nodes[i]);
64 // Traversal by head should always be OK since we have already confirmed
65 // the validity of links.
66 head = head->next;
67 }
68 }
69
70 template <unsigned N>
check_circular(const Node * head,const Node * const (& nodes)[N])71 void check_circular(const Node *head, const Node *const (&nodes)[N]) {
72 // First make sure that the given N nodes form a valid linear list.
73 for (unsigned i = 0; i < N; ++i) {
74 auto next = nodes[(i + 1) % N];
75 auto prev = nodes[(i + N - 1) % N];
76
77 EXPECT_EQ(static_cast<const Node *>(nodes[i]->prev), prev);
78 EXPECT_EQ(static_cast<const Node *>(nodes[i]->next), next);
79 }
80
81 // Then check the list nodes match.
82 for (unsigned i = 0; i < N; ++i) {
83 EXPECT_EQ(head, nodes[i]);
84 // Traversal by head should always be OK since we have already confirmed
85 // the validity of links.
86 head = head->next;
87 }
88 }
89 };
90
TEST_F(LlvmLibcInsqueTest,InsertToNull)91 TEST_F(LlvmLibcInsqueTest, InsertToNull) {
92 Node node{nullptr, nullptr};
93 LIBC_NAMESPACE::insque(&node, nullptr);
94 check_linear(&node, {&node});
95 }
96
TEST_F(LlvmLibcInsqueTest,InsertToLinearSingleton)97 TEST_F(LlvmLibcInsqueTest, InsertToLinearSingleton) {
98 Node base[1];
99 make_linear_links(base);
100
101 Node incoming{nullptr, nullptr};
102 LIBC_NAMESPACE::insque(&incoming, &base[0]);
103 check_linear(base, {&base[0], &incoming});
104 }
105
TEST_F(LlvmLibcInsqueTest,InsertToLinearMiddle)106 TEST_F(LlvmLibcInsqueTest, InsertToLinearMiddle) {
107 Node base[3];
108 make_linear_links(base);
109
110 Node incoming{nullptr, nullptr};
111 LIBC_NAMESPACE::insque(&incoming, &base[1]);
112 check_linear(base, {&base[0], &base[1], &incoming, &base[2]});
113 }
114
TEST_F(LlvmLibcInsqueTest,InsertToLinearBack)115 TEST_F(LlvmLibcInsqueTest, InsertToLinearBack) {
116 Node base[3];
117 make_linear_links(base);
118
119 Node incoming{nullptr, nullptr};
120 LIBC_NAMESPACE::insque(&incoming, &base[2]);
121 check_linear(base, {&base[0], &base[1], &base[2], &incoming});
122 }
123
TEST_F(LlvmLibcInsqueTest,InsertToCircularSingleton)124 TEST_F(LlvmLibcInsqueTest, InsertToCircularSingleton) {
125 Node base[1];
126 make_circular_links(base);
127
128 Node incoming{nullptr, nullptr};
129 LIBC_NAMESPACE::insque(&incoming, &base[0]);
130 check_circular(base, {&base[0], &incoming});
131 }
132
TEST_F(LlvmLibcInsqueTest,InsertToCircular)133 TEST_F(LlvmLibcInsqueTest, InsertToCircular) {
134 Node base[3];
135 make_circular_links(base);
136
137 Node incoming{nullptr, nullptr};
138 LIBC_NAMESPACE::insque(&incoming, &base[1]);
139 check_circular(base, {&base[0], &base[1], &incoming, &base[2]});
140 }
141
TEST_F(LlvmLibcInsqueTest,RemoveFromLinearSingleton)142 TEST_F(LlvmLibcInsqueTest, RemoveFromLinearSingleton) {
143 Node node{nullptr, nullptr};
144 LIBC_NAMESPACE::remque(&node);
145 ASSERT_EQ(node.next, static_cast<Node *>(nullptr));
146 ASSERT_EQ(node.prev, static_cast<Node *>(nullptr));
147 }
148
TEST_F(LlvmLibcInsqueTest,RemoveFromLinearFront)149 TEST_F(LlvmLibcInsqueTest, RemoveFromLinearFront) {
150 Node base[3];
151 make_linear_links(base);
152
153 LIBC_NAMESPACE::remque(&base[0]);
154 check_linear(&base[1], {&base[1], &base[2]});
155 }
156
TEST_F(LlvmLibcInsqueTest,RemoveFromLinearMiddle)157 TEST_F(LlvmLibcInsqueTest, RemoveFromLinearMiddle) {
158 Node base[3];
159 make_linear_links(base);
160
161 LIBC_NAMESPACE::remque(&base[1]);
162 check_linear(&base[0], {&base[0], &base[2]});
163 }
164
TEST_F(LlvmLibcInsqueTest,RemoveFromLinearBack)165 TEST_F(LlvmLibcInsqueTest, RemoveFromLinearBack) {
166 Node base[3];
167 make_linear_links(base);
168
169 LIBC_NAMESPACE::remque(&base[2]);
170 check_linear(&base[0], {&base[0], &base[1]});
171 }
172
TEST_F(LlvmLibcInsqueTest,RemoveFromCircularSingleton)173 TEST_F(LlvmLibcInsqueTest, RemoveFromCircularSingleton) {
174 Node node[1];
175 make_circular_links(node);
176
177 LIBC_NAMESPACE::remque(&node[0]);
178 }
179
TEST_F(LlvmLibcInsqueTest,RemoveFromCircular)180 TEST_F(LlvmLibcInsqueTest, RemoveFromCircular) {
181 Node base[3];
182 make_circular_links(base);
183
184 LIBC_NAMESPACE::remque(&base[1]);
185 check_circular(&base[0], {&base[0], &base[2]});
186 }
187