* Add gl_list_remove_last to list/xlist @ 2020-04-28 7:08 Marc Nieper-Wißkirchen 2020-05-02 0:07 ` Bruno Haible 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-04-28 7:08 UTC (permalink / raw) To: bug-gnulib This is a feature request to add an operation extern gl_list_node_t gl_list_remove_last (gl_list_t list) to the list/xlist interface. This operation would remove the last element of the list and return the node of the previous element (or NULL if no element remained). There are at least two reasons why adding such an operation is meaningful: (1) It is a common operation if the list is used as a stack. Pushing will be gl_list_add_last, popping will be gl_list_remove_last. (2) The complexity of removing an arbitrary element in an ARRAY list is O(n). Removing the last element, however, is only O(1). With an explicit operation gl_list_remove_last, this can be documented in the table at the beginning of lib_gl_list.h. Thanks, Marc ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-04-28 7:08 Add gl_list_remove_last to list/xlist Marc Nieper-Wißkirchen @ 2020-05-02 0:07 ` Bruno Haible 2020-05-02 7:16 ` Marc Nieper-Wißkirchen 0 siblings, 1 reply; 42+ messages in thread From: Bruno Haible @ 2020-05-02 0:07 UTC (permalink / raw) To: bug-gnulib; +Cc: Marc Nieper-Wißkirchen Marc Nieper-Wißkirchen wrote: > This is a feature request to add an operation > > extern gl_list_node_t gl_list_remove_last (gl_list_t list) > > to the list/xlist interface. > > This operation would remove the last element of the list and return > the node of the previous element (or NULL if no element remained). > > There are at least two reasons why adding such an operation is meaningful: > > (1) It is a common operation if the list is used as a stack. Pushing > will be gl_list_add_last, popping will be gl_list_remove_last. > > (2) The complexity of removing an arbitrary element in an ARRAY list > is O(n). Removing the last element, however, is only O(1). With an > explicit operation gl_list_remove_last, this can be documented in the > table at the beginning of lib_gl_list.h. I agree about point (2). It applies also the CARRAY and LINKED list types. Similarly for gl_list_remove_first, which also have smaller complexity than gl_list_remove_at for CARRAY and LINKED list types. However, the return type cannot be gl_list_node_t, because for the LINKED list type, that would be returning a pointer to already freed memory. The return type cannot be 'const void *' either, because then it would not be possible to distinguish a returned NULL element and a call on an empty list - which would also return NULL. So, the best possible return type here is 'bool'. Implemented as follows. Thanks for the suggestion. 2020-05-01 Bruno Haible <bruno@clisp.org> list: Add remove_first and remove_last operations. Suggested by Marc Nieper-Wißkirchen <marc.nieper+gnu@gmail.com> in <https://lists.gnu.org/archive/html/bug-gnulib/2020-04/msg00092.html>. * lib/gl_list.h (struct gl_list_implementation): Add fields remove_first, remove_last. (gl_list_remove_first, gl_list_remove_last): New functions. * lib/gl_array_list.c (gl_array_remove_first, gl_array_remove_last): New functions, based on gl_array_remove_at. (gl_array_list_implementation): Implement the new operations. * lib/gl_carray_list.c (gl_carray_remove_first, gl_carray_remove_last): New functions, based on gl_carray_remove_at. (gl_carray_list_implementation): Implement the new operations. * lib/gl_anylinked_list2.h (gl_linked_remove_first, gl_linked_remove_last): New functions, based on gl_linked_remove_at. * lib/gl_linked_list.c (gl_linked_list_implementation): Implement the new operations. * lib/gl_linkedhash_list.c (gl_linkedhash_list_implementation): Likewise. * lib/gl_anytree_list2.h (gl_tree_remove_first, gl_tree_remove_last): New functions, based on gl_tree_remove_at. * lib/gl_avltree_list.c (gl_avltree_list_implementation): Implement 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_remove_first, gl_sublist_remove_last): New functions, based on gl_sublist_remove_at. (gl_sublist_list_implementation): Implement the new operations. * lib/gl_list.hh (class gl_List): Add methods remove_first, remove_last. * tests/test-array_list.c (main): Test also gl_list_remove_first and gl_list_remove_last. * tests/test-avltree_list.c (main): Likewise. * tests/test-avltreehash_list.c (main): Likewise. * tests/test-carray_list.c (main): Likewise. * tests/test-linked_list.c (main): Likewise. * tests/test-linkedhash_list.c (main): Likewise. * tests/test-rbtree_list.c (main): Likewise. * tests/test-rbtreehash_list.c (main): Likewise. diff --git a/lib/gl_list.h b/lib/gl_list.h index 39d1440..ea5018d 100644 --- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -88,6 +88,8 @@ extern "C" { gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_list_remove_first O(n)/O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_remove_last O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) gl_list_iterator O(1) O(1) O(log n) O(1) O(log n) gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n) @@ -328,6 +330,14 @@ extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node); Returns true. */ extern bool gl_list_remove_at (gl_list_t list, size_t position); +/* Removes the element at the first position from the list. + Returns true if it was found and removed, or false if the list was empty. */ +extern bool gl_list_remove_first (gl_list_t list); + +/* Removes the element at the last position from the list. + Returns true if it was found and removed, or false if the list was empty. */ +extern bool gl_list_remove_last (gl_list_t list); + /* Searches and removes an element from the list. Returns true if it was found and removed. */ extern bool gl_list_remove (gl_list_t list, const void *elt); @@ -508,6 +518,8 @@ struct gl_list_implementation const void *elt); bool (*remove_node) (gl_list_t list, gl_list_node_t node); bool (*remove_at) (gl_list_t list, size_t position); + bool (*remove_first) (gl_list_t list); + bool (*remove_last) (gl_list_t list); bool (*remove_elt) (gl_list_t list, const void *elt); void (*list_free) (gl_list_t list); /* gl_list_iterator_t functions. */ @@ -748,6 +760,20 @@ gl_list_remove_at (gl_list_t list, size_t position) } GL_LIST_INLINE bool +gl_list_remove_first (gl_list_t list) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->remove_first (list); +} + +GL_LIST_INLINE bool +gl_list_remove_last (gl_list_t list) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->remove_last (list); +} + +GL_LIST_INLINE bool gl_list_remove (gl_list_t list, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable diff --git a/lib/gl_list.hh b/lib/gl_list.hh index f67c214..2cc83be 100644 --- a/lib/gl_list.hh +++ b/lib/gl_list.hh @@ -219,6 +219,18 @@ public: bool remove_at (size_t position) { return gl_list_remove_at (_ptr, position); } + /* Removes the element at the first position from the list. + Returns true if it was found and removed, + or false if the list was empty. */ + bool remove_first () + { return gl_list_remove_first (_ptr); } + + /* Removes the element at the last position from the list. + Returns true if it was found and removed, + or false if the list was empty. */ + bool remove_last () + { return gl_list_remove_last (_ptr); } + /* Searches and removes an element from the list. Returns true if it was found and removed. */ bool remove (ELTYPE * elt) diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h index 114106c..0032dc8 100644 --- a/lib/gl_anylinked_list2.h +++ b/lib/gl_anylinked_list2.h @@ -882,6 +882,68 @@ gl_linked_remove_at (gl_list_t list, size_t position) } static bool +gl_linked_remove_first (gl_list_t list) +{ + size_t count = list->count; + gl_list_node_t removed_node; + + if (count == 0) + return false; + /* Here we know count > 0. */ + /* Like gl_linked_remove_at (list, 0). */ + { + gl_list_node_t node; + gl_list_node_t after_removed; + + node = &list->root; + removed_node = node->next; + after_removed = node->next->next; + ASYNCSAFE(gl_list_node_t) node->next = after_removed; + after_removed->prev = node; + } +#if WITH_HASHTABLE + remove_from_bucket (list, removed_node); +#endif + list->count--; + + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (removed_node->value); + free (removed_node); + return true; +} + +static bool +gl_linked_remove_last (gl_list_t list) +{ + size_t count = list->count; + gl_list_node_t removed_node; + + if (count == 0) + return false; + /* Here we know count > 0. */ + /* Like gl_linked_remove_at (list, count - 1). */ + { + gl_list_node_t node; + gl_list_node_t before_removed; + + node = &list->root; + removed_node = node->prev; + before_removed = node->prev->prev; + node->prev = before_removed; + ASYNCSAFE(gl_list_node_t) before_removed->next = node; + } +#if WITH_HASHTABLE + remove_from_bucket (list, removed_node); +#endif + list->count--; + + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (removed_node->value); + free (removed_node); + return true; +} + +static bool gl_linked_remove (gl_list_t list, const void *elt) { gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt); diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h index c5a67db..41e41dd 100644 --- a/lib/gl_anytree_list2.h +++ b/lib/gl_anytree_list2.h @@ -486,6 +486,34 @@ gl_tree_remove_at (gl_list_t list, size_t position) } static bool +gl_tree_remove_first (gl_list_t list) +{ + gl_list_node_t node = list->root; + + if (node != NULL) + { + node = node_at (node, 0); + return gl_tree_remove_node (list, node); + } + else + return false; +} + +static bool +gl_tree_remove_last (gl_list_t list) +{ + gl_list_node_t node = list->root; + + if (node != NULL) + { + node = node_at (node, node->branch_size - 1); + return gl_tree_remove_node (list, node); + } + else + return false; +} + +static bool gl_tree_remove (gl_list_t list, const void *elt) { if (list->root != NULL) diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c index 4950962..e00255c 100644 --- a/lib/gl_array_list.c +++ b/lib/gl_array_list.c @@ -406,6 +406,41 @@ gl_array_remove_at (gl_list_t list, size_t position) } static bool +gl_array_remove_first (gl_list_t list) +{ + size_t count = list->count; + const void **elements; + size_t i; + + if (count == 0) + return false; + /* Like gl_array_remove_at (list, 0). */ + elements = list->elements; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[0]); + for (i = 1; i < count; i++) + elements[i - 1] = elements[i]; + list->count = count - 1; + return true; +} + +static bool +gl_array_remove_last (gl_list_t list) +{ + size_t count = list->count; + const void **elements; + + if (count == 0) + return false; + /* Like gl_array_remove_at (list, count - 1). */ + elements = list->elements; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[count - 1]); + list->count = count - 1; + return true; +} + +static bool gl_array_remove (gl_list_t list, const void *elt) { size_t position = gl_array_indexof_from_to (list, 0, list->count, elt); @@ -662,6 +697,8 @@ const struct gl_list_implementation gl_array_list_implementation = gl_array_nx_add_at, gl_array_remove_node, gl_array_remove_at, + gl_array_remove_first, + gl_array_remove_last, gl_array_remove, gl_array_list_free, gl_array_iterator, diff --git a/lib/gl_avltree_list.c b/lib/gl_avltree_list.c index 35ffec6..2906f5a 100644 --- a/lib/gl_avltree_list.c +++ b/lib/gl_avltree_list.c @@ -89,6 +89,8 @@ const struct gl_list_implementation gl_avltree_list_implementation = gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, + gl_tree_remove_first, + gl_tree_remove_last, gl_tree_remove, gl_tree_list_free, gl_tree_iterator, diff --git a/lib/gl_avltreehash_list.c b/lib/gl_avltreehash_list.c index 9f795ff..576f533 100644 --- a/lib/gl_avltreehash_list.c +++ b/lib/gl_avltreehash_list.c @@ -111,6 +111,8 @@ const struct gl_list_implementation gl_avltreehash_list_implementation = gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, + gl_tree_remove_first, + gl_tree_remove_last, gl_tree_remove, gl_tree_list_free, gl_tree_iterator, diff --git a/lib/gl_carray_list.c b/lib/gl_carray_list.c index 36a8773..fa17d48 100644 --- a/lib/gl_carray_list.c +++ b/lib/gl_carray_list.c @@ -545,6 +545,44 @@ gl_carray_remove_at (gl_list_t list, size_t position) } static bool +gl_carray_remove_first (gl_list_t list) +{ + size_t count = list->count; + size_t i0; + + if (count == 0) + return false; + /* Here we know count > 0. */ + /* Like gl_carray_remove_at (list, 0). */ + i0 = list->offset; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (list->elements[i0]); + i0++; + list->offset = (i0 == list->allocated ? 0 : i0); + list->count = count - 1; + return true; +} + +static bool +gl_carray_remove_last (gl_list_t list) +{ + size_t count = list->count; + size_t i1; + + if (count == 0) + return false; + /* Here we know count > 0. */ + /* Like gl_carray_remove_at (list, count - 1). */ + i1 = list->offset + count - 1; + if (i1 >= list->allocated) + i1 -= list->allocated; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (list->elements[i1]); + list->count = count - 1; + return true; +} + +static bool gl_carray_remove_node (gl_list_t list, gl_list_node_t node) { size_t count = list->count; @@ -855,6 +893,8 @@ const struct gl_list_implementation gl_carray_list_implementation = gl_carray_nx_add_at, gl_carray_remove_node, gl_carray_remove_at, + gl_carray_remove_first, + gl_carray_remove_last, gl_carray_remove, gl_carray_list_free, gl_carray_iterator, diff --git a/lib/gl_linked_list.c b/lib/gl_linked_list.c index b1391ce..e2bf526 100644 --- a/lib/gl_linked_list.c +++ b/lib/gl_linked_list.c @@ -49,6 +49,8 @@ const struct gl_list_implementation gl_linked_list_implementation = gl_linked_nx_add_at, gl_linked_remove_node, gl_linked_remove_at, + gl_linked_remove_first, + gl_linked_remove_last, gl_linked_remove, gl_linked_list_free, gl_linked_iterator, diff --git a/lib/gl_linkedhash_list.c b/lib/gl_linkedhash_list.c index 7c7f999..5ffc0ce 100644 --- a/lib/gl_linkedhash_list.c +++ b/lib/gl_linkedhash_list.c @@ -97,6 +97,8 @@ const struct gl_list_implementation gl_linkedhash_list_implementation = gl_linked_nx_add_at, gl_linked_remove_node, gl_linked_remove_at, + gl_linked_remove_first, + gl_linked_remove_last, gl_linked_remove, gl_linked_list_free, gl_linked_iterator, diff --git a/lib/gl_rbtree_list.c b/lib/gl_rbtree_list.c index d79becf..6ae78c7 100644 --- a/lib/gl_rbtree_list.c +++ b/lib/gl_rbtree_list.c @@ -87,6 +87,8 @@ const struct gl_list_implementation gl_rbtree_list_implementation = gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, + gl_tree_remove_first, + gl_tree_remove_last, gl_tree_remove, gl_tree_list_free, gl_tree_iterator, diff --git a/lib/gl_rbtreehash_list.c b/lib/gl_rbtreehash_list.c index be2ee6f..b59b5f4 100644 --- a/lib/gl_rbtreehash_list.c +++ b/lib/gl_rbtreehash_list.c @@ -112,6 +112,8 @@ const struct gl_list_implementation gl_rbtreehash_list_implementation = gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, + gl_tree_remove_first, + gl_tree_remove_last, gl_tree_remove, gl_tree_list_free, gl_tree_iterator, diff --git a/lib/gl_sublist.c b/lib/gl_sublist.c index e529a6b..6e95c3b 100644 --- a/lib/gl_sublist.c +++ b/lib/gl_sublist.c @@ -259,6 +259,22 @@ gl_sublist_remove_at (gl_list_t list, size_t position) } static bool +gl_sublist_remove_first (gl_list_t list) +{ + if (list->end == list->start) + return false; + return gl_list_remove_at (list->whole, list->start); +} + +static bool +gl_sublist_remove_last (gl_list_t list) +{ + if (list->end == list->start) + return false; + return gl_list_remove_at (list->whole, list->end - 1); +} + +static bool gl_sublist_remove (gl_list_t list, const void *elt) { size_t position = @@ -424,6 +440,8 @@ static const struct gl_list_implementation gl_sublist_list_implementation = gl_sublist_nx_add_at, gl_sublist_remove_node, gl_sublist_remove_at, + gl_sublist_remove_first, + gl_sublist_remove_last, gl_sublist_remove, gl_sublist_list_free, gl_sublist_iterator, diff --git a/tests/test-array_list.c b/tests/test-array_list.c index 158e728..f617787 100644 --- a/tests/test-array_list.c +++ b/tests/test-array_list.c @@ -77,7 +77,7 @@ main (int argc, char *argv[]) for (repeat = 0; repeat < 10000; repeat++) { - unsigned int operation = RANDOM (16); + unsigned int operation = RANDOM (18); switch (operation) { case 0: @@ -252,7 +252,23 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 11: case 12: /* remove 1 element */ + case 11: /* remove first element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_first (list1); + ASSERT (gl_list_remove_first (list2) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 12: /* remove last element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_last (list1); + ASSERT (gl_list_remove_last (list2) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 13: case 14: /* remove 1 element */ if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -262,7 +278,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 13: + case 15: if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -272,7 +288,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n); } break; - case 14: + case 16: { size_t n = gl_list_size (list1); gl_list_iterator_t iter1, iter2; @@ -292,7 +308,7 @@ main (int argc, char *argv[]) gl_list_iterator_free (&iter2); } break; - case 15: + case 17: { size_t end = RANDOM (gl_list_size (list1) + 1); size_t start = RANDOM (end + 1); diff --git a/tests/test-avltree_list.c b/tests/test-avltree_list.c index 03ff024..b69816d 100644 --- a/tests/test-avltree_list.c +++ b/tests/test-avltree_list.c @@ -94,7 +94,7 @@ main (int argc, char *argv[]) for (repeat = 0; repeat < 10000; repeat++) { - unsigned int operation = RANDOM (16); + unsigned int operation = RANDOM (18); switch (operation) { case 0: @@ -325,7 +325,25 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 11: case 12: /* remove 1 element */ + case 11: /* remove first element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_first (list1); + ASSERT (gl_list_remove_first (list2) == removed1); + ASSERT (gl_list_remove_first (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 12: /* remove last element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_last (list1); + ASSERT (gl_list_remove_last (list2) == removed1); + ASSERT (gl_list_remove_last (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 13: case 14: /* remove 1 element */ if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -336,7 +354,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 13: + case 15: if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -347,7 +365,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n); } break; - case 14: + case 16: { size_t n = gl_list_size (list1); gl_list_iterator_t iter1, iter2, iter3; @@ -372,7 +390,7 @@ main (int argc, char *argv[]) gl_list_iterator_free (&iter3); } break; - case 15: + case 17: { size_t end = RANDOM (gl_list_size (list1) + 1); size_t start = RANDOM (end + 1); diff --git a/tests/test-avltreehash_list.c b/tests/test-avltreehash_list.c index 806b0e3..6dcded4 100644 --- a/tests/test-avltreehash_list.c +++ b/tests/test-avltreehash_list.c @@ -124,7 +124,7 @@ main (int argc, char *argv[]) for (repeat = 0; repeat < 10000; repeat++) { - unsigned int operation = RANDOM (16); + unsigned int operation = RANDOM (18); switch (operation) { case 0: @@ -355,7 +355,25 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 11: case 12: /* remove 1 element */ + case 11: /* remove first element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_first (list1); + ASSERT (gl_list_remove_first (list2) == removed1); + ASSERT (gl_list_remove_first (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 12: /* remove last element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_last (list1); + ASSERT (gl_list_remove_last (list2) == removed1); + ASSERT (gl_list_remove_last (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 13: case 14: /* remove 1 element */ if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -366,7 +384,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 13: + case 15: if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -377,7 +395,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n); } break; - case 14: + case 16: { size_t n = gl_list_size (list1); gl_list_iterator_t iter1, iter2, iter3; @@ -402,7 +420,7 @@ main (int argc, char *argv[]) gl_list_iterator_free (&iter3); } break; - case 15: + case 17: { size_t end = RANDOM (gl_list_size (list1) + 1); size_t start = RANDOM (end + 1); diff --git a/tests/test-carray_list.c b/tests/test-carray_list.c index c975266..a6e9511 100644 --- a/tests/test-carray_list.c +++ b/tests/test-carray_list.c @@ -90,7 +90,7 @@ main (int argc, char *argv[]) for (repeat = 0; repeat < 10000; repeat++) { - unsigned int operation = RANDOM (16); + unsigned int operation = RANDOM (18); switch (operation) { case 0: @@ -321,7 +321,25 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 11: case 12: /* remove 1 element */ + case 11: /* remove first element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_first (list1); + ASSERT (gl_list_remove_first (list2) == removed1); + ASSERT (gl_list_remove_first (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 12: /* remove last element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_last (list1); + ASSERT (gl_list_remove_last (list2) == removed1); + ASSERT (gl_list_remove_last (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 13: case 14: /* remove 1 element */ if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -332,7 +350,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 13: + case 15: if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -343,7 +361,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n); } break; - case 14: + case 16: { size_t n = gl_list_size (list1); gl_list_iterator_t iter1, iter2, iter3; @@ -368,7 +386,7 @@ main (int argc, char *argv[]) gl_list_iterator_free (&iter3); } break; - case 15: + case 17: { size_t end = RANDOM (gl_list_size (list1) + 1); size_t start = RANDOM (end + 1); diff --git a/tests/test-linked_list.c b/tests/test-linked_list.c index c139677..7c9954b 100644 --- a/tests/test-linked_list.c +++ b/tests/test-linked_list.c @@ -90,7 +90,7 @@ main (int argc, char *argv[]) for (repeat = 0; repeat < 10000; repeat++) { - unsigned int operation = RANDOM (16); + unsigned int operation = RANDOM (18); switch (operation) { case 0: @@ -321,7 +321,25 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 11: case 12: /* remove 1 element */ + case 11: /* remove first element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_first (list1); + ASSERT (gl_list_remove_first (list2) == removed1); + ASSERT (gl_list_remove_first (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 12: /* remove last element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_last (list1); + ASSERT (gl_list_remove_last (list2) == removed1); + ASSERT (gl_list_remove_last (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 13: case 14: /* remove 1 element */ if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -332,7 +350,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 13: + case 15: if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -343,7 +361,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n); } break; - case 14: + case 16: { size_t n = gl_list_size (list1); gl_list_iterator_t iter1, iter2, iter3; @@ -368,7 +386,7 @@ main (int argc, char *argv[]) gl_list_iterator_free (&iter3); } break; - case 15: + case 17: { size_t end = RANDOM (gl_list_size (list1) + 1); size_t start = RANDOM (end + 1); diff --git a/tests/test-linkedhash_list.c b/tests/test-linkedhash_list.c index 921c62c..7fa8b4f 100644 --- a/tests/test-linkedhash_list.c +++ b/tests/test-linkedhash_list.c @@ -120,7 +120,7 @@ main (int argc, char *argv[]) for (repeat = 0; repeat < 10000; repeat++) { - unsigned int operation = RANDOM (16); + unsigned int operation = RANDOM (18); switch (operation) { case 0: @@ -351,7 +351,25 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 11: case 12: /* remove 1 element */ + case 11: /* remove first element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_first (list1); + ASSERT (gl_list_remove_first (list2) == removed1); + ASSERT (gl_list_remove_first (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 12: /* remove last element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_last (list1); + ASSERT (gl_list_remove_last (list2) == removed1); + ASSERT (gl_list_remove_last (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 13: case 14: /* remove 1 element */ if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -362,7 +380,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 13: + case 15: if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -373,7 +391,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n); } break; - case 14: + case 16: { size_t n = gl_list_size (list1); gl_list_iterator_t iter1, iter2, iter3; @@ -398,7 +416,7 @@ main (int argc, char *argv[]) gl_list_iterator_free (&iter3); } break; - case 15: + case 17: { size_t end = RANDOM (gl_list_size (list1) + 1); size_t start = RANDOM (end + 1); diff --git a/tests/test-rbtree_list.c b/tests/test-rbtree_list.c index 32d9d32..efd2cb1 100644 --- a/tests/test-rbtree_list.c +++ b/tests/test-rbtree_list.c @@ -94,7 +94,7 @@ main (int argc, char *argv[]) for (repeat = 0; repeat < 10000; repeat++) { - unsigned int operation = RANDOM (16); + unsigned int operation = RANDOM (18); switch (operation) { case 0: @@ -325,7 +325,25 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 11: case 12: /* remove 1 element */ + case 11: /* remove first element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_first (list1); + ASSERT (gl_list_remove_first (list2) == removed1); + ASSERT (gl_list_remove_first (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 12: /* remove last element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_last (list1); + ASSERT (gl_list_remove_last (list2) == removed1); + ASSERT (gl_list_remove_last (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 13: case 14: /* remove 1 element */ if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -336,7 +354,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 13: + case 15: if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -347,7 +365,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n); } break; - case 14: + case 16: { size_t n = gl_list_size (list1); gl_list_iterator_t iter1, iter2, iter3; @@ -372,7 +390,7 @@ main (int argc, char *argv[]) gl_list_iterator_free (&iter3); } break; - case 15: + case 17: { size_t end = RANDOM (gl_list_size (list1) + 1); size_t start = RANDOM (end + 1); diff --git a/tests/test-rbtreehash_list.c b/tests/test-rbtreehash_list.c index 949a6f4..d6bbcb3 100644 --- a/tests/test-rbtreehash_list.c +++ b/tests/test-rbtreehash_list.c @@ -124,7 +124,7 @@ main (int argc, char *argv[]) for (repeat = 0; repeat < 10000; repeat++) { - unsigned int operation = RANDOM (16); + unsigned int operation = RANDOM (18); switch (operation) { case 0: @@ -355,7 +355,25 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 11: case 12: /* remove 1 element */ + case 11: /* remove first element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_first (list1); + ASSERT (gl_list_remove_first (list2) == removed1); + ASSERT (gl_list_remove_first (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 12: /* remove last element */ + { + size_t n = gl_list_size (list1); + bool removed1 = gl_list_remove_last (list1); + ASSERT (gl_list_remove_last (list2) == removed1); + ASSERT (gl_list_remove_last (list3) == removed1); + ASSERT (gl_list_size (list1) == n - (int) removed1); + } + break; + case 13: case 14: /* remove 1 element */ if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -366,7 +384,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n - 1); } break; - case 13: + case 15: if (gl_list_size (list1) > 0) { size_t n = gl_list_size (list1); @@ -377,7 +395,7 @@ main (int argc, char *argv[]) ASSERT (gl_list_size (list1) == n); } break; - case 14: + case 16: { size_t n = gl_list_size (list1); gl_list_iterator_t iter1, iter2, iter3; @@ -402,7 +420,7 @@ main (int argc, char *argv[]) gl_list_iterator_free (&iter3); } break; - case 15: + case 17: { size_t end = RANDOM (gl_list_size (list1) + 1); size_t start = RANDOM (end + 1); ^ permalink raw reply related [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 0:07 ` Bruno Haible @ 2020-05-02 7:16 ` Marc Nieper-Wißkirchen 2020-05-02 12:07 ` Bruno Haible 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-02 7:16 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, thanks again very much! Am Sa., 2. Mai 2020 um 02:07 Uhr schrieb Bruno Haible <bruno@clisp.org>: > > Marc Nieper-Wißkirchen wrote: > > This is a feature request to add an operation > > > > extern gl_list_node_t gl_list_remove_last (gl_list_t list) > > > > to the list/xlist interface. > > > > This operation would remove the last element of the list and return > > the node of the previous element (or NULL if no element remained). > > > > There are at least two reasons why adding such an operation is meaningful: > > > > (1) It is a common operation if the list is used as a stack. Pushing > > will be gl_list_add_last, popping will be gl_list_remove_last. > > > > (2) The complexity of removing an arbitrary element in an ARRAY list > > is O(n). Removing the last element, however, is only O(1). With an > > explicit operation gl_list_remove_last, this can be documented in the > > table at the beginning of lib_gl_list.h. > > I agree about point (2). It applies also the CARRAY and LINKED list types. > > Similarly for gl_list_remove_first, which also have smaller complexity than > gl_list_remove_at for CARRAY and LINKED list types. > > However, the return type cannot be gl_list_node_t, because for the LINKED > list type, that would be returning a pointer to already freed memory. Could you explain why it is so? I didn't mean that gl_list_remove_last should return the just deleted node but the node of the element that is now the last one (the respectively first one for gl_list_remove_first) after the removal. If there is none (because the list is empty after the removal), NULL would be returned. It would be an error to apply gl_list_remove_last to an empty list. The motivation behind my suggestion is to make it easy to implement a stack (or a FIFO queue) with the gl_list interface. For this, operations like gl_list_get_first and gl_list_get_last with guaranteed O(1) behavior for a number of list implementations would also be nice. > > The return type cannot be 'const void *' either, because then it would not > be possible to distinguish a returned NULL element and a call on an > empty list - which would also return NULL. > > So, the best possible return type here is 'bool'. > > Implemented as follows. Thanks for the suggestion. > > > 2020-05-01 Bruno Haible <bruno@clisp.org> > > list: Add remove_first and remove_last operations. > Suggested by Marc Nieper-Wißkirchen <marc.nieper+gnu@gmail.com> in > <https://lists.gnu.org/archive/html/bug-gnulib/2020-04/msg00092.html>. > * lib/gl_list.h (struct gl_list_implementation): Add fields > remove_first, remove_last. > (gl_list_remove_first, gl_list_remove_last): New functions. > * lib/gl_array_list.c (gl_array_remove_first, gl_array_remove_last): New > functions, based on gl_array_remove_at. > (gl_array_list_implementation): Implement the new operations. > * lib/gl_carray_list.c (gl_carray_remove_first, gl_carray_remove_last): > New functions, based on gl_carray_remove_at. > (gl_carray_list_implementation): Implement the new operations. > * lib/gl_anylinked_list2.h (gl_linked_remove_first, > gl_linked_remove_last): New functions, based on gl_linked_remove_at. > * lib/gl_linked_list.c (gl_linked_list_implementation): Implement the > new operations. > * lib/gl_linkedhash_list.c (gl_linkedhash_list_implementation): > Likewise. > * lib/gl_anytree_list2.h (gl_tree_remove_first, gl_tree_remove_last): > New functions, based on gl_tree_remove_at. > * lib/gl_avltree_list.c (gl_avltree_list_implementation): Implement 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_remove_first, gl_sublist_remove_last): > New functions, based on gl_sublist_remove_at. > (gl_sublist_list_implementation): Implement the new operations. > * lib/gl_list.hh (class gl_List): Add methods remove_first, > remove_last. > * tests/test-array_list.c (main): Test also gl_list_remove_first and > gl_list_remove_last. > * tests/test-avltree_list.c (main): Likewise. > * tests/test-avltreehash_list.c (main): Likewise. > * tests/test-carray_list.c (main): Likewise. > * tests/test-linked_list.c (main): Likewise. > * tests/test-linkedhash_list.c (main): Likewise. > * tests/test-rbtree_list.c (main): Likewise. > * tests/test-rbtreehash_list.c (main): Likewise. > > diff --git a/lib/gl_list.h b/lib/gl_list.h > index 39d1440..ea5018d 100644 > --- a/lib/gl_list.h > +++ b/lib/gl_list.h > @@ -88,6 +88,8 @@ extern "C" { > gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) > gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) > gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) > + gl_list_remove_first O(n)/O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) > + gl_list_remove_last O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) > gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) > gl_list_iterator O(1) O(1) O(log n) O(1) O(log n) > gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n) > @@ -328,6 +330,14 @@ extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node); > Returns true. */ > extern bool gl_list_remove_at (gl_list_t list, size_t position); > > +/* Removes the element at the first position from the list. > + Returns true if it was found and removed, or false if the list was empty. */ > +extern bool gl_list_remove_first (gl_list_t list); > + > +/* Removes the element at the last position from the list. > + Returns true if it was found and removed, or false if the list was empty. */ > +extern bool gl_list_remove_last (gl_list_t list); > + > /* Searches and removes an element from the list. > Returns true if it was found and removed. */ > extern bool gl_list_remove (gl_list_t list, const void *elt); > @@ -508,6 +518,8 @@ struct gl_list_implementation > const void *elt); > bool (*remove_node) (gl_list_t list, gl_list_node_t node); > bool (*remove_at) (gl_list_t list, size_t position); > + bool (*remove_first) (gl_list_t list); > + bool (*remove_last) (gl_list_t list); > bool (*remove_elt) (gl_list_t list, const void *elt); > void (*list_free) (gl_list_t list); > /* gl_list_iterator_t functions. */ > @@ -748,6 +760,20 @@ gl_list_remove_at (gl_list_t list, size_t position) > } > > GL_LIST_INLINE bool > +gl_list_remove_first (gl_list_t list) > +{ > + return ((const struct gl_list_impl_base *) list)->vtable > + ->remove_first (list); > +} > + > +GL_LIST_INLINE bool > +gl_list_remove_last (gl_list_t list) > +{ > + return ((const struct gl_list_impl_base *) list)->vtable > + ->remove_last (list); > +} > + > +GL_LIST_INLINE bool > gl_list_remove (gl_list_t list, const void *elt) > { > return ((const struct gl_list_impl_base *) list)->vtable > diff --git a/lib/gl_list.hh b/lib/gl_list.hh > index f67c214..2cc83be 100644 > --- a/lib/gl_list.hh > +++ b/lib/gl_list.hh > @@ -219,6 +219,18 @@ public: > bool remove_at (size_t position) > { return gl_list_remove_at (_ptr, position); } > > + /* Removes the element at the first position from the list. > + Returns true if it was found and removed, > + or false if the list was empty. */ > + bool remove_first () > + { return gl_list_remove_first (_ptr); } > + > + /* Removes the element at the last position from the list. > + Returns true if it was found and removed, > + or false if the list was empty. */ > + bool remove_last () > + { return gl_list_remove_last (_ptr); } > + > /* Searches and removes an element from the list. > Returns true if it was found and removed. */ > bool remove (ELTYPE * elt) > diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h > index 114106c..0032dc8 100644 > --- a/lib/gl_anylinked_list2.h > +++ b/lib/gl_anylinked_list2.h > @@ -882,6 +882,68 @@ gl_linked_remove_at (gl_list_t list, size_t position) > } > > static bool > +gl_linked_remove_first (gl_list_t list) > +{ > + size_t count = list->count; > + gl_list_node_t removed_node; > + > + if (count == 0) > + return false; > + /* Here we know count > 0. */ > + /* Like gl_linked_remove_at (list, 0). */ > + { > + gl_list_node_t node; > + gl_list_node_t after_removed; > + > + node = &list->root; > + removed_node = node->next; > + after_removed = node->next->next; > + ASYNCSAFE(gl_list_node_t) node->next = after_removed; > + after_removed->prev = node; > + } > +#if WITH_HASHTABLE > + remove_from_bucket (list, removed_node); > +#endif > + list->count--; > + > + if (list->base.dispose_fn != NULL) > + list->base.dispose_fn (removed_node->value); > + free (removed_node); > + return true; > +} > + > +static bool > +gl_linked_remove_last (gl_list_t list) > +{ > + size_t count = list->count; > + gl_list_node_t removed_node; > + > + if (count == 0) > + return false; > + /* Here we know count > 0. */ > + /* Like gl_linked_remove_at (list, count - 1). */ > + { > + gl_list_node_t node; > + gl_list_node_t before_removed; > + > + node = &list->root; > + removed_node = node->prev; > + before_removed = node->prev->prev; > + node->prev = before_removed; > + ASYNCSAFE(gl_list_node_t) before_removed->next = node; > + } > +#if WITH_HASHTABLE > + remove_from_bucket (list, removed_node); > +#endif > + list->count--; > + > + if (list->base.dispose_fn != NULL) > + list->base.dispose_fn (removed_node->value); > + free (removed_node); > + return true; > +} > + > +static bool > gl_linked_remove (gl_list_t list, const void *elt) > { > gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt); > diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h > index c5a67db..41e41dd 100644 > --- a/lib/gl_anytree_list2.h > +++ b/lib/gl_anytree_list2.h > @@ -486,6 +486,34 @@ gl_tree_remove_at (gl_list_t list, size_t position) > } > > static bool > +gl_tree_remove_first (gl_list_t list) > +{ > + gl_list_node_t node = list->root; > + > + if (node != NULL) > + { > + node = node_at (node, 0); > + return gl_tree_remove_node (list, node); > + } > + else > + return false; > +} > + > +static bool > +gl_tree_remove_last (gl_list_t list) > +{ > + gl_list_node_t node = list->root; > + > + if (node != NULL) > + { > + node = node_at (node, node->branch_size - 1); > + return gl_tree_remove_node (list, node); > + } > + else > + return false; > +} > + > +static bool > gl_tree_remove (gl_list_t list, const void *elt) > { > if (list->root != NULL) > diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c > index 4950962..e00255c 100644 > --- a/lib/gl_array_list.c > +++ b/lib/gl_array_list.c > @@ -406,6 +406,41 @@ gl_array_remove_at (gl_list_t list, size_t position) > } > > static bool > +gl_array_remove_first (gl_list_t list) > +{ > + size_t count = list->count; > + const void **elements; > + size_t i; > + > + if (count == 0) > + return false; > + /* Like gl_array_remove_at (list, 0). */ > + elements = list->elements; > + if (list->base.dispose_fn != NULL) > + list->base.dispose_fn (elements[0]); > + for (i = 1; i < count; i++) > + elements[i - 1] = elements[i]; > + list->count = count - 1; > + return true; > +} > + > +static bool > +gl_array_remove_last (gl_list_t list) > +{ > + size_t count = list->count; > + const void **elements; > + > + if (count == 0) > + return false; > + /* Like gl_array_remove_at (list, count - 1). */ > + elements = list->elements; > + if (list->base.dispose_fn != NULL) > + list->base.dispose_fn (elements[count - 1]); > + list->count = count - 1; > + return true; > +} > + > +static bool > gl_array_remove (gl_list_t list, const void *elt) > { > size_t position = gl_array_indexof_from_to (list, 0, list->count, elt); > @@ -662,6 +697,8 @@ const struct gl_list_implementation gl_array_list_implementation = > gl_array_nx_add_at, > gl_array_remove_node, > gl_array_remove_at, > + gl_array_remove_first, > + gl_array_remove_last, > gl_array_remove, > gl_array_list_free, > gl_array_iterator, > diff --git a/lib/gl_avltree_list.c b/lib/gl_avltree_list.c > index 35ffec6..2906f5a 100644 > --- a/lib/gl_avltree_list.c > +++ b/lib/gl_avltree_list.c > @@ -89,6 +89,8 @@ const struct gl_list_implementation gl_avltree_list_implementation = > gl_tree_nx_add_at, > gl_tree_remove_node, > gl_tree_remove_at, > + gl_tree_remove_first, > + gl_tree_remove_last, > gl_tree_remove, > gl_tree_list_free, > gl_tree_iterator, > diff --git a/lib/gl_avltreehash_list.c b/lib/gl_avltreehash_list.c > index 9f795ff..576f533 100644 > --- a/lib/gl_avltreehash_list.c > +++ b/lib/gl_avltreehash_list.c > @@ -111,6 +111,8 @@ const struct gl_list_implementation gl_avltreehash_list_implementation = > gl_tree_nx_add_at, > gl_tree_remove_node, > gl_tree_remove_at, > + gl_tree_remove_first, > + gl_tree_remove_last, > gl_tree_remove, > gl_tree_list_free, > gl_tree_iterator, > diff --git a/lib/gl_carray_list.c b/lib/gl_carray_list.c > index 36a8773..fa17d48 100644 > --- a/lib/gl_carray_list.c > +++ b/lib/gl_carray_list.c > @@ -545,6 +545,44 @@ gl_carray_remove_at (gl_list_t list, size_t position) > } > > static bool > +gl_carray_remove_first (gl_list_t list) > +{ > + size_t count = list->count; > + size_t i0; > + > + if (count == 0) > + return false; > + /* Here we know count > 0. */ > + /* Like gl_carray_remove_at (list, 0). */ > + i0 = list->offset; > + if (list->base.dispose_fn != NULL) > + list->base.dispose_fn (list->elements[i0]); > + i0++; > + list->offset = (i0 == list->allocated ? 0 : i0); > + list->count = count - 1; > + return true; > +} > + > +static bool > +gl_carray_remove_last (gl_list_t list) > +{ > + size_t count = list->count; > + size_t i1; > + > + if (count == 0) > + return false; > + /* Here we know count > 0. */ > + /* Like gl_carray_remove_at (list, count - 1). */ > + i1 = list->offset + count - 1; > + if (i1 >= list->allocated) > + i1 -= list->allocated; > + if (list->base.dispose_fn != NULL) > + list->base.dispose_fn (list->elements[i1]); > + list->count = count - 1; > + return true; > +} > + > +static bool > gl_carray_remove_node (gl_list_t list, gl_list_node_t node) > { > size_t count = list->count; > @@ -855,6 +893,8 @@ const struct gl_list_implementation gl_carray_list_implementation = > gl_carray_nx_add_at, > gl_carray_remove_node, > gl_carray_remove_at, > + gl_carray_remove_first, > + gl_carray_remove_last, > gl_carray_remove, > gl_carray_list_free, > gl_carray_iterator, > diff --git a/lib/gl_linked_list.c b/lib/gl_linked_list.c > index b1391ce..e2bf526 100644 > --- a/lib/gl_linked_list.c > +++ b/lib/gl_linked_list.c > @@ -49,6 +49,8 @@ const struct gl_list_implementation gl_linked_list_implementation = > gl_linked_nx_add_at, > gl_linked_remove_node, > gl_linked_remove_at, > + gl_linked_remove_first, > + gl_linked_remove_last, > gl_linked_remove, > gl_linked_list_free, > gl_linked_iterator, > diff --git a/lib/gl_linkedhash_list.c b/lib/gl_linkedhash_list.c > index 7c7f999..5ffc0ce 100644 > --- a/lib/gl_linkedhash_list.c > +++ b/lib/gl_linkedhash_list.c > @@ -97,6 +97,8 @@ const struct gl_list_implementation gl_linkedhash_list_implementation = > gl_linked_nx_add_at, > gl_linked_remove_node, > gl_linked_remove_at, > + gl_linked_remove_first, > + gl_linked_remove_last, > gl_linked_remove, > gl_linked_list_free, > gl_linked_iterator, > diff --git a/lib/gl_rbtree_list.c b/lib/gl_rbtree_list.c > index d79becf..6ae78c7 100644 > --- a/lib/gl_rbtree_list.c > +++ b/lib/gl_rbtree_list.c > @@ -87,6 +87,8 @@ const struct gl_list_implementation gl_rbtree_list_implementation = > gl_tree_nx_add_at, > gl_tree_remove_node, > gl_tree_remove_at, > + gl_tree_remove_first, > + gl_tree_remove_last, > gl_tree_remove, > gl_tree_list_free, > gl_tree_iterator, > diff --git a/lib/gl_rbtreehash_list.c b/lib/gl_rbtreehash_list.c > index be2ee6f..b59b5f4 100644 > --- a/lib/gl_rbtreehash_list.c > +++ b/lib/gl_rbtreehash_list.c > @@ -112,6 +112,8 @@ const struct gl_list_implementation gl_rbtreehash_list_implementation = > gl_tree_nx_add_at, > gl_tree_remove_node, > gl_tree_remove_at, > + gl_tree_remove_first, > + gl_tree_remove_last, > gl_tree_remove, > gl_tree_list_free, > gl_tree_iterator, > diff --git a/lib/gl_sublist.c b/lib/gl_sublist.c > index e529a6b..6e95c3b 100644 > --- a/lib/gl_sublist.c > +++ b/lib/gl_sublist.c > @@ -259,6 +259,22 @@ gl_sublist_remove_at (gl_list_t list, size_t position) > } > > static bool > +gl_sublist_remove_first (gl_list_t list) > +{ > + if (list->end == list->start) > + return false; > + return gl_list_remove_at (list->whole, list->start); > +} > + > +static bool > +gl_sublist_remove_last (gl_list_t list) > +{ > + if (list->end == list->start) > + return false; > + return gl_list_remove_at (list->whole, list->end - 1); > +} > + > +static bool > gl_sublist_remove (gl_list_t list, const void *elt) > { > size_t position = > @@ -424,6 +440,8 @@ static const struct gl_list_implementation gl_sublist_list_implementation = > gl_sublist_nx_add_at, > gl_sublist_remove_node, > gl_sublist_remove_at, > + gl_sublist_remove_first, > + gl_sublist_remove_last, > gl_sublist_remove, > gl_sublist_list_free, > gl_sublist_iterator, > diff --git a/tests/test-array_list.c b/tests/test-array_list.c > index 158e728..f617787 100644 > --- a/tests/test-array_list.c > +++ b/tests/test-array_list.c > @@ -77,7 +77,7 @@ main (int argc, char *argv[]) > > for (repeat = 0; repeat < 10000; repeat++) > { > - unsigned int operation = RANDOM (16); > + unsigned int operation = RANDOM (18); > switch (operation) > { > case 0: > @@ -252,7 +252,23 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 11: case 12: /* remove 1 element */ > + case 11: /* remove first element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_first (list1); > + ASSERT (gl_list_remove_first (list2) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 12: /* remove last element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_last (list1); > + ASSERT (gl_list_remove_last (list2) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 13: case 14: /* remove 1 element */ > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -262,7 +278,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 13: > + case 15: > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -272,7 +288,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n); > } > break; > - case 14: > + case 16: > { > size_t n = gl_list_size (list1); > gl_list_iterator_t iter1, iter2; > @@ -292,7 +308,7 @@ main (int argc, char *argv[]) > gl_list_iterator_free (&iter2); > } > break; > - case 15: > + case 17: > { > size_t end = RANDOM (gl_list_size (list1) + 1); > size_t start = RANDOM (end + 1); > diff --git a/tests/test-avltree_list.c b/tests/test-avltree_list.c > index 03ff024..b69816d 100644 > --- a/tests/test-avltree_list.c > +++ b/tests/test-avltree_list.c > @@ -94,7 +94,7 @@ main (int argc, char *argv[]) > > for (repeat = 0; repeat < 10000; repeat++) > { > - unsigned int operation = RANDOM (16); > + unsigned int operation = RANDOM (18); > switch (operation) > { > case 0: > @@ -325,7 +325,25 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 11: case 12: /* remove 1 element */ > + case 11: /* remove first element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_first (list1); > + ASSERT (gl_list_remove_first (list2) == removed1); > + ASSERT (gl_list_remove_first (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 12: /* remove last element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_last (list1); > + ASSERT (gl_list_remove_last (list2) == removed1); > + ASSERT (gl_list_remove_last (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 13: case 14: /* remove 1 element */ > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -336,7 +354,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 13: > + case 15: > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -347,7 +365,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n); > } > break; > - case 14: > + case 16: > { > size_t n = gl_list_size (list1); > gl_list_iterator_t iter1, iter2, iter3; > @@ -372,7 +390,7 @@ main (int argc, char *argv[]) > gl_list_iterator_free (&iter3); > } > break; > - case 15: > + case 17: > { > size_t end = RANDOM (gl_list_size (list1) + 1); > size_t start = RANDOM (end + 1); > diff --git a/tests/test-avltreehash_list.c b/tests/test-avltreehash_list.c > index 806b0e3..6dcded4 100644 > --- a/tests/test-avltreehash_list.c > +++ b/tests/test-avltreehash_list.c > @@ -124,7 +124,7 @@ main (int argc, char *argv[]) > > for (repeat = 0; repeat < 10000; repeat++) > { > - unsigned int operation = RANDOM (16); > + unsigned int operation = RANDOM (18); > switch (operation) > { > case 0: > @@ -355,7 +355,25 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 11: case 12: /* remove 1 element */ > + case 11: /* remove first element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_first (list1); > + ASSERT (gl_list_remove_first (list2) == removed1); > + ASSERT (gl_list_remove_first (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 12: /* remove last element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_last (list1); > + ASSERT (gl_list_remove_last (list2) == removed1); > + ASSERT (gl_list_remove_last (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 13: case 14: /* remove 1 element */ > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -366,7 +384,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 13: > + case 15: > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -377,7 +395,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n); > } > break; > - case 14: > + case 16: > { > size_t n = gl_list_size (list1); > gl_list_iterator_t iter1, iter2, iter3; > @@ -402,7 +420,7 @@ main (int argc, char *argv[]) > gl_list_iterator_free (&iter3); > } > break; > - case 15: > + case 17: > { > size_t end = RANDOM (gl_list_size (list1) + 1); > size_t start = RANDOM (end + 1); > diff --git a/tests/test-carray_list.c b/tests/test-carray_list.c > index c975266..a6e9511 100644 > --- a/tests/test-carray_list.c > +++ b/tests/test-carray_list.c > @@ -90,7 +90,7 @@ main (int argc, char *argv[]) > > for (repeat = 0; repeat < 10000; repeat++) > { > - unsigned int operation = RANDOM (16); > + unsigned int operation = RANDOM (18); > switch (operation) > { > case 0: > @@ -321,7 +321,25 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 11: case 12: /* remove 1 element */ > + case 11: /* remove first element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_first (list1); > + ASSERT (gl_list_remove_first (list2) == removed1); > + ASSERT (gl_list_remove_first (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 12: /* remove last element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_last (list1); > + ASSERT (gl_list_remove_last (list2) == removed1); > + ASSERT (gl_list_remove_last (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 13: case 14: /* remove 1 element */ > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -332,7 +350,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 13: > + case 15: > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -343,7 +361,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n); > } > break; > - case 14: > + case 16: > { > size_t n = gl_list_size (list1); > gl_list_iterator_t iter1, iter2, iter3; > @@ -368,7 +386,7 @@ main (int argc, char *argv[]) > gl_list_iterator_free (&iter3); > } > break; > - case 15: > + case 17: > { > size_t end = RANDOM (gl_list_size (list1) + 1); > size_t start = RANDOM (end + 1); > diff --git a/tests/test-linked_list.c b/tests/test-linked_list.c > index c139677..7c9954b 100644 > --- a/tests/test-linked_list.c > +++ b/tests/test-linked_list.c > @@ -90,7 +90,7 @@ main (int argc, char *argv[]) > > for (repeat = 0; repeat < 10000; repeat++) > { > - unsigned int operation = RANDOM (16); > + unsigned int operation = RANDOM (18); > switch (operation) > { > case 0: > @@ -321,7 +321,25 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 11: case 12: /* remove 1 element */ > + case 11: /* remove first element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_first (list1); > + ASSERT (gl_list_remove_first (list2) == removed1); > + ASSERT (gl_list_remove_first (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 12: /* remove last element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_last (list1); > + ASSERT (gl_list_remove_last (list2) == removed1); > + ASSERT (gl_list_remove_last (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 13: case 14: /* remove 1 element */ > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -332,7 +350,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 13: > + case 15: > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -343,7 +361,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n); > } > break; > - case 14: > + case 16: > { > size_t n = gl_list_size (list1); > gl_list_iterator_t iter1, iter2, iter3; > @@ -368,7 +386,7 @@ main (int argc, char *argv[]) > gl_list_iterator_free (&iter3); > } > break; > - case 15: > + case 17: > { > size_t end = RANDOM (gl_list_size (list1) + 1); > size_t start = RANDOM (end + 1); > diff --git a/tests/test-linkedhash_list.c b/tests/test-linkedhash_list.c > index 921c62c..7fa8b4f 100644 > --- a/tests/test-linkedhash_list.c > +++ b/tests/test-linkedhash_list.c > @@ -120,7 +120,7 @@ main (int argc, char *argv[]) > > for (repeat = 0; repeat < 10000; repeat++) > { > - unsigned int operation = RANDOM (16); > + unsigned int operation = RANDOM (18); > switch (operation) > { > case 0: > @@ -351,7 +351,25 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 11: case 12: /* remove 1 element */ > + case 11: /* remove first element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_first (list1); > + ASSERT (gl_list_remove_first (list2) == removed1); > + ASSERT (gl_list_remove_first (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 12: /* remove last element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_last (list1); > + ASSERT (gl_list_remove_last (list2) == removed1); > + ASSERT (gl_list_remove_last (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 13: case 14: /* remove 1 element */ > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -362,7 +380,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 13: > + case 15: > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -373,7 +391,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n); > } > break; > - case 14: > + case 16: > { > size_t n = gl_list_size (list1); > gl_list_iterator_t iter1, iter2, iter3; > @@ -398,7 +416,7 @@ main (int argc, char *argv[]) > gl_list_iterator_free (&iter3); > } > break; > - case 15: > + case 17: > { > size_t end = RANDOM (gl_list_size (list1) + 1); > size_t start = RANDOM (end + 1); > diff --git a/tests/test-rbtree_list.c b/tests/test-rbtree_list.c > index 32d9d32..efd2cb1 100644 > --- a/tests/test-rbtree_list.c > +++ b/tests/test-rbtree_list.c > @@ -94,7 +94,7 @@ main (int argc, char *argv[]) > > for (repeat = 0; repeat < 10000; repeat++) > { > - unsigned int operation = RANDOM (16); > + unsigned int operation = RANDOM (18); > switch (operation) > { > case 0: > @@ -325,7 +325,25 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 11: case 12: /* remove 1 element */ > + case 11: /* remove first element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_first (list1); > + ASSERT (gl_list_remove_first (list2) == removed1); > + ASSERT (gl_list_remove_first (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 12: /* remove last element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_last (list1); > + ASSERT (gl_list_remove_last (list2) == removed1); > + ASSERT (gl_list_remove_last (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 13: case 14: /* remove 1 element */ > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -336,7 +354,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 13: > + case 15: > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -347,7 +365,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n); > } > break; > - case 14: > + case 16: > { > size_t n = gl_list_size (list1); > gl_list_iterator_t iter1, iter2, iter3; > @@ -372,7 +390,7 @@ main (int argc, char *argv[]) > gl_list_iterator_free (&iter3); > } > break; > - case 15: > + case 17: > { > size_t end = RANDOM (gl_list_size (list1) + 1); > size_t start = RANDOM (end + 1); > diff --git a/tests/test-rbtreehash_list.c b/tests/test-rbtreehash_list.c > index 949a6f4..d6bbcb3 100644 > --- a/tests/test-rbtreehash_list.c > +++ b/tests/test-rbtreehash_list.c > @@ -124,7 +124,7 @@ main (int argc, char *argv[]) > > for (repeat = 0; repeat < 10000; repeat++) > { > - unsigned int operation = RANDOM (16); > + unsigned int operation = RANDOM (18); > switch (operation) > { > case 0: > @@ -355,7 +355,25 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 11: case 12: /* remove 1 element */ > + case 11: /* remove first element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_first (list1); > + ASSERT (gl_list_remove_first (list2) == removed1); > + ASSERT (gl_list_remove_first (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 12: /* remove last element */ > + { > + size_t n = gl_list_size (list1); > + bool removed1 = gl_list_remove_last (list1); > + ASSERT (gl_list_remove_last (list2) == removed1); > + ASSERT (gl_list_remove_last (list3) == removed1); > + ASSERT (gl_list_size (list1) == n - (int) removed1); > + } > + break; > + case 13: case 14: /* remove 1 element */ > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -366,7 +384,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n - 1); > } > break; > - case 13: > + case 15: > if (gl_list_size (list1) > 0) > { > size_t n = gl_list_size (list1); > @@ -377,7 +395,7 @@ main (int argc, char *argv[]) > ASSERT (gl_list_size (list1) == n); > } > break; > - case 14: > + case 16: > { > size_t n = gl_list_size (list1); > gl_list_iterator_t iter1, iter2, iter3; > @@ -402,7 +420,7 @@ main (int argc, char *argv[]) > gl_list_iterator_free (&iter3); > } > break; > - case 15: > + case 17: > { > size_t end = RANDOM (gl_list_size (list1) + 1); > size_t start = RANDOM (end + 1); > ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 7:16 ` Marc Nieper-Wißkirchen @ 2020-05-02 12:07 ` Bruno Haible 2020-05-02 12:49 ` Marc Nieper-Wißkirchen 2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible 0 siblings, 2 replies; 42+ messages in thread From: Bruno Haible @ 2020-05-02 12:07 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Hi Marc, > I didn't mean that gl_list_remove_last > should return the just deleted node but the node of the element that > is now the last one (the respectively first one for > gl_list_remove_first) after the removal. The gl_list_node_t type, in the 'list' interface so far, is used in operations that work on a single position. Except for the functions gl_list_next_node and gl_list_previous_node, which intentionally walk from one node to a neighbour node. Having a function that does an effect on the last element and returns the position of the second-to-last element would be an invitation to incorrect coding. Better keep the operations simple! Also, I don't see why your proposed operation would be important to have in a general API for lists. > The motivation behind my suggestion is to make it easy to implement a > stack (or a FIFO queue) with the gl_list interface. It is already easy to implement a stack or FIFO using the primitives. E.g. stack_pop = 1. gl_list_get_at (list, gl_list_size (list) - 1) 2. gl_list_remove_at (list, gl_list_size (list) - 1) or gl_list_remove_last (list). It would be a mistake to add semantics of stack or FIFO directly to the list interface, because a list *is* not a stack or a FIFO; a list *can be used to implement* a stack or a FIFO. It is an important concept that one interface can be used to implement another interface (-> layered software, hiding implementation details, etc.). See e.g. in Java: they have different interfaces for list [1], stack [2], and FIFO [2]. Initially, they defined Stack as a subclass of AbstractList, but realized later that it was a mistake. You are welcome to add a stack or FIFO module in gnulib. Most likely, each of the two will only have a single implementation. Why? Because - for stacks, the ARRAY and LINKED implementations would have the same O() complexity for each operation, and then ARRAY would be preferred because it is more efficient regarding use of memory and L1/L2 caches, - for FIFOs, the CARRAY and LINKED implementations would have the same O() complexity for each operation, and similarly CARRAY would be preferred because it is more efficient regarding use of memory and L1/L2 caches. > For this, > operations like gl_list_get_first and gl_list_get_last with guaranteed > O(1) behavior for a number of list implementations would also be nice. Hmm. I'm reluctant to introduce 4 new functions gl_list_get_first gl_list_get_last gl_list_set_first gl_list_set_last when the gl_list_get/gl_list_set operations with appropriate position argument already do the job. It appears to be more of a documentation issue, right? I.e. I should better revert yesterday's patch, and instead, in the table show the guaranteed average performance gl_list_get_first gl_list_get_last gl_list_set_first gl_list_set_last gl_list_remove_first gl_list_remove_last where these 6 functions are defined globally, not separately for each implementation. Bruno [1] https://docs.oracle.com/javase/8/docs/api/java/util/AbstractList.html [2] https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 12:07 ` Bruno Haible @ 2020-05-02 12:49 ` Marc Nieper-Wißkirchen 2020-05-02 15:49 ` Bruno Haible 2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible 1 sibling, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-02 12:49 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, [...] > The gl_list_node_t type, in the 'list' interface so far, is used in > operations that work on a single position. Except for the functions > gl_list_next_node and gl_list_previous_node, which intentionally > walk from one node to a neighbour node. Having a function that > does an effect on the last element and returns the position of the > second-to-last element would be an invitation to incorrect coding. > Better keep the operations simple! That's a fair point of view. [...] > > The motivation behind my suggestion is to make it easy to implement a > > stack (or a FIFO queue) with the gl_list interface. > > It is already easy to implement a stack or FIFO using the primitives. > E.g. stack_pop = > 1. gl_list_get_at (list, gl_list_size (list) - 1) > 2. gl_list_remove_at (list, gl_list_size (list) - 1) or > gl_list_remove_last (list). > > It would be a mistake to add semantics of stack or FIFO directly to the > list interface, because a list *is* not a stack or a FIFO; a list *can > be used to implement* a stack or a FIFO. It is an important concept > that one interface can be used to implement another interface (-> > layered software, hiding implementation details, etc.). Okay; I agree that a separate stack or FIFO module can make more sense; in particular when it only has to deal with a single implementation of an underlying data structure. At the moment I do have other work to finish first, but maybe I will find some time in the near future for a stack module. [...] > > For this, > > operations like gl_list_get_first and gl_list_get_last with guaranteed > > O(1) behavior for a number of list implementations would also be nice. > > Hmm. I'm reluctant to introduce 4 new functions > gl_list_get_first > gl_list_get_last > gl_list_set_first > gl_list_set_last > when the gl_list_get/gl_list_set operations with appropriate position > argument already do the job. It appears to be more of a documentation > issue, right? I.e. I should better revert yesterday's patch, and instead, > in the table show the guaranteed average performance > gl_list_get_first > gl_list_get_last > gl_list_set_first > gl_list_set_last > gl_list_remove_first > gl_list_remove_last > where these 6 functions are defined globally, not separately for each > implementation. When the functions can be defined globally, that's better than adding six functions to each vtable. Partly, it is just a documentation issue. I don't see, however, to implement the function dealing with end of the list in O(1) behavior when the underlying data structure is a linked list. Don't we need to expose an implementation-dependent gl_list_get_last_node (gl_list_first_node for symmetry)? The rest should then be implementable easily. Marc ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 12:49 ` Marc Nieper-Wißkirchen @ 2020-05-02 15:49 ` Bruno Haible 2020-05-02 16:04 ` Marc Nieper-Wißkirchen 2020-05-22 15:59 ` Marc Nieper-Wißkirchen 0 siblings, 2 replies; 42+ messages in thread From: Bruno Haible @ 2020-05-02 15:49 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Hi Marc, > Okay; I agree that a separate stack or FIFO module can make more > sense; in particular when it only has to deal with a single > implementation of an underlying data structure. At the moment I do > have other work to finish first, but maybe I will find some time in > the near future for a stack module. Good! When you come to it, please consider our "Contributing to Gnulib" tips: <https://www.gnu.org/software/gnulib/manual/html_node/Contributing-to-Gnulib.html>. > I don't see, however, to implement the function dealing with > end of the list in O(1) behavior when the underlying data structure is > a linked list. The LINKED list implementation is a doubly-linked list, and the functions get_at, set_at, or remove_at are implemented like this: If position < length/2 then walk from the start of the list (O(position)) else walk from the end of the list (O(length-position)). So, the original invocation gl_list_remove_at (list, gl_list_size (list) - 1) already does the job in O(1). Bruno ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 15:49 ` Bruno Haible @ 2020-05-02 16:04 ` Marc Nieper-Wißkirchen 2020-05-22 15:59 ` Marc Nieper-Wißkirchen 1 sibling, 0 replies; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-02 16:04 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, [...] > > I don't see, however, to implement the function dealing with > > end of the list in O(1) behavior when the underlying data structure is > > a linked list. > > The LINKED list implementation is a doubly-linked list, and the functions > get_at, set_at, or remove_at are implemented like this: > If position < length/2 then > walk from the start of the list (O(position)) > else > walk from the end of the list (O(length-position)). > > So, the original invocation > gl_list_remove_at (list, gl_list_size (list) - 1) > already does the job in O(1). Great. (Now that you say it I think I have once looked into the code but forgotten the details.) It would be nice if this could be documented. In any case, the general six functions we discussed should then be possible without any implementation-specifics. ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 15:49 ` Bruno Haible 2020-05-02 16:04 ` Marc Nieper-Wißkirchen @ 2020-05-22 15:59 ` Marc Nieper-Wißkirchen 2020-05-23 12:30 ` stack module Bruno Haible 1 sibling, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-22 15:59 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, Am Sa., 2. Mai 2020 um 17:49 Uhr schrieb Bruno Haible <bruno@clisp.org>: > > Hi Marc, > > > Okay; I agree that a separate stack or FIFO module can make more > > sense; in particular when it only has to deal with a single > > implementation of an underlying data structure. At the moment I do > > have other work to finish first, but maybe I will find some time in > > the near future for a stack module. Alternatively, one could implement a universally usable stack through the following header file (mimicking somewhat C++ templates). What do you think? It will be a lot faster than using the general list modules of Gnulib. It would be used like: STACK (int) stack; STACK_INIT (stack); assert (STACK_EMPTY (stack)); STACK_PUSH (stack, 4) assert (!STACK_EMPTY (stack)); assert (STACK_TOP (stack) == 4); assert (STACK_POP (stack) == 4); assert (STACK_EMPTY (stack)); STACK_CLEAR (stack); So long, Marc **** #ifndef _GL_STACK_H #define _GL_STACK_H #include <stddef.h> #include <stdlib.h> #include <xalloc.h> #define STACK(type) \ struct { \ type *base; \ size_t size; \ size_t allocated; \ } #define STACK_INIT(stack) \ do \ { \ (stack).base = NULL; \ (stack).size = 0; \ (stack).allocated = 0; \ } \ while (0) #define STACK_CLEAR(stack) \ free ((stack).base) #define STACK_EMPTY(stack) \ ((stack).size == 0) #define STACK_BASE(stack) \ ((stack).base) #define STACK_PUSH(stack, item) \ do \ { \ if ((stack).size == (stack).allocated) \ (stack).base = x2nrealloc ((stack).base, &(stack).allocated, sizeof (item)); \ (stack).base [(stack).size++] = item; \ } \ while (0) #define STACK_POP(stack) \ (stack).base [--(stack).size] #define STACK_DISCARD(stack) \ (--(stack).size) #define STACK_TOP(stack) \ (stack).base[(stack).size - 1] #define STACK_SIZE(stack) \ ((stack).size) #endif /* _GL_STACK_H */ ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-22 15:59 ` Marc Nieper-Wißkirchen @ 2020-05-23 12:30 ` Bruno Haible 2020-05-23 12:42 ` Marc Nieper-Wißkirchen 0 siblings, 1 reply; 42+ messages in thread From: Bruno Haible @ 2020-05-23 12:30 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Hi Marc, > Alternatively, one could implement a universally usable stack through > the following header file (mimicking somewhat C++ templates). What do > you think? It will be a lot faster than using the general list modules > of Gnulib. I agree that a generic 'stack' module is useful. I also agree that a single implementation, based on an array, is the way to go. Then it is already faster than the generic list module. In Gnulib, we usually avoid extensive use of multi-line macros, because it hampers debuggability. Here, however, one needs macros, in order to accommodate the TYPE argument, which is not necessarily compatible to 'void *'. Nevertheless, we would try to put as much code as possible into functions. The STACK_INIT macro, for example, could be implemented as a function. > #define STACK_CLEAR(stack) \ > free ((stack).base) Shouldn't this one also set .size and .allocated to 0 ? > #define STACK_POP(stack) \ > (stack).base [--(stack).size] > > #define STACK_DISCARD(stack) \ > (--(stack).size) > > #define STACK_TOP(stack) \ > (stack).base[(stack).size - 1] In these three macros, I would consider to abort() when (stack).size == 0. Bruno ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 12:30 ` stack module Bruno Haible @ 2020-05-23 12:42 ` Marc Nieper-Wißkirchen 2020-05-23 14:02 ` Bruno Haible 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-23 12:42 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, > In Gnulib, we usually avoid extensive use of multi-line macros, because > it hampers debuggability. Here, however, one needs macros, in order to > accommodate the TYPE argument, which is not necessarily compatible to 'void *'. > Nevertheless, we would try to put as much code as possible into functions. > The STACK_INIT macro, for example, could be implemented as a function. How? This would mean that the function stack_init has to take a void * argument, which has to be cast to struct { void *base; ... } and we have to hope that this structure is guaranteed to be compatible to struct { type *base; ... } by the C standard. > > #define STACK_CLEAR(stack) \ > > free ((stack).base) > > Shouldn't this one also set .size and .allocated to 0 ? A stack can be uninitialized or initialized. An uninitialized stack is initialized by STACK_INIT. It is cleared (and uninitialized) by STACK_CLEAR. An uninitialized stack does not have to maintain any invariant. The only way to use it is to initialize it again. Thus, setting .size and .allocated seems pointless. > > #define STACK_POP(stack) \ > > (stack).base [--(stack).size] > > > > #define STACK_DISCARD(stack) \ > > (--(stack).size) > > > > #define STACK_TOP(stack) \ > > (stack).base[(stack).size - 1] > > In these three macros, I would consider to abort() when (stack).size == 0. In the form of assure of the assure module? Or, to facilitate optimization, better assume from verify module? In non-debug builds, I want to make sure that no superfluous checks are made. Marc ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 12:42 ` Marc Nieper-Wißkirchen @ 2020-05-23 14:02 ` Bruno Haible 2020-05-23 14:36 ` Marc Nieper-Wißkirchen 0 siblings, 1 reply; 42+ messages in thread From: Bruno Haible @ 2020-05-23 14:02 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Hi Marc, > > In Gnulib, we usually avoid extensive use of multi-line macros, because > > it hampers debuggability. Here, however, one needs macros, in order to > > accommodate the TYPE argument, which is not necessarily compatible to 'void *'. > > Nevertheless, we would try to put as much code as possible into functions. > > The STACK_INIT macro, for example, could be implemented as a function. > > How? This would mean that the function stack_init has to take a void * > argument, which has to be cast to > > struct > { > void *base; ... > } > > and we have to hope that this structure is guaranteed to be compatible to > > struct > { > type *base; ... > } > > by the C standard. I was expecting that you write struct { void *base; ... } and the cast the base to 'type *' each time you fetch it. I don't think this would go the C standard, nor defeat any possible compiler optimization. > > > #define STACK_CLEAR(stack) \ > > > free ((stack).base) > > > > Shouldn't this one also set .size and .allocated to 0 ? > > A stack can be uninitialized or initialized. An uninitialized stack is > initialized by STACK_INIT. It is cleared (and uninitialized) by > STACK_CLEAR. An uninitialized stack does not have to maintain any > invariant. The only way to use it is to initialize it again. Thus, > setting .size and .allocated seems pointless. Then macro should better be called STACK_FREE or STACK_DESTROY. The name STACK_CLEAR suggests that the result is still a valid stack, and empty. > > > #define STACK_POP(stack) \ > > > (stack).base [--(stack).size] > > > > > > #define STACK_DISCARD(stack) \ > > > (--(stack).size) > > > > > > #define STACK_TOP(stack) \ > > > (stack).base[(stack).size - 1] > > > > In these three macros, I would consider to abort() when (stack).size == 0. > > In the form of assure of the assure module? Or, to facilitate > optimization, better assume from verify module? In non-debug builds, I > want to make sure that no superfluous checks are made. The 'verify' module is for compile-time checks. 'assure' is an improved form of 'assert'. Bruno ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 14:02 ` Bruno Haible @ 2020-05-23 14:36 ` Marc Nieper-Wißkirchen 2020-05-23 15:39 ` Paul Eggert 2020-05-23 17:19 ` Bruno Haible 0 siblings, 2 replies; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-23 14:36 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Am Sa., 23. Mai 2020 um 16:02 Uhr schrieb Bruno Haible <bruno@clisp.org>: > I was expecting that you write > > struct > { > void *base; ... > } This removes type safety. The benefit of the current approach is that stack types of different types are not compatible. > Then macro should better be called STACK_FREE or STACK_DESTROY. > The name STACK_CLEAR suggests that the result is still a valid stack, and empty. Thank you for this suggestion; much better. > > In the form of assure of the assure module? Or, to facilitate > > optimization, better assume from verify module? In non-debug builds, I > > want to make sure that no superfluous checks are made. > > The 'verify' module is for compile-time checks. > > 'assure' is an improved form of 'assert'. The verify also contains a runtime check `assume', which uses __builtin_unreachable if available to help the compiler in optimizing modes. ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 14:36 ` Marc Nieper-Wißkirchen @ 2020-05-23 15:39 ` Paul Eggert 2020-05-23 15:55 ` Marc Nieper-Wißkirchen 2020-05-23 17:19 ` Bruno Haible 1 sibling, 1 reply; 42+ messages in thread From: Paul Eggert @ 2020-05-23 15:39 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib On 5/23/20 7:36 AM, Marc Nieper-Wißkirchen wrote: > The verify also contains a runtime check `assume', which uses > __builtin_unreachable if available to help the compiler in optimizing > modes. I wouldn't call 'assume (X)' a "runtime check". It's more an anti-runtime-check. 'assume (X)' is a directive from the programmer to the compiler that X is true so that the compiler needn't generate code to test whether X is true. This is why 'assume' is in verify.h: it's related to static checking (in this case, static checking done by the programmer), not dynamic checking. Perhaps I should add a comment to this effect.... ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 15:39 ` Paul Eggert @ 2020-05-23 15:55 ` Marc Nieper-Wißkirchen 2020-05-23 16:44 ` Paul Eggert 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-23 15:55 UTC (permalink / raw) To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Am Sa., 23. Mai 2020 um 17:39 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>: > > On 5/23/20 7:36 AM, Marc Nieper-Wißkirchen wrote: > > The verify also contains a runtime check `assume', which uses > > __builtin_unreachable if available to help the compiler in optimizing > > modes. > > I wouldn't call 'assume (X)' a "runtime check". It's more an anti-runtime-check. > > 'assume (X)' is a directive from the programmer to the compiler that X is true > so that the compiler needn't generate code to test whether X is true. This is > why 'assume' is in verify.h: it's related to static checking (in this case, > static checking done by the programmer), not dynamic checking. > > Perhaps I should add a comment to this effect.... A combination of assure and assume would be helpful: #define checked_assume(X) do { assure (X); assume (X); } while (0) In debug builds, we get assertions and can check our assumptions. In non-debug (NDEBUG) builds, we just have the compiler hints. ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 15:55 ` Marc Nieper-Wißkirchen @ 2020-05-23 16:44 ` Paul Eggert 2020-05-23 16:54 ` Marc Nieper-Wißkirchen 0 siblings, 1 reply; 42+ messages in thread From: Paul Eggert @ 2020-05-23 16:44 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib [-- Attachment #1: Type: text/plain, Size: 327 bytes --] On 5/23/20 8:55 AM, Marc Nieper-Wißkirchen wrote: > A combination of assure and assume would be helpful: > > #define checked_assume(X) do { assure (X); assume (X); } while (0) No, because the compiler is entitled to optimize away the 'assure (X)' in this case. I installed the attached to try to explain this better. [-- Attachment #2: 0001-verify-document-assume-better.patch --] [-- Type: text/x-patch, Size: 2382 bytes --] From b2c8d02c9750f335549781d20fa37415c9a1edb3 Mon Sep 17 00:00:00 2001 From: Paul Eggert <eggert@cs.ucla.edu> Date: Sat, 23 May 2020 09:41:54 -0700 Subject: [PATCH] =?UTF-8?q?verify:=20document=20=E2=80=98assume=E2=80=99?= =?UTF-8?q?=20better?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * lib/verify.h (assume): Say it’s for static analysis, not dynamic. --- ChangeLog | 5 +++++ lib/verify.h | 20 ++++++++++++++++---- 2 files changed, 21 insertions(+), 4 deletions(-) diff --git a/ChangeLog b/ChangeLog index a4473284c..44450a354 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,8 @@ +2020-05-23 Paul Eggert <eggert@cs.ucla.edu> + + verify: document ‘assume’ better + * lib/verify.h (assume): Say it’s for static analysis, not dynamic. + 2020-05-22 Asher Gordon <AsDaGo@posteo.net> gendocs: Clarify licenses for templates. diff --git a/lib/verify.h b/lib/verify.h index d9ab89a57..f10976127 100644 --- a/lib/verify.h +++ b/lib/verify.h @@ -277,10 +277,22 @@ template <int w> #endif /* Assume that R always holds. Behavior is undefined if R is false, - fails to evaluate, or has side effects. Although assuming R can - help a compiler generate better code or diagnostics, performance - can suffer if R uses hard-to-optimize features such as function - calls not inlined by the compiler. */ + fails to evaluate, or has side effects. + + 'assume (R)' is a directive from the programmer telling the + compiler that R is true so the compiler needn't generate code to + test R. This is why 'assume' is in verify.h: it's related to + static checking (in this case, static checking done by the + programmer), not dynamic checking. + + 'assume (R)' can affect compilation of all the code, not just code + that happens to be executed after the assume (R) is "executed". + For example, if the code mistakenly does 'assert (R); assume (R);' + the compiler is entitled to optimize away the 'assert (R)'. + + Although assuming R can help a compiler generate better code or + diagnostics, performance can suffer if R uses hard-to-optimize + features such as function calls not inlined by the compiler. */ #if _GL_HAS_BUILTIN_UNREACHABLE # define assume(R) ((R) ? (void) 0 : __builtin_unreachable ()) -- 2.17.1 ^ permalink raw reply related [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 16:44 ` Paul Eggert @ 2020-05-23 16:54 ` Marc Nieper-Wißkirchen 2020-05-23 17:33 ` Paul Eggert 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-23 16:54 UTC (permalink / raw) To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Am Sa., 23. Mai 2020 um 18:44 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>: > > On 5/23/20 8:55 AM, Marc Nieper-Wißkirchen wrote: > > A combination of assure and assume would be helpful: > > > > #define checked_assume(X) do { assure (X); assume (X); } while (0) > > No, because the compiler is entitled to optimize away the 'assure (X)' in this > case. I installed the attached to try to explain this better. Sure, but not in "-O0" or "-Og" builds, I think. Or am I mistaken? But it is definitely better to make it more robust and not rely on optimization levels: #include <assert.h> #include "verify.h" #ifdef NDEBUG # define checked_assume(E) assume (E) #else # define checked_assume(E) assert (E) #endif ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 16:54 ` Marc Nieper-Wißkirchen @ 2020-05-23 17:33 ` Paul Eggert 2020-05-23 17:38 ` Marc Nieper-Wißkirchen 0 siblings, 1 reply; 42+ messages in thread From: Paul Eggert @ 2020-05-23 17:33 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib On 5/23/20 9:54 AM, Marc Nieper-Wißkirchen wrote: > Sure, but not in "-O0" or "-Og" builds, I think. Or am I mistaken? Probably not for -O0. I'm not so sure for -Og. Either way, we shouldn't rely on GCC's current behavior in this area as it is neither documented nor guaranteed to stay the same. > #include <assert.h> > #include "verify.h" > > #ifdef NDEBUG > # define checked_assume(E) assume (E) > #else > # define checked_assume(E) assert (E) > #endif Something like that would work, though the name "checked_assume" is misleading since the assumption is not always checked. "affirm (E)" would be a better name, since the name's not being used anymore by the old software verification project[1] and it slides in well next to "assume" and "assert". (Some day we're going to run out of synonyms. :-) [1] http://www.softwarepreservation.org/projects/verification/affirm/ ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 17:33 ` Paul Eggert @ 2020-05-23 17:38 ` Marc Nieper-Wißkirchen 2020-05-23 20:51 ` Paul Eggert 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-23 17:38 UTC (permalink / raw) To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Paul, Am Sa., 23. Mai 2020 um 19:33 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>: > Probably not for -O0. I'm not so sure for -Og. Either way, we shouldn't rely on > GCC's current behavior in this area as it is neither documented nor guaranteed > to stay the same. Agreed. > > #include <assert.h> > > #include "verify.h" > > > > #ifdef NDEBUG > > # define checked_assume(E) assume (E) > > #else > > # define checked_assume(E) assert (E) > > #endif > > Something like that would work, though the name "checked_assume" is misleading > since the assumption is not always checked. > > "affirm (E)" would be a better name, since the name's not being used anymore by > the old software verification project[1] and it slides in well next to "assume" > and "assert". (Some day we're going to run out of synonyms. :-) Believe it or not, but when I first proposed the (initial version of the) macro, I wanted to name it "affirm" after I had looked for synonyms. Only eventually, I switched to the name "checked_assume". But if "affirm" is fine with you, I would love to see it in a module. Either in verify or assure or in a new module named affirm. ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 17:38 ` Marc Nieper-Wißkirchen @ 2020-05-23 20:51 ` Paul Eggert 2020-05-23 21:07 ` Marc Nieper-Wißkirchen 2020-05-23 22:06 ` Bruno Haible 0 siblings, 2 replies; 42+ messages in thread From: Paul Eggert @ 2020-05-23 20:51 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib [-- Attachment #1: Type: text/plain, Size: 221 bytes --] On 5/23/20 10:38 AM, Marc Nieper-Wißkirchen wrote: > But if "affirm" is fine with you, I would love to see it in a module. > Either in verify or assure or in a new module named affirm. Something like the attached? [-- Attachment #2: affirm.diff --] [-- Type: text/x-patch, Size: 1432 bytes --] diff --git a/lib/assure.h b/lib/assure.h index 8ea2f6e48..2f1326027 100644 --- a/lib/assure.h +++ b/lib/assure.h @@ -22,11 +22,29 @@ #include <assert.h> +/* Check E's value at runtime, and report an error and abort if not. + However, do nothing if NDEBUG is defined; in this case behavior is + undefined if E is false, fails to evaluate, or has side effects. + + Unlike standard 'assert', this macro always compiles E even when + NDEBUG is defined, so as to catch typos, avoid some GCC warnings, + and improve performance when E is simple enough. + + Also see the documentation for 'assume' in verify.h. */ + +#ifdef NDEBUG +# define affirm(E) assume (E) +#else +# define affirm(E) assert (E) +#endif + /* Check E's value at runtime, and report an error and abort if not. However, do nothing if NDEBUG is defined. Unlike standard 'assert', this macro always compiles E even when NDEBUG - is defined, so as to catch typos and avoid some GCC warnings. */ + is defined, so as to catch typos and avoid some GCC warnings. + Unlike 'affirm', it is OK for E to use hard-to-optimize features, + since E is not executed if NDEBUG is defined. */ #ifdef NDEBUG # define assure(E) ((void) (0 && (E))) diff --git a/modules/assure b/modules/assure index 3cfe1f874..c37191717 100644 --- a/modules/assure +++ b/modules/assure @@ -5,6 +5,7 @@ Files: lib/assure.h Depends-on: +verify configure.ac: ^ permalink raw reply related [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 20:51 ` Paul Eggert @ 2020-05-23 21:07 ` Marc Nieper-Wißkirchen 2020-05-23 22:06 ` Bruno Haible 1 sibling, 0 replies; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-23 21:07 UTC (permalink / raw) To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Am Sa., 23. Mai 2020 um 22:51 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>: > > On 5/23/20 10:38 AM, Marc Nieper-Wißkirchen wrote: > > But if "affirm" is fine with you, I would love to see it in a module. > > Either in verify or assure or in a new module named affirm. > > Something like the attached? That would be a good addition to Gnulib, indeed, I think. (And may even already be used by a number of modules, which currently call abort explicitly.) I find the comments in your code very valuable. I may change only one thing. Above the definition of affirm, you write "Unlike standard 'assert', this macro always compiles E even when NDEBUG is defined ...". I think it is better to change it to "... always evaluates E even when ...". In fact, when the assumption is fulfilled, E must have been evaluated. If the assumption fails we are in the realm of undefined behavior, so we may as well claim that E has been evaluated. This is important not only so that the side effects of the evaluation of E are documented, but also to remind the user of a potentially costly evaluation. ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 20:51 ` Paul Eggert 2020-05-23 21:07 ` Marc Nieper-Wißkirchen @ 2020-05-23 22:06 ` Bruno Haible 2020-05-24 2:14 ` Paul Eggert 1 sibling, 1 reply; 42+ messages in thread From: Bruno Haible @ 2020-05-23 22:06 UTC (permalink / raw) To: bug-gnulib; +Cc: Marc Nieper-Wißkirchen, Paul Eggert Hi Paul, > Something like the attached? This documentation is quite misleading: +/* Check E's value at runtime, and report an error and abort if not. + However, do nothing if NDEBUG is defined; in this case behavior is because the "do nothing" is an understatement. 'assume' is a dangerous macro, because it allows the compiler to do optimizations based on putative assumptions. Since 'affirm' invokes 'assume', the documentation should emphasize this danger. How about this instead? /* States an assertion that the programmer believes to be true. When NDEBUG is not defined, this macro is like assert: it verifies the assertion at run time and aborts the program if the assertion is not true. When NDEBUG is defined, the programmer guarantees that the assertion is true, and the macro informs the compiler about it, so that the compiler may produce optimized code based on it. */ Bruno ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 22:06 ` Bruno Haible @ 2020-05-24 2:14 ` Paul Eggert 2020-05-24 8:17 ` Marc Nieper-Wißkirchen 0 siblings, 1 reply; 42+ messages in thread From: Paul Eggert @ 2020-05-24 2:14 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib [-- Attachment #1: Type: text/plain, Size: 229 bytes --] On 5/23/20 3:06 PM, Bruno Haible wrote: > How about this instead? Thanks, good point about the danger. Also, I forgot to include verify.h. I tightened up the commentary, folded in Marc's suggestion, and installed the attached. [-- Attachment #2: 0001-assure-new-macro-affirm.patch --] [-- Type: text/x-patch, Size: 3094 bytes --] From 2df56dc44200074077ebace04079ac4b0a34e4fc Mon Sep 17 00:00:00 2001 From: Paul Eggert <eggert@cs.ucla.edu> Date: Sat, 23 May 2020 19:06:16 -0700 Subject: [PATCH] =?UTF-8?q?assure:=20new=20macro=20=E2=80=98affirm?= =?UTF-8?q?=E2=80=99?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * lib/assure.h: Include verify.h. (affirm): New macro, after a suggestion by Marc Nieper-Wißkirchen in: https://lists.gnu.org/r/bug-gnulib/2020-05/msg00263.html and commentary by Bruno Haible in: https://lists.gnu.org/r/bug-gnulib/2020-05/msg00278.html * modules/assure (Depends-on:): Add verify. --- ChangeLog | 10 ++++++++++ lib/assure.h | 24 ++++++++++++++++++++++-- modules/assure | 1 + 3 files changed, 33 insertions(+), 2 deletions(-) diff --git a/ChangeLog b/ChangeLog index a7101db80..c05ef910d 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2020-05-23 Paul Eggert <eggert@cs.ucla.edu> + + assure: new macro ‘affirm’ + * lib/assure.h: Include verify.h. + (affirm): New macro, after a suggestion by Marc Nieper-Wißkirchen in: + https://lists.gnu.org/r/bug-gnulib/2020-05/msg00263.html + and commentary by Bruno Haible in: + https://lists.gnu.org/r/bug-gnulib/2020-05/msg00278.html + * modules/assure (Depends-on:): Add verify. + 2020-05-23 Bruno Haible <bruno@clisp.org> calloc-gnu: Make test work in non-flat address spaces. diff --git a/lib/assure.h b/lib/assure.h index 8ea2f6e48..09a4edfa5 100644 --- a/lib/assure.h +++ b/lib/assure.h @@ -21,12 +21,32 @@ #define _GL_ASSURE_H #include <assert.h> +#include "verify.h" + +/* Evaluate an assertion E that is guaranteed to be true. + If NDEBUG is not defined, abort the program if E is false. + If NDEBUG is defined, the compiler can assume E and behavior is + undefined if E is false, fails to evaluate, or has side effects. + + Unlike standard 'assert', this macro evaluates E even when NDEBUG + is defined, so as to catch typos, avoid some GCC warnings, and + improve performance when E is simple enough. + + Also see the documentation for 'assume' in verify.h. */ + +#ifdef NDEBUG +# define affirm(E) assume (E) +#else +# define affirm(E) assert (E) +#endif /* Check E's value at runtime, and report an error and abort if not. However, do nothing if NDEBUG is defined. - Unlike standard 'assert', this macro always compiles E even when NDEBUG - is defined, so as to catch typos and avoid some GCC warnings. */ + Unlike standard 'assert', this macro compiles E even when NDEBUG + is defined, so as to catch typos and avoid some GCC warnings. + Unlike 'affirm', it is OK for E to use hard-to-optimize features, + since E is not executed if NDEBUG is defined. */ #ifdef NDEBUG # define assure(E) ((void) (0 && (E))) diff --git a/modules/assure b/modules/assure index 3cfe1f874..c37191717 100644 --- a/modules/assure +++ b/modules/assure @@ -5,6 +5,7 @@ Files: lib/assure.h Depends-on: +verify configure.ac: -- 2.17.1 ^ permalink raw reply related [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-24 2:14 ` Paul Eggert @ 2020-05-24 8:17 ` Marc Nieper-Wißkirchen 2020-05-24 19:07 ` Paul Eggert 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-24 8:17 UTC (permalink / raw) To: Paul Eggert; +Cc: bug-gnulib, Bruno Haible, Marc Nieper-Wißkirchen Thank you very much, Paul! One bit of the commentary is still misleading, though, I think. You wrote for the affirm macro that if NDEBUG is defined that the behavior is undefined if E has side effects. That's not true as long as E does not evaluate to false. Marc Am So., 24. Mai 2020 um 04:14 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>: > > On 5/23/20 3:06 PM, Bruno Haible wrote: > > How about this instead? > > Thanks, good point about the danger. Also, I forgot to include verify.h. > > I tightened up the commentary, folded in Marc's suggestion, and installed the > attached. ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-24 8:17 ` Marc Nieper-Wißkirchen @ 2020-05-24 19:07 ` Paul Eggert 2020-05-24 19:26 ` Bruno Haible 0 siblings, 1 reply; 42+ messages in thread From: Paul Eggert @ 2020-05-24 19:07 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib, Bruno Haible On 5/24/20 1:17 AM, Marc Nieper-Wißkirchen wrote: > You > wrote for the affirm macro that if NDEBUG is defined that the behavior > is undefined if E has side effects. That's not true as long as E does > not evaluate to false. We can *make* it true, by fiat. :-) I don't want to encourage programmers to supply an E with side effects, as side effects are trouble here. Even if side effects happen to work in the current implementation when E is true, I don't want to suggest to programmers that they'll continue to work in future implementations; we may come up with a different implementation that evaluates E twice, for example. ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-24 19:07 ` Paul Eggert @ 2020-05-24 19:26 ` Bruno Haible 2020-06-02 13:44 ` Marc Nieper-Wißkirchen 0 siblings, 1 reply; 42+ messages in thread From: Bruno Haible @ 2020-05-24 19:26 UTC (permalink / raw) To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Paul Eggert wrote: > I don't want to encourage programmers to supply an E with side effects, as side > effects are trouble here. +1 ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-24 19:26 ` Bruno Haible @ 2020-06-02 13:44 ` Marc Nieper-Wißkirchen 0 siblings, 0 replies; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-06-02 13:44 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, Paul Eggert, bug-gnulib So here is the updated stack module. The name "CLEAR" has been changed to "DESTROY" as suggested by Bruno. Error checking has been included. The macro interface remains. Although a macro interface means macros, the macros are trivial and the type safety wins here, I think. I have renamed STACK_BASE to STACK_CURRENT_BASE because the base may be invalidated when items are pushed onto the stack and reallocation has to happen. As I haven't heard anything from the FSF yet, I wouldn't mind if you considered the following in the public domain... #ifndef _GL_STACK_H #define _GL_STACK_H #include <stddef.h> #include <stdlib.h> #include "assure.h" #include "xalloc.h" #define STACK(type) \ struct { \ type *base; \ size_t size; \ size_t allocated; \ } #define STACK_INIT(stack) \ do \ { \ (stack).base = NULL; \ (stack).size = 0; \ (stack).allocated = 0; \ } \ while (0) #define STACK_DESTROY(stack) \ free ((stack).base) #define STACK_EMPTY(stack) \ ((stack).size == 0) #define STACK_CURRENT_BASE(stack) \ ((stack).base) #define STACK_PUSH(stack, item) \ do \ { \ if ((stack).size == (stack).allocated) \ (stack).base = x2nrealloc ((stack).base, &(stack).allocated, sizeof (item)); \ (stack).base [(stack).size++] = item; \ } \ while (0) #define STACK_POP(stack) \ (affirm (!STACK_EMPTY (stack)), (stack).base [--(stack).size]) #define STACK_DISCARD(stack) \ (affirm (!STACK_EMPTY (stack)), (--(stack).size)) #define STACK_TOP(stack) \ (affirm (!STACK_EMPTY (stack)), (stack).base[(stack).size - 1) #define STACK_SIZE(stack) \ ((stack).size) #endif /* _GL_STACK_H */ Am So., 24. Mai 2020 um 21:26 Uhr schrieb Bruno Haible <bruno@clisp.org>: > > Paul Eggert wrote: > > I don't want to encourage programmers to supply an E with side effects, as side > > effects are trouble here. > > +1 > ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 14:36 ` Marc Nieper-Wißkirchen 2020-05-23 15:39 ` Paul Eggert @ 2020-05-23 17:19 ` Bruno Haible 2020-07-22 20:17 ` Marc Nieper-Wißkirchen 1 sibling, 1 reply; 42+ messages in thread From: Bruno Haible @ 2020-05-23 17:19 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Marc Nieper-Wißkirchen wrote: > > I was expecting that you write > > > > struct > > { > > void *base; ... > > } > > This removes type safety. The benefit of the current approach is that > stack types of different types are not compatible. Indeed. Yes, it's a difficult trade-off between debuggability, binary code size, and type safety... Bruno ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-05-23 17:19 ` Bruno Haible @ 2020-07-22 20:17 ` Marc Nieper-Wißkirchen 2020-07-23 10:36 ` Bruno Haible 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-07-22 20:17 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Am Sa., 23. Mai 2020 um 19:19 Uhr schrieb Bruno Haible <bruno@clisp.org>: > > Marc Nieper-Wißkirchen wrote: > > > I was expecting that you write > > > > > > struct > > > { > > > void *base; ... > > > } > > > > This removes type safety. The benefit of the current approach is that > > stack types of different types are not compatible. > > Indeed. Yes, it's a difficult trade-off between debuggability, binary code size, > and type safety... The alternative with the same type safety would be a source file with stack code procedures meant for inclusion (without include guards). The source file would expect a preprocessor defines GL_STACK_NAME, GL_STACK_TYPE, and GL_STACK_EXTERN. The file itself would contain code like the following: #define _GL_STACK_PREFIX(name) _GL_CONCAT(GL_STACK_NAME, _GL_CONCAT(_, name)) typedef struct { GL_STACK_TYPE *base; size_t size; size_t allocated; } GL_STACK_PREFIX(type); GL_STACK_EXTERN GL_STACK_PREFIX(init) (GL_STACK_PREFIX(type) *stack) { stack->base = NULL; stack->size = 0; stack->allocated = 0; } ... The advantage of this model is that it generalizes to other data structures, for which a sole (or at least simple) macro implementation is not possible. What do you think? Marc ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-07-22 20:17 ` Marc Nieper-Wißkirchen @ 2020-07-23 10:36 ` Bruno Haible 2020-07-23 10:56 ` Marc Nieper-Wißkirchen 2020-10-07 9:01 ` Marc Nieper-Wißkirchen 0 siblings, 2 replies; 42+ messages in thread From: Bruno Haible @ 2020-07-23 10:36 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Hi Marc, > The alternative with the same type safety would be a source file with > stack code procedures meant for inclusion (without include guards). > The source file would expect a preprocessor defines GL_STACK_NAME, > GL_STACK_TYPE, and GL_STACK_EXTERN. > > The file itself would contain code like the following: > > #define _GL_STACK_PREFIX(name) _GL_CONCAT(GL_STACK_NAME, _GL_CONCAT(_, name)) > > typedef struct > { > GL_STACK_TYPE *base; > size_t size; > size_t allocated; > } > GL_STACK_PREFIX(type); > > GL_STACK_EXTERN GL_STACK_PREFIX(init) (GL_STACK_PREFIX(type) *stack) > { > stack->base = NULL; > stack->size = 0; > stack->allocated = 0; > } > > ... > > The advantage of this model is that it generalizes to other data > structures, for which a sole (or at least simple) macro implementation > is not possible. This is perfectly acceptable for Gnulib. It has debuggability and type safety. You have precedent e.g. in lib/diffseq.h and lib/aligned-malloc.h. You can even omit the 'GL_' prefix from the macro names. The user can #undef the macros after including the file; therefore there is nearly no risk of collision with macros defined by other code. Bruno ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-07-23 10:36 ` Bruno Haible @ 2020-07-23 10:56 ` Marc Nieper-Wißkirchen 2020-10-07 9:01 ` Marc Nieper-Wißkirchen 1 sibling, 0 replies; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-07-23 10:56 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, > This is perfectly acceptable for Gnulib. It has debuggability and type safety. Perfect. Then I will come up with a module in this form. > You have precedent e.g. in lib/diffseq.h and lib/aligned-malloc.h. Good to know; I hadn't taken a look at these sources yet. > You can even omit the 'GL_' prefix from the macro names. The user can #undef > the macros after including the file; therefore there is nearly no risk of > collision with macros defined by other code. Or the included file #undefs the macros as in lib/diffseq.h. Speaking of prefixes: As macro names (and other names) starting with "_GL_" are not officially allowed by ISO C, I think it makes sense to think of a new convention for new sources (while old sources could later be updated incrementally). For example, one could use the prefix "GL__" (double underscore) for (future) private identifiers. Marc ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-07-23 10:36 ` Bruno Haible 2020-07-23 10:56 ` Marc Nieper-Wißkirchen @ 2020-10-07 9:01 ` Marc Nieper-Wißkirchen 2020-10-07 11:31 ` Marc Nieper-Wißkirchen 1 sibling, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-10-07 9:01 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, I am finally finishing my work on the stack module. Am Do., 23. Juli 2020 um 12:36 Uhr schrieb Bruno Haible <bruno@clisp.org>: [...] > This is perfectly acceptable for Gnulib. It has debuggability and type safety. > > You have precedent e.g. in lib/diffseq.h and lib/aligned-malloc.h. > > You can even omit the 'GL_' prefix from the macro names. The user can #undef > the macros after including the file; therefore there is nearly no risk of > collision with macros defined by other code. After I have given it a bit more thought, I see a different type of collision possibility, namely if some header file uses the stack header file. It will leak the macro names. Assume that the stack module accepts the macro name ELEMENT for the element type. A hypothetical header for the frob type may be implemented as: #ifndef FROB_H #define FROB_H ... #define ELEMENT int #define STORAGECLASS static inline #include "stack.h" ... struct frob { stack frob_stack; ... }; ... #endif /* FROB_H */ Now, user code cannot do: #define ELEMENT hydrogen #include "frob.h" ... (The ELEMENT definition in the first line could in fact be exported by some other header file.) Therefore, I think I prefer to use prefixed names. Cheers, Marc ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-10-07 9:01 ` Marc Nieper-Wißkirchen @ 2020-10-07 11:31 ` Marc Nieper-Wißkirchen 2020-10-10 14:06 ` Bruno Haible 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-10-07 11:31 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib, Bruno Haible [-- Attachment #1: Type: text/plain, Size: 1572 bytes --] Dear Bruno, please see the attached patch for the new module. Thanks, Marc Am Mi., 7. Okt. 2020 um 11:01 Uhr schrieb Marc Nieper-Wißkirchen <marc.nieper+gnu@gmail.com>: > > Hi Bruno, > > I am finally finishing my work on the stack module. > > Am Do., 23. Juli 2020 um 12:36 Uhr schrieb Bruno Haible <bruno@clisp.org>: > > [...] > > > This is perfectly acceptable for Gnulib. It has debuggability and type safety. > > > > You have precedent e.g. in lib/diffseq.h and lib/aligned-malloc.h. > > > > You can even omit the 'GL_' prefix from the macro names. The user can #undef > > the macros after including the file; therefore there is nearly no risk of > > collision with macros defined by other code. > > After I have given it a bit more thought, I see a different type of > collision possibility, namely if some header file uses the stack > header file. It will leak the macro names. Assume that the stack > module accepts the macro name ELEMENT for the element type. A > hypothetical header for the frob type may be implemented as: > > #ifndef FROB_H > #define FROB_H > ... > #define ELEMENT int > #define STORAGECLASS static inline > #include "stack.h" > ... > struct frob > { > stack frob_stack; > ... > }; > ... > #endif /* FROB_H */ > > Now, user code cannot do: > > #define ELEMENT hydrogen > #include "frob.h" > ... > > (The ELEMENT definition in the first line could in fact be exported by > some other header file.) > > Therefore, I think I prefer to use prefixed names. > > Cheers, > > Marc [-- Attachment #2: 0001-Type-safe-stack-data-type.patch --] [-- Type: text/x-patch, Size: 10525 bytes --] From c449d60058f4a5806729ec76779fbb050890ddaf Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20Nieper-Wi=C3=9Fkirchen?= <marc@nieper-wisskirchen.de> Date: Wed, 7 Oct 2020 13:29:10 +0200 Subject: [PATCH] Type-safe stack data type. * MODULES.html.sh: Add entry for the stack module. * modules/stack: New file. * modules/stack-tests: New file. * lib/stack.h: New file. * tests/test-stack.c: New file. --- ChangeLog | 9 +++ MODULES.html.sh | 1 + lib/stack.h | 163 ++++++++++++++++++++++++++++++++++++++++++++ modules/stack | 25 +++++++ modules/stack-tests | 13 ++++ tests/test-stack.c | 74 ++++++++++++++++++++ 6 files changed, 285 insertions(+) create mode 100644 lib/stack.h create mode 100644 modules/stack create mode 100644 modules/stack-tests create mode 100644 tests/test-stack.c diff --git a/ChangeLog b/ChangeLog index 875f3551a..b64689f73 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2020-10-07 Marc nieper-Wißkirchen <marc@nieper-wisskirchen.de> + + stack: New module. + * MODULES.html.sh: Add entry for the stack module. + * modules/stack: New file. + * modules/stack-tests: New file. + * lib/stack.h: New file. + * tests/test-stack.c: New file. + 2020-10-05 Paul Eggert <eggert@cs.ucla.edu> thread: pacify GCC on Solaris 10 diff --git a/MODULES.html.sh b/MODULES.html.sh index a8a629e29..7e7cdae3e 100755 --- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -2031,6 +2031,7 @@ func_all_modules () func_module readline func_module readtokens func_module readtokens0 + func_module stack func_module strverscmp func_module filevercmp func_end_table diff --git a/lib/stack.h b/lib/stack.h new file mode 100644 index 000000000..22e976952 --- /dev/null +++ b/lib/stack.h @@ -0,0 +1,163 @@ +/* Type-safe stack data type. + Copyright (C) 2020 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Written by Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>, 2020. */ + +/* This header file does not have include-guards as it is meant to be + includeable multiple times as long as the necessary defines have + been set up. + + A stack is implemented with a homogenous array of elements in + memory, which will be resized (and moved) as needed. Elements are + passed by value and it is the responsibility of the user-code to + free any allocate and free any resources associated with individual + elements. + + The exported names are all prefixed by ‘stack’ (e.g. stack_init), + but this can be changed by setting an appropriate define. + Type: stack_type + Initialization: stack_init (&stack); + De-initialization: stack_destroy (&stack); + Predicate: bool res = stack_empty (&stack); + Introspection: ELEMENT *base = stack_base (&stack); + Pushing: stack_push (&stack, element); + Popping: ELEMENT element = stack_pop (&stack); + Discarding: stack_discard (&stack); + Top-of-stack: ELEMENT element = stack_top (&stack); + Size: size_t size = stack_size (&stack); +*/ + +/* Before including this file, you need to define: + GL_STACK_ELEMENT The type of the elements on the stack.. + GL_STACK_STORAGECLASS (Optional) The storage class specifier (e.g. static) + to use in the function definitions. + GL_STACK_NAME (Optional) The prefix to use for the type names + and functions definitions instead of the default + ‘stack’. + + After including this file, these names will be undefined. + + Before including this file, you also need to include: + #include "<stdbool.h>" + #include "<stdlib.h>" + #include "assure.h" + #include "xalloc.h" +*/ + +#ifndef GL_STACK_ELEMENT +# error "Please define GL_STACK_ELEMENT first." +#endif + +#ifndef GL_STACK_STORAGECLASS +# define GL_STACK_STORAGECLASS +#endif + +#ifndef GL_STACK_NAME +# define GL_STACK_NAME stack +#endif + +#define _GL_STACK_PREFIX(name) _GL_CONCAT(GL_STACK_NAME, _GL_CONCAT(_, name)) +#define _GL_STACK_TYPE _GL_STACK_PREFIX(type) + +typedef struct +{ + GL_STACK_ELEMENT *base; + size_t size; + size_t allocated; +} _GL_STACK_TYPE; + +/* Initialize a stack. */ +GL_STACK_STORAGECLASS void +_GL_STACK_PREFIX (init) (_GL_STACK_TYPE *stack) +{ + stack->base = NULL; + stack->size = 0; + stack->allocated = 0; +} + +/* Destroy a stack by freeing the allocated space. */ +GL_STACK_STORAGECLASS void +_GL_STACK_PREFIX (destroy) (_GL_STACK_TYPE *stack) +{ + free (stack->base); +} + +/* Return true if the stack currently holds no element. */ +GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE bool +_GL_STACK_PREFIX (empty) (const _GL_STACK_TYPE *stack) +{ + return stack->size == 0; +} + +/* Return the current address of the array of stack elements. + + The result is invalidated as soon as an element is added or removed + from the stack. */ +GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE GL_STACK_ELEMENT * +_GL_STACK_PREFIX (current_base) (const _GL_STACK_TYPE *stack) +{ + return stack->base; +} + +/* Push an element to the top of the stack. */ +GL_STACK_STORAGECLASS void +_GL_STACK_PREFIX (push) (_GL_STACK_TYPE *stack, GL_STACK_ELEMENT item) +{ + if (stack->size == stack->allocated) + stack->base = x2nrealloc (stack->base, &stack->allocated, + sizeof (GL_STACK_ELEMENT)); + stack->base [stack->size++] = item; +} + +/* Pop the element from the top of the stack, which must be non-empty, + and return it. */ +GL_STACK_STORAGECLASS GL_STACK_ELEMENT +_GL_STACK_PREFIX (pop) (_GL_STACK_TYPE *stack) +{ + affirm (!_GL_STACK_PREFIX (empty) (stack)); + return stack->base [--stack->size]; +} + +/* Pop the element from the top of the stack, which must be + non-empty. */ +GL_STACK_STORAGECLASS void +_GL_STACK_PREFIX (discard) (_GL_STACK_TYPE *stack) +{ + affirm (!_GL_STACK_PREFIX (empty) (stack)); + --stack->size; +} + +/* Return the element from the top of the stack, which must be + non-empty. */ +GL_STACK_STORAGECLASS GL_STACK_ELEMENT +_GL_STACK_PREFIX (top) (const _GL_STACK_TYPE *stack) +{ + affirm (!_GL_STACK_PREFIX (empty) (stack)); + return stack->base [stack->size - 1]; +} + +/* Return the currently stored number of elements in the stack. */ +GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE size_t +_GL_STACK_PREFIX (size) (const _GL_STACK_TYPE *stack) +{ + return stack->size; +} + +#undef GL_STACK_ELEMENT +#undef GL_STACK_STORAGECLASS +#undef GL_STACK_NAME +#undef _GL_STACK_PREFIX +#undef _GL_STACK_TYPE diff --git a/modules/stack b/modules/stack new file mode 100644 index 000000000..95f2ce9b9 --- /dev/null +++ b/modules/stack @@ -0,0 +1,25 @@ +Description: +Type-safe stack data type. + +Files: +lib/stack.h + +Depends-on: +assure +stdbool +stdlib +xalloc + +configure.ac: + +Makefile.am: +lib_SOURCES += stack.h + +Include: +"stack.h" + +License: +GPL + +Maintainer: +Marc Nieper-Wißkirchen diff --git a/modules/stack-tests b/modules/stack-tests new file mode 100644 index 000000000..308d7258e --- /dev/null +++ b/modules/stack-tests @@ -0,0 +1,13 @@ +Files: +tests/test-stack.c +tests/macros.h + +Depends-on: +string + +configure.ac: + +Makefile.am: +TESTS += test-stack +check_PROGRAMS += test-stack +test_stack_SOURCES = test-stack.c diff --git a/tests/test-stack.c b/tests/test-stack.c new file mode 100644 index 000000000..dbf4e19a3 --- /dev/null +++ b/tests/test-stack.c @@ -0,0 +1,74 @@ +/* Test of the type-safe stack data type. + Copyright (C) 2020 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Written by Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>, 2020. */ + +#include <config.h> + +#include <stdbool.h> +#include <stdlib.h> +#include <string.h> +#include "assure.h" +#include "xalloc.h" + +#include "macros.h" + +#define GL_STACK_ELEMENT int +#define GL_STACK_STORAGECLASS static +#include "stack.h" + +#define GL_STACK_ELEMENT const char * +#define GL_STACK_STORAGECLASS static +#define GL_STACK_NAME string_stack +#include "stack.h" + +int +main (void) +{ + stack_type int_stack; + stack_init (&int_stack); + ASSERT (stack_size (&int_stack) == 0); + ASSERT (stack_empty (&int_stack)); + stack_push (&int_stack, 0); + stack_push (&int_stack, 1); + stack_push (&int_stack, 2); + stack_push (&int_stack, 3); + stack_push (&int_stack, 4); + stack_push (&int_stack, 5); + stack_push (&int_stack, 6); + stack_push (&int_stack, 7); + stack_push (&int_stack, 8); + stack_push (&int_stack, 9); + ASSERT (stack_size (&int_stack) == 10); + ASSERT (!stack_empty (&int_stack)); + ASSERT (stack_top (&int_stack) == 9); + ASSERT (stack_size (&int_stack) == 10); + ASSERT (stack_pop (&int_stack) == 9); + ASSERT (stack_size (&int_stack) == 9); + stack_discard (&int_stack); + ASSERT (stack_size (&int_stack) == 8); + ASSERT (stack_top (&int_stack) == 7); + stack_destroy (&int_stack); + + string_stack_type string_stack [1]; + string_stack_init (string_stack); + string_stack_push (string_stack, "foo"); + ASSERT (STREQ (string_stack_pop (string_stack), "foo")); + ASSERT (string_stack_empty (string_stack)); + string_stack_destroy (string_stack); + + return EXIT_SUCCESS; +} -- 2.25.1 ^ permalink raw reply related [flat|nested] 42+ messages in thread
* Re: stack module 2020-10-07 11:31 ` Marc Nieper-Wißkirchen @ 2020-10-10 14:06 ` Bruno Haible 2020-10-10 14:35 ` Marc Nieper-Wißkirchen 0 siblings, 1 reply; 42+ messages in thread From: Bruno Haible @ 2020-10-10 14:06 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Hi Marc, > please see the attached patch for the new module. Very nice. Looks all good, except for some nit-picking in the comments: > + Introspection: ELEMENT *base = stack_base (&stack); I would add a comment here: Where ELEMENT is the type to which GL_STACK_ELEMENT was defined when this file was included. (It would be tempting to write GL_STACK_ELEMENT *base = stack_base (&stack); but GL_STACK_ELEMENT is no longer defined after the file was included...) Other than that, please feel free to commit and push this. Thanks!! Bruno ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: stack module 2020-10-10 14:06 ` Bruno Haible @ 2020-10-10 14:35 ` Marc Nieper-Wißkirchen 2020-10-10 15:10 ` ChangeLog entries Bruno Haible 0 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-10-10 14:35 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, Am Sa., 10. Okt. 2020 um 16:06 Uhr schrieb Bruno Haible <bruno@clisp.org>: > > Hi Marc, > > > please see the attached patch for the new module. > > Very nice. Looks all good, except for some nit-picking in the comments: Thanks. > > > + Introspection: ELEMENT *base = stack_base (&stack); > > I would add a comment here: > Where ELEMENT is the type to which GL_STACK_ELEMENT was defined when > this file was included. > (It would be tempting to write > GL_STACK_ELEMENT *base = stack_base (&stack); > but GL_STACK_ELEMENT is no longer defined after the file was included...) I will add this comment. > Other than that, please feel free to commit and push this. Thanks!! I will do this as soon as I have been approved by Paul. (Do I have to do something about the ChangeLog entry or will it be auto-generated from my Git commit message?) Marc ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: ChangeLog entries 2020-10-10 14:35 ` Marc Nieper-Wißkirchen @ 2020-10-10 15:10 ` Bruno Haible 0 siblings, 0 replies; 42+ messages in thread From: Bruno Haible @ 2020-10-10 15:10 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Hi Marc, > (Do I have to > do something about the ChangeLog entry or will it be auto-generated > from my Git commit message?) The ChangeLog entries are not auto-generated, no. We want the ChangeLog entries to be essentially in sync with the git commits. This means, you typically prepare the ChangeLog entry and reuse it for the git commit. Or you prepare a git commit message (with line width <= 72) and use it in the ChangeLog entry. To avoid conflicts in ChangeLog during "git pull", I recomment to use the git-merge-changelog program (see the comments in lib/git-merge-changelog.c). Bruno ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 12:07 ` Bruno Haible 2020-05-02 12:49 ` Marc Nieper-Wißkirchen @ 2020-05-02 21:24 ` Bruno Haible 2020-05-03 11:14 ` Bruno Haible ` (2 more replies) 1 sibling, 3 replies; 42+ messages in thread From: Bruno Haible @ 2020-05-02 21:24 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib [-- Attachment #1: Type: text/plain, Size: 1380 bytes --] I wrote: > I should better revert yesterday's patch, and instead, > in the table show the guaranteed average performance > gl_list_get_first > gl_list_get_last > gl_list_set_first > gl_list_set_last > gl_list_remove_first > gl_list_remove_last > where these 6 functions are defined globally, not separately for each > implementation. Done through the two attached patches. 2020-05-02 Bruno Haible <bruno@clisp.org> 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 <bruno@clisp.org> 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. (gl_list_remove_first, gl_list_remove_last): Implement in a generic way. * lib/gl_array_list.c: Revert last change. * lib/gl_carray_list.c: Likewise. * lib/gl_anylinked_list2.h: Likewise. * lib/gl_linked_list.c: Likewise. * lib/gl_linkedhash_list.c: Likewise. * lib/gl_anytree_list2.h: Likewise. * lib/gl_avltree_list.c: Likewise. * lib/gl_avltreehash_list.c: Likewise. * lib/gl_rbtree_list.c: Likewise. * lib/gl_rbtreehash_list.c: Likewise. * lib/gl_sublist.c: Likewise. [-- Attachment #2: 0001-list-Remove-redundant-code-for-remove_first-and-remo.patch --] [-- Type: text/x-patch, Size: 12997 bytes --] From 3abe3e9a03a481163e4141e7defd30df051b42ca Mon Sep 17 00:00:00 2001 From: Bruno Haible <bruno@clisp.org> Date: Sat, 2 May 2020 21:14:29 +0200 Subject: [PATCH 1/2] 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. (gl_list_remove_first, gl_list_remove_last): Implement in a generic way. * lib/gl_array_list.c: Revert last change. * lib/gl_carray_list.c: Likewise. * lib/gl_anylinked_list2.h: Likewise. * lib/gl_linked_list.c: Likewise. * lib/gl_linkedhash_list.c: Likewise. * lib/gl_anytree_list2.h: Likewise. * lib/gl_avltree_list.c: Likewise. * lib/gl_avltreehash_list.c: Likewise. * lib/gl_rbtree_list.c: Likewise. * lib/gl_rbtreehash_list.c: Likewise. * lib/gl_sublist.c: Likewise. --- ChangeLog | 18 ++++++++++++++ lib/gl_anylinked_list2.h | 62 ----------------------------------------------- lib/gl_anytree_list2.h | 28 --------------------- lib/gl_array_list.c | 37 ---------------------------- lib/gl_avltree_list.c | 2 -- lib/gl_avltreehash_list.c | 2 -- lib/gl_carray_list.c | 40 ------------------------------ lib/gl_linked_list.c | 2 -- lib/gl_linkedhash_list.c | 2 -- lib/gl_list.h | 16 +++++++----- lib/gl_rbtree_list.c | 2 -- lib/gl_rbtreehash_list.c | 2 -- lib/gl_sublist.c | 18 -------------- 13 files changed, 28 insertions(+), 203 deletions(-) diff --git a/ChangeLog b/ChangeLog index 6c0f620..ac23544 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,23 @@ 2020-05-02 Bruno Haible <bruno@clisp.org> + 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. + (gl_list_remove_first, gl_list_remove_last): Implement in a generic way. + * lib/gl_array_list.c: Revert last change. + * lib/gl_carray_list.c: Likewise. + * lib/gl_anylinked_list2.h: Likewise. + * lib/gl_linked_list.c: Likewise. + * lib/gl_linkedhash_list.c: Likewise. + * lib/gl_anytree_list2.h: Likewise. + * lib/gl_avltree_list.c: Likewise. + * lib/gl_avltreehash_list.c: Likewise. + * lib/gl_rbtree_list.c: Likewise. + * lib/gl_rbtreehash_list.c: Likewise. + * lib/gl_sublist.c: Likewise. + +2020-05-02 Bruno Haible <bruno@clisp.org> + bison-i18n: Add support for cross-compilation. Reported by Hongxu Jia <hongxu.jia@windriver.com> in <https://lists.gnu.org/archive/html/bison-patches/2016-02/msg00000.html> diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h index 0032dc8..114106c 100644 --- a/lib/gl_anylinked_list2.h +++ b/lib/gl_anylinked_list2.h @@ -882,68 +882,6 @@ gl_linked_remove_at (gl_list_t list, size_t position) } static bool -gl_linked_remove_first (gl_list_t list) -{ - size_t count = list->count; - gl_list_node_t removed_node; - - if (count == 0) - return false; - /* Here we know count > 0. */ - /* Like gl_linked_remove_at (list, 0). */ - { - gl_list_node_t node; - gl_list_node_t after_removed; - - node = &list->root; - removed_node = node->next; - after_removed = node->next->next; - ASYNCSAFE(gl_list_node_t) node->next = after_removed; - after_removed->prev = node; - } -#if WITH_HASHTABLE - remove_from_bucket (list, removed_node); -#endif - list->count--; - - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (removed_node->value); - free (removed_node); - return true; -} - -static bool -gl_linked_remove_last (gl_list_t list) -{ - size_t count = list->count; - gl_list_node_t removed_node; - - if (count == 0) - return false; - /* Here we know count > 0. */ - /* Like gl_linked_remove_at (list, count - 1). */ - { - gl_list_node_t node; - gl_list_node_t before_removed; - - node = &list->root; - removed_node = node->prev; - before_removed = node->prev->prev; - node->prev = before_removed; - ASYNCSAFE(gl_list_node_t) before_removed->next = node; - } -#if WITH_HASHTABLE - remove_from_bucket (list, removed_node); -#endif - list->count--; - - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (removed_node->value); - free (removed_node); - return true; -} - -static bool gl_linked_remove (gl_list_t list, const void *elt) { gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt); diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h index 41e41dd..c5a67db 100644 --- a/lib/gl_anytree_list2.h +++ b/lib/gl_anytree_list2.h @@ -486,34 +486,6 @@ gl_tree_remove_at (gl_list_t list, size_t position) } static bool -gl_tree_remove_first (gl_list_t list) -{ - gl_list_node_t node = list->root; - - if (node != NULL) - { - node = node_at (node, 0); - return gl_tree_remove_node (list, node); - } - else - return false; -} - -static bool -gl_tree_remove_last (gl_list_t list) -{ - gl_list_node_t node = list->root; - - if (node != NULL) - { - node = node_at (node, node->branch_size - 1); - return gl_tree_remove_node (list, node); - } - else - return false; -} - -static bool gl_tree_remove (gl_list_t list, const void *elt) { if (list->root != NULL) diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c index e00255c..4950962 100644 --- a/lib/gl_array_list.c +++ b/lib/gl_array_list.c @@ -406,41 +406,6 @@ gl_array_remove_at (gl_list_t list, size_t position) } static bool -gl_array_remove_first (gl_list_t list) -{ - size_t count = list->count; - const void **elements; - size_t i; - - if (count == 0) - return false; - /* Like gl_array_remove_at (list, 0). */ - elements = list->elements; - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (elements[0]); - for (i = 1; i < count; i++) - elements[i - 1] = elements[i]; - list->count = count - 1; - return true; -} - -static bool -gl_array_remove_last (gl_list_t list) -{ - size_t count = list->count; - const void **elements; - - if (count == 0) - return false; - /* Like gl_array_remove_at (list, count - 1). */ - elements = list->elements; - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (elements[count - 1]); - list->count = count - 1; - return true; -} - -static bool gl_array_remove (gl_list_t list, const void *elt) { size_t position = gl_array_indexof_from_to (list, 0, list->count, elt); @@ -697,8 +662,6 @@ const struct gl_list_implementation gl_array_list_implementation = gl_array_nx_add_at, gl_array_remove_node, gl_array_remove_at, - gl_array_remove_first, - gl_array_remove_last, gl_array_remove, gl_array_list_free, gl_array_iterator, diff --git a/lib/gl_avltree_list.c b/lib/gl_avltree_list.c index 2906f5a..35ffec6 100644 --- a/lib/gl_avltree_list.c +++ b/lib/gl_avltree_list.c @@ -89,8 +89,6 @@ const struct gl_list_implementation gl_avltree_list_implementation = gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, - gl_tree_remove_first, - gl_tree_remove_last, gl_tree_remove, gl_tree_list_free, gl_tree_iterator, diff --git a/lib/gl_avltreehash_list.c b/lib/gl_avltreehash_list.c index 576f533..9f795ff 100644 --- a/lib/gl_avltreehash_list.c +++ b/lib/gl_avltreehash_list.c @@ -111,8 +111,6 @@ const struct gl_list_implementation gl_avltreehash_list_implementation = gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, - gl_tree_remove_first, - gl_tree_remove_last, gl_tree_remove, gl_tree_list_free, gl_tree_iterator, diff --git a/lib/gl_carray_list.c b/lib/gl_carray_list.c index fa17d48..36a8773 100644 --- a/lib/gl_carray_list.c +++ b/lib/gl_carray_list.c @@ -545,44 +545,6 @@ gl_carray_remove_at (gl_list_t list, size_t position) } static bool -gl_carray_remove_first (gl_list_t list) -{ - size_t count = list->count; - size_t i0; - - if (count == 0) - return false; - /* Here we know count > 0. */ - /* Like gl_carray_remove_at (list, 0). */ - i0 = list->offset; - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (list->elements[i0]); - i0++; - list->offset = (i0 == list->allocated ? 0 : i0); - list->count = count - 1; - return true; -} - -static bool -gl_carray_remove_last (gl_list_t list) -{ - size_t count = list->count; - size_t i1; - - if (count == 0) - return false; - /* Here we know count > 0. */ - /* Like gl_carray_remove_at (list, count - 1). */ - i1 = list->offset + count - 1; - if (i1 >= list->allocated) - i1 -= list->allocated; - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (list->elements[i1]); - list->count = count - 1; - return true; -} - -static bool gl_carray_remove_node (gl_list_t list, gl_list_node_t node) { size_t count = list->count; @@ -893,8 +855,6 @@ const struct gl_list_implementation gl_carray_list_implementation = gl_carray_nx_add_at, gl_carray_remove_node, gl_carray_remove_at, - gl_carray_remove_first, - gl_carray_remove_last, gl_carray_remove, gl_carray_list_free, gl_carray_iterator, diff --git a/lib/gl_linked_list.c b/lib/gl_linked_list.c index e2bf526..b1391ce 100644 --- a/lib/gl_linked_list.c +++ b/lib/gl_linked_list.c @@ -49,8 +49,6 @@ const struct gl_list_implementation gl_linked_list_implementation = gl_linked_nx_add_at, gl_linked_remove_node, gl_linked_remove_at, - gl_linked_remove_first, - gl_linked_remove_last, gl_linked_remove, gl_linked_list_free, gl_linked_iterator, diff --git a/lib/gl_linkedhash_list.c b/lib/gl_linkedhash_list.c index 5ffc0ce..7c7f999 100644 --- a/lib/gl_linkedhash_list.c +++ b/lib/gl_linkedhash_list.c @@ -97,8 +97,6 @@ const struct gl_list_implementation gl_linkedhash_list_implementation = gl_linked_nx_add_at, gl_linked_remove_node, gl_linked_remove_at, - gl_linked_remove_first, - gl_linked_remove_last, gl_linked_remove, gl_linked_list_free, gl_linked_iterator, diff --git a/lib/gl_list.h b/lib/gl_list.h index ea5018d..8094006 100644 --- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -518,8 +518,6 @@ struct gl_list_implementation const void *elt); bool (*remove_node) (gl_list_t list, gl_list_node_t node); bool (*remove_at) (gl_list_t list, size_t position); - bool (*remove_first) (gl_list_t list); - bool (*remove_last) (gl_list_t list); bool (*remove_elt) (gl_list_t list, const void *elt); void (*list_free) (gl_list_t list); /* gl_list_iterator_t functions. */ @@ -762,15 +760,21 @@ gl_list_remove_at (gl_list_t list, size_t position) GL_LIST_INLINE bool gl_list_remove_first (gl_list_t list) { - return ((const struct gl_list_impl_base *) list)->vtable - ->remove_first (list); + size_t size = gl_list_size (list); + if (size > 0) + return gl_list_remove_at (list, 0); + else + return false; } GL_LIST_INLINE bool gl_list_remove_last (gl_list_t list) { - return ((const struct gl_list_impl_base *) list)->vtable - ->remove_last (list); + size_t size = gl_list_size (list); + if (size > 0) + return gl_list_remove_at (list, size - 1); + else + return false; } GL_LIST_INLINE bool diff --git a/lib/gl_rbtree_list.c b/lib/gl_rbtree_list.c index 6ae78c7..d79becf 100644 --- a/lib/gl_rbtree_list.c +++ b/lib/gl_rbtree_list.c @@ -87,8 +87,6 @@ const struct gl_list_implementation gl_rbtree_list_implementation = gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, - gl_tree_remove_first, - gl_tree_remove_last, gl_tree_remove, gl_tree_list_free, gl_tree_iterator, diff --git a/lib/gl_rbtreehash_list.c b/lib/gl_rbtreehash_list.c index b59b5f4..be2ee6f 100644 --- a/lib/gl_rbtreehash_list.c +++ b/lib/gl_rbtreehash_list.c @@ -112,8 +112,6 @@ const struct gl_list_implementation gl_rbtreehash_list_implementation = gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, - gl_tree_remove_first, - gl_tree_remove_last, gl_tree_remove, gl_tree_list_free, gl_tree_iterator, diff --git a/lib/gl_sublist.c b/lib/gl_sublist.c index 6e95c3b..e529a6b 100644 --- a/lib/gl_sublist.c +++ b/lib/gl_sublist.c @@ -259,22 +259,6 @@ gl_sublist_remove_at (gl_list_t list, size_t position) } static bool -gl_sublist_remove_first (gl_list_t list) -{ - if (list->end == list->start) - return false; - return gl_list_remove_at (list->whole, list->start); -} - -static bool -gl_sublist_remove_last (gl_list_t list) -{ - if (list->end == list->start) - return false; - return gl_list_remove_at (list->whole, list->end - 1); -} - -static bool gl_sublist_remove (gl_list_t list, const void *elt) { size_t position = @@ -440,8 +424,6 @@ static const struct gl_list_implementation gl_sublist_list_implementation = gl_sublist_nx_add_at, gl_sublist_remove_node, gl_sublist_remove_at, - gl_sublist_remove_first, - gl_sublist_remove_last, gl_sublist_remove, gl_sublist_list_free, gl_sublist_iterator, -- 2.7.4 [-- Attachment #3: 0002-list-Add-get_first-get_last-set_first-set_last-opera.patch --] [-- Type: text/x-patch, Size: 7132 bytes --] From aaf24f107ae05afec56d797421aee7a287b051e9 Mon Sep 17 00:00:00 2001 From: Bruno Haible <bruno@clisp.org> 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 <bruno@clisp.org> + 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 <bruno@clisp.org> + 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 ^ permalink raw reply related [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible @ 2020-05-03 11:14 ` Bruno Haible 2020-05-05 8:37 ` Marc Nieper-Wißkirchen 2020-06-03 16:32 ` Marc Nieper-Wißkirchen 2 siblings, 0 replies; 42+ messages in thread From: Bruno Haible @ 2020-05-03 11:14 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib > Done through the two attached patches. And another patch, for the C++ interface. 2020-05-03 Bruno Haible <bruno@clisp.org> list-c++: Add get_first, get_last, set_first, set_last operations. * lib/gl_list.hh (class gl_List): Add methods get_first, get_last, set_first, set_last. * lib/gl_list.h: Tweak comments. diff --git a/lib/gl_list.h b/lib/gl_list.h index 7786092..dfec6d0 100644 --- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -215,11 +215,11 @@ extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node 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. */ + The 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. */ + The 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. @@ -237,8 +237,8 @@ extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position, ; /* Replaces the element at the first position in the list. - LIST must be non-empty. - Returns its node. */ + Returns its node. + The list must be non-empty. */ /* 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. */ @@ -249,8 +249,8 @@ extern gl_list_node_t gl_list_nx_set_first (gl_list_t list, const void *elt) ; /* Replaces the element at the last position in the list. - LIST must be non-empty. - Returns its node. */ + Returns its node. + The list must be non-empty. */ /* 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. */ diff --git a/lib/gl_list.hh b/lib/gl_list.hh index 2cc83be..b19bda7 100644 --- a/lib/gl_list.hh +++ b/lib/gl_list.hh @@ -137,6 +137,16 @@ public: ELTYPE * get_at (size_t position) const { return static_cast<ELTYPE *>(gl_list_get_at (_ptr, position)); } + /* Returns the element at the first position in the list. + The list must be non-empty. */ + ELTYPE * get_first () const + { return static_cast<ELTYPE *>(gl_list_get_first (_ptr)); } + + /* Returns the element at the last position in the list. + The list must be non-empty. */ + ELTYPE * get_last () const + { return static_cast<ELTYPE *>(gl_list_get_last (_ptr)); } + /* Searches whether an element is already in the list. Returns its node if found, or NULL if not present in the list. */ gl_list_node_t search (ELTYPE * elt) const @@ -183,6 +193,18 @@ public: gl_list_node_t set_at (size_t position, ELTYPE * elt) { return gl_list_set_at (_ptr, position, elt); } + /* Replaces the element at the first position in the list. + Returns its node. + The list must be non-empty. */ + gl_list_node_t set_first (ELTYPE * elt) + { return gl_list_set_first (_ptr, elt); } + + /* Replaces the element at the last position in the list. + Returns its node. + The list must be non-empty. */ + gl_list_node_t set_last (ELTYPE * elt) + { return gl_list_set_last (_ptr, elt); } + /* Adds an element as the first element of the list. Returns its node. */ gl_list_node_t add_first (ELTYPE * elt) ^ permalink raw reply related [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible 2020-05-03 11:14 ` Bruno Haible @ 2020-05-05 8:37 ` Marc Nieper-Wißkirchen 2020-05-08 17:28 ` Bruno Haible 2020-06-03 16:32 ` Marc Nieper-Wißkirchen 2 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-05-05 8:37 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, excellent; thank you very much! Just one note: The documentation needs to be updated in section 14.8 as well ([1]). So long, Marc [1] https://www.gnu.org/software/gnulib/manual/gnulib.html#Container-data-types Am Sa., 2. Mai 2020 um 23:24 Uhr schrieb Bruno Haible <bruno@clisp.org>: > > I wrote: > > I should better revert yesterday's patch, and instead, > > in the table show the guaranteed average performance > > gl_list_get_first > > gl_list_get_last > > gl_list_set_first > > gl_list_set_last > > gl_list_remove_first > > gl_list_remove_last > > where these 6 functions are defined globally, not separately for each > > implementation. > > Done through the two attached patches. > > 2020-05-02 Bruno Haible <bruno@clisp.org> > > 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 <bruno@clisp.org> > > 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. > (gl_list_remove_first, gl_list_remove_last): Implement in a generic way. > * lib/gl_array_list.c: Revert last change. > * lib/gl_carray_list.c: Likewise. > * lib/gl_anylinked_list2.h: Likewise. > * lib/gl_linked_list.c: Likewise. > * lib/gl_linkedhash_list.c: Likewise. > * lib/gl_anytree_list2.h: Likewise. > * lib/gl_avltree_list.c: Likewise. > * lib/gl_avltreehash_list.c: Likewise. > * lib/gl_rbtree_list.c: Likewise. > * lib/gl_rbtreehash_list.c: Likewise. > * lib/gl_sublist.c: Likewise. > ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-05 8:37 ` Marc Nieper-Wißkirchen @ 2020-05-08 17:28 ` Bruno Haible 0 siblings, 0 replies; 42+ messages in thread From: Bruno Haible @ 2020-05-08 17:28 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Hi Marc, > Just one note: The documentation needs to be updated in section 14.8 > as well ([1]). Right. Thank you for the reminder. Done through the patch below. Note that it can take a couple of months until the doc on www.gnu.org is updated; we don't push a doc update that frequently. 2020-05-08 Bruno Haible <bruno@clisp.org> list: Update documentation. Reported by Marc Nieper-Wißkirchen <marc.nieper+gnu@gmail.com> in <https://lists.gnu.org/archive/html/bug-gnulib/2020-05/msg00062.html>. * doc/containers.texi (Container data types): Document the new list operations and their complexity. diff --git a/doc/containers.texi b/doc/containers.texi index b3f154d..dd92529 100644 --- a/doc/containers.texi +++ b/doc/containers.texi @@ -160,6 +160,24 @@ for the ``sequential list'' data type are: @tab @math{O(n)} @tab @math{O(@log n)} @tab @math{O(@log n)} +@item @code{gl_list_get_first} +@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_last} +@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_set_at} @tab @math{O(1)} @tab @math{O(1)} @@ -169,6 +187,24 @@ for the ``sequential list'' data type are: @tab @math{O(n)} @tab @math{O((@log n)@mathopsup{2})} @tab @math{O(@log n)} +@item @code{gl_list_set_first} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O((@log n)@mathopsup{2})} +@tab @math{O(@log n)} +@item @code{gl_list_set_last} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O((@log n)@mathopsup{2})} +@tab @math{O(@log n)} @item @code{gl_list_search} @tab @math{O(n)} @tab @math{O(n)} @@ -286,6 +322,24 @@ for the ``sequential list'' data type are: @tab @math{O(n)} @tab @math{O((@log n)@mathopsup{2})} @tab @math{O(@log n)} +@item @code{gl_list_remove_first} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O((@log n)@mathopsup{2})} +@tab @math{O(@log n)} +@item @code{gl_list_remove_last} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O((@log n)@mathopsup{2})} +@tab @math{O(@log n)} @item @code{gl_list_remove} @tab @math{O(n)} @tab @math{O(n)} ^ permalink raw reply related [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible 2020-05-03 11:14 ` Bruno Haible 2020-05-05 8:37 ` Marc Nieper-Wißkirchen @ 2020-06-03 16:32 ` Marc Nieper-Wißkirchen 2020-06-03 21:08 ` Bruno Haible 2 siblings, 1 reply; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-06-03 16:32 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Hi Bruno, now that some operations together with their complexity for dealing with the end of the list have been added, what do you think of adding a reverse iterator? Thanks, Marc PS I've received a reply by the FSF; now I am waiting for the response by my university's lawyer. Am Sa., 2. Mai 2020 um 23:24 Uhr schrieb Bruno Haible <bruno@clisp.org>: > > I wrote: > > I should better revert yesterday's patch, and instead, > > in the table show the guaranteed average performance > > gl_list_get_first > > gl_list_get_last > > gl_list_set_first > > gl_list_set_last > > gl_list_remove_first > > gl_list_remove_last > > where these 6 functions are defined globally, not separately for each > > implementation. > > Done through the two attached patches. > > 2020-05-02 Bruno Haible <bruno@clisp.org> > > 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 <bruno@clisp.org> > > 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. > (gl_list_remove_first, gl_list_remove_last): Implement in a generic way. > * lib/gl_array_list.c: Revert last change. > * lib/gl_carray_list.c: Likewise. > * lib/gl_anylinked_list2.h: Likewise. > * lib/gl_linked_list.c: Likewise. > * lib/gl_linkedhash_list.c: Likewise. > * lib/gl_anytree_list2.h: Likewise. > * lib/gl_avltree_list.c: Likewise. > * lib/gl_avltreehash_list.c: Likewise. > * lib/gl_rbtree_list.c: Likewise. > * lib/gl_rbtreehash_list.c: Likewise. > * lib/gl_sublist.c: Likewise. > ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-06-03 16:32 ` Marc Nieper-Wißkirchen @ 2020-06-03 21:08 ` Bruno Haible 2020-06-03 21:22 ` Marc Nieper-Wißkirchen 0 siblings, 1 reply; 42+ messages in thread From: Bruno Haible @ 2020-06-03 21:08 UTC (permalink / raw) To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib Hi Marc, > now that some operations together with their complexity for dealing > with the end of the list have been added, what do you think of adding > a reverse iterator? Not a good idea, IMO. It's rarely used: In most cases, a list is either traversed one way or the other way. If a list going to be traversed in reverse order, the programmer can just keep it in opposite order and use the normal forward iterator. Or they can use an array (or an array-based list) and use indices. I find the amount of bloat in the C++ standard library horrible. In C at least, we can concentrate on the things that get used, not on the things that some rare programmer might find useful some day. Bruno ^ permalink raw reply [flat|nested] 42+ messages in thread
* Re: Add gl_list_remove_last to list/xlist 2020-06-03 21:08 ` Bruno Haible @ 2020-06-03 21:22 ` Marc Nieper-Wißkirchen 0 siblings, 0 replies; 42+ messages in thread From: Marc Nieper-Wißkirchen @ 2020-06-03 21:22 UTC (permalink / raw) To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib Am Mi., 3. Juni 2020 um 23:08 Uhr schrieb Bruno Haible <bruno@clisp.org>: > It's rarely used: In most cases, a list is either traversed one way or > the other way. One could say that a list that is to be transversed in both ways is a different abstract data type; nevertheless, they appear (e.g. lists of instructions in compiler analysis usually have to traversed in both ways). > If a list going to be traversed in reverse order, the programmer can just > keep it in opposite order and use the normal forward iterator. > Or they can use an array (or an array-based list) and use indices. For an array-based list, this is fine. For a general list, one could use gl_list_previous_node; however, one would have to keep a node of the last element (there's no gl_list_first_node/gl_list_last_node). > I find the amount of bloat in the C++ standard library horrible. In C > at least, we can concentrate on the things that get used, not on the > things that some rare programmer might find useful some day. I admit that there is some wisdom in these words. :) ^ permalink raw reply [flat|nested] 42+ messages in thread
end of thread, other threads:[~2020-10-10 15:11 UTC | newest] Thread overview: 42+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-04-28 7:08 Add gl_list_remove_last to list/xlist Marc Nieper-Wißkirchen 2020-05-02 0:07 ` Bruno Haible 2020-05-02 7:16 ` Marc Nieper-Wißkirchen 2020-05-02 12:07 ` Bruno Haible 2020-05-02 12:49 ` Marc Nieper-Wißkirchen 2020-05-02 15:49 ` Bruno Haible 2020-05-02 16:04 ` Marc Nieper-Wißkirchen 2020-05-22 15:59 ` Marc Nieper-Wißkirchen 2020-05-23 12:30 ` stack module Bruno Haible 2020-05-23 12:42 ` Marc Nieper-Wißkirchen 2020-05-23 14:02 ` Bruno Haible 2020-05-23 14:36 ` Marc Nieper-Wißkirchen 2020-05-23 15:39 ` Paul Eggert 2020-05-23 15:55 ` Marc Nieper-Wißkirchen 2020-05-23 16:44 ` Paul Eggert 2020-05-23 16:54 ` Marc Nieper-Wißkirchen 2020-05-23 17:33 ` Paul Eggert 2020-05-23 17:38 ` Marc Nieper-Wißkirchen 2020-05-23 20:51 ` Paul Eggert 2020-05-23 21:07 ` Marc Nieper-Wißkirchen 2020-05-23 22:06 ` Bruno Haible 2020-05-24 2:14 ` Paul Eggert 2020-05-24 8:17 ` Marc Nieper-Wißkirchen 2020-05-24 19:07 ` Paul Eggert 2020-05-24 19:26 ` Bruno Haible 2020-06-02 13:44 ` Marc Nieper-Wißkirchen 2020-05-23 17:19 ` Bruno Haible 2020-07-22 20:17 ` Marc Nieper-Wißkirchen 2020-07-23 10:36 ` Bruno Haible 2020-07-23 10:56 ` Marc Nieper-Wißkirchen 2020-10-07 9:01 ` Marc Nieper-Wißkirchen 2020-10-07 11:31 ` Marc Nieper-Wißkirchen 2020-10-10 14:06 ` Bruno Haible 2020-10-10 14:35 ` Marc Nieper-Wißkirchen 2020-10-10 15:10 ` ChangeLog entries Bruno Haible 2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible 2020-05-03 11:14 ` Bruno Haible 2020-05-05 8:37 ` Marc Nieper-Wißkirchen 2020-05-08 17:28 ` Bruno Haible 2020-06-03 16:32 ` Marc Nieper-Wißkirchen 2020-06-03 21:08 ` Bruno Haible 2020-06-03 21:22 ` Marc Nieper-Wißkirchen
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).