[libc] implement insque and remque (#80305)

This PR implements the `insque` and `remque` entrypoint functions.

14 files changed, 393 insertions, 2 deletions

diff --git a/libc/config/linux/aarch64/entrypoints.txt b/libc/config/linux/aarch64/entrypoints.txt
index 12c5351..1ff9c90 100644
--- a/libc/config/linux/aarch64/entrypoints.txt
+++ b/libc/config/linux/aarch64/entrypoints.txt
@@ -496,6 +496,8 @@ if(LLVM_LIBC_FULL_BUILD)
     libc.src.search.hsearch_r
     libc.src.search.hdestroy
     libc.src.search.hdestroy_r
+    libc.src.search.insque
+    libc.src.search.remque
 
     # threads.h entrypoints
     libc.src.threads.call_once
diff --git a/libc/config/linux/riscv/entrypoints.txt b/libc/config/linux/riscv/entrypoints.txt
index e2a3860..7473ac8 100644
--- a/libc/config/linux/riscv/entrypoints.txt
+++ b/libc/config/linux/riscv/entrypoints.txt
@@ -522,6 +522,8 @@ if(LLVM_LIBC_FULL_BUILD)
     libc.src.search.hsearch_r
     libc.src.search.hdestroy
     libc.src.search.hdestroy_r
+    libc.src.search.insque
+    libc.src.search.remque
 
     # threads.h entrypoints
     libc.src.threads.call_once
diff --git a/libc/config/linux/x86_64/entrypoints.txt b/libc/config/linux/x86_64/entrypoints.txt
index e3ed5db..a123681 100644
--- a/libc/config/linux/x86_64/entrypoints.txt
+++ b/libc/config/linux/x86_64/entrypoints.txt
@@ -546,6 +546,8 @@ if(LLVM_LIBC_FULL_BUILD)
     libc.src.search.hsearch_r
     libc.src.search.hdestroy
     libc.src.search.hdestroy_r
+    libc.src.search.insque
+    libc.src.search.remque
 
     # threads.h entrypoints
     libc.src.threads.call_once
diff --git a/libc/docs/libc_search.rst b/libc/docs/libc_search.rst
index ff6a419..605efa8 100644
--- a/libc/docs/libc_search.rst
+++ b/libc/docs/libc_search.rst
@@ -41,10 +41,10 @@ Function Name                Available
 hcreate                      |check|
 hdestroy                     |check|
 hsearch                      |check|
-insque                       
+insque                       |check|
 lfind                        
 lsearch                      
-remque
+remque                       |check|
 tdelete
 tfind
 tsearch
diff --git a/libc/spec/posix.td b/libc/spec/posix.td
index 40a663a..92d0f8e 100644
--- a/libc/spec/posix.td
+++ b/libc/spec/posix.td
@@ -1323,6 +1323,21 @@ def POSIX : StandardSpec<"POSIX"> {
                 ArgSpec<ActionType>
             ]
         >,
+        FunctionSpec<
+            "insque",
+            RetValSpec<VoidType>,
+            [
+                ArgSpec<VoidPtr>,
+                ArgSpec<VoidPtr>
+            ]
+        >,
+        FunctionSpec<
+            "remque",
+            RetValSpec<VoidType>,
+            [
+                ArgSpec<VoidPtr>
+            ]
+        >,
     ]
   >; 
 
diff --git a/libc/src/__support/CMakeLists.txt b/libc/src/__support/CMakeLists.txt
index 5951247..bd814a0 100644
--- a/libc/src/__support/CMakeLists.txt
+++ b/libc/src/__support/CMakeLists.txt
@@ -250,6 +250,14 @@ add_header_library(
     libc.src.__support.macros.config
 )
 
+add_header_library(
+  intrusive_list
+  HDRS
+    intrusive_list.h
+  DEPENDS
+    libc.src.__support.macros.attributes
+)
+
 add_subdirectory(FPUtil)
 add_subdirectory(OSUtil)
 add_subdirectory(StringUtil)
diff --git a/libc/src/__support/intrusive_list.h b/libc/src/__support/intrusive_list.h
new file mode 100644
index 0000000..69be877
--- /dev/null
+++ b/libc/src/__support/intrusive_list.h
@@ -0,0 +1,65 @@
+//===-- Intrusive queue implementation. -------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// An intrusive list that implements the insque and remque semantics.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC___SUPPORT_INTRUSIVE_LIST_H
+#define LLVM_LIBC_SRC___SUPPORT_INTRUSIVE_LIST_H
+
+#include "common.h"
+
+namespace LIBC_NAMESPACE {
+namespace internal {
+
+class IntrusiveList {
+  struct IntrusiveNodeHeader {
+    IntrusiveNodeHeader *next;
+    IntrusiveNodeHeader *prev;
+  };
+
+public:
+  LIBC_INLINE static void insert(void *elem, void *prev) {
+    auto elem_header = static_cast<IntrusiveNodeHeader *>(elem);
+    auto prev_header = static_cast<IntrusiveNodeHeader *>(prev);
+
+    if (!prev_header) {
+      // The list is linear and elem will be the only element.
+      elem_header->next = nullptr;
+      elem_header->prev = nullptr;
+      return;
+    }
+
+    auto next = prev_header->next;
+
+    elem_header->next = next;
+    elem_header->prev = prev_header;
+
+    prev_header->next = elem_header;
+    if (next)
+      next->prev = elem_header;
+  }
+
+  LIBC_INLINE static void remove(void *elem) {
+    auto elem_header = static_cast<IntrusiveNodeHeader *>(elem);
+
+    auto prev = elem_header->prev;
+    auto next = elem_header->next;
+
+    if (prev)
+      prev->next = next;
+    if (next)
+      next->prev = prev;
+  }
+};
+
+} // namespace internal
+} // namespace LIBC_NAMESPACE
+
+#endif // LLVM_LIBC_SRC___SUPPORT_INTRUSIVE_LIST_H
diff --git a/libc/src/search/CMakeLists.txt b/libc/src/search/CMakeLists.txt
index 24a4ba6..46ad3e3 100644
--- a/libc/src/search/CMakeLists.txt
+++ b/libc/src/search/CMakeLists.txt
@@ -76,3 +76,25 @@ add_entrypoint_object(
     libc.src.__support.HashTable.table
     libc.include.search
 )
