From 8db1fb76584a22ec4f93da1b52b3ff63a8e21c96 Mon Sep 17 00:00:00 2001
From: "Luke T. Shumaker" <lukeshu@lukeshu.com>
Date: Fri, 11 Apr 2025 07:21:28 -0600
Subject: Move the linkedlist to libmisc

---
 libmisc/CMakeLists.txt               |  1 +
 libmisc/include/libmisc/linkedlist.h | 57 +++++++++++++++++++++++++++++++++
 libmisc/linkedlist.c                 | 62 ++++++++++++++++++++++++++++++++++++
 3 files changed, 120 insertions(+)
 create mode 100644 libmisc/include/libmisc/linkedlist.h
 create mode 100644 libmisc/linkedlist.c

(limited to 'libmisc')

diff --git a/libmisc/CMakeLists.txt b/libmisc/CMakeLists.txt
index 4599ead..c80e060 100644
--- a/libmisc/CMakeLists.txt
+++ b/libmisc/CMakeLists.txt
@@ -8,6 +8,7 @@ target_include_directories(libmisc PUBLIC INTERFACE ${CMAKE_CURRENT_SOURCE_DIR}/
 target_sources(libmisc INTERFACE
 	assert.c
 	intercept.c
+	linkedlist.c
 	log.c
 )
 target_compile_options(libmisc INTERFACE "$<$<COMPILE_LANGUAGE:C>:-fplan9-extensions>")
diff --git a/libmisc/include/libmisc/linkedlist.h b/libmisc/include/libmisc/linkedlist.h
new file mode 100644
index 0000000..045a468
--- /dev/null
+++ b/libmisc/include/libmisc/linkedlist.h
@@ -0,0 +1,57 @@
+/* libmisc/linkedlist.h - Singly- and doubly- linked lists
+ *
+ * Copyright (C) 2024-2025  Luke T. Shumaker <lukeshu@lukeshu.com>
+ * SPDX-License-Identifier: AGPL-3.0-or-later
+ */
+
+#ifndef _LIBMISC_LINKEDLIST_H_
+#define _LIBMISC_LINKEDLIST_H_
+
+#include <libmisc/assert.h>
+
+/* singly linked list *********************************************************/
+
+typedef struct _lm_sll_node {
+	struct _lm_sll_node *rear;
+} lm_sll_node;
+
+typedef struct {
+	lm_sll_node *front, *rear;
+} lm_sll_root;
+
+#define lm_sll_node_cast(node_typ, node_ptr)                                    \
+	({                                                                      \
+		static_assert(_Generic(node_ptr, lm_sll_node *: 1, default: 0), \
+		              "typeof("#node_ptr") != lm_sll_node *");          \
+		assert(node_ptr);                                               \
+		static_assert(offsetof(node_typ, lm_sll_node) == 0);            \
+		((node_typ*)(node_ptr));                                        \
+	})
+
+void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node);
+void lm_sll_pop_from_front(lm_sll_root *root);
+
+/* doubly linked list *********************************************************/
+
+typedef struct _lm_dll_node {
+	struct _lm_dll_node *front, *rear;
+} lm_dll_node;
+
+typedef struct {
+	lm_dll_node *front, *rear;
+} lm_dll_root;
+
+#define lm_dll_node_cast(node_typ, node_ptr)                                    \
+	({                                                                      \
+		static_assert(_Generic(node_ptr, lm_dll_node *: 1, default: 0), \
+		              "typeof("#node_ptr") != lm_dll_node *");          \
+		assert(node_ptr);                                               \
+		static_assert(offsetof(node_typ, lm_dll_node) == 0);            \
+		((node_typ*)(node_ptr));                                        \
+	})
+
+void lm_dll_push_to_rear(lm_dll_root *root, lm_dll_node *node);
+void lm_dll_remove(lm_dll_root *root, lm_dll_node *node);
+void lm_dll_pop_from_front(lm_dll_root *root);
+
+#endif /* _LIBMISC_LINKEDLIST_H_ */
diff --git a/libmisc/linkedlist.c b/libmisc/linkedlist.c
new file mode 100644
index 0000000..5fe0977
--- /dev/null
+++ b/libmisc/linkedlist.c
@@ -0,0 +1,62 @@
+/* libmisc/linkedlist.c - Singly- and doubly- linked lists
+ *
+ * Copyright (C) 2024-2025  Luke T. Shumaker <lukeshu@lukeshu.com>
+ * SPDX-License-Identifier: AGPL-3.0-or-later
+ */
+
+#include <stddef.h> /* for NULL */
+
+#include <libmisc/linkedlist.h>
+
+/* singly linked list *********************************************************/
+
+void lm_sll_push_to_rear(lm_sll_root *root, lm_sll_node *node) {
+	assert(root);
+	node->rear = NULL;
+	if (root->rear)
+		root->rear->rear = node;
+	else
+		root->front = node;
+	root->rear = node;
+}
+
+void lm_sll_pop_from_front(lm_sll_root *root) {
+	assert(root);
+	assert(root->front);
+	root->front = root->front->rear;
+	if (!root->front)
+		root->rear = NULL;
+}
+
+/* doubly linked list *********************************************************/
+
+void lm_dll_push_to_rear(lm_dll_root *root, lm_dll_node *node) {
+	assert(root);
+	assert(node);
+	node->front = root->rear;
+	node->rear = NULL;
+	if (root->rear)
+		root->rear->rear = node;
+	else
+		root->front = node;
+	root->rear = node;
+}
+
+void lm_dll_remove(lm_dll_root *root, lm_dll_node *node) {
+	assert(root);
+	assert(node);
+	if (node->front)
+		node->front->rear = node->rear;
+	else
+		root->front = node->rear;
+	if (node->rear)
+		node->rear->front = node->front;
+	else
+		root->rear = node->front;
+}
+
+void lm_dll_pop_from_front(lm_dll_root *root) {
+	assert(root);
+	assert(root->front);
+	lm_dll_remove(root, root->front);
+}
-- 
cgit v1.2.3-2-g168b