[PATCH v0 01/15] libiberty: add implementations of common methods for type-sensitive doubly linked lists
Matthieu Longo
matthieu.longo@arm.com
Mon Mar 10 17:51:14 GMT 2025
Those methods's implementation is relying on duck-typing at compile
time.
The structure corresponding to the node of a doubly linked list needs
to define attributes 'prev' and 'next' which are pointers on the type
of a node.
The structure wrapping the nodes and others metadata (first, last, size)
needs to define pointers 'first_', and 'last_' of the node's type, and
an integer type for 'size'.
Mutative methods are bundled together and are declarable once via a
same macro. The merge sort is bundled separately.
There are 3 types of macros:
1. for the declaration of protypes: to use in a header file for a
public declaration, or as a forward declaration in the souce file
for private declaration.
2. for the declaration of the implementation: always to use in a
source file.
3. for the invokation of the functions.
The methods are declarable public or private via the second argument of
the declaration macros.
List of currently implemented methods:
- LINKED_LIST_:
- APPEND: insert a node at the end of the list.
- PREPEND: insert a node at the beginning of the list.
- INSERT_BEFORE: insert a node before the given node.
- POP_FRONT: remove the first node of the list.
- POP_BACK: remove the last node of the list.
- REMOVE: remove the given node from the list.
- LINKED_LIST_MERGE_SORT: a merge sort implementation.
---
include/double-linked-list.h | 313 +++++++++++++++++++++++++
libiberty/Makefile.in | 1 +
libiberty/testsuite/Makefile.in | 12 +-
libiberty/testsuite/test-linked-list.c | 244 +++++++++++++++++++
4 files changed, 569 insertions(+), 1 deletion(-)
create mode 100644 include/double-linked-list.h
create mode 100644 libiberty/testsuite/test-linked-list.c
diff --git a/include/double-linked-list.h b/include/double-linked-list.h
new file mode 100644
index 00000000000..4bd41933d71
--- /dev/null
+++ b/include/double-linked-list.h
@@ -0,0 +1,313 @@
+/* Copyright (C) 2025 Free Software Foundation, Inc.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+
+#pragma once
+
+#include <assert.h>
+
+
+/***********************
+ * Mutative operations *
+ ***********************/
+
+#define LINKED_LIST_MUTATIVE_OPS_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_); \
+ \
+ EXPORT void \
+ LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_); \
+ \
+ EXPORT void \
+ LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \
+ LTYPE *new_, \
+ LTYPE *where); \
+ \
+ EXPORT LTYPE * \
+ LTYPE##_pop_front (LWRAPPERTYPE *wrapper); \
+ \
+ EXPORT LTYPE * \
+ LTYPE##_pop_back (LWRAPPERTYPE *wrapper); \
+ \
+ EXPORT LTYPE * \
+ LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node)
+
+
+#define LINKED_LIST_APPEND(LTYPE) LTYPE##_append
+#define LINKED_LIST_PREPEND(LTYPE) LTYPE##_prepend
+#define LINKED_LIST_INSERT_BEFORE(LTYPE) LTYPE##_insert_before
+#define LINKED_LIST_POP_FRONT(LTYPE) LTYPE##_pop_front
+#define LINKED_LIST_POP_BACK(LTYPE) LTYPE##_pop_back
+#define LINKED_LIST_REMOVE(LTYPE) LTYPE##_remove
+
+
+#define LINKED_LIST_MUTATIVE_OPS_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
+/* Note: all the mutative operations below also update the data in */ \
+/* the wrapper, i.e. first_, last_ and size. */ \
+\
+/* Append the given node new_ to the exising list. */ \
+EXPORT void \
+LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_) \
+{ \
+ if (wrapper->last_) \
+ { \
+ new_->prev = wrapper->last_; \
+ wrapper->last_->next = new_; \
+ } \
+ else \
+ { \
+ new_->prev = NULL; \
+ wrapper->first_ = new_; \
+ } \
+ wrapper->last_ = new_; \
+ ++wrapper->size; \
+} \
+\
+/* Prepend the given node new_ to the exiting list. */ \
+EXPORT void \
+LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_) \
+{ \
+ if (wrapper->first_ == NULL) \
+ wrapper->last_ = new_; \
+ else \
+ { \
+ new_->next = wrapper->first_; \
+ wrapper->first_->prev = new_; \
+ } \
+ wrapper->first_ = new_; \
+ ++wrapper->size; \
+} \
+\
+/* Insert the given node new_ after where in the existing list. */ \
+/* If where == NULL, the insertion is equivalent to an append. */ \
+/* If where == first_, the insertion is equivalent to a prepend. */ \
+EXPORT void \
+LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \
+ LTYPE *new_, \
+ LTYPE *where) \
+{ \
+ if (where == wrapper->first_) \
+ LTYPE##_prepend (wrapper, new_); \
+ else if (where == NULL) \
+ LTYPE##_append (wrapper, new_); \
+ else \
+ { \
+ where->prev->next = new_; \
+ new_->prev = where->prev; \
+ where->prev = new_; \
+ new_->next = where; \
+ ++wrapper->size; \
+ } \
+} \
+\
+/* Pop the first node of the list. */ \
+EXPORT LTYPE * \
+LTYPE##_pop_front (LWRAPPERTYPE *wrapper) \
+{ \
+ LTYPE *front_node = wrapper->first_; \
+ if (front_node != NULL) \
+ { \
+ wrapper->first_ = front_node->next; \
+ if (front_node->next != NULL) \
+ { \
+ front_node->next->prev = NULL; \
+ front_node->next = NULL; \
+ } \
+ if (wrapper->last_ == front_node) \
+ wrapper->last_ = NULL; \
+ --wrapper->size; \
+ } \
+ return front_node; \
+} \
+\
+/* Pop the last node of the list. */ \
+EXPORT LTYPE * \
+LTYPE##_pop_back (LWRAPPERTYPE *wrapper) \
+{ \
+ LTYPE *back_node = wrapper->last_; \
+ if (back_node != NULL) \
+ { \
+ wrapper->last_ = back_node->prev; \
+ if (back_node->prev != NULL) \
+ { \
+ back_node->prev->next = NULL; \
+ back_node->prev = NULL; \
+ } \
+ if (wrapper->first_ == back_node) \
+ wrapper->first_ = NULL; \
+ --wrapper->size; \
+ } \
+ return back_node; \
+} \
+\
+/* Remove the given node from the existing list, and return the */ \
+/* previous node. */ \
+EXPORT LTYPE * \
+LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node) \
+{ \
+ LTYPE *previous = NULL; \
+ \
+ if (node->prev != NULL) \
+ { \
+ node->prev->next = node->next; \
+ if (node->next == NULL) \
+ wrapper->last_ = node->prev; \
+ else \
+ node->next->prev = node->prev; \
+ previous = node->prev; \
+ --wrapper->size; \
+ } \
+ else \
+ LTYPE##_pop_front (wrapper); \
+ \
+ node->next = NULL; \
+ node->prev = NULL; \
+ \
+ return previous; \
+}
+
+
+/***********
+ * Sorting *
+ ***********/
+
+#define _LINKED_LIST_MERGE_SORT(LTYPE) _##LTYPE##_merge_sort
+
+#define LINKED_LIST_MERGE_SORT(LTYPE) LTYPE##_merge_sort
+
+#define _LINKED_LIST_MERGE_SORT_PROTOTYPE(LTYPE, EXPORT) \
+ EXPORT LTYPE * \
+ _##LTYPE##_merge_sort (LTYPE *node, int (*fn_cmp)(LTYPE *, LTYPE *))
+
+#define LINKED_LIST_MERGE_SORT_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, int (*fn_cmp)(LTYPE *, LTYPE *))
+
+#define LINKED_LIST_MERGE_SORT_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
+ \
+static LTYPE * \
+_##LTYPE##_merge_sort_compute_turtle (LTYPE *node) \
+{ \
+ if (node == NULL) \
+ return node; \
+ \
+ LTYPE *turtle = node, *hare = node->next; \
+ while (hare != NULL && hare->next != NULL) \
+ { \
+ turtle = turtle->next; \
+ hare = hare->next->next; \
+ } \
+ return turtle; \
+} \
+ \
+static LTYPE * \
+_##LTYPE##_merge_sort_merge (LTYPE *l_left, LTYPE *l_right, \
+ int (*fn_cmp) (LTYPE *, LTYPE *)) \
+{ \
+ if (l_left == NULL) \
+ return l_right; \
+ else if (l_right == NULL) \
+ return l_left; \
+ \
+ LTYPE *l_out, *current = NULL; \
+ \
+ LTYPE * _update (LTYPE *n) \
+ { \
+ if (current == NULL) \
+ { \
+ current = n; \
+ l_out = current; \
+ n->prev = NULL; \
+ } \
+ else \
+ { \
+ current->next = n; \
+ n->prev = current; \
+ current = n; \
+ } \
+ \
+ return n->next; \
+ } \
+ \
+ LTYPE *l_l = l_left, *l_r = l_right; \
+ while (l_l != NULL && l_r != NULL) \
+ { \
+ int cmp = fn_cmp (l_l, l_r); \
+ if (cmp <= 0) \
+ l_l = _update (l_l); \
+ else \
+ l_r = _update (l_r); \
+ } \
+ \
+ for (; l_l != NULL; l_l = l_l->next) \
+ { \
+ current->next = l_l; \
+ l_l->prev = current; \
+ current = current->next; \
+ } \
+ \
+ for (; l_r != NULL; l_r = l_r->next) \
+ { \
+ current->next = l_r; \
+ l_r->prev = current; \
+ current = current->next; \
+ } \
+ \
+ return l_out; \
+} \
+ \
+/* Merge sort implementation taking the first node of the list to */ \
+/* sort, and the comparison function. Returns the first node of the */ \
+/* sorted list. */ \
+/* Note: use this if you don't care about updating the information */ \
+/* in the wrapper. */ \
+EXPORT LTYPE * \
+_##LTYPE##_merge_sort (LTYPE *node, int (*fn_cmp)(LTYPE *, LTYPE *)) \
+{ \
+ assert (fn_cmp != NULL); \
+ if (node == NULL) \
+ return NULL; \
+ else if (node->next == NULL) \
+ return node; \
+ \
+ LTYPE *left_end = _##LTYPE##_merge_sort_compute_turtle (node); \
+ LTYPE *left_begin = node; \
+ LTYPE *right_begin = left_end->next; \
+ /* break the list. */ \
+ left_end->next = NULL; \
+ right_begin->prev = NULL; \
+ \
+ left_begin = _##LTYPE##_merge_sort (left_begin, fn_cmp); \
+ right_begin = _##LTYPE##_merge_sort (right_begin, fn_cmp); \
+ return _##LTYPE##_merge_sort_merge (left_begin, right_begin, fn_cmp); \
+} \
+ \
+/* Merge sort wrapper that the end-user should be using as it updates */ \
+/* the first_ and last_ metadata of the list in wrapper as well. */ \
+/* If the user does not want to pay the cost of the update of the */ \
+/* data, it can directly use _##LTYPE##_merge_sort_merge. */ \
+EXPORT void \
+LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, int (*fn_cmp)(LTYPE *, LTYPE *)) \
+{ \
+ wrapper->first_ = _##LTYPE##_merge_sort (wrapper->first_, fn_cmp); \
+ \
+ if (wrapper->first_ == NULL || wrapper->first_->next == NULL) \
+ wrapper->last_ = wrapper->first_; \
+ else \
+ for (LTYPE *node = wrapper->first_; \
+ node != NULL; \
+ node = node->next) \
+ wrapper->last_ = node; \
+}
diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in
index b11df756b4b..a92491ca4cf 100644
--- a/libiberty/Makefile.in
+++ b/libiberty/Makefile.in
@@ -236,6 +236,7 @@ CONFIGURED_OFILES = ./asprintf.$(objext) ./atexit.$(objext) \
INSTALLED_HEADERS = \
$(INCDIR)/ansidecl.h \
$(INCDIR)/demangle.h \
+ $(INCDIR)/double-linked-list.h \
$(INCDIR)/dyn-string.h \
$(INCDIR)/fibheap.h \
$(INCDIR)/floatformat.h \
diff --git a/libiberty/testsuite/Makefile.in b/libiberty/testsuite/Makefile.in
index 2b0883c7630..f3aa5f7f236 100644
--- a/libiberty/testsuite/Makefile.in
+++ b/libiberty/testsuite/Makefile.in
@@ -45,7 +45,8 @@ all:
check: @CHECK@
really-check: check-cplus-dem check-d-demangle check-rust-demangle \
- check-pexecute check-expandargv check-strtol
+ check-pexecute check-expandargv check-strtol \
+ check-linked-list
# Run some tests of the demangler.
check-cplus-dem: test-demangle $(srcdir)/demangle-expected
@@ -69,6 +70,10 @@ check-expandargv: test-expandargv
check-strtol: test-strtol
./test-strtol
+# Check the linked list functionality
+check-linked-list: test-linked-list
+ ./test-linked-list
+
# Run the demangler fuzzer
fuzz-demangler: demangler-fuzzer
./demangler-fuzzer
@@ -90,6 +95,10 @@ test-strtol: $(srcdir)/test-strtol.c ../libiberty.a
$(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-strtol \
$(srcdir)/test-strtol.c ../libiberty.a
+test-linked-list: $(srcdir)/test-linked-list.c
+ $(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-linked-list \
+ $(srcdir)/test-linked-list.c
+
demangler-fuzzer: $(srcdir)/demangler-fuzzer.c ../libiberty.a
$(TEST_COMPILE) -o demangler-fuzzer \
$(srcdir)/demangler-fuzzer.c ../libiberty.a
@@ -104,6 +113,7 @@ mostlyclean:
rm -f test-pexecute
rm -f test-expandargv
rm -f test-strtol
+ rm -f test-linked-list
rm -f demangler-fuzzer
rm -f core
clean: mostlyclean
diff --git a/libiberty/testsuite/test-linked-list.c b/libiberty/testsuite/test-linked-list.c
new file mode 100644
index 00000000000..0a249eca294
--- /dev/null
+++ b/libiberty/testsuite/test-linked-list.c
@@ -0,0 +1,244 @@
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "double-linked-list.h"
+
+#ifndef EXIT_SUCCESS
+#define EXIT_SUCCESS 0
+#endif
+
+#ifndef EXIT_FAILURE
+#define EXIT_FAILURE 1
+#endif
+
+/* Implementation */
+
+typedef int T;
+
+typedef struct ListNodeType
+{
+ T value;
+ struct ListNodeType *next;
+ struct ListNodeType *prev;
+} ListNodeType;
+
+ListNodeType * l_new_node (T value)
+{
+ ListNodeType *n = malloc (sizeof (ListNodeType));
+ n->next = NULL;
+ n->prev = NULL;
+ n->value = value;
+ return n;
+}
+
+typedef struct LinkedListWrapperType
+{
+ ListNodeType *first_;
+ ListNodeType *last_;
+ size_t size;
+} LinkedListWrapperType;
+
+int compare_nodes (ListNodeType *n1, ListNodeType *n2)
+{
+ if (n1->value == n2->value)
+ return 0;
+ else if (n1->value < n2->value)
+ return -1;
+ else
+ return 1;
+}
+
+LINKED_LIST_MUTATIVE_OPS_DECL (LinkedListWrapperType, ListNodeType, static)
+LINKED_LIST_MERGE_SORT_DECL (LinkedListWrapperType, ListNodeType, static)
+
+ListNodeType * find_last_node (ListNodeType *head)
+{
+ if (head == NULL)
+ return NULL;
+
+ ListNodeType *n = head;
+ while (n->next != NULL)
+ n = n->next;
+
+ return n;
+}
+
+void l_print (ListNodeType *node)
+{
+ for (ListNodeType *l = node; l != NULL; l = l->next)
+ printf ("%d ", l->value);
+ printf ("\n");
+}
+
+void l_reverse_print (ListNodeType *last_node)
+{
+ for (ListNodeType *l = last_node; l != NULL; l = l->prev)
+ printf ("%d ", l->value);
+ printf ("\n");
+}
+
+struct test_data_t
+{
+ T const *content;
+ size_t size;
+};
+
+bool run_test (const struct test_data_t *expect,
+ LinkedListWrapperType *current,
+ bool reversed)
+{
+ ListNodeType *node = (reversed) ? current->last_ : current->first_;
+ bool passed = true;
+ for (int i=0; i<expect->size && node != NULL; ++i)
+ {
+ if (reversed)
+ {
+ if (expect->content[expect->size - 1 - i] != node->value)
+ {
+ printf ("FAIL: mismatching expected (%d) VS current (%d).\n",
+ expect->content[expect->size - 1 - i], node->value);
+ passed = false;
+ }
+ if (node->prev == NULL && current->first_ != node)
+ {
+ printf ("FAIL: first_ is not matching the first node.\n");
+ passed = false;
+ }
+ }
+ else
+ {
+ if (expect->content[i] != node->value)
+ {
+ printf ("FAIL: mismatching expected (%d) VS current (%d).\n",
+ expect->content[i], node->value);
+ passed = false;
+ }
+ if (node->next == NULL && current->last_ != node)
+ {
+ printf ("FAIL: last_ is not matching the last node.\n");
+ passed = false;
+ }
+ }
+
+ if (!passed)
+ return false;
+
+ if (reversed)
+ node = node->prev;
+ else
+ node = node->next;
+ }
+
+ if (node != NULL)
+ {
+ printf ("FAIL: the list is longer than expected.\n");
+ passed = false;
+ }
+ if (expect->size != current->size)
+ {
+ printf ("FAIL: size (%d) is not matching the real size of the list (%d).\n",
+ current->size, expect->size);
+ passed = false;
+ }
+
+ return passed;
+}
+
+bool check(const char *op,
+ const struct test_data_t *expect,
+ LinkedListWrapperType *wrapper)
+{
+ bool success = true;
+ bool res;
+
+ l_print (wrapper->first_);
+ res = run_test (expect, wrapper, false);
+ printf ("%s: test-linked-list::%s: check forward conformity\n",
+ res ? "PASS": "FAIL", op);
+ success &= res;
+
+ l_reverse_print (wrapper->last_);
+ res = run_test (expect, wrapper, true);
+ printf ("%s: test-linked-list::%s: check backward conformity\n",
+ res ? "PASS": "FAIL", op);
+ success &= res;
+
+ return success;
+}
+
+const int EXPECT_0 [] = { 10, 4, 3, 1, 9, 2 };
+const int EXPECT_1 [] = { 1, 2, 3, 4, 9, 10 };
+const int EXPECT_2 [] = { 11, 1, 2, 3, 4, 9, 10 };
+const int EXPECT_3 [] = { 11, 1, 2, 3, 4, 9, 8, 10 };
+const int EXPECT_4 [] = { 11, 2, 3, 4, 9, 8, 10 };
+const int EXPECT_5 [] = { 2, 3, 4, 8, 9, 10, 11 };
+const int EXPECT_6 [] = { 3, 4, 8, 9, 10, 11 };
+const int EXPECT_7 [] = { 3, 4, 8, 9, 10 };
+const struct test_data_t test_data[] = {
+ { .content = EXPECT_0, .size = sizeof(EXPECT_0) / sizeof(EXPECT_0[0]) },
+ { .content = EXPECT_1, .size = sizeof(EXPECT_1) / sizeof(EXPECT_1[0]) },
+ { .content = EXPECT_2, .size = sizeof(EXPECT_2) / sizeof(EXPECT_2[0]) },
+ { .content = EXPECT_3, .size = sizeof(EXPECT_3) / sizeof(EXPECT_3[0]) },
+ { .content = EXPECT_4, .size = sizeof(EXPECT_4) / sizeof(EXPECT_4[0]) },
+ { .content = EXPECT_5, .size = sizeof(EXPECT_5) / sizeof(EXPECT_5[0]) },
+ { .content = EXPECT_6, .size = sizeof(EXPECT_6) / sizeof(EXPECT_6[0]) },
+ { .content = EXPECT_7, .size = sizeof(EXPECT_7) / sizeof(EXPECT_7[0]) },
+};
+
+int main (void)
+{
+ int failures = 0;
+
+ LinkedListWrapperType wrapper = {
+ .first_ = NULL,
+ .last_ = NULL,
+ .size = 0,
+ };
+
+ /* Append nodes. */
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (10));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (4));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (3));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (1));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (9));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (2));
+
+ failures += ! check ("append", &test_data[0], &wrapper);
+
+ /* Sort nodes (without updating wrapper). */
+ wrapper.first_ =
+ _LINKED_LIST_MERGE_SORT(ListNodeType) (wrapper.first_, compare_nodes);
+ wrapper.last_ = find_last_node (wrapper.first_);
+
+ failures += ! check ("sort", &test_data[1], &wrapper);
+
+ /* Save a reference to this node for later. */
+ ListNodeType *n_to_remove = wrapper.first_;
+
+ /* Prepend node. */
+ LINKED_LIST_PREPEND(ListNodeType) (&wrapper, l_new_node (11));
+ failures += ! check ("prepend", &test_data[2], &wrapper);
+
+ /* Insert node. */
+ LINKED_LIST_INSERT_BEFORE(ListNodeType) (&wrapper, l_new_node (8), wrapper.last_);
+ failures += ! check ("insert_before", &test_data[3], &wrapper);
+
+ /* Remove a node. */
+ LINKED_LIST_REMOVE(ListNodeType) (&wrapper, n_to_remove);
+ failures += ! check ("remove", &test_data[4], &wrapper);
+
+ /* Sort nodes. */
+ LINKED_LIST_MERGE_SORT(ListNodeType) (&wrapper, compare_nodes);
+ failures += ! check ("sort", &test_data[5], &wrapper);
+
+ /* Pop front. */
+ LINKED_LIST_POP_FRONT(ListNodeType) (&wrapper);
+ failures += ! check ("pop_front", &test_data[6], &wrapper);
+
+ /* Pop back. */
+ LINKED_LIST_POP_BACK(ListNodeType) (&wrapper);
+ failures += ! check ("pop_back", &test_data[7], &wrapper);
+
+ exit (failures ? EXIT_FAILURE : EXIT_SUCCESS);
+}
--
2.48.1
More information about the Binutils
mailing list