Matthieu Longo <matthieu.lo...@arm.com> writes: > 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 can be bundled together and be declarable once via a > same macro, or can be declared separately. The merge sort is bundled > separately. > There are 3 types of macros: > 1. for the declaration of prototypes: to use in a header file for a > public declaration, or as a forward declaration in the source file > for private declaration. > 2. for the declaration of the implementation: to use always in a > source file. > 3. for the invocation of the functions. > > The methods can be declared either 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. > - SWAP: swap the two given nodes in the list. > - LINKED_LIST_MERGE_SORT: a merge sort implementation.
Thanks for the update, LGTM. OK for trunk (and for binutils). Richard > --- > include/doubly-linked-list.h | 447 ++++++++++++++++++ > libiberty/Makefile.in | 1 + > libiberty/testsuite/Makefile.in | 12 +- > libiberty/testsuite/test-doubly-linked-list.c | 269 +++++++++++ > 4 files changed, 728 insertions(+), 1 deletion(-) > create mode 100644 include/doubly-linked-list.h > create mode 100644 libiberty/testsuite/test-doubly-linked-list.c > > diff --git a/include/doubly-linked-list.h b/include/doubly-linked-list.h > new file mode 100644 > index 00000000000..3f5ea2808f9 > --- /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 ce54d88278d..e4d7d0aafa0 100644 > --- a/libiberty/Makefile.in > +++ b/libiberty/Makefile.in > @@ -237,6 +237,7 @@ CONFIGURED_OFILES = ./asprintf.$(objext) > ./atexit.$(objext) \ > 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 2b0883c7630..ef549ca910a 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-doubly-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-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-strtol: $(srcdir)/test-strtol.c ../libiberty.a > $(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 @@ mostlyclean: > 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 00000000000..1e1fc637653 > --- /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); > +}
