//===-- Unittests for insque ----------------------------------------------===//
//
// 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 "src/search/insque.h"
#include "src/search/remque.h"
#include "test/UnitTest/Test.h"

namespace {

struct Node {
  Node *next;
  Node *prev;
};

template <unsigned N> void make_linear_links(Node (&nodes)[N]) {
  for (unsigned i = 0; i < N; ++i) {
    if (i == N - 1)
      nodes[i].next = nullptr;
    else
      nodes[i].next = &nodes[i + 1];

    if (i == 0)
      nodes[i].prev = nullptr;
    else
      nodes[i].prev = &nodes[i - 1];
  }
}

template <unsigned N> void make_circular_links(Node (&nodes)[N]) {
  for (unsigned i = 0; i < N; ++i) {
    nodes[i].next = &nodes[(i + 1) % N];
    nodes[i].prev = &nodes[(i + N - 1) % N];
  }
}

} // namespace

class LlvmLibcInsqueTest : public LIBC_NAMESPACE::testing::Test {
protected:
  template <unsigned N>
  void check_linear(const Node *head, const Node *const (&nodes)[N]) {
    // First make sure that the given N nodes form a valid linear list.
    for (unsigned i = 0; i < N; ++i) {
      const Node *next = nullptr;
      if (i + 1 < N)
        next = nodes[i + 1];

      const Node *prev = nullptr;
      if (i > 0)
        prev = nodes[i - 1];

      EXPECT_EQ(static_cast<const Node *>(nodes[i]->next), next);
      EXPECT_EQ(static_cast<const Node *>(nodes[i]->prev), prev);
    }

    // Then check the list nodes match.
    for (unsigned i = 0; i < N; ++i) {
      EXPECT_EQ(head, nodes[i]);
      // Traversal by head should always be OK since we have already confirmed
      // the validity of links.
      head = head->next;
    }
  }

  template <unsigned N>
  void check_circular(const Node *head, const Node *const (&nodes)[N]) {
    // First make sure that the given N nodes form a valid linear list.
    for (unsigned i = 0; i < N; ++i) {
      auto next = nodes[(i + 1) % N];
      auto prev = nodes[(i + N - 1) % N];

      EXPECT_EQ(static_cast<const Node *>(nodes[i]->prev), prev);
      EXPECT_EQ(static_cast<const Node *>(nodes[i]->next), next);
    }

    // Then check the list nodes match.
    for (unsigned i = 0; i < N; ++i) {
      EXPECT_EQ(head, nodes[i]);
      // Traversal by head should always be OK since we have already confirmed
      // the validity of links.
      head = head->next;
    }
  }
};

TEST_F(LlvmLibcInsqueTest, InsertToNull) {
  Node node{nullptr, nullptr};
  LIBC_NAMESPACE::insque(&node, nullptr);
  check_linear(&node, {&node});
}

TEST_F(LlvmLibcInsqueTest, InsertToLinearSingleton) {
  Node base[1];
  make_linear_links(base);

  Node incoming{nullptr, nullptr};
  LIBC_NAMESPACE::insque(&incoming, &base[0]);
  check_linear(base, {&base[0], &incoming});
}

TEST_F(LlvmLibcInsqueTest, InsertToLinearMiddle) {
  Node base[3];
  make_linear_links(base);

  Node incoming{nullptr, nullptr};
  LIBC_NAMESPACE::insque(&incoming, &base[1]);
  check_linear(base, {&base[0], &base[1], &incoming, &base[2]});
}

TEST_F(LlvmLibcInsqueTest, InsertToLinearBack) {
  Node base[3];
  make_linear_links(base);

  Node incoming{nullptr, nullptr};
  LIBC_NAMESPACE::insque(&incoming, &base[2]);
  check_linear(base, {&base[0], &base[1], &base[2], &incoming});
}

TEST_F(LlvmLibcInsqueTest, InsertToCircularSingleton) {
  Node base[1];
  make_circular_links(base);

  Node incoming{nullptr, nullptr};
  LIBC_NAMESPACE::insque(&incoming, &base[0]);
  check_circular(base, {&base[0], &incoming});
}

TEST_F(LlvmLibcInsqueTest, InsertToCircular) {
  Node base[3];
  make_circular_links(base);

  Node incoming{nullptr, nullptr};
  LIBC_NAMESPACE::insque(&incoming, &base[1]);
  check_circular(base, {&base[0], &base[1], &incoming, &base[2]});
}

TEST_F(LlvmLibcInsqueTest, RemoveFromLinearSingleton) {
  Node node{nullptr, nullptr};
  LIBC_NAMESPACE::remque(&node);
  ASSERT_EQ(node.next, static_cast<Node *>(nullptr));
  ASSERT_EQ(node.prev, static_cast<Node *>(nullptr));
}

TEST_F(LlvmLibcInsqueTest, RemoveFromLinearFront) {
  Node base[3];
  make_linear_links(base);

  LIBC_NAMESPACE::remque(&base[0]);
  check_linear(&base[1], {&base[1], &base[2]});
}

TEST_F(LlvmLibcInsqueTest, RemoveFromLinearMiddle) {
  Node base[3];
  make_linear_links(base);

  LIBC_NAMESPACE::remque(&base[1]);
  check_linear(&base[0], {&base[0], &base[2]});
}

TEST_F(LlvmLibcInsqueTest, RemoveFromLinearBack) {
  Node base[3];
  make_linear_links(base);

  LIBC_NAMESPACE::remque(&base[2]);
  check_linear(&base[0], {&base[0], &base[1]});
}

TEST_F(LlvmLibcInsqueTest, RemoveFromCircularSingleton) {
  Node node[1];
  make_circular_links(node);

  LIBC_NAMESPACE::remque(&node[0]);
}

TEST_F(LlvmLibcInsqueTest, RemoveFromCircular) {
  Node base[3];
  make_circular_links(base);

  LIBC_NAMESPACE::remque(&base[1]);
  check_circular(&base[0], {&base[0], &base[2]});
}