Re: Node to first or last element of a sequential list in module list/xlist

[Bruno Haible <bruno@clisp.org>]

Hi Marc,

> At the moment, there does not seem to be an easy way to retrieve the node
> of the first or the last element in a list.

The purpose of the gl_list_node_t is to write algorithms that work
efficiently with linked-lists, when it is necessary (for performance)
to hold a reference to a linked-list node that is far from the first and
far from the last linked-list node.

For the first and the last node in a list, there is no such performance
problem. Hence what you ask for is not needed.

> This is useful if the list has to be traversed while nodes are added
> because an iterator cannot be used here.

I don't understand. You want to use a list_node_t while adding nodes to
the list? This is invalid, since the comments in gl_list.h say:

  /* Type representing the position of an element in the list, in a way that
     is more adapted to the list implementation than a plain index.
     Note: It is invalidated by insertions and removals!  */
  typedef struct gl_list_node_impl * gl_list_node_t;

> What is currently possible is to use get_first/set_first (and
> get_last/set_last) to get hold of the first (and last) node but this is
> clearly a hack.
> 
> Another way to get hold of the first node is to create an iterator and to
> call its next procedure just once. But this is overkill if the iterator
> isn't used afterward.

Yes these are two existing ways to do what you want. An iterator is a
small stack-allocated object; it is designed for being created and then
thrown away soon afterwards.

> What I want to propose is to allow the NULL value in
> gl_next_node/gl_previous_node. In this case, gl_next_node shall return the
> first node and gl_previous_node shall return the last node.

It's not useful to extend an API
  - for a rare fringe use-case,
  - when there are already two other ways to do what you ask for (with the
    same O(·) performance).

Bruno