[PATCH v0 01/15] libiberty: add implementations of common methods for type-sensitive doubly linked lists

[Jan Beulich]

On 11.03.2025 12:24, Matthieu Longo wrote:
> On 2025-03-11 07:57, Jan Beulich wrote:
>> On 10.03.2025 18:51, 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 are bundled together and are declarable once via a
>>> same macro. The merge sort is bundled separately.
>>> There are 3 types of macros:
>>> 1. for the declaration of protypes: to use in a header file for a
>>>     public declaration, or as a forward declaration in the souce file
>>>     for private declaration.
>>> 2. for the declaration of the implementation: always to use in a
>>>     source file.
>>> 3. for the invokation of the functions.
>>>
>>> The methods are declarable 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.
>>> - LINKED_LIST_MERGE_SORT: a merge sort implementation.
>>> ---
>>>   include/double-linked-list.h           | 313 +++++++++++++++++++++++++
>>>   libiberty/Makefile.in                  |   1 +
>>>   libiberty/testsuite/Makefile.in        |  12 +-
>>>   libiberty/testsuite/test-linked-list.c | 244 +++++++++++++++++++
>>>   4 files changed, 569 insertions(+), 1 deletion(-)
>>>   create mode 100644 include/double-linked-list.h
>>>   create mode 100644 libiberty/testsuite/test-linked-list.c
>>
>> Iiuc libiberty changes want to go through gcc, to then be mirrored into binutils.
> 
> The idea here is that I am introducing a new container along the code 
> changes using it. If I send directly this patch to GCC mailing list, I 
> am suspecting that the first questions from the reviewers would be: "Why 
> did you add this ? What is it used for ?".

Just to mention it: If you foresee such a response, you can preempt it
by providing a description which addresses the questions right away. Or
maybe just a post-commit-message remark.

Jan

> I am aligned with you on this, and I understand well that this change 
> has to go through GCC at first to be merged. However, I would be 
> interested in getting feedbacks here in binutils, because it is very 
> likely that GCC will never use this as it already has access to the C++ 
> list container.
> 
> Matthieu.