[PATCH v2 1/1] libiberty: add routines to handle type-sensitive doubly linked lists
Matthieu Longo
matthieu.longo@arm.com
Mon Aug 4 10:42:15 GMT 2025
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.
Matthieu
diff --git a/libiberty/testsuite/test-doubly-linked-list.c
b/libiberty/testsuite/test-doubly-linked-list.c
index 1e1fc637653..93fe19a27ae 100644
--- 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