[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 18:46:14 +0200

Hi Bruno,

thank you very much!

Am Sa., 3. Apr. 2021 um 18:28 Uhr schrieb Bruno Haible <bruno@clisp.org>:
Marc Nieper-Wißkirchen wrote:
> 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.

Now I see what you mean. Quasi companion functions to gl_list_next_node
and gl_list_previous_node: gl_list_first_node and gl_list_last_node,

I'm sorry for any confusion. I should have expressed myself more clearly in my initial email.
> What I want to propose is to allow the NULL value in
> gl_next_node/gl_previous_node. In this case, gl_next_node shall return the
> first node and gl_previous_node shall return the last node.

Yes, gl_list_first_node and gl_list_last_node are indeed much better. I was only worried about the size of the vtable.
I don't think this encourages robust programs. If a program passes a NULL
pointer to gl_list_next_node or gl_list_previous_node, the program should
better crash.

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

Yes, some algorithms need a second, temporary list. Not all algorithms
can be written to use the original list, be efficient in O() terms, and
be implementation-independent.

Speaking of this, this is not always non-trivial if the dispose function is not NULL. Consider an algorithm that processes one list to produce a new one. In the end, the old list shall be removed but the items that have ended up in the new list shall not be disposed. I guess that the canonical way to achieve this is to use gl_list_set to overwrite the values in the old list with dummy values (e.g. NULL) so that they are not freed on eventual removal.

-- Marc

reply via email to

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