This patch was originally part of [1]. Merging it in GCC is a prerequisite of
merging it inside binutils.
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.
Regression tested on aarch64-unknown-linux-gnu. No failure found.
[1]:
https://inbox.sourceware.org/binutils/20250509151319.88725-10-matthieu.lo...@arm.com/
## Diff against previous revisions
### Revision 1 -> 2:
Patch series v1:
https://inbox.sourceware.org/gcc-patches/20250703105942.732907-1-matthieu.lo...@arm.com/
Diff:
- Address Richard Sandiford's comments from revision 1.
- Add 2 new tests cases for swap.
Regards,
Matthieu
Matthieu Longo (1):
libiberty: add routines to handle type-sensitive doubly linked lists
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
--
2.50.1
