From cce713624d68c60d9d6eeb11747500db998821a2 Mon Sep 17 00:00:00 2001 From: Bruno Haible 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 . * 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 + list: Add operations first_node, last_node. + Reported by Marc Nieper-Wißkirchen in + . + * 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 + 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