[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Marc Nieper-Wißkirchen
Subject: Re: Node to first or last element of a sequential list in module list/xlist
Date: Sat, 3 Apr 2021 12:26:08 +0200

Am Sa., 3. Apr. 2021 um 12:14 Uhr schrieb Bruno Haible <bruno@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.

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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]