[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Add gl_list_remove_last to list/xlist
|
From: |
Marc Nieper-Wißkirchen |
|
Subject: |
Re: Add gl_list_remove_last to list/xlist |
|
Date: |
Sat, 2 May 2020 09:16:19 +0200 |
Hi Bruno,
thanks again very much!
Am Sa., 2. Mai 2020 um 02:07 Uhr schrieb Bruno Haible <address@hidden>:
>
> 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 <address@hidden>
>
> list: Add remove_first and remove_last operations.
> Suggested by Marc Nieper-Wißkirchen <address@hidden> 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);
>
- Re: Add gl_list_remove_last to list/xlist, Bruno Haible, 2020/05/01
- Re: Add gl_list_remove_last to list/xlist,
Marc Nieper-Wißkirchen <=
- Re: Add gl_list_remove_last to list/xlist, Bruno Haible, 2020/05/02
- Re: Add gl_list_remove_last to list/xlist, Marc Nieper-Wißkirchen, 2020/05/02
- Re: Add gl_list_remove_last to list/xlist, Bruno Haible, 2020/05/02
- Re: Add gl_list_remove_last to list/xlist, Marc Nieper-Wißkirchen, 2020/05/02
- Re: Add gl_list_remove_last to list/xlist, Marc Nieper-Wißkirchen, 2020/05/22
- Re: stack module, Bruno Haible, 2020/05/23
- Re: stack module, Marc Nieper-Wißkirchen, 2020/05/23
- Re: stack module, Bruno Haible, 2020/05/23
- Re: stack module, Marc Nieper-Wißkirchen, 2020/05/23
- Re: stack module, Paul Eggert, 2020/05/23