On 2025-07-08 16:25, Richard Sandiford wrote:
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.
This mostly looks good, but some comments below:
---
include/doubly-linked-list.h | 440 ++++++++++++++++++
libiberty/Makefile.in | 1 +
libiberty/testsuite/Makefile.in | 12 +-
libiberty/testsuite/test-doubly-linked-list.c | 253 ++++++++++
4 files changed, 705 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..3b3ce1ee6b9
--- /dev/null
+++ b/include/doubly-linked-list.h
@@ -0,0 +1,440 @@
+/* Copyright (C) 2025 Free Software Foundation, Inc.
There should be a one-line summary of the file before the copyright.
Fixed in the next revision.
+
+ 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
+
+#include <assert.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).
Was there a reason for adding underscores to "first" and "last" but not
to "prev", "next" and "size"?
No, no good reason. I changed them to "first" and "last" in the next
revision.
+ */
+
+
+/* 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. */
+#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_) \
+ { \
+ new_->prev = wrapper->last_; \
+ wrapper->last_->next = new_; \
+ } \
+ else \
+ { \
+ new_->prev = NULL; \
+ wrapper->first_ = new_; \
+ } \
+ wrapper->last_ = new_; \
+ ++wrapper->size; \
+}
It feels inconsistent to set new_->prev to NULL but not set new_->next
to NULL. How about either (a) setting new_->next to NULL unconditionally
or (b) removing the new_->prev assignment and adding an explicit precondition
that prev and next must already be null. I suppose the latter would be
more consistent with "prepend" below.
I opted for (b).
Fixed in the next revision.
+
+/* Prepend the given node new_ to the exiting list. */
existing
+#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_ after where in the existing list.
s/after/before/ :)
Fixed in the next revision.
+ 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 (front_node->next != NULL) \
+ { \
+ front_node->next->prev = NULL; \
+ front_node->next = NULL; \
+ } \
+ if (wrapper->last_ == front_node) \
+ wrapper->last_ = NULL; \
Very minor, but:
if (wrapper->last_ == front_node) \
wrapper->last_ = NULL; \
else \
{ \
front_node->next->prev = NULL; \
front_node->next = NULL; \
} \
might be more consistent with the way that insert_before is written.
There is only really one condition here, rather than two.
Fixed in the next revision.
+ --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 (back_node->prev != NULL) \
+ { \
+ back_node->prev->next = NULL; \
+ back_node->prev = NULL; \
+ } \
+ if (wrapper->first_ == back_node) \
+ wrapper->first_ = NULL; \
Same idea here.
Fixed in the next revision.
+ --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; \
+ --wrapper->size; \
+ } \
+ else \
+ LTYPE##_pop_front (wrapper); \
+ \
+ node->next = NULL; \
+ node->prev = NULL; \
I suppose this could be moved inside the "if", since pop_front also leaves
both fields null. As it is, I was wondering whether pop_front didn't
guarantee null prevs and nexts on return.
Fixed in the next revision.
+ \
+ 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)
+
+#define VALUE_SWAP(a, b) \
+ do { typeof(a) temp = a; a = b; b = temp; } while (0)
typeof only became a standard C feature in C23. Since the macro is only
used twice, it might be better to open-code it.
I removed the macro as you suggested.
+
+/* Swap two nodes in a list. */
+#define LINKED_LIST_DEFN_SWAP(LWRAPPERTYPE, LTYPE, EXPORT) \
+EXPORT void \
+LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2) \
+{ \
+ if (node1->prev != NULL) \
+ node1->prev->next = node2; \
+ if (node2->prev != NULL) \
+ node2->prev->next = node1; \
+ if (node1->next != NULL) \
+ node1->next->prev = node2; \
+ if (node2->next != NULL) \
+ node2->next->prev = node1; \
+ \
+ VALUE_SWAP (node1->next, node2->next); \
+ VALUE_SWAP (node1->prev, node2->prev); \
+ \
+ if (wrapper->first_ == node1) \
+ wrapper->first_ = node2; \
+ else if (wrapper->first_ == node2) \
+ wrapper->first_ = node1; \
+ \
+ if (wrapper->last_ == node1) \
+ wrapper->last_ = node2; \
+ else if (wrapper->last_ == node2) \
+ wrapper->last_ = node1; \
Similarly to the above, there are only 4 conditions here, so this could be:
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; \
etc. (done before the swaps). Caching prev1 etc. is needed for the case
where node1->prev == node2 or node2->prev == node1. With the current
system, if we start with:
A: { prev: ???, next: node1 }
node1: { prev: A, next: node2 }
node2: { prev: node1, next: B }
B: { prev: node2, next: ??? }
then after:
+ if (node1->prev != NULL) \
+ node1->prev->next = node2; \
+ if (node2->prev != NULL) \
+ node2->prev->next = node1; \
we have:
A: { prev: ???, next: node2 }
node1: { prev: A, next: node1 }
node2: { prev: node1, next: B }
B: { prev: node2, next: ??? }
and after:
+ if (node1->next != NULL) \
+ node1->next->prev = node2; \
+ if (node2->next != NULL) \
+ node2->next->prev = node1; \
we have:
A: { prev: ???, next: node2 }
node1: { prev: node2, next: node1 }
node2: { prev: node1, next: B }
B: { prev: node1, next: ??? }
which after the swap becomes:
A: { prev: ???, next: node2 }
node2: { prev: node2, next: node1 }
node1: { prev: node1, next: B }
B: { prev: node1, next: ??? }
with the prevs becoming self-pointers.
I added two more test cases for the swap. It was failing indeed. Thanks
for catching that.
I rewrote the function as you suggested.
+}
+
+/* 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
It might be more namespace-correct to append an underscore, rather than
prepending one. "_..." is reserved for the implementation.
Fixed in the next revision.
+
+#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 *)) \
+{ \
+ assert (fn_cmp != NULL); \
This is the only use of assert that I could see in the file. I wonder
if it's worth including assert.h just for this check, given that things
would go wrong in an obvious way if the comparison function were null.
This file wouldn't be used in GCC now that GCC is written in C++, but
the policy in GCC is to use gcc_assert instead of assert, and other
projects could have similar restrictions.
Thanks,
Richard
Fixed in the next revision. I removed the assert.
Thanks for the thorough review.
Matthieu
+ 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 */
[...]
