Hi Bruno, thanks again very much!
Am Sa., 2. Mai 2020 um 02:07 Uhr schrieb Bruno Haible <br...@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 <br...@clisp.org> > > list: Add remove_first and remove_last operations. > Suggested by Marc Nieper-Wißkirchen <marc.nieper+...@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); >
