list: Add remove_first and remove_last operations.

Suggested by Marc Nieper-Wißkirchen <marc.nieper+gnu@gmail.com> in
<https://lists.gnu.org/archive/html/bug-gnulib/2020-04/msg00092.html>.

* lib/gl_list.h (struct gl_list_implementation): Add fields
remove_first, remove_last.
(gl_list_remove_first, gl_list_remove_last): New functions.
* lib/gl_array_list.c (gl_array_remove_first, gl_array_remove_last): New
functions, based on gl_array_remove_at.
(gl_array_list_implementation): Implement the new operations.
* lib/gl_carray_list.c (gl_carray_remove_first, gl_carray_remove_last):
New functions, based on gl_carray_remove_at.
(gl_carray_list_implementation): Implement the new operations.
* lib/gl_anylinked_list2.h (gl_linked_remove_first,
gl_linked_remove_last): New functions, based on gl_linked_remove_at.
* lib/gl_linked_list.c (gl_linked_list_implementation): Implement the
new operations.
* lib/gl_linkedhash_list.c (gl_linkedhash_list_implementation):
Likewise.
* lib/gl_anytree_list2.h (gl_tree_remove_first, gl_tree_remove_last):
New functions, based on gl_tree_remove_at.
* lib/gl_avltree_list.c (gl_avltree_list_implementation): Implement the
new operations.
* lib/gl_avltreehash_list.c (gl_avltreehash_list_implementation):
Likewise.
* lib/gl_rbtree_list.c (gl_rbtree_list_implementation): Likewise.
* lib/gl_rbtreehash_list.c (gl_rbtreehash_list_implementation):
Likewise.
* lib/gl_sublist.c (gl_sublist_remove_first, gl_sublist_remove_last):
New functions, based on gl_sublist_remove_at.
(gl_sublist_list_implementation): Implement the new operations.
* lib/gl_list.hh (class gl_List): Add methods remove_first,
remove_last.
* tests/test-array_list.c (main): Test also gl_list_remove_first and
gl_list_remove_last.
* tests/test-avltree_list.c (main): Likewise.
* tests/test-avltreehash_list.c (main): Likewise.
* tests/test-carray_list.c (main): Likewise.
* tests/test-linked_list.c (main): Likewise.
* tests/test-linkedhash_list.c (main): Likewise.
* tests/test-rbtree_list.c (main): Likewise.
* tests/test-rbtreehash_list.c (main): Likewise.

1 files changed, 62 insertions, 0 deletions

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
@@ -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);