libiberty: sync with gcc
Import the following commits from GCC as of r16-2170-g2f2e9bcfb0fd9c:
0fd98b6f9f2 libiberty: add routines to handle type-sensitive doubly linked lists
diff --git a/include/doubly-linked-list.h b/include/doubly-linked-list.h
new file mode 100644
index 0000000..3f5ea28
--- /dev/null
+++ b/include/doubly-linked-list.h
@@ -0,0 +1,447 @@
+/* Manipulate doubly linked lists.
+ 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/>. */
+
+
+#ifndef _DOUBLY_LINKED_LIST_H
+#define _DOUBLY_LINKED_LIST_H
+
+/* Doubly linked list implementation enforcing typing.
+
+ This implementation of doubly linked list tries to achieve the enforcement of
+ typing similarly to C++ templates, but without encapsulation.
+
+ All the functions are prefixed with the type of the value: "AType_xxx".
+ Some functions are prefixed with "_AType_xxx" and are not part of the public
+ API, so should not be used, except for _##LTYPE##_merge_sort with a caveat
+ (see note above its definition).
+
+ Each function (### is a placeholder for method name) has a macro for:
+ (1) its invocation LINKED_LIST_###(LTYPE).
+ (2) its prototype LINKED_LIST_DECL_###(A, A2, scope). To add in a header
+ file, or a source file for forward declaration. 'scope' should be set
+ respectively to 'extern', or 'static'.
+ (3) its definition LINKED_LIST_DEFN_###(A, A2, scope). To add in a source
+ file with the 'scope' set respectively to nothing, or 'static' depending
+ on (2).
+
+ Data structures requirements:
+ - LTYPE corresponds to the node of a doubly linked list. It needs to define
+ attributes 'prev' and 'next' which are pointers on the type of a node.
+ For instance:
+ struct my_list_node
+ {
+ T value;
+ struct my_list_node *prev;
+ struct my_list_node *next;
+ };
+ - LWRAPPERTYPE is a structure wrapping the nodes and others metadata (first,
+ last, size).
+ */
+
+
+/* Mutative operations:
+ - append
+ - prepend
+ - insert_before
+ - pop_front
+ - pop_back
+ - remove
+ - swap
+ The header and body of each of those operation can be declared individually,
+ or as a whole via LINKED_LIST_MUTATIVE_OPS_PROTOTYPE for the prototypes, and
+ LINKED_LIST_MUTATIVE_OPS_DECL for the implementations. */
+
+/* Append the given node new_ to the exising list.
+ Precondition: prev and next of new_ must be NULL. */
+#define LINKED_LIST_APPEND(LTYPE) LTYPE##_append
+
+#define LINKED_LIST_DECL_APPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_)
+
+#define LINKED_LIST_DEFN_APPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
+EXPORT void \
+LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_) \
+{ \
+ if (wrapper->last == NULL) \
+ wrapper->first = new_; \
+ else \
+ { \
+ new_->prev = wrapper->last; \
+ wrapper->last->next = new_; \
+ } \
+ wrapper->last = new_; \
+ ++wrapper->size; \
+}
+
+/* Prepend the given node new_ to the existing list.
+ Precondition: prev and next of new_ must be NULL. */
+#define LINKED_LIST_PREPEND(LTYPE) LTYPE##_prepend
+
+#define LINKED_LIST_DECL_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_)
+
+#define LINKED_LIST_DEFN_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
+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_ before '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. */
+#define LINKED_LIST_INSERT_BEFORE(LTYPE) LTYPE##_insert_before
+
+#define LINKED_LIST_DECL_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \
+ LTYPE *new_, \
+ LTYPE *where)
+
+#define LINKED_LIST_DEFN_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \
+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. */
+#define LINKED_LIST_POP_FRONT(LTYPE) LTYPE##_pop_front
+
+#define LINKED_LIST_DECL_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT LTYPE * \
+ LTYPE##_pop_front (LWRAPPERTYPE *wrapper)
+
+#define LINKED_LIST_DEFN_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT) \
+EXPORT LTYPE * \
+LTYPE##_pop_front (LWRAPPERTYPE *wrapper) \
+{ \
+ LTYPE *front_node = wrapper->first; \
+ if (front_node != NULL) \
+ { \
+ wrapper->first = front_node->next; \
+ if (wrapper->last == front_node) \
+ wrapper->last = NULL; \
+ else \
+ { \
+ front_node->next->prev = NULL; \
+ front_node->next = NULL; \
+ } \
+ front_node->next = NULL; \
+ --wrapper->size; \
+ } \
+ return front_node; \
+}
+
+/* Pop the last node of the list. */
+#define LINKED_LIST_POP_BACK(LTYPE) LTYPE##_pop_back
+
+#define LINKED_LIST_DECL_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT LTYPE * \
+ LTYPE##_pop_back (LWRAPPERTYPE *wrapper)
+
+#define LINKED_LIST_DEFN_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT) \
+EXPORT LTYPE * \
+LTYPE##_pop_back (LWRAPPERTYPE *wrapper) \
+{ \
+ LTYPE *back_node = wrapper->last; \
+ if (back_node != NULL) \
+ { \
+ wrapper->last = back_node->prev; \
+ if (wrapper->first == back_node) \
+ wrapper->first = NULL; \
+ else \
+ { \
+ back_node->prev->next = NULL; \
+ back_node->prev = NULL; \
+ } \
+ back_node->prev = NULL; \
+ --wrapper->size; \
+ } \
+ return back_node; \
+}
+
+/* Remove the given node from the existing list, and return the previous
+ node. */
+#define LINKED_LIST_REMOVE(LTYPE) LTYPE##_remove
+
+#define LINKED_LIST_DECL_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT LTYPE * \
+ LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node)
+
+#define LINKED_LIST_DEFN_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT) \
+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; \
+ node->next = NULL; \
+ node->prev = NULL; \
+ --wrapper->size; \
+ } \
+ else \
+ LTYPE##_pop_front (wrapper); \
+ \
+ return previous; \
+}
+
+/* Generic swap. */
+#define LINKED_LIST_SWAP(LTYPE) LTYPE##_swap
+
+#define LINKED_LIST_DECL_SWAP(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2)
+
+/* Swap two nodes in a list. */
+#define LINKED_LIST_DEFN_SWAP(LWRAPPERTYPE, LTYPE, EXPORT) \
+EXPORT void \
+LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2) \
+{ \
+ LTYPE *prev1 = node1->prev; \
+ LTYPE *next1 = node1->next; \
+ LTYPE *prev2 = node2->prev; \
+ LTYPE *next2 = node2->next; \
+ \
+ if (prev1 != NULL) \
+ prev1->next = node2; \
+ else \
+ wrapper->first = node2; \
+ if (prev2 != NULL) \
+ prev2->next = node1; \
+ else \
+ wrapper->first = node1; \
+ \
+ if (next1 != NULL) \
+ next1->prev = node2; \
+ else \
+ wrapper->last = node2; \
+ if (next2 != NULL) \
+ next2->prev = node1; \
+ else \
+ wrapper->last = node1; \
+ \
+ { \
+ LTYPE *temp = node1->next; \
+ node1->next = node2->next; \
+ node2->next = temp; \
+ } \
+ { \
+ LTYPE *temp = node1->prev; \
+ node1->prev = node2->prev; \
+ node2->prev = temp; \
+ } \
+}
+
+/* Note: all the mutative operations below also update the data in the wrapper,
+ i.e. first, last and size. */
+#define LINKED_LIST_MUTATIVE_OPS_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ LINKED_LIST_DECL_APPEND(LWRAPPERTYPE, LTYPE, EXPORT); \
+ LINKED_LIST_DECL_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT); \
+ LINKED_LIST_DECL_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT); \
+ LINKED_LIST_DECL_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT); \
+ LINKED_LIST_DECL_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT); \
+ LINKED_LIST_DECL_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT); \
+ LINKED_LIST_DECL_SWAP(LWRAPPERTYPE, LTYPE, EXPORT)
+
+#define LINKED_LIST_MUTATIVE_OPS_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
+ LINKED_LIST_DEFN_APPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
+ LINKED_LIST_DEFN_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
+ LINKED_LIST_DEFN_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ LINKED_LIST_DEFN_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT) \
+ LINKED_LIST_DEFN_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT) \
+ LINKED_LIST_DEFN_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ LINKED_LIST_DEFN_SWAP(LWRAPPERTYPE, LTYPE, EXPORT)
+
+
+/* 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) (const LTYPE *, const LTYPE *))
+
+#define LINKED_LIST_MERGE_SORT_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, \
+ int (*fn_cmp) (const LTYPE *, const LTYPE *))
+
+/* Note: all the functions and macros below starting with "_" should be
+ considered private. */
+
+/* Compute the middle element of the list based on the turtle and hare
+ approach, i.e. the hare runs twice faster than the turtle. */
+#define _MERGE_SORT_IMPL_COMPUTE_TURTLE(LTYPE) \
+static inline 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; \
+}
+
+/* Append n at the end of l_out, and return the next node after n.
+ l_out and l_last should be ideally encapsulated into a list structure
+ but this is overkill for what we need here. */
+#define _MERGE_SORT_IMPL_OUT_APPEND(LTYPE) \
+static inline LTYPE * \
+LTYPE##_merge_sort_out_append_ (LTYPE **l_out, LTYPE **l_last, \
+ LTYPE *n) \
+{ \
+ if (*l_last == NULL) \
+ { \
+ *l_last = n; \
+ *l_out = n; \
+ n->prev = NULL; \
+ } \
+ else \
+ { \
+ (*l_last)->next = n; \
+ n->prev = *l_last; \
+ *l_last = n; \
+ } \
+ \
+ return n->next; \
+}
+
+/* Merge two sorted lists together.
+ The returned value corresponds to the first element of the list.
+ Note: both input lists are invalidated after the call. */
+#define _MERGE_SORT_IMPL_MERGE(LTYPE) \
+static inline LTYPE * \
+LTYPE##_merge_sort_merge_ (LTYPE *l_left, LTYPE *l_right, \
+ int (*fn_cmp) (const LTYPE *, const LTYPE *))\
+{ \
+ if (l_left == NULL) \
+ return l_right; \
+ else if (l_right == NULL) \
+ return l_left; \
+ \
+ LTYPE *l_out = NULL, *l_last = NULL; \
+ \
+ 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 = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_l); \
+ else \
+ l_r = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_r); \
+ } \
+ \
+ LTYPE *l_remaining = (l_l != NULL) ? l_l : l_r; \
+ while (l_remaining != NULL) \
+ l_remaining = \
+ LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_remaining); \
+ \
+ 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. */
+#define _MERGE_SORT_DEFN_SORT(LTYPE, EXPORT) \
+EXPORT LTYPE * \
+LTYPE##_merge_sort_ (LTYPE *node, \
+ int (*fn_cmp)(const LTYPE *, const LTYPE *)) \
+{ \
+ 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. */
+#define _MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT) \
+EXPORT void \
+LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, \
+ int (*fn_cmp) (const LTYPE *, const 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; \
+}
+
+#define LINKED_LIST_MERGE_SORT_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
+ _MERGE_SORT_IMPL_COMPUTE_TURTLE(LTYPE) \
+ _MERGE_SORT_IMPL_OUT_APPEND(LTYPE) \
+ _MERGE_SORT_IMPL_MERGE(LTYPE) \
+ _MERGE_SORT_DEFN_SORT(LTYPE, EXPORT) \
+ _MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT)
+
+#endif /* _DOUBLY_LINKED_LIST_H */
diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in
index 387975d..d507f27 100644
--- a/libiberty/Makefile.in
+++ b/libiberty/Makefile.in
@@ -237,6 +237,7 @@
INSTALLED_HEADERS = \
$(INCDIR)/ansidecl.h \
$(INCDIR)/demangle.h \
+ $(INCDIR)/doubly-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 2b0883c..ef549ca 100644
--- a/libiberty/testsuite/Makefile.in
+++ b/libiberty/testsuite/Makefile.in
@@ -45,7 +45,8 @@
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-doubly-linked-list
# Run some tests of the demangler.
check-cplus-dem: test-demangle $(srcdir)/demangle-expected
@@ -69,6 +70,10 @@
check-strtol: test-strtol
./test-strtol
+# Check the linked list functionality
+check-doubly-linked-list: test-doubly-linked-list
+ ./test-doubly-linked-list
+
# Run the demangler fuzzer
fuzz-demangler: demangler-fuzzer
./demangler-fuzzer
@@ -90,6 +95,10 @@
$(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-strtol \
$(srcdir)/test-strtol.c ../libiberty.a
+test-doubly-linked-list: $(srcdir)/test-doubly-linked-list.c
+ $(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-doubly-linked-list \
+ $(srcdir)/test-doubly-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 @@
rm -f test-pexecute
rm -f test-expandargv
rm -f test-strtol
+ rm -f test-doubly-linked-list
rm -f demangler-fuzzer
rm -f core
clean: mostlyclean
diff --git a/libiberty/testsuite/test-doubly-linked-list.c b/libiberty/testsuite/test-doubly-linked-list.c
new file mode 100644
index 0000000..1e1fc63
--- /dev/null
+++ b/libiberty/testsuite/test-doubly-linked-list.c
@@ -0,0 +1,269 @@
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "doubly-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 (const ListNodeType *n1, const ListNodeType *n2)
+{
+ if (n1->value == n2->value)
+ return 0;
+ else if (n1->value < n2->value)
+ return -1;
+ else
+ return 1;
+}
+
+LINKED_LIST_MUTATIVE_OPS_PROTOTYPE (LinkedListWrapperType, ListNodeType, static);
+LINKED_LIST_MERGE_SORT_PROTOTYPE (LinkedListWrapperType, ListNodeType, static);
+
+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 (%ld) is not matching the real size of the list (%ld).\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;
+
+ printf("\n");
+
+ 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 [] = { 10, 2, 3, 4, 9, 8, 11 };
+const int EXPECT_6 [] = { 10, 3, 2, 4, 9, 8, 11 };
+const int EXPECT_7 [] = { 10, 9, 2, 4, 3, 8, 11 };
+const int EXPECT_8 [] = { 2, 3, 4, 8, 9, 10, 11 };
+const int EXPECT_9 [] = { 3, 4, 8, 9, 10, 11 };
+const int EXPECT_10 [] = { 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]) },
+ { .content = EXPECT_8, .size = sizeof(EXPECT_8) / sizeof(EXPECT_8[0]) },
+ { .content = EXPECT_9, .size = sizeof(EXPECT_9) / sizeof(EXPECT_9[0]) },
+ { .content = EXPECT_10, .size = sizeof(EXPECT_10) / sizeof(EXPECT_10[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);
+
+ /* Swap first and last. */
+ LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first, wrapper.last);
+ failures += ! check ("swap first and last", &test_data[5], &wrapper);
+
+ /* Swap adjacent nodes. */
+ LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first->next,
+ wrapper.first->next->next);
+ failures += ! check ("swap adjacent nodes", &test_data[6], &wrapper);
+
+ /* Swap non-adjacent nodes, but neither first nor last. */
+ LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first->next,
+ wrapper.first->next->next->next->next);
+ failures += ! check ("swap non-adjacent nodes", &test_data[7], &wrapper);
+
+ /* Sort nodes. */
+ LINKED_LIST_MERGE_SORT(ListNodeType) (&wrapper, compare_nodes);
+ failures += ! check ("sort", &test_data[8], &wrapper);
+
+ /* Pop front. */
+ LINKED_LIST_POP_FRONT(ListNodeType) (&wrapper);
+ failures += ! check ("pop_front", &test_data[9], &wrapper);
+
+ /* Pop back. */
+ LINKED_LIST_POP_BACK(ListNodeType) (&wrapper);
+ failures += ! check ("pop_back", &test_data[10], &wrapper);
+
+ exit (failures ? EXIT_FAILURE : EXIT_SUCCESS);
+}
