[PATCH v3 09/26] libiberty: add common methods for type-sensitive doubly linked lists

[Matthieu Longo]

On 2025-06-17 14:54, Richard Earnshaw (lists) wrote:
> On 09/05/2025 16:12, 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: to use always in a
>>     source file.
>> 3. for the invokation 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                  | 355 ++++++++++++++++++
>>   libiberty/Makefile.in                         |   1 +
>>   libiberty/testsuite/Makefile.in               |  12 +-
>>   libiberty/testsuite/test-doubly-linked-list.c | 250 ++++++++++++
>>   4 files changed, 617 insertions(+), 1 deletion(-)
>>   create mode 100644 include/doubly-linked-list.h
>>   create mode 100644 libiberty/testsuite/test-doubly-linked-list.c
>>
>> diff --git a/include/doubly-linked-list.h b/include/doubly-linked-list.h
>> new file mode 100644
>> index 00000000000..520a3b0dd3c
>> --- /dev/null
>> +++ b/include/doubly-linked-list.h
>> @@ -0,0 +1,355 @@
>> +/* 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/>.  */
>> +
>> +
>> +#ifndef _DOUBLY_LINKED_LIST_H
>> +#define _DOUBLY_LINKED_LIST_H
>> +
>> +#include <assert.h>
>> +
> 
> I think there should be a comment here documenting the API that this header exports.  Most of this code is just 'implementation' that shouldn't concern users, but the API itself and any limitations should be made clear up-front.
> 
> Note that multi-line comments in GNU code use one '/*' on the first line and one '*/' on the final line.  We don't use additional comment start end in between and we don't put '*' at the begining or end of lines.  So,
> 
> /* This is the start of
>     a multi-line comment.  */
> 
> Not
> 
> /* This is the start of */
> /* a multi-line comment.  */
> 
> or
> 
> /* This is the start of   *
>   * a multi-line comment.  */
> 
> or any other permutation of slashes and asterisks.
> 
> 

Fixed in the next revision.

>> +
>> +/***********************
>> + * Mutative operations *
>> + ***********************/
> 
> The convention is generally to separate sub-sections using page-break/form-feed control characters, (ie ^L - ascii 0x0c).  The comment that immediately follows that would then use the normal style.  So:
> 
> ^L
> /* Mutative operations.  */
> 

Fixed in the next revision.

>> +
>> +#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);			\
>> +  \
>> +  EXPORT void								\
>> +  LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2)
>> +
>> +#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_SWAP(LTYPE)			LTYPE##_swap
>> +
>> +#define VALUE_SWAP(a, b) do { typeof(a) temp = a; a = b; b = temp; } while (0)
>> +
>> +#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.  */			\
> 
> Put the comment above the macro, not as part of it.
> 

Fixed in the next revision.

>> +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;							\
>> +}									\
> 
> I would create one macro for each operation, then define one macro that uses all the individual operations.  That keeps each macro small enough to be comprehensible as a unit and means that function-related comments can live outside the macro itself.
> 

Fixed in the next revision.

> Do these operations need to be addressable?  If not, I'd make them all static inline, that should also solve the problem of needing to use pragma onece.  If there are instances that need to be addressed, you can still use suitable combinations of inline and extern inline to create the relevant definitions, but one file will need to invoke a macro that creates the concrete definitions.  So something like
> 
> LINKED_LIST_MUTATIVE_OPS_DECL (LinkedListWrapperType, ListNodeType, static)
> 
> /* Create the non-inline functions.  Only needed in one file.  */
> LINKED_LIST_MUTATIVE_OPS_DEFN (LinkedListWrapperType, ListNodeType, static)
> 

Yes, I would expect that the symbol of the operation is exportable if 
static is not specified for LINKED_LIST_MUTATIVE_OPS_DEFN.

>> +\
>> +/* Prepend the given node new_ to the exiting list.  */			\
>> +EXPORT void								\
>> +LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_)			\
>> +{									\
>> +  if (wrapper->first_ == NULL)						\
> 
> How about using wrapper->LTYPE##_first rather than relying on potentially non-portable leading or trailing variable names?
> 
> If that's too cumbersome just document that the header reserves fields starting with, say, dbl_ll_ then use that as a prefix when needed, giving dbl_ll_first in this instance.  (I was going to suggest dll_ as a prefix, but that might be confused with, well, DLLs.)
> 

I opted for documenting those requirements in the header.
Clashes of name for the attributes are detected by the compiler, and I 
prefer to delegate to the list structures the responsibility that there 
is no clash.
So I would prefer to keep the names as they are.