Marc Nieper-Wißkirchen wrote:
> This is a feature request to add an operation
>
> extern gl_list_node_t gl_list_remove_last (gl_list_t list)
>
> to the list/xlist interface.
>
> This operation would remove the last element of the list and return
> the node of the previous element (or NULL if no element remained).
>
> There are at least two reasons why adding such an operation is meaningful:
>
> (1) It is a common operation if the list is used as a stack. Pushing
> will be gl_list_add_last, popping will be gl_list_remove_last.
>
> (2) The complexity of removing an arbitrary element in an ARRAY list
> is O(n). Removing the last element, however, is only O(1). With an
> explicit operation gl_list_remove_last, this can be documented in the
> table at the beginning of lib_gl_list.h.
I agree about point (2). It applies also the CARRAY and LINKED list types.
Similarly for gl_list_remove_first, which also have smaller complexity than
gl_list_remove_at for CARRAY and LINKED list types.
However, the return type cannot be gl_list_node_t, because for the LINKED
list type, that would be returning a pointer to already freed memory.
The return type cannot be 'const void *' either, because then it would not
be possible to distinguish a returned NULL element and a call on an
empty list - which would also return NULL.
So, the best possible return type here is 'bool'.
Implemented as follows. Thanks for the suggestion.
2020-05-01 Bruno Haible <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);
