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
13namespace {
14
15struct Node {
16 Node *next;
17 Node *prev;
18};
19
20template <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
34template <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
43class LlvmLibcInsqueTest : public LIBC_NAMESPACE::testing::Test {
44protected:
45 template <unsigned 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>
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
91TEST_F(LlvmLibcInsqueTest, InsertToNull) {
92 Node node{.next: nullptr, .prev: nullptr};
93 LIBC_NAMESPACE::insque(elem: &node, prev: nullptr);
94 check_linear(head: &node, nodes: {&node});
95}
96
97TEST_F(LlvmLibcInsqueTest, InsertToLinearSingleton) {
98 Node base[1];
99 make_linear_links(nodes&: base);
100
101 Node incoming{.next: nullptr, .prev: nullptr};
102 LIBC_NAMESPACE::insque(elem: &incoming, prev: &base[0]);
103 check_linear(head: base, nodes: {&base[0], &incoming});
104}
105
106TEST_F(LlvmLibcInsqueTest, InsertToLinearMiddle) {
107 Node base[3];
108 make_linear_links(nodes&: base);
109
110 Node incoming{.next: nullptr, .prev: nullptr};
111 LIBC_NAMESPACE::insque(elem: &incoming, prev: &base[1]);
112 check_linear(head: base, nodes: {&base[0], &base[1], &incoming, &base[2]});
113}
114
115TEST_F(LlvmLibcInsqueTest, InsertToLinearBack) {
116 Node base[3];
117 make_linear_links(nodes&: base);
118
119 Node incoming{.next: nullptr, .prev: nullptr};
120 LIBC_NAMESPACE::insque(elem: &incoming, prev: &base[2]);
121 check_linear(head: base, nodes: {&base[0], &base[1], &base[2], &incoming});
122}
123
124TEST_F(LlvmLibcInsqueTest, InsertToCircularSingleton) {
125 Node base[1];
126 make_circular_links(nodes&: base);
127
128 Node incoming{.next: nullptr, .prev: nullptr};
129 LIBC_NAMESPACE::insque(elem: &incoming, prev: &base[0]);
130 check_circular(head: base, nodes: {&base[0], &incoming});
131}
132
133TEST_F(LlvmLibcInsqueTest, InsertToCircular) {
134 Node base[3];
135 make_circular_links(nodes&: base);
136
137 Node incoming{.next: nullptr, .prev: nullptr};
138 LIBC_NAMESPACE::insque(elem: &incoming, prev: &base[1]);
139 check_circular(head: base, nodes: {&base[0], &base[1], &incoming, &base[2]});
140}
141
142TEST_F(LlvmLibcInsqueTest, RemoveFromLinearSingleton) {
143 Node node{.next: nullptr, .prev: nullptr};
144 LIBC_NAMESPACE::remque(elem: &node);
145 ASSERT_EQ(node.next, static_cast<Node *>(nullptr));
146 ASSERT_EQ(node.prev, static_cast<Node *>(nullptr));
147}
148
149TEST_F(LlvmLibcInsqueTest, RemoveFromLinearFront) {
150 Node base[3];
151 make_linear_links(nodes&: base);
152
153 LIBC_NAMESPACE::remque(elem: &base[0]);
154 check_linear(head: &base[1], nodes: {&base[1], &base[2]});
155}
156
157TEST_F(LlvmLibcInsqueTest, RemoveFromLinearMiddle) {
158 Node base[3];
159 make_linear_links(nodes&: base);
160
161 LIBC_NAMESPACE::remque(elem: &base[1]);
162 check_linear(head: &base[0], nodes: {&base[0], &base[2]});
163}
164
165TEST_F(LlvmLibcInsqueTest, RemoveFromLinearBack) {
166 Node base[3];
167 make_linear_links(nodes&: base);
168
169 LIBC_NAMESPACE::remque(elem: &base[2]);
170 check_linear(head: &base[0], nodes: {&base[0], &base[1]});
171}
172
173TEST_F(LlvmLibcInsqueTest, RemoveFromCircularSingleton) {
174 Node node[1];
175 make_circular_links(nodes&: node);
176
177 LIBC_NAMESPACE::remque(elem: &node[0]);
178}
179
180TEST_F(LlvmLibcInsqueTest, RemoveFromCircular) {
181 Node base[3];
182 make_circular_links(nodes&: base);
183
184 LIBC_NAMESPACE::remque(elem: &base[1]);
185 check_circular(head: &base[0], nodes: {&base[0], &base[2]});
186}
187

source code of libc/test/src/search/insque_test.cpp