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

[Matthieu Longo]

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

    return success;
  }