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
