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

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

[Marc Nieper-Wißkirchen]

[-- Attachment #1: Type: text/plain, Size: 758 bytes --]

Hi!

At the moment, there does not seem to be an easy way to retrieve the node
of the first or the last element in a list.

This is useful if the list has to be traversed while nodes are added
because an iterator cannot be used here.

What is currently possible is to use get_first/set_first (and
get_last/set_last) to get hold of the first (and last) node but this is
clearly a hack.

Another way to get hold of the first node is to create an iterator and to
call its next procedure just once. But this is overkill if the iterator
isn't used afterward.

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.

Thanks,

Marc

[-- Attachment #2: Type: text/html, Size: 1810 bytes --]

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

[Bruno Haible]

Hi Marc,

> At the moment, there does not seem to be an easy way to retrieve the node
> of the first or the last element in a list.

The purpose of the gl_list_node_t is to write algorithms that work
efficiently with linked-lists, when it is necessary (for performance)
to hold a reference to a linked-list node that is far from the first and
far from the last linked-list node.

For the first and the last node in a list, there is no such performance
problem. Hence what you ask for is not needed.

> This is useful if the list has to be traversed while nodes are added
> because an iterator cannot be used here.

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;

> What is currently possible is to use get_first/set_first (and
> get_last/set_last) to get hold of the first (and last) node but this is
> clearly a hack.
> 
> Another way to get hold of the first node is to create an iterator and to
> call its next procedure just once. But this is overkill if the iterator
> isn't used afterward.

Yes these are two existing ways to do what you want. An iterator is a
small stack-allocated object; it is designed for being created and then
thrown away soon afterwards.

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

It's not useful to extend an API
  - for a rare fringe use-case,
  - when there are already two other ways to do what you ask for (with the
    same O(·) performance).

Bruno

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

[Marc Nieper-Wißkirchen]

[-- Attachment #1: Type: text/plain, Size: 1494 bytes --]

Hi,

Am Sa., 3. Apr. 2021 um 00:49 Uhr schrieb Bruno Haible <bruno@clisp.org>:

> This is useful if the list has to be traversed while nodes are added
> > because an iterator cannot be used here.
>
> 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.


> > 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.
>
> It's not useful to extend an API
>   - for a rare fringe use-case,
>

Why do you think it is a fringe use-case? Algorithms that walk a list and
add nodes during the traversal are not uncommon.

  - when there are already two other ways to do what you ask for (with the
>     same O(·) performance).
>

User's code would be more self-documenting if a "hack" like

gl_list_node_t last_node = gl_list_set_last (list, gl_get_last (list))

wouldn't be needed.

Thanks,

Marc

[-- Attachment #2: Type: text/html, Size: 3075 bytes --]

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

[Bruno Haible]

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]

Bruno

[1] https://savannah.gnu.org/forum/forum.php?forum_id=9898

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

[Marc Nieper-Wißkirchen]

[-- Attachment #1: Type: text/plain, Size: 1577 bytes --]

Am Sa., 3. Apr. 2021 um 11:49 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 I look into
"lib/gl_array_list.c", I see that a valid node is returned, namely the node
corresponding to the newly inserted element.  Besides, what's the point of
returning nodes if they weren't valid?  Note that we are not talking about
reusing the node object used as the argument to add_before or add_after.
That is invalid, indeed.

[-- Attachment #2: Type: text/html, Size: 2078 bytes --]

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

[Bruno Haible]

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.

> Besides, what's the point of
> returning nodes if they weren't valid?

They are valid, but only until the next destructive operation.

Bruno

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

[Marc Nieper-Wißkirchen]

[-- Attachment #1: Type: text/plain, Size: 2994 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 4664 bytes --]

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

[Bruno Haible]

[-- Attachment #1: Type: text/plain, Size: 3197 bytes --]

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.


[-- Attachment #2: 0001-list-Add-operations-first_node-last_node.patch --]
[-- Type: text/x-patch, Size: 16642 bytes --]

From cce713624d68c60d9d6eeb11747500db998821a2 Mon Sep 17 00:00:00 2001
From: Bruno Haible <bruno@clisp.org>
Date: Sat, 3 Apr 2021 17:59:47 +0200
Subject: [PATCH 1/2] list: Add operations first_node, last_node.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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.
---
 ChangeLog                 | 35 +++++++++++++++++++++++++++++++++++
 doc/containers.texi       | 18 ++++++++++++++++++
 lib/gl_anylinked_list2.h  | 18 ++++++++++++++++++
 lib/gl_anytree_list2.h    | 26 ++++++++++++++++++++++++++
 lib/gl_array_list.c       | 20 ++++++++++++++++++++
 lib/gl_avltree_list.c     |  2 ++
 lib/gl_avltreehash_list.c |  2 ++
 lib/gl_carray_list.c      | 20 ++++++++++++++++++++
 lib/gl_linked_list.c      |  2 ++
 lib/gl_linkedhash_list.c  |  2 ++
 lib/gl_list.h             | 35 +++++++++++++++++++++++++++++++++++
 lib/gl_list.hh            |  8 ++++++++
 lib/gl_rbtree_list.c      |  2 ++
 lib/gl_rbtreehash_list.c  |  2 ++
 lib/gl_sublist.c          | 21 +++++++++++++++++++++
 15 files changed, 213 insertions(+)

diff --git a/ChangeLog b/ChangeLog
index 9323aa9..958ad02 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,40 @@
 2021-04-03  Bruno Haible  <bruno@clisp.org>
 
+	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.
+
+2021-04-03  Bruno Haible  <bruno@clisp.org>
+
 	xalloc-die: Fix compilation error (regression from 2021-03-28).
 	* lib/xalloc.h: Don't include idx.h and xalloc-oversized.h if the module
 	'xalloc' is not in use.
diff --git a/doc/containers.texi b/doc/containers.texi
index cb0c22a..15c915b 100644
--- a/doc/containers.texi
+++ b/doc/containers.texi
@@ -151,6 +151,24 @@ for the ``sequential list'' data type are:
 @tab @math{O(1)}
 @tab @math{O(@log n)}
 @tab @math{O(@log n)}
+@item @code{gl_list_first_node}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(@log n)}
+@item @code{gl_list_last_node}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(@log n)}
 @item @code{gl_list_get_at}
 @tab @math{O(1)}
 @tab @math{O(1)}
diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h
index 1434d59..6af3f76 100644
--- a/lib/gl_anylinked_list2.h
+++ b/lib/gl_anylinked_list2.h
@@ -229,6 +229,24 @@ gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
   return (node->prev != &list->root ? node->prev : NULL);
 }
 
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_linked_first_node (gl_list_t list)
+{
+  if (list->count > 0)
+    return list->root.next;
+  else
+    return NULL;
+}
+
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_linked_last_node (gl_list_t list)
+{
+  if (list->count > 0)
+    return list->root.prev;
+  else
+    return NULL;
+}
+
 static const void * _GL_ATTRIBUTE_PURE
 gl_linked_get_at (gl_list_t list, size_t position)
 {
diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h
index 59fe01d..fbf514b 100644
--- a/lib/gl_anytree_list2.h
+++ b/lib/gl_anytree_list2.h
@@ -140,6 +140,32 @@ gl_tree_previous_node (gl_list_t list _GL_ATTRIBUTE_MAYBE_UNUSED,
   return node;
 }
 
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_tree_first_node (gl_list_t list _GL_ATTRIBUTE_MAYBE_UNUSED)
+{
+  gl_list_node_t node = list->root;
+
+  if (node != NULL)
+    {
+      while (node->left != NULL)
+        node = node->left;
+    }
+  return node;
+}
+
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_tree_last_node (gl_list_t list _GL_ATTRIBUTE_MAYBE_UNUSED)
+{
+  gl_list_node_t node = list->root;
+
+  if (node != NULL)
+    {
+      while (node->right != NULL)
+        node = node->right;
+    }
+  return node;
+}
+
 /* Returns the node at the given position < gl_tree_size (list).  */
 static gl_list_node_t _GL_ATTRIBUTE_PURE
 node_at (gl_list_node_t root, size_t position)
diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c
index e30b881..203e618 100644
--- a/lib/gl_array_list.c
+++ b/lib/gl_array_list.c
@@ -166,6 +166,24 @@ gl_array_previous_node (gl_list_t list, gl_list_node_t node)
     return NULL;
 }
 
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_array_first_node (gl_list_t list)
+{
+  if (list->count > 0)
+    return INDEX_TO_NODE (0);
+  else
+    return NULL;
+}
+
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_array_last_node (gl_list_t list)
+{
+  if (list->count > 0)
+    return INDEX_TO_NODE (list->count - 1);
+  else
+    return NULL;
+}
+
 static const void * _GL_ATTRIBUTE_PURE
 gl_array_get_at (gl_list_t list, size_t position)
 {
@@ -651,6 +669,8 @@ const struct gl_list_implementation gl_array_list_implementation =
     gl_array_node_nx_set_value,
     gl_array_next_node,
     gl_array_previous_node,
+    gl_array_first_node,
+    gl_array_last_node,
     gl_array_get_at,
     gl_array_nx_set_at,
     gl_array_search_from_to,
diff --git a/lib/gl_avltree_list.c b/lib/gl_avltree_list.c
index 241949a..801b141 100644
--- a/lib/gl_avltree_list.c
+++ b/lib/gl_avltree_list.c
@@ -77,6 +77,8 @@ const struct gl_list_implementation gl_avltree_list_implementation =
     gl_tree_node_nx_set_value,
     gl_tree_next_node,
     gl_tree_previous_node,
+    gl_tree_first_node,
+    gl_tree_last_node,
     gl_tree_get_at,
     gl_tree_nx_set_at,
     gl_tree_search_from_to,
diff --git a/lib/gl_avltreehash_list.c b/lib/gl_avltreehash_list.c
index 5d0be7e..9a96f68 100644
--- a/lib/gl_avltreehash_list.c
+++ b/lib/gl_avltreehash_list.c
@@ -100,6 +100,8 @@ const struct gl_list_implementation gl_avltreehash_list_implementation =
     gl_tree_node_nx_set_value,
     gl_tree_next_node,
     gl_tree_previous_node,
+    gl_tree_first_node,
+    gl_tree_last_node,
     gl_tree_get_at,
     gl_tree_nx_set_at,
     gl_tree_search_from_to,
diff --git a/lib/gl_carray_list.c b/lib/gl_carray_list.c
index a50f093..add4cc3 100644
--- a/lib/gl_carray_list.c
+++ b/lib/gl_carray_list.c
@@ -181,6 +181,24 @@ gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
     return NULL;
 }
 
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_carray_first_node (gl_list_t list)
+{
+  if (list->count > 0)
+    return INDEX_TO_NODE (0);
+  else
+    return NULL;
+}
+
+static gl_list_node_t _GL_ATTRIBUTE_PURE
+gl_carray_last_node (gl_list_t list)
+{
+  if (list->count > 0)
+    return INDEX_TO_NODE (list->count - 1);
+  else
+    return NULL;
+}
+
 static const void * _GL_ATTRIBUTE_PURE
 gl_carray_get_at (gl_list_t list, size_t position)
 {
@@ -844,6 +862,8 @@ const struct gl_list_implementation gl_carray_list_implementation =
     gl_carray_node_nx_set_value,
     gl_carray_next_node,
     gl_carray_previous_node,
+    gl_carray_first_node,
+    gl_carray_last_node,
     gl_carray_get_at,
     gl_carray_nx_set_at,
     gl_carray_search_from_to,
diff --git a/lib/gl_linked_list.c b/lib/gl_linked_list.c
index f46d45b..087968e 100644
--- a/lib/gl_linked_list.c
+++ b/lib/gl_linked_list.c
@@ -38,6 +38,8 @@ const struct gl_list_implementation gl_linked_list_implementation =
     gl_linked_node_nx_set_value,
     gl_linked_next_node,
     gl_linked_previous_node,
+    gl_linked_first_node,
+    gl_linked_last_node,
     gl_linked_get_at,
     gl_linked_nx_set_at,
     gl_linked_search_from_to,
diff --git a/lib/gl_linkedhash_list.c b/lib/gl_linkedhash_list.c
index 2c76bae..70eca52 100644
--- a/lib/gl_linkedhash_list.c
+++ b/lib/gl_linkedhash_list.c
@@ -86,6 +86,8 @@ const struct gl_list_implementation gl_linkedhash_list_implementation =
     gl_linked_node_nx_set_value,
     gl_linked_next_node,
     gl_linked_previous_node,
+    gl_linked_first_node,
+    gl_linked_last_node,
     gl_linked_get_at,
     gl_linked_nx_set_at,
     gl_linked_search_from_to,
diff --git a/lib/gl_list.h b/lib/gl_list.h
index 3c1aede..7fc22bb 100644
--- a/lib/gl_list.h
+++ b/lib/gl_list.h
@@ -73,6 +73,8 @@ extern "C" {
    gl_list_node_set_value      O(1)     O(1)     O(1)      O(1)    O((log n)²)/O(1)
    gl_list_next_node           O(1)     O(1)   O(log n)    O(1)       O(log n)
    gl_list_previous_node       O(1)     O(1)   O(log n)    O(1)       O(log n)
+   gl_list_first_node          O(1)     O(1)   O(log n)    O(1)       O(log n)
+   gl_list_last_node           O(1)     O(1)   O(log n)    O(1)       O(log n)
    gl_list_get_at              O(1)     O(n)   O(log n)    O(n)       O(log n)
    gl_list_get_first           O(1)     O(1)   O(log n)    O(1)       O(log n)
    gl_list_get_last            O(1)     O(1)   O(log n)    O(1)       O(log n)
@@ -207,6 +209,23 @@ extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
    if the given node is the first (leftmost) one in the list.  */
 extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
 
+/* Returns the first node in the list, or NULL if the list is empty.
+   This function is useful for iterating through the list like this:
+     gl_list_node_t node;
+     for (node = gl_list_first_node (list); node != NULL; node = gl_list_next_node (node))
+       ...
+ */
+extern gl_list_node_t gl_list_first_node (gl_list_t list);
+
+/* Returns the last node in the list, or NULL if the list is empty.
+   This function is useful for iterating through the list in backward order,
+   like this:
+     gl_list_node_t node;
+     for (node = gl_list_last_node (list); node != NULL; node = gl_list_previous_node (node))
+       ...
+ */
+extern gl_list_node_t gl_list_last_node (gl_list_t list);
+
 /* Returns the element at a given position in the list.
    POSITION must be >= 0 and < gl_list_size (list).  */
 extern const void * gl_list_get_at (gl_list_t list, size_t position);
@@ -507,6 +526,8 @@ struct gl_list_implementation
                             const void *elt);
   gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
   gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
+  gl_list_node_t (*first_node) (gl_list_t list);
+  gl_list_node_t (*last_node) (gl_list_t list);
   const void * (*get_at) (gl_list_t list, size_t position);
   gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
                                const void *elt);
@@ -631,6 +652,20 @@ gl_list_previous_node (gl_list_t list, gl_list_node_t node)
          ->previous_node (list, node);
 }
 
+GL_LIST_INLINE gl_list_node_t
+gl_list_first_node (gl_list_t list)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+         ->first_node (list);
+}
+
+GL_LIST_INLINE gl_list_node_t
+gl_list_last_node (gl_list_t list)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+         ->last_node (list);
+}
+
 GL_LIST_INLINE const void *
 gl_list_get_at (gl_list_t list, size_t position)
 {
diff --git a/lib/gl_list.hh b/lib/gl_list.hh
index 7bff5dd..af2ca67 100644
--- a/lib/gl_list.hh
+++ b/lib/gl_list.hh
@@ -134,6 +134,14 @@ public:
   gl_list_node_t previous_node (gl_list_node_t node) const
     { return gl_list_previous_node (_ptr, node); }
 
+  /* Returns the first node in the list, or NULL if the list is empty.  */
+  gl_list_node_t first_node () const
+    { return gl_list_first_node (_ptr); }
+
+  /* Returns the last node in the list, or NULL if the list is empty.  */
+  gl_list_node_t last_node () const
+    { return gl_list_last_node (_ptr); }
+
   /* Returns the element at a given position in the list.
      POSITION must be >= 0 and < gl_list_size (list).  */
   ELTYPE * get_at (size_t position) const
diff --git a/lib/gl_rbtree_list.c b/lib/gl_rbtree_list.c
index 185ed82..9a053b4 100644
--- a/lib/gl_rbtree_list.c
+++ b/lib/gl_rbtree_list.c
@@ -78,6 +78,8 @@ const struct gl_list_implementation gl_rbtree_list_implementation =
     gl_tree_node_nx_set_value,
     gl_tree_next_node,
     gl_tree_previous_node,
+    gl_tree_first_node,
+    gl_tree_last_node,
     gl_tree_get_at,
     gl_tree_nx_set_at,
     gl_tree_search_from_to,
diff --git a/lib/gl_rbtreehash_list.c b/lib/gl_rbtreehash_list.c
index c4a3c7d..d8fcb8e 100644
--- a/lib/gl_rbtreehash_list.c
+++ b/lib/gl_rbtreehash_list.c
@@ -101,6 +101,8 @@ const struct gl_list_implementation gl_rbtreehash_list_implementation =
     gl_tree_node_nx_set_value,
     gl_tree_next_node,
     gl_tree_previous_node,
+    gl_tree_first_node,
+    gl_tree_last_node,
     gl_tree_get_at,
     gl_tree_nx_set_at,
     gl_tree_search_from_to,
diff --git a/lib/gl_sublist.c b/lib/gl_sublist.c
index bdd7d50..63359b8 100644
--- a/lib/gl_sublist.c
+++ b/lib/gl_sublist.c
@@ -122,6 +122,25 @@ gl_sublist_previous_node (gl_list_t list, gl_list_node_t node)
     return NULL;
 }
 
+static gl_list_node_t
+gl_sublist_first_node (gl_list_t list)
+{
+  if (list->end > list->start)
+    return INDEX_TO_NODE (0);
+  else
+    return NULL;
+}
+
+static gl_list_node_t
+gl_sublist_last_node (gl_list_t list)
+{
+  size_t count = list->end - list->start;
+  if (count > 0)
+    return INDEX_TO_NODE (count - 1);
+  else
+    return NULL;
+}
+
 static const void *
 gl_sublist_get_at (gl_list_t list, size_t position)
 {
@@ -413,6 +432,8 @@ static const struct gl_list_implementation gl_sublist_list_implementation =
     gl_sublist_node_nx_set_value,
     gl_sublist_next_node,
     gl_sublist_previous_node,
+    gl_sublist_first_node,
+    gl_sublist_last_node,
     gl_sublist_get_at,
     gl_sublist_nx_set_at,
     gl_sublist_search_from_to,
-- 
2.7.4


[-- Attachment #3: 0002-list-tests-Add-more-tests.patch --]
[-- Type: text/x-patch, Size: 15792 bytes --]

From 781f81012720e7f9f4c50630f37dfc73e2ad4906 Mon Sep 17 00:00:00 2001
From: Bruno Haible <bruno@clisp.org>
Date: Sat, 3 Apr 2021 18:25:56 +0200
Subject: [PATCH 2/2] *-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.
---
 ChangeLog                     | 12 ++++++++++++
 tests/test-array_list.c       | 39 +++++++++++++++++++++++++++++++++++++++
 tests/test-avltree_list.c     | 33 +++++++++++++++++++++++++++++++++
 tests/test-avltreehash_list.c | 33 +++++++++++++++++++++++++++++++++
 tests/test-carray_list.c      | 33 +++++++++++++++++++++++++++++++++
 tests/test-linked_list.c      | 33 +++++++++++++++++++++++++++++++++
 tests/test-linkedhash_list.c  | 33 +++++++++++++++++++++++++++++++++
 tests/test-rbtree_list.c      | 33 +++++++++++++++++++++++++++++++++
 tests/test-rbtreehash_list.c  | 33 +++++++++++++++++++++++++++++++++
 9 files changed, 282 insertions(+)

diff --git a/ChangeLog b/ChangeLog
index 958ad02..117ea44 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,17 @@
 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>.
diff --git a/tests/test-array_list.c b/tests/test-array_list.c
index 1c736ee..fa60691 100644
--- a/tests/test-array_list.c
+++ b/tests/test-array_list.c
@@ -44,6 +44,42 @@ check_equals (gl_list_t list1, gl_list_t list2)
     }
 }
 
+static void
+check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  size_t n = gl_list_size (list1);
+  size_t i;
+  gl_list_node_t node2;
+
+  i = 0;
+  node2 = gl_list_first_node (list2);
+  while (i < n && node2 != NULL)
+    {
+      ASSERT (gl_list_get_at (list1, i) == gl_list_node_value (list2, node2));
+      i++;
+      node2 = gl_list_next_node (list2, node2);
+    }
+  ASSERT ((i == n) == (node2 == NULL));
+}
+
+static void
+check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  size_t n = gl_list_size (list1);
+  size_t i;
+  gl_list_node_t node2;
+
+  i = n - 1;
+  node2 = gl_list_last_node (list2);
+  while (i != (size_t)(-1) && node2 != NULL)
+    {
+      ASSERT (gl_list_get_at (list1, i) == gl_list_node_value (list2, node2));
+      i--;
+      node2 = gl_list_previous_node (list2, node2);
+    }
+  ASSERT ((i == (size_t)(-1)) == (node2 == NULL));
+}
+
 int
 main (int argc, char *argv[])
 {
@@ -75,6 +111,9 @@ main (int argc, char *argv[])
 
     check_equals (list1, list2);
 
+    check_equals_by_forward_iteration (list1, list2);
+    check_equals_by_backward_iteration (list1, list2);
+
     for (repeat = 0; repeat < 10000; repeat++)
       {
         unsigned int operation = RANDOM (18);
diff --git a/tests/test-avltree_list.c b/tests/test-avltree_list.c
index c4c0f02..b4938c4 100644
--- a/tests/test-avltree_list.c
+++ b/tests/test-avltree_list.c
@@ -48,6 +48,36 @@ check_equals (gl_list_t list1, gl_list_t list2)
 }
 
 static void
+check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_first_node (list1);
+  gl_list_node_t node2 = gl_list_first_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_next_node (list1, node1);
+      node2 = gl_list_next_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
+check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_last_node (list1);
+  gl_list_node_t node2 = gl_list_last_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_previous_node (list1, node1);
+      node2 = gl_list_previous_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
 check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
 {
   gl_avltree_list_check_invariants (list2);
@@ -92,6 +122,9 @@ main (int argc, char *argv[])
 
     check_all (list1, list2, list3);
 
+    check_equals_by_forward_iteration (list1, list2);
+    check_equals_by_backward_iteration (list1, list2);
+
     for (repeat = 0; repeat < 10000; repeat++)
       {
         unsigned int operation = RANDOM (18);
diff --git a/tests/test-avltreehash_list.c b/tests/test-avltreehash_list.c
index a77ee86..040efd3 100644
--- a/tests/test-avltreehash_list.c
+++ b/tests/test-avltreehash_list.c
@@ -75,6 +75,36 @@ check_equals (gl_list_t list1, gl_list_t list2)
 }
 
 static void
+check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_first_node (list1);
+  gl_list_node_t node2 = gl_list_first_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_next_node (list1, node1);
+      node2 = gl_list_next_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
+check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_last_node (list1);
+  gl_list_node_t node2 = gl_list_last_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_previous_node (list1, node1);
+      node2 = gl_list_previous_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
 check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
 {
   gl_avltreehash_list_check_invariants (list2);
@@ -122,6 +152,9 @@ main (int argc, char *argv[])
 
     check_all (list1, list2, list3);
 
+    check_equals_by_forward_iteration (list1, list2);
+    check_equals_by_backward_iteration (list1, list2);
+
     for (repeat = 0; repeat < 10000; repeat++)
       {
         unsigned int operation = RANDOM (18);
diff --git a/tests/test-carray_list.c b/tests/test-carray_list.c
index 53ab6f5..4077571 100644
--- a/tests/test-carray_list.c
+++ b/tests/test-carray_list.c
@@ -46,6 +46,36 @@ check_equals (gl_list_t list1, gl_list_t list2)
 }
 
 static void
+check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_first_node (list1);
+  gl_list_node_t node2 = gl_list_first_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_next_node (list1, node1);
+      node2 = gl_list_next_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
+check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_last_node (list1);
+  gl_list_node_t node2 = gl_list_last_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_previous_node (list1, node1);
+      node2 = gl_list_previous_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
 check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
 {
   check_equals (list1, list2);
@@ -88,6 +118,9 @@ main (int argc, char *argv[])
 
     check_all (list1, list2, list3);
 
+    check_equals_by_forward_iteration (list1, list2);
+    check_equals_by_backward_iteration (list1, list2);
+
     for (repeat = 0; repeat < 10000; repeat++)
       {
         unsigned int operation = RANDOM (18);
diff --git a/tests/test-linked_list.c b/tests/test-linked_list.c
index 4f3ec5d..fff7e06 100644
--- a/tests/test-linked_list.c
+++ b/tests/test-linked_list.c
@@ -46,6 +46,36 @@ check_equals (gl_list_t list1, gl_list_t list2)
 }
 
 static void
+check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_first_node (list1);
+  gl_list_node_t node2 = gl_list_first_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_next_node (list1, node1);
+      node2 = gl_list_next_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
+check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_last_node (list1);
+  gl_list_node_t node2 = gl_list_last_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_previous_node (list1, node1);
+      node2 = gl_list_previous_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
 check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
 {
   check_equals (list1, list2);
@@ -88,6 +118,9 @@ main (int argc, char *argv[])
 
     check_all (list1, list2, list3);
 
+    check_equals_by_forward_iteration (list1, list2);
+    check_equals_by_backward_iteration (list1, list2);
+
     for (repeat = 0; repeat < 10000; repeat++)
       {
         unsigned int operation = RANDOM (18);
diff --git a/tests/test-linkedhash_list.c b/tests/test-linkedhash_list.c
index b61feda..fc2a8a05 100644
--- a/tests/test-linkedhash_list.c
+++ b/tests/test-linkedhash_list.c
@@ -73,6 +73,36 @@ check_equals (gl_list_t list1, gl_list_t list2)
 }
 
 static void
+check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_first_node (list1);
+  gl_list_node_t node2 = gl_list_first_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_next_node (list1, node1);
+      node2 = gl_list_next_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
+check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_last_node (list1);
+  gl_list_node_t node2 = gl_list_last_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_previous_node (list1, node1);
+      node2 = gl_list_previous_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
 check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
 {
   check_equals (list1, list2);
@@ -118,6 +148,9 @@ main (int argc, char *argv[])
 
     check_all (list1, list2, list3);
 
+    check_equals_by_forward_iteration (list1, list2);
+    check_equals_by_backward_iteration (list1, list2);
+
     for (repeat = 0; repeat < 10000; repeat++)
       {
         unsigned int operation = RANDOM (18);
diff --git a/tests/test-rbtree_list.c b/tests/test-rbtree_list.c
index 9c403f7..d3ea656 100644
--- a/tests/test-rbtree_list.c
+++ b/tests/test-rbtree_list.c
@@ -48,6 +48,36 @@ check_equals (gl_list_t list1, gl_list_t list2)
 }
 
 static void
+check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_first_node (list1);
+  gl_list_node_t node2 = gl_list_first_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_next_node (list1, node1);
+      node2 = gl_list_next_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
+check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_last_node (list1);
+  gl_list_node_t node2 = gl_list_last_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_previous_node (list1, node1);
+      node2 = gl_list_previous_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
 check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
 {
   gl_rbtree_list_check_invariants (list2);
@@ -92,6 +122,9 @@ main (int argc, char *argv[])
 
     check_all (list1, list2, list3);
 
+    check_equals_by_forward_iteration (list1, list2);
+    check_equals_by_backward_iteration (list1, list2);
+
     for (repeat = 0; repeat < 10000; repeat++)
       {
         unsigned int operation = RANDOM (18);
diff --git a/tests/test-rbtreehash_list.c b/tests/test-rbtreehash_list.c
index 41ef5c4..89fc3eb 100644
--- a/tests/test-rbtreehash_list.c
+++ b/tests/test-rbtreehash_list.c
@@ -75,6 +75,36 @@ check_equals (gl_list_t list1, gl_list_t list2)
 }
 
 static void
+check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_first_node (list1);
+  gl_list_node_t node2 = gl_list_first_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_next_node (list1, node1);
+      node2 = gl_list_next_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
+check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
+{
+  gl_list_node_t node1 = gl_list_last_node (list1);
+  gl_list_node_t node2 = gl_list_last_node (list2);
+  while (node1 != NULL && node2 != NULL)
+    {
+      ASSERT (gl_list_node_value (list1, node1)
+              == gl_list_node_value (list2, node2));
+      node1 = gl_list_previous_node (list1, node1);
+      node2 = gl_list_previous_node (list2, node2);
+    }
+  ASSERT ((node1 == NULL) == (node2 == NULL));
+}
+
+static void
 check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
 {
   gl_rbtreehash_list_check_invariants (list2);
@@ -122,6 +152,9 @@ main (int argc, char *argv[])
 
     check_all (list1, list2, list3);
 
+    check_equals_by_forward_iteration (list1, list2);
+    check_equals_by_backward_iteration (list1, list2);
+
     for (repeat = 0; repeat < 10000; repeat++)
       {
         unsigned int operation = RANDOM (18);
-- 
2.7.4

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

[Marc Nieper-Wißkirchen]

[-- Attachment #1: Type: text/plain, Size: 2041 bytes --]

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

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

[-- Attachment #2: Type: text/html, Size: 3392 bytes --]

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

[Bruno Haible]

Marc Nieper-Wißkirchen wrote:
> > 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.

This is one way to handle the situation. Another way is to have a backing-
store of all objects somewhere, in such a way that on the particular gl_list_t
the dispose function can be NULL. In other words, complicated algorithms
work only on a subset of all objects, and the memory management for the
objects is elsewhere in the program.

Bruno

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

[Bruno Haible]

[Adding back bug-gnulib in CC.]

Hi Marc,

> > 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.
> >
> 
> Is there a fundamental reason why a list walking algorithm that both
> inserts and removes items is not possible with an arbitrary Gnulib list
> container? Obviously, the current API doesn't allow it. If it is just the
> limitation of an API that forces one to work with a second, temporary list,
> 
> Would it be possible for all list types to provide a
> 
> gl_list_node_t gl_list_remove_node_then (gl_list_t list, gl_list_node_t
> node, gl_list_node_t then)
> 
> that removes NODE from LIST and returns the node of that element
> represented by THEN before the removal.  The precondition is, of course,
> that THEN != NODE.  Furthermore, if THEN is NULL, NULL is returned.
> 
> A typical pattern would be:
> 
> for (gl_list_node_t i = gl_list_first_node (list); i != NULL;)
>   {
>     Fruit fruit;
>     if (is_apple (fruit))
>       node = gl_list_next_node (list, gl_list_next_node (list,
> gl_list_add_before (list, node, make_pear ())));
>     else if (is_peach (fruit))
>       node = gl_list_next_node (gl_list_add_after (list, node,
> make_strawberry ()));
>     else if (is_banana (fruit))
>       node = gl_list_remove_node_then (list, node, gl_list_next_node
> (list));
>   }
> (This is just a silly example for an algorithm that may want to replace
> elements by sublists (including sublists of length 0).)

This example makes it clear what you mean.

And what if the programmer wants to preserve not one 'then' node, but
several at once? One could generalize the function to

  void gl_list_remove_preserving_nodes (gl_list_t list, gl_list_node_t victim,
                                        size_t count, gl_list_node_t *to_preserve);

which would preserve the nodes to_preserve[0 .. count-1].

But for my feeling, programmers will not want to code like this. It is
so much easier to allocate a new list and destroy the old one afterwards.

Bruno

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

[Marc Nieper-Wißkirchen]

[-- Attachment #1: Type: text/plain, Size: 2609 bytes --]

Hi Bruno,

Am Mo., 5. Apr. 2021 um 04:45 Uhr schrieb Bruno Haible <bruno@clisp.org>:

> [Adding back bug-gnulib in CC.]
>

Thanks!


> > Is there a fundamental reason why a list walking algorithm that both
> > inserts and removes items is not possible with an arbitrary Gnulib list
> > container? Obviously, the current API doesn't allow it. If it is just the
> > limitation of an API that forces one to work with a second, temporary
> list,
> >
> > Would it be possible for all list types to provide a
> >
> > gl_list_node_t gl_list_remove_node_then (gl_list_t list, gl_list_node_t
> > node, gl_list_node_t then)
> >
> > that removes NODE from LIST and returns the node of that element
> > represented by THEN before the removal.  The precondition is, of course,
> > that THEN != NODE.  Furthermore, if THEN is NULL, NULL is returned.
> >
> > A typical pattern would be:
> >
> > for (gl_list_node_t i = gl_list_first_node (list); i != NULL;)
> >   {
> >     Fruit fruit;
> >     if (is_apple (fruit))
> >       node = gl_list_next_node (list, gl_list_next_node (list,
> > gl_list_add_before (list, node, make_pear ())));
> >     else if (is_peach (fruit))
> >       node = gl_list_next_node (gl_list_add_after (list, node,
> > make_strawberry ()));
> >     else if (is_banana (fruit))
> >       node = gl_list_remove_node_then (list, node, gl_list_next_node
> > (list));
> >   }
> > (This is just a silly example for an algorithm that may want to replace
> > elements by sublists (including sublists of length 0).)
>
> This example makes it clear what you mean.
>
> And what if the programmer wants to preserve not one 'then' node, but
> several at once? One could generalize the function to
>
>   void gl_list_remove_preserving_nodes (gl_list_t list, gl_list_node_t
> victim,
>                                         size_t count, gl_list_node_t
> *to_preserve);
>
> which would preserve the nodes to_preserve[0 .. count-1].
>

I think there is a conceptual difference between preserving a single node
and preserving an arbitrary number of nodes. The point is that
gl_list_add_before and gl_list_add_after, which also mutate the list,
return a single node from where the algorithm can continue (as the loop
above shows). So it is one thing to ask for gl_list_remove_node to return a
single valid node from where an iteration can proceed but quite a different
thing to ask it to preserve an arbitrary number of nodes.

Instead of the THEN node being arbitrary, it could also make sense to force
it to be the node before or after, i.e. to have gl_list_remove_node_next
and gl_list_remove_node_previous.
Marc

[-- Attachment #2: Type: text/html, Size: 3902 bytes --]