Home Original page

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

Matthieu Longo matthieu.longo@arm.com
Thu Aug 7 09:39:22 GMT 2025 
On 2025-08-04 12:33, Jan Beulich wrote:
> On 04.08.2025 12:42, Matthieu Longo wrote:
>> On 2025-08-04 11:33, Richard Sandiford wrote:
>>> 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;
>>>>     }
>>
>> Thanks Richard for the quick review :)
>>
>> Just to confirm my understanding of your suggestion, you prefer to avoid
>> #if/#endif in the code and let the compiler prune the code depending on
>> the constant value of the condition. Is it correct ?
>>
>> Here below is the modified version.
> 
> Fine with me as well, thanks. Also okay to then put on the 2.45 branch.
> 
> Jan
> 

FYI I updated libiberty with the fix in binutils's master and 
binutils-2_45-branch.

Matthieu

>> --- a/libiberty/testsuite/test-doubly-linked-list.c
>> +++ b/libiberty/testsuite/test-doubly-linked-list.c
>> @@ -155,19 +155,26 @@ bool check(const char *op,
>>      bool success = true;
>>      bool res;
>>
>> -  l_print (wrapper->first);
>> +#define DUMP_LIST 0
>> +
>> +  if (DUMP_LIST)
>> +    l_print (wrapper->first);
>> +
>>      res = run_test (expect, wrapper, false);
>>      printf ("%s: test-linked-list::%s: check forward conformity\n",
>>             res ? "PASS": "FAIL", op);
>>      success &= res;
>>
>> -  l_reverse_print (wrapper->last);
>> +  if (DUMP_LIST)
>> +    l_reverse_print (wrapper->last);
>> +
>>      res = run_test (expect, wrapper, true);
>>      printf ("%s: test-linked-list::%s: check backward conformity\n",
>>             res ? "PASS": "FAIL", op);
>>      success &= res;
>>
>> -  printf("\n");
>> +  if (DUMP_LIST)
>> +    printf("\n");
>>
>>      return success;
>>    }
>
More information about the Binutils mailing list