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

[Matthieu Longo]

On 2025-03-20 14:24, Jan Beulich wrote:
> On 20.03.2025 15:05, Matthieu Longo wrote:
>> On 2025-03-11 12:03, Jan Beulich wrote:
>>> 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.
>>
>> I would prefer to have feedback here before going to GCC.
>> The example of usages are primarily in this patch series. If you spot
>> something in the interface that you don't like, it would be easier for
>> me to iterate over it if everything is tracked into the same mail thread.
>> If I get a first validation from a maintainer here, then I will send the
>> patch to GCC mailing list to get reviewed and hopefully merged.
>> Are you happy of this approach ?
> 
> Thing is - I have no clue what is or is not acceptable as brand new addition
> to libiberty. Having only briefly looked over that code, the one thing I can
> say is that I'm not a fan of such huge macros. Yet still I can see why you
> use them there. I'm further unclear about the need of some of the trailing
> underscores. On new_ that may be to cope with C++, but for the others I have
> no idea. The final piece I noticed is "#pragma once", which isn't a C99
> thing.
> 

 > the one thing I can say is that I'm not a fan of such huge macros. 
Yet still I can see why you use them there.

I tried to implement the equivalent of a templated doubly linked list by 
wrapping the code into macros. I am not a fan as well, but I don't see 
how I could have got a typed linked list without this mechanism. If such 
macros are well tested, it seems to me an acceptable solution.

 > I'm further unclear about the need of some of the trailing underscores.

I guess you are talking about update_ which is by the way a nested 
function that I need to get rid of. I wanted to make it look like it is 
private from the name, maybe I should have followed a the python way 
calling it _update. I don't mind changing the name.

 > The final piece I noticed is "#pragma once", which isn't a C99 thing.

"#pragma once" seems to be widely supported even if it is not "official 
C99".

https://en.wikipedia.org/wiki/Pragma_once#Portability lists the support 
of this feature in 22 compilers. Out of all of those, GCC and LLVM are 
the most popular, and probably the ones used to build binutils in most 
of cases.

Both GCC and LLVM support this macro officially. Support was added in:
- GCC 3.4: I don't know if there is a lot of people that are using GCC 
3.4 or older, I doubt so. And even if they would, would they build the 
latest version of binutils with it ?
- LLVM 3.4.1 if I cross reference 
https://web.archive.org/web/20140404052351/http://clang.llvm.org/doxygen/Pragma_8cpp-source.html#l00184 
and https://releases.llvm.org/. The same here, I doubt that a lot of 
people are using LLVM 3.4.1 or older today.

Sorry for the digression from the original topic, but would it make 
sense to accept "#pragma once" and deviate one millimeter away from the 
C99 standard instead of using #ifndef ... #endif.

I don't want to start a troll here but I cannot prevent myself to 
highlight the benefits that using wide spread modern features provided 
by more modern language (classes, lambdas, and common containers: 
nothing more than GCC with C++) in binutils in areas like bfd, or 
basically everywhere, would make things easier to read and maintain for 
everyone.

This macro "#pragma once" is really a minor feature and seems 
insignificant compared to what C++ would have to offer, but this macro 
is easier for me and others developers in general (there is probably the 
reason why it was widely adopted by all those compilers) than #ifndef 
... #endif.

I propose to open a thread to discuss the adoption of this pragma in 
binutils code base. What do you think ?

In the mean time, I will remove "#pragma once" from this header.

Matthieu

> So while I have a few comments here (and there may be more if I looked more
> closely), these could all be treated as meaningless - I'm not a libiberty
> maintainer, after all.
> 
> Jan