Re: Add gl_list_remove_last to list/xlist

[Bruno Haible]

Hi Marc,

> I didn't mean that gl_list_remove_last
> should return the just deleted node but the node of the element that
> is now the last one (the respectively first one for
> gl_list_remove_first) after the removal.

The gl_list_node_t type, in the 'list' interface so far, is used in
operations that work on a single position. Except for the functions
gl_list_next_node and gl_list_previous_node, which intentionally
walk from one node to a neighbour node. Having a function that
does an effect on the last element and returns the position of the
second-to-last element would be an invitation to incorrect coding.
Better keep the operations simple!

Also, I don't see why your proposed operation would be important to
have in a general API for lists.

> The motivation behind my suggestion is to make it easy to implement a
> stack (or a FIFO queue) with the gl_list interface.

It is already easy to implement a stack or FIFO using the primitives.
E.g. stack_pop = 
  1. gl_list_get_at (list, gl_list_size (list) - 1)
  2. gl_list_remove_at (list, gl_list_size (list) - 1) or
     gl_list_remove_last (list).

It would be a mistake to add semantics of stack or FIFO directly to the
list interface, because a list *is* not a stack or a FIFO; a list *can
be used to implement* a stack or a FIFO. It is an important concept
that one interface can be used to implement another interface (->
layered software, hiding implementation details, etc.).

See e.g. in Java: they have different interfaces for list [1], stack [2],
and FIFO [2]. Initially, they defined Stack as a subclass of AbstractList,
but realized later that it was a mistake.

You are welcome to add a stack or FIFO module in gnulib. Most likely,
each of the two will only have a single implementation. Why? Because
  - for stacks, the ARRAY and LINKED implementations would have the
    same O() complexity for each operation, and then ARRAY would be
    preferred because it is more efficient regarding use of memory
    and L1/L2 caches,
  - for FIFOs, the CARRAY and LINKED implementations would have the
    same O() complexity for each operation, and similarly CARRAY would
    be preferred because it is more efficient regarding use of memory
    and L1/L2 caches.

> For this,
> operations like gl_list_get_first and gl_list_get_last with guaranteed
> O(1) behavior for a number of list implementations would also be nice.

Hmm. I'm reluctant to introduce 4 new functions
  gl_list_get_first
  gl_list_get_last
  gl_list_set_first
  gl_list_set_last
when the gl_list_get/gl_list_set operations with appropriate position
argument already do the job. It appears to be more of a documentation
issue, right? I.e. I should better revert yesterday's patch, and instead,
in the table show the guaranteed average performance
  gl_list_get_first
  gl_list_get_last
  gl_list_set_first
  gl_list_set_last
  gl_list_remove_first
  gl_list_remove_last
where these 6 functions are defined globally, not separately for each
implementation.

Bruno

[1] https://docs.oracle.com/javase/8/docs/api/java/util/AbstractList.html
[2] https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html