From aaf24f107ae05afec56d797421aee7a287b051e9 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sat, 2 May 2020 23:21:00 +0200 Subject: [PATCH 2/2] list: Add get_first, get_last, set_first, set_last operations. * lib/gl_list.h (gl_list_get_first, gl_list_get_last, gl_list_nx_set_first, gl_list_nx_set_last): New functions. * lib/gl_xlist.h (gl_list_set_first, gl_list_set_last): New functions. --- ChangeLog | 7 +++++++ lib/gl_list.h | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/gl_xlist.h | 20 ++++++++++++++++++ 3 files changed, 93 insertions(+) diff --git a/ChangeLog b/ChangeLog index ac23544..0bf6ca0 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,12 @@ 2020-05-02 Bruno Haible + list: Add get_first, get_last, set_first, set_last operations. + * lib/gl_list.h (gl_list_get_first, gl_list_get_last, + gl_list_nx_set_first, gl_list_nx_set_last): New functions. + * lib/gl_xlist.h (gl_list_set_first, gl_list_set_last): New functions. + +2020-05-02 Bruno Haible + list: Remove redundant code for remove_first and remove_last operations. * lib/gl_list.h (struct gl_list_implementation): Remove fields remove_first, remove_last. diff --git a/lib/gl_list.h b/lib/gl_list.h index 8094006..7786092 100644 --- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -74,7 +74,11 @@ extern "C" { 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_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) gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_list_set_first O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_set_last O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1) gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) @@ -210,6 +214,14 @@ extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node POSITION must be >= 0 and < gl_list_size (list). */ extern const void * gl_list_get_at (gl_list_t list, size_t position); +/* Returns the element at the first position in the list. + LIST must be non-empty. */ +extern const void * gl_list_get_first (gl_list_t list); + +/* Returns the element at the last position in the list. + LIST must be non-empty. */ +extern const void * gl_list_get_last (gl_list_t list); + /* Replaces the element at a given position in the list. POSITION must be >= 0 and < gl_list_size (list). Returns its node. */ @@ -224,6 +236,30 @@ extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position, #endif ; +/* Replaces the element at the first position in the list. + LIST must be non-empty. + Returns its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_set_first (gl_list_t list, const void *elt); +/* Likewise. Returns NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_set_first (gl_list_t list, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Replaces the element at the last position in the list. + LIST must be non-empty. + Returns its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_set_last (gl_list_t list, const void *elt); +/* Likewise. Returns NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_set_last (gl_list_t list, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + /* Searches whether an element is already in the list. Returns its node if found, or NULL if not present in the list. */ extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt); @@ -635,6 +671,18 @@ gl_list_get_at (gl_list_t list, size_t position) ->get_at (list, position); } +GL_LIST_INLINE const void * +gl_list_get_first (gl_list_t list) +{ + return gl_list_get_at (list, 0); +} + +GL_LIST_INLINE const void * +gl_list_get_last (gl_list_t list) +{ + return gl_list_get_at (list, gl_list_size (list) - 1); +} + GL_LIST_INLINE gl_list_node_t #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) __attribute__ ((__warn_unused_result__)) @@ -646,6 +694,24 @@ gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt) } GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_set_first (gl_list_t list, const void *elt) +{ + return gl_list_nx_set_at (list, 0, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_set_last (gl_list_t list, const void *elt) +{ + return gl_list_nx_set_at (list, gl_list_size (list) - 1, elt); +} + +GL_LIST_INLINE gl_list_node_t gl_list_search (gl_list_t list, const void *elt) { size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); diff --git a/lib/gl_xlist.h b/lib/gl_xlist.h index ef6b93f..7bf9c23 100644 --- a/lib/gl_xlist.h +++ b/lib/gl_xlist.h @@ -52,6 +52,8 @@ extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt); extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position, const void *elt); +extern gl_list_node_t gl_list_set_first (gl_list_t list, const void *elt); +extern gl_list_node_t gl_list_set_last (gl_list_t list, const void *elt); extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt); extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt); extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node, @@ -114,6 +116,24 @@ gl_list_set_at (gl_list_t list, size_t position, const void *elt) } GL_XLIST_INLINE gl_list_node_t +gl_list_set_first (gl_list_t list, const void *elt) +{ + gl_list_node_t result = gl_list_nx_set_first (list, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE gl_list_node_t +gl_list_set_last (gl_list_t list, const void *elt) +{ + gl_list_node_t result = gl_list_nx_set_last (list, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt) { gl_list_node_t result = gl_list_nx_add_first (list, elt); -- 2.7.4