From 0ed596dfa4990aa25378bb09e4217f9f50f13973 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sat, 2 May 2020 01:56:17 +0200 Subject: [PATCH] list: Add remove_first and remove_last operations. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Suggested by Marc Nieper-Wißkirchen in . * 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. --- ChangeLog | 44 +++++++++++++++++++++++++ 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 | 26 +++++++++++++++ lib/gl_list.hh | 12 +++++++ lib/gl_rbtree_list.c | 2 ++ lib/gl_rbtreehash_list.c | 2 ++ lib/gl_sublist.c | 18 ++++++++++ tests/test-array_list.c | 26 ++++++++++++--- tests/test-avltree_list.c | 28 +++++++++++++--- tests/test-avltreehash_list.c | 28 +++++++++++++--- tests/test-carray_list.c | 28 +++++++++++++--- tests/test-linked_list.c | 28 +++++++++++++--- tests/test-linkedhash_list.c | 28 +++++++++++++--- tests/test-rbtree_list.c | 28 +++++++++++++--- tests/test-rbtreehash_list.c | 28 +++++++++++++--- 22 files changed, 461 insertions(+), 40 deletions(-) diff --git a/ChangeLog b/ChangeLog index 567aafa32f..033f3be48e 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,47 @@ +2020-05-01 Bruno Haible + + list: Add remove_first and remove_last operations. + Suggested by Marc Nieper-Wißkirchen in + . + * 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. + 2020-05-01 Bruno Haible parse-datetime: Fix a build failure with an older bison version. diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h index 114106c7dc..0032dc8826 100644 --- a/lib/gl_anylinked_list2.h +++ b/lib/gl_anylinked_list2.h @@ -881,6 +881,68 @@ gl_linked_remove_at (gl_list_t list, size_t position) return true; } +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) { diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h index c5a67dbd0c..41e41dd81b 100644 --- a/lib/gl_anytree_list2.h +++ b/lib/gl_anytree_list2.h @@ -485,6 +485,34 @@ gl_tree_remove_at (gl_list_t list, size_t position) return gl_tree_remove_node (list, node); } +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) { diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c index 49509620f7..e00255c724 100644 --- a/lib/gl_array_list.c +++ b/lib/gl_array_list.c @@ -405,6 +405,41 @@ gl_array_remove_at (gl_list_t list, size_t position) return true; } +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) { @@ -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 35ffec6f3c..2906f5a8ca 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 9f795ff864..576f5336a4 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 36a8773c35..fa17d48e6b 100644 --- a/lib/gl_carray_list.c +++ b/lib/gl_carray_list.c @@ -544,6 +544,44 @@ gl_carray_remove_at (gl_list_t list, size_t position) return true; } +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) { @@ -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 b1391cef9a..e2bf526d1a 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 7c7f999f87..5ffc0cef2f 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_list.h b/lib/gl_list.h index 39d14401f9..ea5018d34e 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. */ @@ -747,6 +759,20 @@ gl_list_remove_at (gl_list_t list, size_t position) ->remove_at (list, 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) { diff --git a/lib/gl_list.hh b/lib/gl_list.hh index f67c214477..2cc83be3a2 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_rbtree_list.c b/lib/gl_rbtree_list.c index d79becf4aa..6ae78c7fd8 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 be2ee6f4e9..b59b5f4877 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 e529a6b897..6e95c3b3ef 100644 --- a/lib/gl_sublist.c +++ b/lib/gl_sublist.c @@ -258,6 +258,22 @@ gl_sublist_remove_at (gl_list_t list, size_t position) return gl_list_remove_at (list->whole, list->start + 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) { @@ -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 158e72814c..f617787674 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 03ff024edc..b69816d705 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 806b0e37b2..6dcded4603 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 c97526685f..a6e9511a75 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 c139677fef..7c9954bbeb 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 921c62ccc2..7fa8b4f4b7 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 32d9d3206b..efd2cb18e7 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 949a6f4827..d6bbcb3b73 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); -- 2.39.5