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

[Richard Sandiford]

Matthieu Longo <matthieu.longo@arm.com> writes:
> On 2025-07-31 13:39, Jan Beulich wrote:
>> 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
>
> Hi Jan,
>
> Indeed those lines are making the output too verbose.
> What do you think of the following patch ?
> If you are happy with it, I will publish it to the GCC mailing list at 
> first, and then will sync libiberty from binutils with GCC's one once it 
> is merged.
>
> Matthieu
>
>
> Author: Matthieu Longo <matthieu.longo@arm.com>
> Date:   Mon Aug 4 11:04:13 2025 +0100
>
>      libiberty: disable logging of list content for doubly-linked list tests
>
>      When the doubly-linked list tests were introduced, the tests were
>      printing the content of the list forward and backward. However, this
>      printing is not needed outside of debugging, and confuses people 
> because
>      the output is not only composed of PASS: lines.
>
>      This patch disables the printing of the list content by default. If
>      one wants to re-enable it for debugging, he can set the macro DUMP_LIST
>      to 1.
>
> diff --git a/libiberty/testsuite/test-doubly-linked-list.c 
> b/libiberty/testsuite/test-doubly-linked-list.c
> index 1e1fc637653..520463701e7 100644
> --- a/libiberty/testsuite/test-doubly-linked-list.c
> +++ b/libiberty/testsuite/test-doubly-linked-list.c
> @@ -155,19 +155,27 @@ bool check(const char *op,
>     bool success = true;
>     bool res;
>
> +#define DUMP_LIST 0
> +
> +#if DUMP_LIST
>     l_print (wrapper->first);
> +#endif
>     res = run_test (expect, wrapper, false);
>     printf ("%s: test-linked-list::%s: check forward conformity\n",
>            res ? "PASS": "FAIL", op);
>     success &= res;
>
> +#if DUMP_LIST
>     l_reverse_print (wrapper->last);
> +#endif
>     res = run_test (expect, wrapper, true);
>     printf ("%s: test-linked-list::%s: check backward conformity\n",
>            res ? "PASS": "FAIL", op);
>     success &= res;
>
> +#if DUMP_LIST
>     printf("\n");
> +#endif

Pre-approved for GCC with:

  if (DUMP_LIST)

in place of the #ifdef/#endifs.

Thanks,
Richard

>
>     return success;
>   }