+
+add_entrypoint_object(
+  insque
+  SRCS
+    insque.cpp
+  HDRS
+    insque.h
+  DEPENDS
+    libc.include.search
+    libc.src.__support.intrusive_list
+)
+
+add_entrypoint_object(
+  remque
+  SRCS
+    remque.cpp
+  HDRS
+    remque.h
+  DEPENDS
+    libc.include.search
+    libc.src.__support.intrusive_list
+)
diff --git a/libc/src/search/insque.cpp b/libc/src/search/insque.cpp
new file mode 100644
index 0000000..7b7d7c7
--- /dev/null
+++ b/libc/src/search/insque.cpp
@@ -0,0 +1,19 @@
+//===-- Implementation of insque --------------------------------*- C++ -*-===//
+//
+// 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/__support/common.h"
+#include "src/__support/intrusive_list.h"
+
+namespace LIBC_NAMESPACE {
+
+LLVM_LIBC_FUNCTION(void, insque, (void *elem, void *prev)) {
+  internal::IntrusiveList::insert(elem, prev);
+}
+
+} // namespace LIBC_NAMESPACE
diff --git a/libc/src/search/insque.h b/libc/src/search/insque.h
new file mode 100644
index 0000000..e0fb69e
--- /dev/null
+++ b/libc/src/search/insque.h
@@ -0,0 +1,20 @@
+//===-- Implementation header for insque ------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_INSQUE_H
+#define LLVM_LIBC_SRC_SEARCH_INSQUE_H
+
+#include <search.h>
+
+namespace LIBC_NAMESPACE {
+
+void insque(void *elem, void *prev);
+
+} // namespace LIBC_NAMESPACE
+
+#endif // LLVM_LIBC_SRC_SEARCH_INSQUE_H
diff --git a/libc/src/search/remque.cpp b/libc/src/search/remque.cpp
new file mode 100644
index 0000000..f1d9859
--- /dev/null
+++ b/libc/src/search/remque.cpp
@@ -0,0 +1,19 @@
+//===-- Implementation of remque --------------------------------*- C++ -*-===//
+//
+// 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/remque.h"
+#include "src/__support/common.h"
+#include "src/__support/intrusive_list.h"
+
+namespace LIBC_NAMESPACE {
+
+LLVM_LIBC_FUNCTION(void, remque, (void *elem)) {
+  internal::IntrusiveList::remove(elem);
+}
+
+} // namespace LIBC_NAMESPACE
diff --git a/libc/src/search/remque.h b/libc/src/search/remque.h
new file mode 100644
index 0000000..51f225c
--- /dev/null
+++ b/libc/src/search/remque.h
@@ -0,0 +1,20 @@
+//===-- Implementation header for remque ------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_REMQUE_H
+#define LLVM_LIBC_SRC_SEARCH_REMQUE_H
+
+#include <search.h>
+
+namespace LIBC_NAMESPACE {
+
+void remque(void *elem);
+
+} // namespace LIBC_NAMESPACE
+
+#endif // LLVM_LIBC_SRC_SEARCH_REMQUE_H
diff --git a/libc/test/src/search/CMakeLists.txt b/libc/test/src/search/CMakeLists.txt
index d624f14..8a33edc 100644
--- a/libc/test/src/search/CMakeLists.txt
+++ b/libc/test/src/search/CMakeLists.txt
@@ -14,3 +14,14 @@ add_libc_unittest(
     libc.src.search.hdestroy
     libc.src.errno.errno
 )
+
+add_libc_unittest(
+  insque_test
+  SUITE
+    libc_search_unittests
+  SRCS
+    insque_test.cpp
+  DEPENDS
+    libc.src.search.insque
+    libc.src.search.remque
+)
diff --git a/libc/test/src/search/insque_test.cpp b/libc/test/src/search/insque_test.cpp
new file mode 100644
index 0000000..8aab53c
--- /dev/null
+++ b/libc/test/src/search/insque_test.cpp
@@ -0,0 +1,186 @@
+//===-- 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]});
+}