From 1d131c99c96bd6c8424f0ee562a9db9f0e90e437 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sat, 2 May 2020 23:21:00 +0200 Subject: [PATCH] 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 ac235441d4..0bf6ca0dd8 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +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. diff --git a/lib/gl_list.h b/lib/gl_list.h index 8094006dd3..7786092232 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__)) @@ -645,6 +693,24 @@ gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt) ->nx_set_at (list, position, 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) { diff --git a/lib/gl_xlist.h b/lib/gl_xlist.h index ef6b93f6a5..7bf9c23953 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, @@ -113,6 +115,24 @@ gl_list_set_at (gl_list_t list, size_t position, const void *elt) return result; } +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) { -- 2.39.5