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/
Regards,
Matthieu
Matthieu Longo (1):
libiberty: add common methods for type-sensitive doubly linked lists
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
--
2.50.0
