Re: Add gl_list_remove_last to list/xlist

[Marc Nieper-Wißkirchen]

Hi Bruno,

[...]

> 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!

That's a fair point of view.

[...]

> > 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.).

Okay; I agree that a separate stack or FIFO module can make more
sense; in particular when it only has to deal with a single
implementation of an underlying data structure. At the moment I do
have other work to finish first, but maybe I will find some time in
the near future for a stack module.

[...]

> > 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.

When the functions can be defined globally, that's better than adding
six functions to each vtable. Partly, it is just a documentation
issue. I don't see, however, to implement the function dealing with
end of the list in O(1) behavior when the underlying data structure is
a linked list. Don't we need to expose an implementation-dependent
gl_list_get_last_node (gl_list_first_node for symmetry)? The rest
should then be implementable easily.

Marc