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

[Bruno Haible]

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

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

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.


2021-04-03  Bruno Haible  <bruno@clisp.org>

        *-list tests: Add more tests.
        * tests/test-array_list.c (check_equals_by_forward_iteration,
        check_equals_by_backward_iteration): New functions.
        (main): Invoke them.
        * tests/test-carray_list.c: Likewise.
        * tests/test-linked_list.c: Likewise.
        * tests/test-linkedhash_list.c: Likewise.
        * tests/test-avltree_list.c: Likewise.
        * tests/test-avltreehash_list.c: Likewise.
        * tests/test-rbtree_list.c: Likewise.
        * tests/test-rbtreehash_list.c: Likewise.

        list: Add operations first_node, last_node.
        Reported by Marc Nieper-Wißkirchen in
        <https://lists.gnu.org/archive/html/bug-gnulib/2021-04/msg00005.html>.
        * lib/gl_list.h (gl_list_first_node, gl_list_last_node): New functions.
        (struct gl_list_implementation): Add members first_node, last_node.
        * lib/gl_array_list.c (gl_array_first_node, gl_array_last_node): New
        functions.
        (gl_array_list_implementation): Add the new operations.
        * lib/gl_carray_list.c (gl_carray_first_node, gl_carray_last_node): New
        functions.
        (gl_carray_list_implementation): Add the new operations.
        * lib/gl_anylinked_list2.h (gl_linked_first_node, gl_linked_last_node):
        New functions.
        * lib/gl_linked_list.c (gl_linked_list_implementation): Add the new
        operations.
        * lib/gl_linkedhash_list.c (gl_linkedhash_list_implementation):
        Likewise.
        * lib/gl_anytree_list2.h (gl_tree_first_node, gl_tree_last_node): New
        functions.
        * lib/gl_avltree_list.c (gl_avltree_list_implementation): Add the new
        operations.
        * lib/gl_avltreehash_list.c (gl_avltreehash_list_implementation):
        Likewise.
        * lib/gl_rbtree_list.c (gl_rbtree_list_implementation): Likewise.
        * lib/gl_rbtreehash_list.c (gl_rbtreehash_list_implementation):
        Likewise.
        * lib/gl_sublist.c (gl_sublist_first_node, gl_sublist_last_node): New
        functions.
        (gl_sublist_list_implementation): Add the new operations.
        * lib/gl_list.hh (class gl_List): Add member functions first_node,
        last_node.
        * doc/containers.texi: Update table.

0001-list-Add-operations-first_node-last_node.patch
Description: Text Data

0002-list-tests-Add-more-tests.patch
Description: Text Data