[v0,01/15] libiberty: add implementations of common methods for type-sensitive doubly linked lists
Checks
Commit Message
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
Comments
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.
Jan
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.
>
> Jan
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 ?".
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.
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.
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.
>
> Jan
>
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 ?
Matthieu
>> 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.
>
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.
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
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
On 20.03.2025 17:36, Matthieu Longo wrote:
> 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.
I didn't even spot that one (and no, _update may not be a good name). In
fact, searching through the original submission I can't spot any update_.
I noticed first_ and last_, for example.
> > 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 ?
Feel free. My comment here wasn't strictly an objection. I nevertheless
felt it was necessary to point out that looked like an attempt to slip
something in that doesn't match the supposed language baseline of the
project. Imo something like this would need calling out prominently in
the description, making people aware before they even hit the construct.
(Else how do I know I didn't overlook something else that's non-
standard, and hence may cause issues down the road?)
Jan
On 2025-03-20 16:46, Jan Beulich wrote:
> On 20.03.2025 17:36, Matthieu Longo wrote:
>> 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.
>
> I didn't even spot that one (and no, _update may not be a good name). In
> fact, searching through the original submission I can't spot any update_.
>
You are right, this _update is actually the equivalent of an append to
the output list + return the next element of n in its original list.
In the next revision, I moved the function out, and renamed it:
_##LTYPE##_merge_sort_out_append
I think that the code is a bit more explicit now, but the naming is
horrible.
> I noticed first_ and last_, for example.
>
Regarding those specific trailing underscores, it is the same story
except that I followed one among the C++ code style for private
attributes in a class.
The idea is that you can read those values, but you should never have to
change first_ or last_ yourself. There are mutative methods for that.
All this naming weirdness stems in the fact that I don't have a way in C
to encapsulate things and try to convey via naming what you can and
cannot do with this member of the struct. It helps me to read the code,
but it might not make any sense to others people :(
I will handover the final say to the maintainers of libiberty for this.
Thanks for pointing these weirdness out because I think I need to
explain them in the cover letter that I will send to GCC.
Thanks for your time and reviewing this code even if you're not a
maintainer of it. Your input is very valuable.
>> > 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 ?
>
> Feel free. My comment here wasn't strictly an objection. I nevertheless
> felt it was necessary to point out that looked like an attempt to slip
> something in that doesn't match the supposed language baseline of the
> project. Imo something like this would need calling out prominently in
> the description, making people aware before they even hit the construct.
> (Else how do I know I didn't overlook something else that's non-
> standard, and hence may cause issues down the road?)
Very good point. I will add those details to the patch to GCC libiberty.
To be honest, I didn't even know that this "#pragma once" was not
standard until you pointed it out and I do the research about the
support in the different compilers. Over the last 10+ years, I saw it
being used a lot in a various C/C++ projects, and I thought up until now
that there were just two ways of doing the same thing, one old and one new.
>
> Jan
Matthieu
new file mode 100644
@@ -0,0 +1,313 @@
+/* Copyright (C) 2025 Free Software Foundation, Inc.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+
+#pragma once
+
+#include <assert.h>
+
+
+/***********************
+ * Mutative operations *
+ ***********************/
+
+#define LINKED_LIST_MUTATIVE_OPS_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_); \
+ \
+ EXPORT void \
+ LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_); \
+ \
+ EXPORT void \
+ LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \
+ LTYPE *new_, \
+ LTYPE *where); \
+ \
+ EXPORT LTYPE * \
+ LTYPE##_pop_front (LWRAPPERTYPE *wrapper); \
+ \
+ EXPORT LTYPE * \
+ LTYPE##_pop_back (LWRAPPERTYPE *wrapper); \
+ \
+ EXPORT LTYPE * \
+ LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node)
+
+
+#define LINKED_LIST_APPEND(LTYPE) LTYPE##_append
+#define LINKED_LIST_PREPEND(LTYPE) LTYPE##_prepend
+#define LINKED_LIST_INSERT_BEFORE(LTYPE) LTYPE##_insert_before
+#define LINKED_LIST_POP_FRONT(LTYPE) LTYPE##_pop_front
+#define LINKED_LIST_POP_BACK(LTYPE) LTYPE##_pop_back
+#define LINKED_LIST_REMOVE(LTYPE) LTYPE##_remove
+
+
+#define LINKED_LIST_MUTATIVE_OPS_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
+/* Note: all the mutative operations below also update the data in */ \
+/* the wrapper, i.e. first_, last_ and size. */ \
+\
+/* Append the given node new_ to the exising list. */ \
+EXPORT void \
+LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_) \
+{ \
+ if (wrapper->last_) \
+ { \
+ new_->prev = wrapper->last_; \
+ wrapper->last_->next = new_; \
+ } \
+ else \
+ { \
+ new_->prev = NULL; \
+ wrapper->first_ = new_; \
+ } \
+ wrapper->last_ = new_; \
+ ++wrapper->size; \
+} \
+\
+/* Prepend the given node new_ to the exiting list. */ \
+EXPORT void \
+LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_) \
+{ \
+ if (wrapper->first_ == NULL) \
+ wrapper->last_ = new_; \
+ else \
+ { \
+ new_->next = wrapper->first_; \
+ wrapper->first_->prev = new_; \
+ } \
+ wrapper->first_ = new_; \
+ ++wrapper->size; \
+} \
+\
+/* Insert the given node new_ after where in the existing list. */ \
+/* If where == NULL, the insertion is equivalent to an append. */ \
+/* If where == first_, the insertion is equivalent to a prepend. */ \
+EXPORT void \
+LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \
+ LTYPE *new_, \
+ LTYPE *where) \
+{ \
+ if (where == wrapper->first_) \
+ LTYPE##_prepend (wrapper, new_); \
+ else if (where == NULL) \
+ LTYPE##_append (wrapper, new_); \
+ else \
+ { \
+ where->prev->next = new_; \
+ new_->prev = where->prev; \
+ where->prev = new_; \
+ new_->next = where; \
+ ++wrapper->size; \
+ } \
+} \
+\
+/* Pop the first node of the list. */ \
+EXPORT LTYPE * \
+LTYPE##_pop_front (LWRAPPERTYPE *wrapper) \
+{ \
+ LTYPE *front_node = wrapper->first_; \
+ if (front_node != NULL) \
+ { \
+ wrapper->first_ = front_node->next; \
+ if (front_node->next != NULL) \
+ { \
+ front_node->next->prev = NULL; \
+ front_node->next = NULL; \
+ } \
+ if (wrapper->last_ == front_node) \
+ wrapper->last_ = NULL; \
+ --wrapper->size; \
+ } \
+ return front_node; \
+} \
+\
+/* Pop the last node of the list. */ \
+EXPORT LTYPE * \
+LTYPE##_pop_back (LWRAPPERTYPE *wrapper) \
+{ \
+ LTYPE *back_node = wrapper->last_; \
+ if (back_node != NULL) \
+ { \
+ wrapper->last_ = back_node->prev; \
+ if (back_node->prev != NULL) \
+ { \
+ back_node->prev->next = NULL; \
+ back_node->prev = NULL; \
+ } \
+ if (wrapper->first_ == back_node) \
+ wrapper->first_ = NULL; \
+ --wrapper->size; \
+ } \
+ return back_node; \
+} \
+\
+/* Remove the given node from the existing list, and return the */ \
+/* previous node. */ \
+EXPORT LTYPE * \
+LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node) \
+{ \
+ LTYPE *previous = NULL; \
+ \
+ if (node->prev != NULL) \
+ { \
+ node->prev->next = node->next; \
+ if (node->next == NULL) \
+ wrapper->last_ = node->prev; \
+ else \
+ node->next->prev = node->prev; \
+ previous = node->prev; \
+ --wrapper->size; \
+ } \
+ else \
+ LTYPE##_pop_front (wrapper); \
+ \
+ node->next = NULL; \
+ node->prev = NULL; \
+ \
+ return previous; \
+}
+
+
+/***********
+ * Sorting *
+ ***********/
+
+#define _LINKED_LIST_MERGE_SORT(LTYPE) _##LTYPE##_merge_sort
+
+#define LINKED_LIST_MERGE_SORT(LTYPE) LTYPE##_merge_sort
+
+#define _LINKED_LIST_MERGE_SORT_PROTOTYPE(LTYPE, EXPORT) \
+ EXPORT LTYPE * \
+ _##LTYPE##_merge_sort (LTYPE *node, int (*fn_cmp)(LTYPE *, LTYPE *))
+
+#define LINKED_LIST_MERGE_SORT_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, int (*fn_cmp)(LTYPE *, LTYPE *))
+
+#define LINKED_LIST_MERGE_SORT_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
+ \
+static LTYPE * \
+_##LTYPE##_merge_sort_compute_turtle (LTYPE *node) \
+{ \
+ if (node == NULL) \
+ return node; \
+ \
+ LTYPE *turtle = node, *hare = node->next; \
+ while (hare != NULL && hare->next != NULL) \
+ { \
+ turtle = turtle->next; \
+ hare = hare->next->next; \
+ } \
+ return turtle; \
+} \
+ \
+static LTYPE * \
+_##LTYPE##_merge_sort_merge (LTYPE *l_left, LTYPE *l_right, \
+ int (*fn_cmp) (LTYPE *, LTYPE *)) \
+{ \
+ if (l_left == NULL) \
+ return l_right; \
+ else if (l_right == NULL) \
+ return l_left; \
+ \
+ LTYPE *l_out, *current = NULL; \
+ \
+ LTYPE * _update (LTYPE *n) \
+ { \
+ if (current == NULL) \
+ { \
+ current = n; \
+ l_out = current; \
+ n->prev = NULL; \
+ } \
+ else \
+ { \
+ current->next = n; \
+ n->prev = current; \
+ current = n; \
+ } \
+ \
+ return n->next; \
+ } \
+ \
+ LTYPE *l_l = l_left, *l_r = l_right; \
+ while (l_l != NULL && l_r != NULL) \
+ { \
+ int cmp = fn_cmp (l_l, l_r); \
+ if (cmp <= 0) \
+ l_l = _update (l_l); \
+ else \
+ l_r = _update (l_r); \
+ } \
+ \
+ for (; l_l != NULL; l_l = l_l->next) \
+ { \
+ current->next = l_l; \
+ l_l->prev = current; \
+ current = current->next; \
+ } \
+ \
+ for (; l_r != NULL; l_r = l_r->next) \
+ { \
+ current->next = l_r; \
+ l_r->prev = current; \
+ current = current->next; \
+ } \
+ \
+ return l_out; \
+} \
+ \
+/* Merge sort implementation taking the first node of the list to */ \
+/* sort, and the comparison function. Returns the first node of the */ \
+/* sorted list. */ \
+/* Note: use this if you don't care about updating the information */ \
+/* in the wrapper. */ \
+EXPORT LTYPE * \
+_##LTYPE##_merge_sort (LTYPE *node, int (*fn_cmp)(LTYPE *, LTYPE *)) \
+{ \
+ assert (fn_cmp != NULL); \
+ if (node == NULL) \
+ return NULL; \
+ else if (node->next == NULL) \
+ return node; \
+ \
+ LTYPE *left_end = _##LTYPE##_merge_sort_compute_turtle (node); \
+ LTYPE *left_begin = node; \
+ LTYPE *right_begin = left_end->next; \
+ /* break the list. */ \
+ left_end->next = NULL; \
+ right_begin->prev = NULL; \
+ \
+ left_begin = _##LTYPE##_merge_sort (left_begin, fn_cmp); \
+ right_begin = _##LTYPE##_merge_sort (right_begin, fn_cmp); \
+ return _##LTYPE##_merge_sort_merge (left_begin, right_begin, fn_cmp); \
+} \
+ \
+/* Merge sort wrapper that the end-user should be using as it updates */ \
+/* the first_ and last_ metadata of the list in wrapper as well. */ \
+/* If the user does not want to pay the cost of the update of the */ \
+/* data, it can directly use _##LTYPE##_merge_sort_merge. */ \
+EXPORT void \
+LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, int (*fn_cmp)(LTYPE *, LTYPE *)) \
+{ \
+ wrapper->first_ = _##LTYPE##_merge_sort (wrapper->first_, fn_cmp); \
+ \
+ if (wrapper->first_ == NULL || wrapper->first_->next == NULL) \
+ wrapper->last_ = wrapper->first_; \
+ else \
+ for (LTYPE *node = wrapper->first_; \
+ node != NULL; \
+ node = node->next) \
+ wrapper->last_ = node; \
+}
@@ -236,6 +236,7 @@ CONFIGURED_OFILES = ./asprintf.$(objext) ./atexit.$(objext) \
INSTALLED_HEADERS = \
$(INCDIR)/ansidecl.h \
$(INCDIR)/demangle.h \
+ $(INCDIR)/double-linked-list.h \
$(INCDIR)/dyn-string.h \
$(INCDIR)/fibheap.h \
$(INCDIR)/floatformat.h \
@@ -45,7 +45,8 @@ all:
check: @CHECK@
really-check: check-cplus-dem check-d-demangle check-rust-demangle \
- check-pexecute check-expandargv check-strtol
+ check-pexecute check-expandargv check-strtol \
+ check-linked-list
# Run some tests of the demangler.
check-cplus-dem: test-demangle $(srcdir)/demangle-expected
@@ -69,6 +70,10 @@ check-expandargv: test-expandargv
check-strtol: test-strtol
./test-strtol
+# Check the linked list functionality
+check-linked-list: test-linked-list
+ ./test-linked-list
+
# Run the demangler fuzzer
fuzz-demangler: demangler-fuzzer
./demangler-fuzzer
@@ -90,6 +95,10 @@ test-strtol: $(srcdir)/test-strtol.c ../libiberty.a
$(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-strtol \
$(srcdir)/test-strtol.c ../libiberty.a
+test-linked-list: $(srcdir)/test-linked-list.c
+ $(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-linked-list \
+ $(srcdir)/test-linked-list.c
+
demangler-fuzzer: $(srcdir)/demangler-fuzzer.c ../libiberty.a
$(TEST_COMPILE) -o demangler-fuzzer \
$(srcdir)/demangler-fuzzer.c ../libiberty.a
@@ -104,6 +113,7 @@ mostlyclean:
rm -f test-pexecute
rm -f test-expandargv
rm -f test-strtol
+ rm -f test-linked-list
rm -f demangler-fuzzer
rm -f core
clean: mostlyclean
new file mode 100644
@@ -0,0 +1,244 @@
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "double-linked-list.h"
+
+#ifndef EXIT_SUCCESS
+#define EXIT_SUCCESS 0
+#endif
+
+#ifndef EXIT_FAILURE
+#define EXIT_FAILURE 1
+#endif
+
+/* Implementation */
+
+typedef int T;
+
+typedef struct ListNodeType
+{
+ T value;
+ struct ListNodeType *next;
+ struct ListNodeType *prev;
+} ListNodeType;
+
+ListNodeType * l_new_node (T value)
+{
+ ListNodeType *n = malloc (sizeof (ListNodeType));
+ n->next = NULL;
+ n->prev = NULL;
+ n->value = value;
+ return n;
+}
+
+typedef struct LinkedListWrapperType
+{
+ ListNodeType *first_;
+ ListNodeType *last_;
+ size_t size;
+} LinkedListWrapperType;
+
+int compare_nodes (ListNodeType *n1, ListNodeType *n2)
+{
+ if (n1->value == n2->value)
+ return 0;
+ else if (n1->value < n2->value)
+ return -1;
+ else
+ return 1;
+}
+
+LINKED_LIST_MUTATIVE_OPS_DECL (LinkedListWrapperType, ListNodeType, static)
+LINKED_LIST_MERGE_SORT_DECL (LinkedListWrapperType, ListNodeType, static)
+
+ListNodeType * find_last_node (ListNodeType *head)
+{
+ if (head == NULL)
+ return NULL;
+
+ ListNodeType *n = head;
+ while (n->next != NULL)
+ n = n->next;
+
+ return n;
+}
+
+void l_print (ListNodeType *node)
+{
+ for (ListNodeType *l = node; l != NULL; l = l->next)
+ printf ("%d ", l->value);
+ printf ("\n");
+}
+
+void l_reverse_print (ListNodeType *last_node)
+{
+ for (ListNodeType *l = last_node; l != NULL; l = l->prev)
+ printf ("%d ", l->value);
+ printf ("\n");
+}
+
+struct test_data_t
+{
+ T const *content;
+ size_t size;
+};
+
+bool run_test (const struct test_data_t *expect,
+ LinkedListWrapperType *current,
+ bool reversed)
+{
+ ListNodeType *node = (reversed) ? current->last_ : current->first_;
+ bool passed = true;
+ for (int i=0; i<expect->size && node != NULL; ++i)
+ {
+ if (reversed)
+ {
+ if (expect->content[expect->size - 1 - i] != node->value)
+ {
+ printf ("FAIL: mismatching expected (%d) VS current (%d).\n",
+ expect->content[expect->size - 1 - i], node->value);
+ passed = false;
+ }
+ if (node->prev == NULL && current->first_ != node)
+ {
+ printf ("FAIL: first_ is not matching the first node.\n");
+ passed = false;
+ }
+ }
+ else
+ {
+ if (expect->content[i] != node->value)
+ {
+ printf ("FAIL: mismatching expected (%d) VS current (%d).\n",
+ expect->content[i], node->value);
+ passed = false;
+ }
+ if (node->next == NULL && current->last_ != node)
+ {
+ printf ("FAIL: last_ is not matching the last node.\n");
+ passed = false;
+ }
+ }
+
+ if (!passed)
+ return false;
+
+ if (reversed)
+ node = node->prev;
+ else
+ node = node->next;
+ }
+
+ if (node != NULL)
+ {
+ printf ("FAIL: the list is longer than expected.\n");
+ passed = false;
+ }
+ if (expect->size != current->size)
+ {
+ printf ("FAIL: size (%d) is not matching the real size of the list (%d).\n",
+ current->size, expect->size);
+ passed = false;
+ }
+
+ return passed;
+}
+
+bool check(const char *op,
+ const struct test_data_t *expect,
+ LinkedListWrapperType *wrapper)
+{
+ bool success = true;
+ bool res;
+
+ 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_);
+ res = run_test (expect, wrapper, true);
+ printf ("%s: test-linked-list::%s: check backward conformity\n",
+ res ? "PASS": "FAIL", op);
+ success &= res;
+
+ return success;
+}
+
+const int EXPECT_0 [] = { 10, 4, 3, 1, 9, 2 };
+const int EXPECT_1 [] = { 1, 2, 3, 4, 9, 10 };
+const int EXPECT_2 [] = { 11, 1, 2, 3, 4, 9, 10 };
+const int EXPECT_3 [] = { 11, 1, 2, 3, 4, 9, 8, 10 };
+const int EXPECT_4 [] = { 11, 2, 3, 4, 9, 8, 10 };
+const int EXPECT_5 [] = { 2, 3, 4, 8, 9, 10, 11 };
+const int EXPECT_6 [] = { 3, 4, 8, 9, 10, 11 };
+const int EXPECT_7 [] = { 3, 4, 8, 9, 10 };
+const struct test_data_t test_data[] = {
+ { .content = EXPECT_0, .size = sizeof(EXPECT_0) / sizeof(EXPECT_0[0]) },
+ { .content = EXPECT_1, .size = sizeof(EXPECT_1) / sizeof(EXPECT_1[0]) },
+ { .content = EXPECT_2, .size = sizeof(EXPECT_2) / sizeof(EXPECT_2[0]) },
+ { .content = EXPECT_3, .size = sizeof(EXPECT_3) / sizeof(EXPECT_3[0]) },
+ { .content = EXPECT_4, .size = sizeof(EXPECT_4) / sizeof(EXPECT_4[0]) },
+ { .content = EXPECT_5, .size = sizeof(EXPECT_5) / sizeof(EXPECT_5[0]) },
+ { .content = EXPECT_6, .size = sizeof(EXPECT_6) / sizeof(EXPECT_6[0]) },
+ { .content = EXPECT_7, .size = sizeof(EXPECT_7) / sizeof(EXPECT_7[0]) },
+};
+
+int main (void)
+{
+ int failures = 0;
+
+ LinkedListWrapperType wrapper = {
+ .first_ = NULL,
+ .last_ = NULL,
+ .size = 0,
+ };
+
+ /* Append nodes. */
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (10));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (4));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (3));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (1));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (9));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (2));
+
+ failures += ! check ("append", &test_data[0], &wrapper);
+
+ /* Sort nodes (without updating wrapper). */
+ wrapper.first_ =
+ _LINKED_LIST_MERGE_SORT(ListNodeType) (wrapper.first_, compare_nodes);
+ wrapper.last_ = find_last_node (wrapper.first_);
+
+ failures += ! check ("sort", &test_data[1], &wrapper);
+
+ /* Save a reference to this node for later. */
+ ListNodeType *n_to_remove = wrapper.first_;
+
+ /* Prepend node. */
+ LINKED_LIST_PREPEND(ListNodeType) (&wrapper, l_new_node (11));
+ failures += ! check ("prepend", &test_data[2], &wrapper);
+
+ /* Insert node. */
+ LINKED_LIST_INSERT_BEFORE(ListNodeType) (&wrapper, l_new_node (8), wrapper.last_);
+ failures += ! check ("insert_before", &test_data[3], &wrapper);
+
+ /* Remove a node. */
+ LINKED_LIST_REMOVE(ListNodeType) (&wrapper, n_to_remove);
+ failures += ! check ("remove", &test_data[4], &wrapper);
+
+ /* Sort nodes. */
+ LINKED_LIST_MERGE_SORT(ListNodeType) (&wrapper, compare_nodes);
+ failures += ! check ("sort", &test_data[5], &wrapper);
+
+ /* Pop front. */
+ LINKED_LIST_POP_FRONT(ListNodeType) (&wrapper);
+ failures += ! check ("pop_front", &test_data[6], &wrapper);
+
+ /* Pop back. */
+ LINKED_LIST_POP_BACK(ListNodeType) (&wrapper);
+ failures += ! check ("pop_back", &test_data[7], &wrapper);
+
+ exit (failures ? EXIT_FAILURE : EXIT_SUCCESS);
+}