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 <br...@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.
From cce713624d68c60d9d6eeb11747500db998821a2 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@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 <br...@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 <br...@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
From 781f81012720e7f9f4c50630f37dfc73e2ad4906 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@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 <br...@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
