187 lines · cpp
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-exception6//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 else25 nodes[i].next = &nodes[i + 1];26 27 if (i == 0)28 nodes[i].prev = nullptr;29 else30 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} // namespace42 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 confirmed65 // 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 confirmed85 // the validity of links.86 head = head->next;87 }88 }89};90 91TEST_F(LlvmLibcInsqueTest, InsertToNull) {92 Node node{nullptr, nullptr};93 LIBC_NAMESPACE::insque(&node, nullptr);94 check_linear(&node, {&node});95}96 97TEST_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 106TEST_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 115TEST_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 124TEST_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 133TEST_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 142TEST_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 149TEST_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 157TEST_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 165TEST_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 173TEST_F(LlvmLibcInsqueTest, RemoveFromCircularSingleton) {174 Node node[1];175 make_circular_links(node);176 177 LIBC_NAMESPACE::remque(&node[0]);178}179 180TEST_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