[PATCH v2 1/1] libiberty: add routines to handle type-sensitive doubly linked lists

[Jan Beulich]

On 09.07.2025 14:48, Matthieu Longo wrote:
> 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.
> ---
>  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

This new testing is what I suspect to have added significant clutter to
binutils 2.45 (i.e. it made it into a release this way) "make check"
output: Everything is clean and homogeneous from

PASS: test-buildargv-0.
PASS: test-expandargv-0.
PASS: test-buildargv-1.
PASS: test-expandargv-1.

throughout

PASS: test-strtol-18.
PASS: test-strtol-19.
PASS: test-strtol-20.

but then one gets

10 4 3 1 9 2 
PASS: test-linked-list::append: check forward conformity
2 9 1 3 4 10 
PASS: test-linked-list::append: check backward conformity

1 2 3 4 9 10 
PASS: test-linked-list::sort: check forward conformity
10 9 4 3 2 1 
PASS: test-linked-list::sort: check backward conformity

11 1 2 3 4 9 10 
PASS: test-linked-list::prepend: check forward conformity
10 9 4 3 2 1 11 
PASS: test-linked-list::prepend: check backward conformity

11 1 2 3 4 9 8 10 
PASS: test-linked-list::insert_before: check forward conformity
10 8 9 4 3 2 1 11 
PASS: test-linked-list::insert_before: check backward conformity

11 2 3 4 9 8 10 
PASS: test-linked-list::remove: check forward conformity
10 8 9 4 3 2 11 
PASS: test-linked-list::remove: check backward conformity

10 2 3 4 9 8 11 
PASS: test-linked-list::swap first and last: check forward conformity
11 8 9 4 3 2 10 
PASS: test-linked-list::swap first and last: check backward conformity

10 3 2 4 9 8 11 
PASS: test-linked-list::swap adjacent nodes: check forward conformity
11 8 9 4 2 3 10 
PASS: test-linked-list::swap adjacent nodes: check backward conformity

10 9 2 4 3 8 11 
PASS: test-linked-list::swap non-adjacent nodes: check forward conformity
11 8 3 4 2 9 10 
PASS: test-linked-list::swap non-adjacent nodes: check backward conformity

2 3 4 8 9 10 11 
PASS: test-linked-list::sort: check forward conformity
11 10 9 8 4 3 2 
PASS: test-linked-list::sort: check backward conformity

3 4 8 9 10 11 
PASS: test-linked-list::pop_front: check forward conformity
11 10 9 8 4 3 
PASS: test-linked-list::pop_front: check backward conformity

3 4 8 9 10 
PASS: test-linked-list::pop_back: check forward conformity
10 9 8 4 3 
PASS: test-linked-list::pop_back: check backward conformity

All the output besides the PASS: lines made me first think something went
wrong. And imo only the PASS: (or FAIL:) lines should appear on stdout.
Everything else should go to log files, just like other testing does.

Jan