Am Sa., 3. Apr. 2021 um 12:14 Uhr schrieb Bruno Haible <br...@clisp.org>:
> Marc Nieper-Wißkirchen wrote: > > > > > 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; > > > > > > > > > > > > > It won't work with removals but it does work with insertions because > > > > gl_list_add_before/gl_list_add_after/... etc. all return new, valid > list > > > > node objects. > > > > > > While this may be true for the linked-list implementation, it is not > true > > > for the array-list and other implementation. But the point of the > Gnulib > > > list module is to allow the developer to switch to a different > > > implementation > > > without changing their algorithms. [1] > > > > > > > I understand the point about being able to switch to a different > > implementation and subscribe to it, but I don't understand why there > should > > be a problem with array-list or other implementations. > > When a program, say, takes the gl_list_node_t to the 3rd element of a list, > then inserts an element at the beginning or between the two first elements > of the list, and then attempts to use said gl_list_node_t: > - In the case of a linked-list, it will refer to the 4th element of the > list, > - In the case of an array-list, it will refer to the 3rd element of the > list, > that is, to the element that was previously the 2nd one. > > You can't write implementation-independent algorithms while doing this > kind of things. > This is not what I have been having in mind and it's clear that such a thing wouldn't work. I have been talking about list walking algorithms that insert items in the list *while* walking (and which cannot be done with iterators). For example, given a list of fruits, insert "pear" after each "apple" and "peach" before each "apple". This can be easily done through gl_list_add_before/gl_list_add_after/gl_list_next_node without using invalidated nodes. The only missing piece to have a clear C formulation of the algorithm (without having to resort to the "set_first (get_first)"-hack) is a canonical clean way to retrieve the first node (or last node for similar algorithms). > > Besides, what's the point of > > returning nodes if they weren't valid? > > They are valid, but only until the next destructive operation. > Exactly! And more isn't needed. Thanks, Marc PS What can't be done (because gl_list_remove doesn't return a valid (next?) node) is list walking algorithms that both remove and insert nodes. For removal, one has to use an iterator.
