* Re: ChangeLog entries
2016-11-21 20:24 ` Pedro Alves
@ 2016-11-21 23:34 ` Bruno Haible
0 siblings, 0 replies; 43+ messages in thread
From: Bruno Haible @ 2016-11-21 23:34 UTC (permalink / raw)
To: Pedro Alves; +Cc: bug-gnulib
Pedro Alves wrote:
> > I added ChangeLog entries for your two patches from 2016-11-12
> > (that Paul committed).
>
> Thanks! Should I assume you're all using git-merge-changelog and
Yes, we are all using the git-merge-changelog. It handles about 60% of
the ChangeLog entry conflicts correctly. (A couple of years ago, it
handled 95% of such conflicts correctly. I guess something in the git
internals has changed...)
> include ChangeLog changes in the diff as well as in the
> commit log?
Yes, this is how we all do it when we commit a patch.
When a contributor sends in a patch, the person who pushes it on behalf
of the author takes care of doing the right thing.
Many of us also use vc-dwim: It makes it less tedious to create the detailed
ChangeLog entry.
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
* Add gl_list_remove_last to list/xlist
@ 2020-04-28 7:08 Marc Nieper-Wißkirchen
2020-05-02 0:07 ` Bruno Haible
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-04-28 7:08 UTC (permalink / raw)
To: bug-gnulib
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.
Thanks,
Marc
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-04-28 7:08 Add gl_list_remove_last to list/xlist Marc Nieper-Wißkirchen
@ 2020-05-02 0:07 ` Bruno Haible
2020-05-02 7:16 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 43+ messages in thread
From: Bruno Haible @ 2020-05-02 0:07 UTC (permalink / raw)
To: bug-gnulib; +Cc: Marc Nieper-Wißkirchen
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 <bruno@clisp.org>
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.
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);
^ permalink raw reply related [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 0:07 ` Bruno Haible
@ 2020-05-02 7:16 ` Marc Nieper-Wißkirchen
2020-05-02 12:07 ` Bruno Haible
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-02 7:16 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
thanks again very much!
Am Sa., 2. Mai 2020 um 02:07 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> Marc Nieper-Wißkirchen wrote:
> > This is a feature request to add an operation
> >
> > extern gl_list_node_t gl_list_remove_last (gl_list_t list)
> >
> > to the list/xlist interface.
> >
> > This operation would remove the last element of the list and return
> > the node of the previous element (or NULL if no element remained).
> >
> > There are at least two reasons why adding such an operation is meaningful:
> >
> > (1) It is a common operation if the list is used as a stack. Pushing
> > will be gl_list_add_last, popping will be gl_list_remove_last.
> >
> > (2) The complexity of removing an arbitrary element in an ARRAY list
> > is O(n). Removing the last element, however, is only O(1). With an
> > explicit operation gl_list_remove_last, this can be documented in the
> > table at the beginning of lib_gl_list.h.
>
> I agree about point (2). It applies also the CARRAY and LINKED list types.
>
> Similarly for gl_list_remove_first, which also have smaller complexity than
> gl_list_remove_at for CARRAY and LINKED list types.
>
> However, the return type cannot be gl_list_node_t, because for the LINKED
> list type, that would be returning a pointer to already freed memory.
Could you explain why it is so? I didn't mean that gl_list_remove_last
should return the just deleted node but the node of the element that
is now the last one (the respectively first one for
gl_list_remove_first) after the removal. If there is none (because the
list is empty after the removal), NULL would be returned. It would be
an error to apply gl_list_remove_last to an empty list.
The motivation behind my suggestion is to make it easy to implement a
stack (or a FIFO queue) with the gl_list interface. For this,
operations like gl_list_get_first and gl_list_get_last with guaranteed
O(1) behavior for a number of list implementations would also be nice.
>
> The return type cannot be 'const void *' either, because then it would not
> be possible to distinguish a returned NULL element and a call on an
> empty list - which would also return NULL.
>
> So, the best possible return type here is 'bool'.
>
> Implemented as follows. Thanks for the suggestion.
>
>
> 2020-05-01 Bruno Haible <bruno@clisp.org>
>
> 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.
>
> 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);
>
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 7:16 ` Marc Nieper-Wißkirchen
@ 2020-05-02 12:07 ` Bruno Haible
2020-05-02 12:49 ` Marc Nieper-Wißkirchen
2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible
0 siblings, 2 replies; 43+ messages in thread
From: Bruno Haible @ 2020-05-02 12:07 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Hi Marc,
> 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.
The gl_list_node_t type, in the 'list' interface so far, is used in
operations that work on a single position. Except for the functions
gl_list_next_node and gl_list_previous_node, which intentionally
walk from one node to a neighbour node. Having a function that
does an effect on the last element and returns the position of the
second-to-last element would be an invitation to incorrect coding.
Better keep the operations simple!
Also, I don't see why your proposed operation would be important to
have in a general API for lists.
> The motivation behind my suggestion is to make it easy to implement a
> stack (or a FIFO queue) with the gl_list interface.
It is already easy to implement a stack or FIFO using the primitives.
E.g. stack_pop =
1. gl_list_get_at (list, gl_list_size (list) - 1)
2. gl_list_remove_at (list, gl_list_size (list) - 1) or
gl_list_remove_last (list).
It would be a mistake to add semantics of stack or FIFO directly to the
list interface, because a list *is* not a stack or a FIFO; a list *can
be used to implement* a stack or a FIFO. It is an important concept
that one interface can be used to implement another interface (->
layered software, hiding implementation details, etc.).
See e.g. in Java: they have different interfaces for list [1], stack [2],
and FIFO [2]. Initially, they defined Stack as a subclass of AbstractList,
but realized later that it was a mistake.
You are welcome to add a stack or FIFO module in gnulib. Most likely,
each of the two will only have a single implementation. Why? Because
- for stacks, the ARRAY and LINKED implementations would have the
same O() complexity for each operation, and then ARRAY would be
preferred because it is more efficient regarding use of memory
and L1/L2 caches,
- for FIFOs, the CARRAY and LINKED implementations would have the
same O() complexity for each operation, and similarly CARRAY would
be preferred because it is more efficient regarding use of memory
and L1/L2 caches.
> 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.
Hmm. I'm reluctant to introduce 4 new functions
gl_list_get_first
gl_list_get_last
gl_list_set_first
gl_list_set_last
when the gl_list_get/gl_list_set operations with appropriate position
argument already do the job. It appears to be more of a documentation
issue, right? I.e. I should better revert yesterday's patch, and instead,
in the table show the guaranteed average performance
gl_list_get_first
gl_list_get_last
gl_list_set_first
gl_list_set_last
gl_list_remove_first
gl_list_remove_last
where these 6 functions are defined globally, not separately for each
implementation.
Bruno
[1] https://docs.oracle.com/javase/8/docs/api/java/util/AbstractList.html
[2] https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 12:07 ` Bruno Haible
@ 2020-05-02 12:49 ` Marc Nieper-Wißkirchen
2020-05-02 15:49 ` Bruno Haible
2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible
1 sibling, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-02 12:49 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
[...]
> The gl_list_node_t type, in the 'list' interface so far, is used in
> operations that work on a single position. Except for the functions
> gl_list_next_node and gl_list_previous_node, which intentionally
> walk from one node to a neighbour node. Having a function that
> does an effect on the last element and returns the position of the
> second-to-last element would be an invitation to incorrect coding.
> Better keep the operations simple!
That's a fair point of view.
[...]
> > The motivation behind my suggestion is to make it easy to implement a
> > stack (or a FIFO queue) with the gl_list interface.
>
> It is already easy to implement a stack or FIFO using the primitives.
> E.g. stack_pop =
> 1. gl_list_get_at (list, gl_list_size (list) - 1)
> 2. gl_list_remove_at (list, gl_list_size (list) - 1) or
> gl_list_remove_last (list).
>
> It would be a mistake to add semantics of stack or FIFO directly to the
> list interface, because a list *is* not a stack or a FIFO; a list *can
> be used to implement* a stack or a FIFO. It is an important concept
> that one interface can be used to implement another interface (->
> layered software, hiding implementation details, etc.).
Okay; I agree that a separate stack or FIFO module can make more
sense; in particular when it only has to deal with a single
implementation of an underlying data structure. At the moment I do
have other work to finish first, but maybe I will find some time in
the near future for a stack module.
[...]
> > 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.
>
> Hmm. I'm reluctant to introduce 4 new functions
> gl_list_get_first
> gl_list_get_last
> gl_list_set_first
> gl_list_set_last
> when the gl_list_get/gl_list_set operations with appropriate position
> argument already do the job. It appears to be more of a documentation
> issue, right? I.e. I should better revert yesterday's patch, and instead,
> in the table show the guaranteed average performance
> gl_list_get_first
> gl_list_get_last
> gl_list_set_first
> gl_list_set_last
> gl_list_remove_first
> gl_list_remove_last
> where these 6 functions are defined globally, not separately for each
> implementation.
When the functions can be defined globally, that's better than adding
six functions to each vtable. Partly, it is just a documentation
issue. I don't see, however, to implement the function dealing with
end of the list in O(1) behavior when the underlying data structure is
a linked list. Don't we need to expose an implementation-dependent
gl_list_get_last_node (gl_list_first_node for symmetry)? The rest
should then be implementable easily.
Marc
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 12:49 ` Marc Nieper-Wißkirchen
@ 2020-05-02 15:49 ` Bruno Haible
2020-05-02 16:04 ` Marc Nieper-Wißkirchen
2020-05-22 15:59 ` Marc Nieper-Wißkirchen
0 siblings, 2 replies; 43+ messages in thread
From: Bruno Haible @ 2020-05-02 15:49 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Hi Marc,
> Okay; I agree that a separate stack or FIFO module can make more
> sense; in particular when it only has to deal with a single
> implementation of an underlying data structure. At the moment I do
> have other work to finish first, but maybe I will find some time in
> the near future for a stack module.
Good! When you come to it, please consider our "Contributing to Gnulib" tips:
<https://www.gnu.org/software/gnulib/manual/html_node/Contributing-to-Gnulib.html>.
> I don't see, however, to implement the function dealing with
> end of the list in O(1) behavior when the underlying data structure is
> a linked list.
The LINKED list implementation is a doubly-linked list, and the functions
get_at, set_at, or remove_at are implemented like this:
If position < length/2 then
walk from the start of the list (O(position))
else
walk from the end of the list (O(length-position)).
So, the original invocation
gl_list_remove_at (list, gl_list_size (list) - 1)
already does the job in O(1).
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 15:49 ` Bruno Haible
@ 2020-05-02 16:04 ` Marc Nieper-Wißkirchen
2020-05-22 15:59 ` Marc Nieper-Wißkirchen
1 sibling, 0 replies; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-02 16:04 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
[...]
> > I don't see, however, to implement the function dealing with
> > end of the list in O(1) behavior when the underlying data structure is
> > a linked list.
>
> The LINKED list implementation is a doubly-linked list, and the functions
> get_at, set_at, or remove_at are implemented like this:
> If position < length/2 then
> walk from the start of the list (O(position))
> else
> walk from the end of the list (O(length-position)).
>
> So, the original invocation
> gl_list_remove_at (list, gl_list_size (list) - 1)
> already does the job in O(1).
Great. (Now that you say it I think I have once looked into the code
but forgotten the details.) It would be nice if this could be
documented. In any case, the general six functions we discussed should
then be possible without any implementation-specifics.
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 12:07 ` Bruno Haible
2020-05-02 12:49 ` Marc Nieper-Wißkirchen
@ 2020-05-02 21:24 ` Bruno Haible
2020-05-03 11:14 ` Bruno Haible
` (2 more replies)
1 sibling, 3 replies; 43+ messages in thread
From: Bruno Haible @ 2020-05-02 21:24 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
[-- Attachment #1: Type: text/plain, Size: 1380 bytes --]
I wrote:
> I should better revert yesterday's patch, and instead,
> in the table show the guaranteed average performance
> gl_list_get_first
> gl_list_get_last
> gl_list_set_first
> gl_list_set_last
> gl_list_remove_first
> gl_list_remove_last
> where these 6 functions are defined globally, not separately for each
> implementation.
Done through the two attached patches.
2020-05-02 Bruno Haible <bruno@clisp.org>
list: Add get_first, get_last, set_first, set_last operations.
* lib/gl_list.h (gl_list_get_first, gl_list_get_last,
gl_list_nx_set_first, gl_list_nx_set_last): New functions.
* lib/gl_xlist.h (gl_list_set_first, gl_list_set_last): New functions.
2020-05-02 Bruno Haible <bruno@clisp.org>
list: Remove redundant code for remove_first and remove_last operations.
* lib/gl_list.h (struct gl_list_implementation): Remove fields
remove_first, remove_last.
(gl_list_remove_first, gl_list_remove_last): Implement in a generic way.
* lib/gl_array_list.c: Revert last change.
* lib/gl_carray_list.c: Likewise.
* lib/gl_anylinked_list2.h: Likewise.
* lib/gl_linked_list.c: Likewise.
* lib/gl_linkedhash_list.c: Likewise.
* lib/gl_anytree_list2.h: Likewise.
* lib/gl_avltree_list.c: Likewise.
* lib/gl_avltreehash_list.c: Likewise.
* lib/gl_rbtree_list.c: Likewise.
* lib/gl_rbtreehash_list.c: Likewise.
* lib/gl_sublist.c: Likewise.
[-- Attachment #2: 0001-list-Remove-redundant-code-for-remove_first-and-remo.patch --]
[-- Type: text/x-patch, Size: 12997 bytes --]
From 3abe3e9a03a481163e4141e7defd30df051b42ca Mon Sep 17 00:00:00 2001
From: Bruno Haible <bruno@clisp.org>
Date: Sat, 2 May 2020 21:14:29 +0200
Subject: [PATCH 1/2] list: Remove redundant code for remove_first and
remove_last operations.
* lib/gl_list.h (struct gl_list_implementation): Remove fields
remove_first, remove_last.
(gl_list_remove_first, gl_list_remove_last): Implement in a generic way.
* lib/gl_array_list.c: Revert last change.
* lib/gl_carray_list.c: Likewise.
* lib/gl_anylinked_list2.h: Likewise.
* lib/gl_linked_list.c: Likewise.
* lib/gl_linkedhash_list.c: Likewise.
* lib/gl_anytree_list2.h: Likewise.
* lib/gl_avltree_list.c: Likewise.
* lib/gl_avltreehash_list.c: Likewise.
* lib/gl_rbtree_list.c: Likewise.
* lib/gl_rbtreehash_list.c: Likewise.
* lib/gl_sublist.c: Likewise.
---
ChangeLog | 18 ++++++++++++++
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 | 16 +++++++-----
lib/gl_rbtree_list.c | 2 --
lib/gl_rbtreehash_list.c | 2 --
lib/gl_sublist.c | 18 --------------
13 files changed, 28 insertions(+), 203 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 6c0f620..ac23544 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,23 @@
2020-05-02 Bruno Haible <bruno@clisp.org>
+ list: Remove redundant code for remove_first and remove_last operations.
+ * lib/gl_list.h (struct gl_list_implementation): Remove fields
+ remove_first, remove_last.
+ (gl_list_remove_first, gl_list_remove_last): Implement in a generic way.
+ * lib/gl_array_list.c: Revert last change.
+ * lib/gl_carray_list.c: Likewise.
+ * lib/gl_anylinked_list2.h: Likewise.
+ * lib/gl_linked_list.c: Likewise.
+ * lib/gl_linkedhash_list.c: Likewise.
+ * lib/gl_anytree_list2.h: Likewise.
+ * lib/gl_avltree_list.c: Likewise.
+ * lib/gl_avltreehash_list.c: Likewise.
+ * lib/gl_rbtree_list.c: Likewise.
+ * lib/gl_rbtreehash_list.c: Likewise.
+ * lib/gl_sublist.c: Likewise.
+
+2020-05-02 Bruno Haible <bruno@clisp.org>
+
bison-i18n: Add support for cross-compilation.
Reported by Hongxu Jia <hongxu.jia@windriver.com> in
<https://lists.gnu.org/archive/html/bison-patches/2016-02/msg00000.html>
diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h
index 0032dc8..114106c 100644
--- a/lib/gl_anylinked_list2.h
+++ b/lib/gl_anylinked_list2.h
@@ -882,68 +882,6 @@ 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 41e41dd..c5a67db 100644
--- a/lib/gl_anytree_list2.h
+++ b/lib/gl_anytree_list2.h
@@ -486,34 +486,6 @@ 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 e00255c..4950962 100644
--- a/lib/gl_array_list.c
+++ b/lib/gl_array_list.c
@@ -406,41 +406,6 @@ 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);
@@ -697,8 +662,6 @@ 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 2906f5a..35ffec6 100644
--- a/lib/gl_avltree_list.c
+++ b/lib/gl_avltree_list.c
@@ -89,8 +89,6 @@ 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 576f533..9f795ff 100644
--- a/lib/gl_avltreehash_list.c
+++ b/lib/gl_avltreehash_list.c
@@ -111,8 +111,6 @@ 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 fa17d48..36a8773 100644
--- a/lib/gl_carray_list.c
+++ b/lib/gl_carray_list.c
@@ -545,44 +545,6 @@ 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;
@@ -893,8 +855,6 @@ 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 e2bf526..b1391ce 100644
--- a/lib/gl_linked_list.c
+++ b/lib/gl_linked_list.c
@@ -49,8 +49,6 @@ 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 5ffc0ce..7c7f999 100644
--- a/lib/gl_linkedhash_list.c
+++ b/lib/gl_linkedhash_list.c
@@ -97,8 +97,6 @@ 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 ea5018d..8094006 100644
--- a/lib/gl_list.h
+++ b/lib/gl_list.h
@@ -518,8 +518,6 @@ 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. */
@@ -762,15 +760,21 @@ 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);
+ size_t size = gl_list_size (list);
+ if (size > 0)
+ return gl_list_remove_at (list, 0);
+ else
+ return false;
}
GL_LIST_INLINE bool
gl_list_remove_last (gl_list_t list)
{
- return ((const struct gl_list_impl_base *) list)->vtable
- ->remove_last (list);
+ size_t size = gl_list_size (list);
+ if (size > 0)
+ return gl_list_remove_at (list, size - 1);
+ else
+ return false;
}
GL_LIST_INLINE bool
diff --git a/lib/gl_rbtree_list.c b/lib/gl_rbtree_list.c
index 6ae78c7..d79becf 100644
--- a/lib/gl_rbtree_list.c
+++ b/lib/gl_rbtree_list.c
@@ -87,8 +87,6 @@ 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 b59b5f4..be2ee6f 100644
--- a/lib/gl_rbtreehash_list.c
+++ b/lib/gl_rbtreehash_list.c
@@ -112,8 +112,6 @@ 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 6e95c3b..e529a6b 100644
--- a/lib/gl_sublist.c
+++ b/lib/gl_sublist.c
@@ -259,22 +259,6 @@ 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 =
@@ -440,8 +424,6 @@ 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,
--
2.7.4
[-- Attachment #3: 0002-list-Add-get_first-get_last-set_first-set_last-opera.patch --]
[-- Type: text/x-patch, Size: 7132 bytes --]
From aaf24f107ae05afec56d797421aee7a287b051e9 Mon Sep 17 00:00:00 2001
From: Bruno Haible <bruno@clisp.org>
Date: Sat, 2 May 2020 23:21:00 +0200
Subject: [PATCH 2/2] list: Add get_first, get_last, set_first, set_last
operations.
* lib/gl_list.h (gl_list_get_first, gl_list_get_last,
gl_list_nx_set_first, gl_list_nx_set_last): New functions.
* lib/gl_xlist.h (gl_list_set_first, gl_list_set_last): New functions.
---
ChangeLog | 7 +++++++
lib/gl_list.h | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/gl_xlist.h | 20 ++++++++++++++++++
3 files changed, 93 insertions(+)
diff --git a/ChangeLog b/ChangeLog
index ac23544..0bf6ca0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
2020-05-02 Bruno Haible <bruno@clisp.org>
+ list: Add get_first, get_last, set_first, set_last operations.
+ * lib/gl_list.h (gl_list_get_first, gl_list_get_last,
+ gl_list_nx_set_first, gl_list_nx_set_last): New functions.
+ * lib/gl_xlist.h (gl_list_set_first, gl_list_set_last): New functions.
+
+2020-05-02 Bruno Haible <bruno@clisp.org>
+
list: Remove redundant code for remove_first and remove_last operations.
* lib/gl_list.h (struct gl_list_implementation): Remove fields
remove_first, remove_last.
diff --git a/lib/gl_list.h b/lib/gl_list.h
index 8094006..7786092 100644
--- a/lib/gl_list.h
+++ b/lib/gl_list.h
@@ -74,7 +74,11 @@ extern "C" {
gl_list_next_node O(1) O(1) O(log n) O(1) O(log n)
gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n)
gl_list_get_at O(1) O(n) O(log n) O(n) O(log n)
+ gl_list_get_first O(1) O(1) O(log n) O(1) O(log n)
+ gl_list_get_last O(1) O(1) O(log n) O(1) O(log n)
gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n)
+ gl_list_set_first O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
+ gl_list_set_last O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1)
gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
@@ -210,6 +214,14 @@ extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node
POSITION must be >= 0 and < gl_list_size (list). */
extern const void * gl_list_get_at (gl_list_t list, size_t position);
+/* Returns the element at the first position in the list.
+ LIST must be non-empty. */
+extern const void * gl_list_get_first (gl_list_t list);
+
+/* Returns the element at the last position in the list.
+ LIST must be non-empty. */
+extern const void * gl_list_get_last (gl_list_t list);
+
/* Replaces the element at a given position in the list.
POSITION must be >= 0 and < gl_list_size (list).
Returns its node. */
@@ -224,6 +236,30 @@ extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
#endif
;
+/* Replaces the element at the first position in the list.
+ LIST must be non-empty.
+ Returns its node. */
+/* declared in gl_xlist.h */
+extern gl_list_node_t gl_list_set_first (gl_list_t list, const void *elt);
+/* Likewise. Returns NULL upon out-of-memory. */
+extern gl_list_node_t gl_list_nx_set_first (gl_list_t list, const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
+/* Replaces the element at the last position in the list.
+ LIST must be non-empty.
+ Returns its node. */
+/* declared in gl_xlist.h */
+extern gl_list_node_t gl_list_set_last (gl_list_t list, const void *elt);
+/* Likewise. Returns NULL upon out-of-memory. */
+extern gl_list_node_t gl_list_nx_set_last (gl_list_t list, const void *elt)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+ ;
+
/* Searches whether an element is already in the list.
Returns its node if found, or NULL if not present in the list. */
extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
@@ -635,6 +671,18 @@ gl_list_get_at (gl_list_t list, size_t position)
->get_at (list, position);
}
+GL_LIST_INLINE const void *
+gl_list_get_first (gl_list_t list)
+{
+ return gl_list_get_at (list, 0);
+}
+
+GL_LIST_INLINE const void *
+gl_list_get_last (gl_list_t list)
+{
+ return gl_list_get_at (list, gl_list_size (list) - 1);
+}
+
GL_LIST_INLINE gl_list_node_t
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
__attribute__ ((__warn_unused_result__))
@@ -646,6 +694,24 @@ gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
}
GL_LIST_INLINE gl_list_node_t
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_list_nx_set_first (gl_list_t list, const void *elt)
+{
+ return gl_list_nx_set_at (list, 0, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+ __attribute__ ((__warn_unused_result__))
+#endif
+gl_list_nx_set_last (gl_list_t list, const void *elt)
+{
+ return gl_list_nx_set_at (list, gl_list_size (list) - 1, elt);
+}
+
+GL_LIST_INLINE gl_list_node_t
gl_list_search (gl_list_t list, const void *elt)
{
size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
diff --git a/lib/gl_xlist.h b/lib/gl_xlist.h
index ef6b93f..7bf9c23 100644
--- a/lib/gl_xlist.h
+++ b/lib/gl_xlist.h
@@ -52,6 +52,8 @@ extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
const void *elt);
extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
const void *elt);
+extern gl_list_node_t gl_list_set_first (gl_list_t list, const void *elt);
+extern gl_list_node_t gl_list_set_last (gl_list_t list, const void *elt);
extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
@@ -114,6 +116,24 @@ gl_list_set_at (gl_list_t list, size_t position, const void *elt)
}
GL_XLIST_INLINE gl_list_node_t
+gl_list_set_first (gl_list_t list, const void *elt)
+{
+ gl_list_node_t result = gl_list_nx_set_first (list, elt);
+ if (result == NULL)
+ xalloc_die ();
+ return result;
+}
+
+GL_XLIST_INLINE gl_list_node_t
+gl_list_set_last (gl_list_t list, const void *elt)
+{
+ gl_list_node_t result = gl_list_nx_set_last (list, elt);
+ if (result == NULL)
+ xalloc_die ();
+ return result;
+}
+
+GL_XLIST_INLINE gl_list_node_t
gl_list_add_first (gl_list_t list, const void *elt)
{
gl_list_node_t result = gl_list_nx_add_first (list, elt);
--
2.7.4
^ permalink raw reply related [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible
@ 2020-05-03 11:14 ` Bruno Haible
2020-05-05 8:37 ` Marc Nieper-Wißkirchen
2020-06-03 16:32 ` Marc Nieper-Wißkirchen
2 siblings, 0 replies; 43+ messages in thread
From: Bruno Haible @ 2020-05-03 11:14 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
> Done through the two attached patches.
And another patch, for the C++ interface.
2020-05-03 Bruno Haible <bruno@clisp.org>
list-c++: Add get_first, get_last, set_first, set_last operations.
* lib/gl_list.hh (class gl_List): Add methods get_first, get_last,
set_first, set_last.
* lib/gl_list.h: Tweak comments.
diff --git a/lib/gl_list.h b/lib/gl_list.h
index 7786092..dfec6d0 100644
--- a/lib/gl_list.h
+++ b/lib/gl_list.h
@@ -215,11 +215,11 @@ extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node
extern const void * gl_list_get_at (gl_list_t list, size_t position);
/* Returns the element at the first position in the list.
- LIST must be non-empty. */
+ The list must be non-empty. */
extern const void * gl_list_get_first (gl_list_t list);
/* Returns the element at the last position in the list.
- LIST must be non-empty. */
+ The list must be non-empty. */
extern const void * gl_list_get_last (gl_list_t list);
/* Replaces the element at a given position in the list.
@@ -237,8 +237,8 @@ extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
;
/* Replaces the element at the first position in the list.
- LIST must be non-empty.
- Returns its node. */
+ Returns its node.
+ The list must be non-empty. */
/* declared in gl_xlist.h */
extern gl_list_node_t gl_list_set_first (gl_list_t list, const void *elt);
/* Likewise. Returns NULL upon out-of-memory. */
@@ -249,8 +249,8 @@ extern gl_list_node_t gl_list_nx_set_first (gl_list_t list, const void *elt)
;
/* Replaces the element at the last position in the list.
- LIST must be non-empty.
- Returns its node. */
+ Returns its node.
+ The list must be non-empty. */
/* declared in gl_xlist.h */
extern gl_list_node_t gl_list_set_last (gl_list_t list, const void *elt);
/* Likewise. Returns NULL upon out-of-memory. */
diff --git a/lib/gl_list.hh b/lib/gl_list.hh
index 2cc83be..b19bda7 100644
--- a/lib/gl_list.hh
+++ b/lib/gl_list.hh
@@ -137,6 +137,16 @@ public:
ELTYPE * get_at (size_t position) const
{ return static_cast<ELTYPE *>(gl_list_get_at (_ptr, position)); }
+ /* Returns the element at the first position in the list.
+ The list must be non-empty. */
+ ELTYPE * get_first () const
+ { return static_cast<ELTYPE *>(gl_list_get_first (_ptr)); }
+
+ /* Returns the element at the last position in the list.
+ The list must be non-empty. */
+ ELTYPE * get_last () const
+ { return static_cast<ELTYPE *>(gl_list_get_last (_ptr)); }
+
/* Searches whether an element is already in the list.
Returns its node if found, or NULL if not present in the list. */
gl_list_node_t search (ELTYPE * elt) const
@@ -183,6 +193,18 @@ public:
gl_list_node_t set_at (size_t position, ELTYPE * elt)
{ return gl_list_set_at (_ptr, position, elt); }
+ /* Replaces the element at the first position in the list.
+ Returns its node.
+ The list must be non-empty. */
+ gl_list_node_t set_first (ELTYPE * elt)
+ { return gl_list_set_first (_ptr, elt); }
+
+ /* Replaces the element at the last position in the list.
+ Returns its node.
+ The list must be non-empty. */
+ gl_list_node_t set_last (ELTYPE * elt)
+ { return gl_list_set_last (_ptr, elt); }
+
/* Adds an element as the first element of the list.
Returns its node. */
gl_list_node_t add_first (ELTYPE * elt)
^ permalink raw reply related [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible
2020-05-03 11:14 ` Bruno Haible
@ 2020-05-05 8:37 ` Marc Nieper-Wißkirchen
2020-05-08 17:28 ` Bruno Haible
2020-06-03 16:32 ` Marc Nieper-Wißkirchen
2 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-05 8:37 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
excellent; thank you very much!
Just one note: The documentation needs to be updated in section 14.8
as well ([1]).
So long,
Marc
[1] https://www.gnu.org/software/gnulib/manual/gnulib.html#Container-data-types
Am Sa., 2. Mai 2020 um 23:24 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> I wrote:
> > I should better revert yesterday's patch, and instead,
> > in the table show the guaranteed average performance
> > gl_list_get_first
> > gl_list_get_last
> > gl_list_set_first
> > gl_list_set_last
> > gl_list_remove_first
> > gl_list_remove_last
> > where these 6 functions are defined globally, not separately for each
> > implementation.
>
> Done through the two attached patches.
>
> 2020-05-02 Bruno Haible <bruno@clisp.org>
>
> list: Add get_first, get_last, set_first, set_last operations.
> * lib/gl_list.h (gl_list_get_first, gl_list_get_last,
> gl_list_nx_set_first, gl_list_nx_set_last): New functions.
> * lib/gl_xlist.h (gl_list_set_first, gl_list_set_last): New functions.
>
> 2020-05-02 Bruno Haible <bruno@clisp.org>
>
> list: Remove redundant code for remove_first and remove_last operations.
> * lib/gl_list.h (struct gl_list_implementation): Remove fields
> remove_first, remove_last.
> (gl_list_remove_first, gl_list_remove_last): Implement in a generic way.
> * lib/gl_array_list.c: Revert last change.
> * lib/gl_carray_list.c: Likewise.
> * lib/gl_anylinked_list2.h: Likewise.
> * lib/gl_linked_list.c: Likewise.
> * lib/gl_linkedhash_list.c: Likewise.
> * lib/gl_anytree_list2.h: Likewise.
> * lib/gl_avltree_list.c: Likewise.
> * lib/gl_avltreehash_list.c: Likewise.
> * lib/gl_rbtree_list.c: Likewise.
> * lib/gl_rbtreehash_list.c: Likewise.
> * lib/gl_sublist.c: Likewise.
>
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-05 8:37 ` Marc Nieper-Wißkirchen
@ 2020-05-08 17:28 ` Bruno Haible
0 siblings, 0 replies; 43+ messages in thread
From: Bruno Haible @ 2020-05-08 17:28 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Hi Marc,
> Just one note: The documentation needs to be updated in section 14.8
> as well ([1]).
Right. Thank you for the reminder. Done through the patch below. Note that
it can take a couple of months until the doc on www.gnu.org is updated; we
don't push a doc update that frequently.
2020-05-08 Bruno Haible <bruno@clisp.org>
list: Update documentation.
Reported by Marc Nieper-Wißkirchen <marc.nieper+gnu@gmail.com> in
<https://lists.gnu.org/archive/html/bug-gnulib/2020-05/msg00062.html>.
* doc/containers.texi (Container data types): Document the new list
operations and their complexity.
diff --git a/doc/containers.texi b/doc/containers.texi
index b3f154d..dd92529 100644
--- a/doc/containers.texi
+++ b/doc/containers.texi
@@ -160,6 +160,24 @@ for the ``sequential list'' data type are:
@tab @math{O(n)}
@tab @math{O(@log n)}
@tab @math{O(@log n)}
+@item @code{gl_list_get_first}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(@log n)}
+@item @code{gl_list_get_last}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(@log n)}
@item @code{gl_list_set_at}
@tab @math{O(1)}
@tab @math{O(1)}
@@ -169,6 +187,24 @@ for the ``sequential list'' data type are:
@tab @math{O(n)}
@tab @math{O((@log n)@mathopsup{2})}
@tab @math{O(@log n)}
+@item @code{gl_list_set_first}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(n)}
+@tab @math{O(1)}
+@tab @math{O((@log n)@mathopsup{2})}
+@tab @math{O(@log n)}
+@item @code{gl_list_set_last}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(n)}
+@tab @math{O(1)}
+@tab @math{O((@log n)@mathopsup{2})}
+@tab @math{O(@log n)}
@item @code{gl_list_search}
@tab @math{O(n)}
@tab @math{O(n)}
@@ -286,6 +322,24 @@ for the ``sequential list'' data type are:
@tab @math{O(n)}
@tab @math{O((@log n)@mathopsup{2})}
@tab @math{O(@log n)}
+@item @code{gl_list_remove_first}
+@tab @math{O(n)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(n)}
+@tab @math{O(1)}
+@tab @math{O((@log n)@mathopsup{2})}
+@tab @math{O(@log n)}
+@item @code{gl_list_remove_last}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(1)}
+@tab @math{O(@log n)}
+@tab @math{O(n)}
+@tab @math{O(1)}
+@tab @math{O((@log n)@mathopsup{2})}
+@tab @math{O(@log n)}
@item @code{gl_list_remove}
@tab @math{O(n)}
@tab @math{O(n)}
^ permalink raw reply related [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 15:49 ` Bruno Haible
2020-05-02 16:04 ` Marc Nieper-Wißkirchen
@ 2020-05-22 15:59 ` Marc Nieper-Wißkirchen
2020-05-23 12:30 ` stack module Bruno Haible
1 sibling, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-22 15:59 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
Am Sa., 2. Mai 2020 um 17:49 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> Hi Marc,
>
> > Okay; I agree that a separate stack or FIFO module can make more
> > sense; in particular when it only has to deal with a single
> > implementation of an underlying data structure. At the moment I do
> > have other work to finish first, but maybe I will find some time in
> > the near future for a stack module.
Alternatively, one could implement a universally usable stack through
the following header file (mimicking somewhat C++ templates). What do
you think? It will be a lot faster than using the general list modules
of Gnulib.
It would be used like:
STACK (int) stack;
STACK_INIT (stack);
assert (STACK_EMPTY (stack));
STACK_PUSH (stack, 4)
assert (!STACK_EMPTY (stack));
assert (STACK_TOP (stack) == 4);
assert (STACK_POP (stack) == 4);
assert (STACK_EMPTY (stack));
STACK_CLEAR (stack);
So long,
Marc
****
#ifndef _GL_STACK_H
#define _GL_STACK_H
#include <stddef.h>
#include <stdlib.h>
#include <xalloc.h>
#define STACK(type) \
struct { \
type *base; \
size_t size; \
size_t allocated; \
}
#define STACK_INIT(stack) \
do \
{ \
(stack).base = NULL; \
(stack).size = 0; \
(stack).allocated = 0; \
} \
while (0)
#define STACK_CLEAR(stack) \
free ((stack).base)
#define STACK_EMPTY(stack) \
((stack).size == 0)
#define STACK_BASE(stack) \
((stack).base)
#define STACK_PUSH(stack, item) \
do \
{ \
if ((stack).size == (stack).allocated) \
(stack).base = x2nrealloc ((stack).base, &(stack).allocated,
sizeof (item)); \
(stack).base [(stack).size++] = item; \
} \
while (0)
#define STACK_POP(stack) \
(stack).base [--(stack).size]
#define STACK_DISCARD(stack) \
(--(stack).size)
#define STACK_TOP(stack) \
(stack).base[(stack).size - 1]
#define STACK_SIZE(stack) \
((stack).size)
#endif /* _GL_STACK_H */
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-22 15:59 ` Marc Nieper-Wißkirchen
@ 2020-05-23 12:30 ` Bruno Haible
2020-05-23 12:42 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 43+ messages in thread
From: Bruno Haible @ 2020-05-23 12:30 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Hi Marc,
> Alternatively, one could implement a universally usable stack through
> the following header file (mimicking somewhat C++ templates). What do
> you think? It will be a lot faster than using the general list modules
> of Gnulib.
I agree that a generic 'stack' module is useful. I also agree that a single
implementation, based on an array, is the way to go. Then it is already
faster than the generic list module.
In Gnulib, we usually avoid extensive use of multi-line macros, because
it hampers debuggability. Here, however, one needs macros, in order to
accommodate the TYPE argument, which is not necessarily compatible to 'void *'.
Nevertheless, we would try to put as much code as possible into functions.
The STACK_INIT macro, for example, could be implemented as a function.
> #define STACK_CLEAR(stack) \
> free ((stack).base)
Shouldn't this one also set .size and .allocated to 0 ?
> #define STACK_POP(stack) \
> (stack).base [--(stack).size]
>
> #define STACK_DISCARD(stack) \
> (--(stack).size)
>
> #define STACK_TOP(stack) \
> (stack).base[(stack).size - 1]
In these three macros, I would consider to abort() when (stack).size == 0.
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 12:30 ` stack module Bruno Haible
@ 2020-05-23 12:42 ` Marc Nieper-Wißkirchen
2020-05-23 14:02 ` Bruno Haible
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-23 12:42 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
> In Gnulib, we usually avoid extensive use of multi-line macros, because
> it hampers debuggability. Here, however, one needs macros, in order to
> accommodate the TYPE argument, which is not necessarily compatible to 'void *'.
> Nevertheless, we would try to put as much code as possible into functions.
> The STACK_INIT macro, for example, could be implemented as a function.
How? This would mean that the function stack_init has to take a void *
argument, which has to be cast to
struct
{
void *base; ...
}
and we have to hope that this structure is guaranteed to be compatible to
struct
{
type *base; ...
}
by the C standard.
> > #define STACK_CLEAR(stack) \
> > free ((stack).base)
>
> Shouldn't this one also set .size and .allocated to 0 ?
A stack can be uninitialized or initialized. An uninitialized stack is
initialized by STACK_INIT. It is cleared (and uninitialized) by
STACK_CLEAR. An uninitialized stack does not have to maintain any
invariant. The only way to use it is to initialize it again. Thus,
setting .size and .allocated seems pointless.
> > #define STACK_POP(stack) \
> > (stack).base [--(stack).size]
> >
> > #define STACK_DISCARD(stack) \
> > (--(stack).size)
> >
> > #define STACK_TOP(stack) \
> > (stack).base[(stack).size - 1]
>
> In these three macros, I would consider to abort() when (stack).size == 0.
In the form of assure of the assure module? Or, to facilitate
optimization, better assume from verify module? In non-debug builds, I
want to make sure that no superfluous checks are made.
Marc
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 12:42 ` Marc Nieper-Wißkirchen
@ 2020-05-23 14:02 ` Bruno Haible
2020-05-23 14:36 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 43+ messages in thread
From: Bruno Haible @ 2020-05-23 14:02 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Hi Marc,
> > In Gnulib, we usually avoid extensive use of multi-line macros, because
> > it hampers debuggability. Here, however, one needs macros, in order to
> > accommodate the TYPE argument, which is not necessarily compatible to 'void *'.
> > Nevertheless, we would try to put as much code as possible into functions.
> > The STACK_INIT macro, for example, could be implemented as a function.
>
> How? This would mean that the function stack_init has to take a void *
> argument, which has to be cast to
>
> struct
> {
> void *base; ...
> }
>
> and we have to hope that this structure is guaranteed to be compatible to
>
> struct
> {
> type *base; ...
> }
>
> by the C standard.
I was expecting that you write
struct
{
void *base; ...
}
and the cast the base to 'type *' each time you fetch it. I don't think this
would go the C standard, nor defeat any possible compiler optimization.
> > > #define STACK_CLEAR(stack) \
> > > free ((stack).base)
> >
> > Shouldn't this one also set .size and .allocated to 0 ?
>
> A stack can be uninitialized or initialized. An uninitialized stack is
> initialized by STACK_INIT. It is cleared (and uninitialized) by
> STACK_CLEAR. An uninitialized stack does not have to maintain any
> invariant. The only way to use it is to initialize it again. Thus,
> setting .size and .allocated seems pointless.
Then macro should better be called STACK_FREE or STACK_DESTROY.
The name STACK_CLEAR suggests that the result is still a valid stack, and empty.
> > > #define STACK_POP(stack) \
> > > (stack).base [--(stack).size]
> > >
> > > #define STACK_DISCARD(stack) \
> > > (--(stack).size)
> > >
> > > #define STACK_TOP(stack) \
> > > (stack).base[(stack).size - 1]
> >
> > In these three macros, I would consider to abort() when (stack).size == 0.
>
> In the form of assure of the assure module? Or, to facilitate
> optimization, better assume from verify module? In non-debug builds, I
> want to make sure that no superfluous checks are made.
The 'verify' module is for compile-time checks.
'assure' is an improved form of 'assert'.
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 14:02 ` Bruno Haible
@ 2020-05-23 14:36 ` Marc Nieper-Wißkirchen
2020-05-23 15:39 ` Paul Eggert
2020-05-23 17:19 ` Bruno Haible
0 siblings, 2 replies; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-23 14:36 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Am Sa., 23. Mai 2020 um 16:02 Uhr schrieb Bruno Haible <bruno@clisp.org>:
> I was expecting that you write
>
> struct
> {
> void *base; ...
> }
This removes type safety. The benefit of the current approach is that
stack types of different types are not compatible.
> Then macro should better be called STACK_FREE or STACK_DESTROY.
> The name STACK_CLEAR suggests that the result is still a valid stack, and empty.
Thank you for this suggestion; much better.
> > In the form of assure of the assure module? Or, to facilitate
> > optimization, better assume from verify module? In non-debug builds, I
> > want to make sure that no superfluous checks are made.
>
> The 'verify' module is for compile-time checks.
>
> 'assure' is an improved form of 'assert'.
The verify also contains a runtime check `assume', which uses
__builtin_unreachable if available to help the compiler in optimizing
modes.
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 14:36 ` Marc Nieper-Wißkirchen
@ 2020-05-23 15:39 ` Paul Eggert
2020-05-23 15:55 ` Marc Nieper-Wißkirchen
2020-05-23 17:19 ` Bruno Haible
1 sibling, 1 reply; 43+ messages in thread
From: Paul Eggert @ 2020-05-23 15:39 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
On 5/23/20 7:36 AM, Marc Nieper-Wißkirchen wrote:
> The verify also contains a runtime check `assume', which uses
> __builtin_unreachable if available to help the compiler in optimizing
> modes.
I wouldn't call 'assume (X)' a "runtime check". It's more an anti-runtime-check.
'assume (X)' is a directive from the programmer to the compiler that X is true
so that the compiler needn't generate code to test whether X is true. This is
why 'assume' is in verify.h: it's related to static checking (in this case,
static checking done by the programmer), not dynamic checking.
Perhaps I should add a comment to this effect....
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 15:39 ` Paul Eggert
@ 2020-05-23 15:55 ` Marc Nieper-Wißkirchen
2020-05-23 16:44 ` Paul Eggert
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-23 15:55 UTC (permalink / raw)
To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Am Sa., 23. Mai 2020 um 17:39 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>:
>
> On 5/23/20 7:36 AM, Marc Nieper-Wißkirchen wrote:
> > The verify also contains a runtime check `assume', which uses
> > __builtin_unreachable if available to help the compiler in optimizing
> > modes.
>
> I wouldn't call 'assume (X)' a "runtime check". It's more an anti-runtime-check.
>
> 'assume (X)' is a directive from the programmer to the compiler that X is true
> so that the compiler needn't generate code to test whether X is true. This is
> why 'assume' is in verify.h: it's related to static checking (in this case,
> static checking done by the programmer), not dynamic checking.
>
> Perhaps I should add a comment to this effect....
A combination of assure and assume would be helpful:
#define checked_assume(X) do { assure (X); assume (X); } while (0)
In debug builds, we get assertions and can check our assumptions. In
non-debug (NDEBUG) builds, we just have the compiler hints.
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 15:55 ` Marc Nieper-Wißkirchen
@ 2020-05-23 16:44 ` Paul Eggert
2020-05-23 16:54 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 43+ messages in thread
From: Paul Eggert @ 2020-05-23 16:44 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
[-- Attachment #1: Type: text/plain, Size: 327 bytes --]
On 5/23/20 8:55 AM, Marc Nieper-Wißkirchen wrote:
> A combination of assure and assume would be helpful:
>
> #define checked_assume(X) do { assure (X); assume (X); } while (0)
No, because the compiler is entitled to optimize away the 'assure (X)' in this
case. I installed the attached to try to explain this better.
[-- Attachment #2: 0001-verify-document-assume-better.patch --]
[-- Type: text/x-patch, Size: 2382 bytes --]
From b2c8d02c9750f335549781d20fa37415c9a1edb3 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sat, 23 May 2020 09:41:54 -0700
Subject: [PATCH] =?UTF-8?q?verify:=20document=20=E2=80=98assume=E2=80=99?=
=?UTF-8?q?=20better?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
* lib/verify.h (assume): Say it’s for static analysis, not dynamic.
---
ChangeLog | 5 +++++
lib/verify.h | 20 ++++++++++++++++----
2 files changed, 21 insertions(+), 4 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index a4473284c..44450a354 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2020-05-23 Paul Eggert <eggert@cs.ucla.edu>
+
+ verify: document ‘assume’ better
+ * lib/verify.h (assume): Say it’s for static analysis, not dynamic.
+
2020-05-22 Asher Gordon <AsDaGo@posteo.net>
gendocs: Clarify licenses for templates.
diff --git a/lib/verify.h b/lib/verify.h
index d9ab89a57..f10976127 100644
--- a/lib/verify.h
+++ b/lib/verify.h
@@ -277,10 +277,22 @@ template <int w>
#endif
/* Assume that R always holds. Behavior is undefined if R is false,
- fails to evaluate, or has side effects. Although assuming R can
- help a compiler generate better code or diagnostics, performance
- can suffer if R uses hard-to-optimize features such as function
- calls not inlined by the compiler. */
+ fails to evaluate, or has side effects.
+
+ 'assume (R)' is a directive from the programmer telling the
+ compiler that R is true so the compiler needn't generate code to
+ test R. This is why 'assume' is in verify.h: it's related to
+ static checking (in this case, static checking done by the
+ programmer), not dynamic checking.
+
+ 'assume (R)' can affect compilation of all the code, not just code
+ that happens to be executed after the assume (R) is "executed".
+ For example, if the code mistakenly does 'assert (R); assume (R);'
+ the compiler is entitled to optimize away the 'assert (R)'.
+
+ Although assuming R can help a compiler generate better code or
+ diagnostics, performance can suffer if R uses hard-to-optimize
+ features such as function calls not inlined by the compiler. */
#if _GL_HAS_BUILTIN_UNREACHABLE
# define assume(R) ((R) ? (void) 0 : __builtin_unreachable ())
--
2.17.1
^ permalink raw reply related [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 16:44 ` Paul Eggert
@ 2020-05-23 16:54 ` Marc Nieper-Wißkirchen
2020-05-23 17:33 ` Paul Eggert
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-23 16:54 UTC (permalink / raw)
To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Am Sa., 23. Mai 2020 um 18:44 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>:
>
> On 5/23/20 8:55 AM, Marc Nieper-Wißkirchen wrote:
> > A combination of assure and assume would be helpful:
> >
> > #define checked_assume(X) do { assure (X); assume (X); } while (0)
>
> No, because the compiler is entitled to optimize away the 'assure (X)' in this
> case. I installed the attached to try to explain this better.
Sure, but not in "-O0" or "-Og" builds, I think. Or am I mistaken?
But it is definitely better to make it more robust and not rely on
optimization levels:
#include <assert.h>
#include "verify.h"
#ifdef NDEBUG
# define checked_assume(E) assume (E)
#else
# define checked_assume(E) assert (E)
#endif
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 14:36 ` Marc Nieper-Wißkirchen
2020-05-23 15:39 ` Paul Eggert
@ 2020-05-23 17:19 ` Bruno Haible
2020-07-22 20:17 ` Marc Nieper-Wißkirchen
1 sibling, 1 reply; 43+ messages in thread
From: Bruno Haible @ 2020-05-23 17:19 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Marc Nieper-Wißkirchen wrote:
> > I was expecting that you write
> >
> > struct
> > {
> > void *base; ...
> > }
>
> This removes type safety. The benefit of the current approach is that
> stack types of different types are not compatible.
Indeed. Yes, it's a difficult trade-off between debuggability, binary code size,
and type safety...
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 16:54 ` Marc Nieper-Wißkirchen
@ 2020-05-23 17:33 ` Paul Eggert
2020-05-23 17:38 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 43+ messages in thread
From: Paul Eggert @ 2020-05-23 17:33 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
On 5/23/20 9:54 AM, Marc Nieper-Wißkirchen wrote:
> Sure, but not in "-O0" or "-Og" builds, I think. Or am I mistaken?
Probably not for -O0. I'm not so sure for -Og. Either way, we shouldn't rely on
GCC's current behavior in this area as it is neither documented nor guaranteed
to stay the same.
> #include <assert.h>
> #include "verify.h"
>
> #ifdef NDEBUG
> # define checked_assume(E) assume (E)
> #else
> # define checked_assume(E) assert (E)
> #endif
Something like that would work, though the name "checked_assume" is misleading
since the assumption is not always checked.
"affirm (E)" would be a better name, since the name's not being used anymore by
the old software verification project[1] and it slides in well next to "assume"
and "assert". (Some day we're going to run out of synonyms. :-)
[1] http://www.softwarepreservation.org/projects/verification/affirm/
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 17:33 ` Paul Eggert
@ 2020-05-23 17:38 ` Marc Nieper-Wißkirchen
2020-05-23 20:51 ` Paul Eggert
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-23 17:38 UTC (permalink / raw)
To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Paul,
Am Sa., 23. Mai 2020 um 19:33 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>:
> Probably not for -O0. I'm not so sure for -Og. Either way, we shouldn't rely on
> GCC's current behavior in this area as it is neither documented nor guaranteed
> to stay the same.
Agreed.
> > #include <assert.h>
> > #include "verify.h"
> >
> > #ifdef NDEBUG
> > # define checked_assume(E) assume (E)
> > #else
> > # define checked_assume(E) assert (E)
> > #endif
>
> Something like that would work, though the name "checked_assume" is misleading
> since the assumption is not always checked.
>
> "affirm (E)" would be a better name, since the name's not being used anymore by
> the old software verification project[1] and it slides in well next to "assume"
> and "assert". (Some day we're going to run out of synonyms. :-)
Believe it or not, but when I first proposed the (initial version of
the) macro, I wanted to name it "affirm" after I had looked for
synonyms. Only eventually, I switched to the name "checked_assume".
But if "affirm" is fine with you, I would love to see it in a module.
Either in verify or assure or in a new module named affirm.
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 17:38 ` Marc Nieper-Wißkirchen
@ 2020-05-23 20:51 ` Paul Eggert
2020-05-23 21:07 ` Marc Nieper-Wißkirchen
2020-05-23 22:06 ` Bruno Haible
0 siblings, 2 replies; 43+ messages in thread
From: Paul Eggert @ 2020-05-23 20:51 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
[-- Attachment #1: Type: text/plain, Size: 221 bytes --]
On 5/23/20 10:38 AM, Marc Nieper-Wißkirchen wrote:
> But if "affirm" is fine with you, I would love to see it in a module.
> Either in verify or assure or in a new module named affirm.
Something like the attached?
[-- Attachment #2: affirm.diff --]
[-- Type: text/x-patch, Size: 1432 bytes --]
diff --git a/lib/assure.h b/lib/assure.h
index 8ea2f6e48..2f1326027 100644
--- a/lib/assure.h
+++ b/lib/assure.h
@@ -22,11 +22,29 @@
#include <assert.h>
+/* Check E's value at runtime, and report an error and abort if not.
+ However, do nothing if NDEBUG is defined; in this case behavior is
+ undefined if E is false, fails to evaluate, or has side effects.
+
+ Unlike standard 'assert', this macro always compiles E even when
+ NDEBUG is defined, so as to catch typos, avoid some GCC warnings,
+ and improve performance when E is simple enough.
+
+ Also see the documentation for 'assume' in verify.h. */
+
+#ifdef NDEBUG
+# define affirm(E) assume (E)
+#else
+# define affirm(E) assert (E)
+#endif
+
/* Check E's value at runtime, and report an error and abort if not.
However, do nothing if NDEBUG is defined.
Unlike standard 'assert', this macro always compiles E even when NDEBUG
- is defined, so as to catch typos and avoid some GCC warnings. */
+ is defined, so as to catch typos and avoid some GCC warnings.
+ Unlike 'affirm', it is OK for E to use hard-to-optimize features,
+ since E is not executed if NDEBUG is defined. */
#ifdef NDEBUG
# define assure(E) ((void) (0 && (E)))
diff --git a/modules/assure b/modules/assure
index 3cfe1f874..c37191717 100644
--- a/modules/assure
+++ b/modules/assure
@@ -5,6 +5,7 @@ Files:
lib/assure.h
Depends-on:
+verify
configure.ac:
^ permalink raw reply related [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 20:51 ` Paul Eggert
@ 2020-05-23 21:07 ` Marc Nieper-Wißkirchen
2020-05-23 22:06 ` Bruno Haible
1 sibling, 0 replies; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-23 21:07 UTC (permalink / raw)
To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Am Sa., 23. Mai 2020 um 22:51 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>:
>
> On 5/23/20 10:38 AM, Marc Nieper-Wißkirchen wrote:
> > But if "affirm" is fine with you, I would love to see it in a module.
> > Either in verify or assure or in a new module named affirm.
>
> Something like the attached?
That would be a good addition to Gnulib, indeed, I think. (And may
even already be used by a number of modules, which currently call
abort explicitly.)
I find the comments in your code very valuable. I may change only one
thing. Above the definition of affirm, you write "Unlike standard
'assert', this macro always compiles E even when NDEBUG is defined
...". I think it is better to change it to "... always evaluates E
even when ...". In fact, when the assumption is fulfilled, E must have
been evaluated. If the assumption fails we are in the realm of
undefined behavior, so we may as well claim that E has been evaluated.
This is important not only so that the side effects of the evaluation
of E are documented, but also to remind the user of a potentially
costly evaluation.
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 20:51 ` Paul Eggert
2020-05-23 21:07 ` Marc Nieper-Wißkirchen
@ 2020-05-23 22:06 ` Bruno Haible
2020-05-24 2:14 ` Paul Eggert
1 sibling, 1 reply; 43+ messages in thread
From: Bruno Haible @ 2020-05-23 22:06 UTC (permalink / raw)
To: bug-gnulib; +Cc: Marc Nieper-Wißkirchen, Paul Eggert
Hi Paul,
> Something like the attached?
This documentation is quite misleading:
+/* Check E's value at runtime, and report an error and abort if not.
+ However, do nothing if NDEBUG is defined; in this case behavior is
because the "do nothing" is an understatement. 'assume' is a dangerous macro,
because it allows the compiler to do optimizations based on putative
assumptions. Since 'affirm' invokes 'assume', the documentation should
emphasize this danger.
How about this instead?
/* States an assertion that the programmer believes to be true.
When NDEBUG is not defined, this macro is like assert: it verifies the
assertion at run time and aborts the program if the assertion is not true.
When NDEBUG is defined, the programmer guarantees that the assertion is
true, and the macro informs the compiler about it, so that the compiler
may produce optimized code based on it. */
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 22:06 ` Bruno Haible
@ 2020-05-24 2:14 ` Paul Eggert
2020-05-24 8:17 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 43+ messages in thread
From: Paul Eggert @ 2020-05-24 2:14 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
[-- Attachment #1: Type: text/plain, Size: 229 bytes --]
On 5/23/20 3:06 PM, Bruno Haible wrote:
> How about this instead?
Thanks, good point about the danger. Also, I forgot to include verify.h.
I tightened up the commentary, folded in Marc's suggestion, and installed the
attached.
[-- Attachment #2: 0001-assure-new-macro-affirm.patch --]
[-- Type: text/x-patch, Size: 3094 bytes --]
From 2df56dc44200074077ebace04079ac4b0a34e4fc Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sat, 23 May 2020 19:06:16 -0700
Subject: [PATCH] =?UTF-8?q?assure:=20new=20macro=20=E2=80=98affirm?=
=?UTF-8?q?=E2=80=99?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
* lib/assure.h: Include verify.h.
(affirm): New macro, after a suggestion by Marc Nieper-Wißkirchen in:
https://lists.gnu.org/r/bug-gnulib/2020-05/msg00263.html
and commentary by Bruno Haible in:
https://lists.gnu.org/r/bug-gnulib/2020-05/msg00278.html
* modules/assure (Depends-on:): Add verify.
---
ChangeLog | 10 ++++++++++
lib/assure.h | 24 ++++++++++++++++++++++--
modules/assure | 1 +
3 files changed, 33 insertions(+), 2 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index a7101db80..c05ef910d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2020-05-23 Paul Eggert <eggert@cs.ucla.edu>
+
+ assure: new macro ‘affirm’
+ * lib/assure.h: Include verify.h.
+ (affirm): New macro, after a suggestion by Marc Nieper-Wißkirchen in:
+ https://lists.gnu.org/r/bug-gnulib/2020-05/msg00263.html
+ and commentary by Bruno Haible in:
+ https://lists.gnu.org/r/bug-gnulib/2020-05/msg00278.html
+ * modules/assure (Depends-on:): Add verify.
+
2020-05-23 Bruno Haible <bruno@clisp.org>
calloc-gnu: Make test work in non-flat address spaces.
diff --git a/lib/assure.h b/lib/assure.h
index 8ea2f6e48..09a4edfa5 100644
--- a/lib/assure.h
+++ b/lib/assure.h
@@ -21,12 +21,32 @@
#define _GL_ASSURE_H
#include <assert.h>
+#include "verify.h"
+
+/* Evaluate an assertion E that is guaranteed to be true.
+ If NDEBUG is not defined, abort the program if E is false.
+ If NDEBUG is defined, the compiler can assume E and behavior is
+ undefined if E is false, fails to evaluate, or has side effects.
+
+ Unlike standard 'assert', this macro evaluates E even when NDEBUG
+ is defined, so as to catch typos, avoid some GCC warnings, and
+ improve performance when E is simple enough.
+
+ Also see the documentation for 'assume' in verify.h. */
+
+#ifdef NDEBUG
+# define affirm(E) assume (E)
+#else
+# define affirm(E) assert (E)
+#endif
/* Check E's value at runtime, and report an error and abort if not.
However, do nothing if NDEBUG is defined.
- Unlike standard 'assert', this macro always compiles E even when NDEBUG
- is defined, so as to catch typos and avoid some GCC warnings. */
+ Unlike standard 'assert', this macro compiles E even when NDEBUG
+ is defined, so as to catch typos and avoid some GCC warnings.
+ Unlike 'affirm', it is OK for E to use hard-to-optimize features,
+ since E is not executed if NDEBUG is defined. */
#ifdef NDEBUG
# define assure(E) ((void) (0 && (E)))
diff --git a/modules/assure b/modules/assure
index 3cfe1f874..c37191717 100644
--- a/modules/assure
+++ b/modules/assure
@@ -5,6 +5,7 @@ Files:
lib/assure.h
Depends-on:
+verify
configure.ac:
--
2.17.1
^ permalink raw reply related [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-24 2:14 ` Paul Eggert
@ 2020-05-24 8:17 ` Marc Nieper-Wißkirchen
2020-05-24 19:07 ` Paul Eggert
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-05-24 8:17 UTC (permalink / raw)
To: Paul Eggert; +Cc: bug-gnulib, Bruno Haible, Marc Nieper-Wißkirchen
Thank you very much, Paul!
One bit of the commentary is still misleading, though, I think. You
wrote for the affirm macro that if NDEBUG is defined that the behavior
is undefined if E has side effects. That's not true as long as E does
not evaluate to false.
Marc
Am So., 24. Mai 2020 um 04:14 Uhr schrieb Paul Eggert <eggert@cs.ucla.edu>:
>
> On 5/23/20 3:06 PM, Bruno Haible wrote:
> > How about this instead?
>
> Thanks, good point about the danger. Also, I forgot to include verify.h.
>
> I tightened up the commentary, folded in Marc's suggestion, and installed the
> attached.
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-24 8:17 ` Marc Nieper-Wißkirchen
@ 2020-05-24 19:07 ` Paul Eggert
2020-05-24 19:26 ` Bruno Haible
0 siblings, 1 reply; 43+ messages in thread
From: Paul Eggert @ 2020-05-24 19:07 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib, Bruno Haible
On 5/24/20 1:17 AM, Marc Nieper-Wißkirchen wrote:
> You
> wrote for the affirm macro that if NDEBUG is defined that the behavior
> is undefined if E has side effects. That's not true as long as E does
> not evaluate to false.
We can *make* it true, by fiat. :-)
I don't want to encourage programmers to supply an E with side effects, as side
effects are trouble here. Even if side effects happen to work in the current
implementation when E is true, I don't want to suggest to programmers that
they'll continue to work in future implementations; we may come up with a
different implementation that evaluates E twice, for example.
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-24 19:07 ` Paul Eggert
@ 2020-05-24 19:26 ` Bruno Haible
2020-06-02 13:44 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 43+ messages in thread
From: Bruno Haible @ 2020-05-24 19:26 UTC (permalink / raw)
To: Paul Eggert; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Paul Eggert wrote:
> I don't want to encourage programmers to supply an E with side effects, as side
> effects are trouble here.
+1
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-24 19:26 ` Bruno Haible
@ 2020-06-02 13:44 ` Marc Nieper-Wißkirchen
0 siblings, 0 replies; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-06-02 13:44 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, Paul Eggert, bug-gnulib
So here is the updated stack module. The name "CLEAR" has been changed
to "DESTROY" as suggested by Bruno. Error checking has been included.
The macro interface remains. Although a macro interface means macros,
the macros are trivial and the type safety wins here, I think. I have
renamed STACK_BASE to STACK_CURRENT_BASE because the base may be
invalidated when items are pushed onto the stack and reallocation has
to happen.
As I haven't heard anything from the FSF yet, I wouldn't mind if you
considered the following in the public domain...
#ifndef _GL_STACK_H
#define _GL_STACK_H
#include <stddef.h>
#include <stdlib.h>
#include "assure.h"
#include "xalloc.h"
#define STACK(type) \
struct { \
type *base; \
size_t size; \
size_t allocated; \
}
#define STACK_INIT(stack) \
do \
{ \
(stack).base = NULL; \
(stack).size = 0; \
(stack).allocated = 0; \
} \
while (0)
#define STACK_DESTROY(stack) \
free ((stack).base)
#define STACK_EMPTY(stack) \
((stack).size == 0)
#define STACK_CURRENT_BASE(stack) \
((stack).base)
#define STACK_PUSH(stack, item) \
do \
{ \
if ((stack).size == (stack).allocated) \
(stack).base = x2nrealloc ((stack).base, &(stack).allocated,
sizeof (item)); \
(stack).base [(stack).size++] = item; \
} \
while (0)
#define STACK_POP(stack) \
(affirm (!STACK_EMPTY (stack)), (stack).base [--(stack).size])
#define STACK_DISCARD(stack) \
(affirm (!STACK_EMPTY (stack)), (--(stack).size))
#define STACK_TOP(stack) \
(affirm (!STACK_EMPTY (stack)), (stack).base[(stack).size - 1)
#define STACK_SIZE(stack) \
((stack).size)
#endif /* _GL_STACK_H */
Am So., 24. Mai 2020 um 21:26 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> Paul Eggert wrote:
> > I don't want to encourage programmers to supply an E with side effects, as side
> > effects are trouble here.
>
> +1
>
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible
2020-05-03 11:14 ` Bruno Haible
2020-05-05 8:37 ` Marc Nieper-Wißkirchen
@ 2020-06-03 16:32 ` Marc Nieper-Wißkirchen
2020-06-03 21:08 ` Bruno Haible
2 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-06-03 16:32 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
now that some operations together with their complexity for dealing
with the end of the list have been added, what do you think of adding
a reverse iterator?
Thanks,
Marc
PS I've received a reply by the FSF; now I am waiting for the response
by my university's lawyer.
Am Sa., 2. Mai 2020 um 23:24 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> I wrote:
> > I should better revert yesterday's patch, and instead,
> > in the table show the guaranteed average performance
> > gl_list_get_first
> > gl_list_get_last
> > gl_list_set_first
> > gl_list_set_last
> > gl_list_remove_first
> > gl_list_remove_last
> > where these 6 functions are defined globally, not separately for each
> > implementation.
>
> Done through the two attached patches.
>
> 2020-05-02 Bruno Haible <bruno@clisp.org>
>
> list: Add get_first, get_last, set_first, set_last operations.
> * lib/gl_list.h (gl_list_get_first, gl_list_get_last,
> gl_list_nx_set_first, gl_list_nx_set_last): New functions.
> * lib/gl_xlist.h (gl_list_set_first, gl_list_set_last): New functions.
>
> 2020-05-02 Bruno Haible <bruno@clisp.org>
>
> list: Remove redundant code for remove_first and remove_last operations.
> * lib/gl_list.h (struct gl_list_implementation): Remove fields
> remove_first, remove_last.
> (gl_list_remove_first, gl_list_remove_last): Implement in a generic way.
> * lib/gl_array_list.c: Revert last change.
> * lib/gl_carray_list.c: Likewise.
> * lib/gl_anylinked_list2.h: Likewise.
> * lib/gl_linked_list.c: Likewise.
> * lib/gl_linkedhash_list.c: Likewise.
> * lib/gl_anytree_list2.h: Likewise.
> * lib/gl_avltree_list.c: Likewise.
> * lib/gl_avltreehash_list.c: Likewise.
> * lib/gl_rbtree_list.c: Likewise.
> * lib/gl_rbtreehash_list.c: Likewise.
> * lib/gl_sublist.c: Likewise.
>
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-06-03 16:32 ` Marc Nieper-Wißkirchen
@ 2020-06-03 21:08 ` Bruno Haible
2020-06-03 21:22 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 43+ messages in thread
From: Bruno Haible @ 2020-06-03 21:08 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Hi Marc,
> now that some operations together with their complexity for dealing
> with the end of the list have been added, what do you think of adding
> a reverse iterator?
Not a good idea, IMO.
It's rarely used: In most cases, a list is either traversed one way or
the other way.
If a list going to be traversed in reverse order, the programmer can just
keep it in opposite order and use the normal forward iterator.
Or they can use an array (or an array-based list) and use indices.
I find the amount of bloat in the C++ standard library horrible. In C
at least, we can concentrate on the things that get used, not on the
things that some rare programmer might find useful some day.
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Add gl_list_remove_last to list/xlist
2020-06-03 21:08 ` Bruno Haible
@ 2020-06-03 21:22 ` Marc Nieper-Wißkirchen
0 siblings, 0 replies; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-06-03 21:22 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Am Mi., 3. Juni 2020 um 23:08 Uhr schrieb Bruno Haible <bruno@clisp.org>:
> It's rarely used: In most cases, a list is either traversed one way or
> the other way.
One could say that a list that is to be transversed in both ways is a
different abstract data type; nevertheless, they appear (e.g. lists of
instructions in compiler analysis usually have to traversed in both
ways).
> If a list going to be traversed in reverse order, the programmer can just
> keep it in opposite order and use the normal forward iterator.
> Or they can use an array (or an array-based list) and use indices.
For an array-based list, this is fine. For a general list, one could
use gl_list_previous_node; however, one would have to keep a node of
the last element (there's no gl_list_first_node/gl_list_last_node).
> I find the amount of bloat in the C++ standard library horrible. In C
> at least, we can concentrate on the things that get used, not on the
> things that some rare programmer might find useful some day.
I admit that there is some wisdom in these words. :)
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-05-23 17:19 ` Bruno Haible
@ 2020-07-22 20:17 ` Marc Nieper-Wißkirchen
2020-07-23 10:36 ` Bruno Haible
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-07-22 20:17 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Am Sa., 23. Mai 2020 um 19:19 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> Marc Nieper-Wißkirchen wrote:
> > > I was expecting that you write
> > >
> > > struct
> > > {
> > > void *base; ...
> > > }
> >
> > This removes type safety. The benefit of the current approach is that
> > stack types of different types are not compatible.
>
> Indeed. Yes, it's a difficult trade-off between debuggability, binary code size,
> and type safety...
The alternative with the same type safety would be a source file with
stack code procedures meant for inclusion (without include guards).
The source file would expect a preprocessor defines GL_STACK_NAME,
GL_STACK_TYPE, and GL_STACK_EXTERN.
The file itself would contain code like the following:
#define _GL_STACK_PREFIX(name) _GL_CONCAT(GL_STACK_NAME, _GL_CONCAT(_, name))
typedef struct
{
GL_STACK_TYPE *base;
size_t size;
size_t allocated;
}
GL_STACK_PREFIX(type);
GL_STACK_EXTERN GL_STACK_PREFIX(init) (GL_STACK_PREFIX(type) *stack)
{
stack->base = NULL;
stack->size = 0;
stack->allocated = 0;
}
...
The advantage of this model is that it generalizes to other data
structures, for which a sole (or at least simple) macro implementation
is not possible.
What do you think?
Marc
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-07-22 20:17 ` Marc Nieper-Wißkirchen
@ 2020-07-23 10:36 ` Bruno Haible
2020-07-23 10:56 ` Marc Nieper-Wißkirchen
2020-10-07 9:01 ` Marc Nieper-Wißkirchen
0 siblings, 2 replies; 43+ messages in thread
From: Bruno Haible @ 2020-07-23 10:36 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Hi Marc,
> The alternative with the same type safety would be a source file with
> stack code procedures meant for inclusion (without include guards).
> The source file would expect a preprocessor defines GL_STACK_NAME,
> GL_STACK_TYPE, and GL_STACK_EXTERN.
>
> The file itself would contain code like the following:
>
> #define _GL_STACK_PREFIX(name) _GL_CONCAT(GL_STACK_NAME, _GL_CONCAT(_, name))
>
> typedef struct
> {
> GL_STACK_TYPE *base;
> size_t size;
> size_t allocated;
> }
> GL_STACK_PREFIX(type);
>
> GL_STACK_EXTERN GL_STACK_PREFIX(init) (GL_STACK_PREFIX(type) *stack)
> {
> stack->base = NULL;
> stack->size = 0;
> stack->allocated = 0;
> }
>
> ...
>
> The advantage of this model is that it generalizes to other data
> structures, for which a sole (or at least simple) macro implementation
> is not possible.
This is perfectly acceptable for Gnulib. It has debuggability and type safety.
You have precedent e.g. in lib/diffseq.h and lib/aligned-malloc.h.
You can even omit the 'GL_' prefix from the macro names. The user can #undef
the macros after including the file; therefore there is nearly no risk of
collision with macros defined by other code.
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-07-23 10:36 ` Bruno Haible
@ 2020-07-23 10:56 ` Marc Nieper-Wißkirchen
2020-10-07 9:01 ` Marc Nieper-Wißkirchen
1 sibling, 0 replies; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-07-23 10:56 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
> This is perfectly acceptable for Gnulib. It has debuggability and type safety.
Perfect. Then I will come up with a module in this form.
> You have precedent e.g. in lib/diffseq.h and lib/aligned-malloc.h.
Good to know; I hadn't taken a look at these sources yet.
> You can even omit the 'GL_' prefix from the macro names. The user can #undef
> the macros after including the file; therefore there is nearly no risk of
> collision with macros defined by other code.
Or the included file #undefs the macros as in lib/diffseq.h.
Speaking of prefixes: As macro names (and other names) starting with
"_GL_" are not officially allowed by ISO C, I think it makes sense to
think of a new convention for new sources (while old sources could
later be updated incrementally).
For example, one could use the prefix "GL__" (double underscore) for
(future) private identifiers.
Marc
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-07-23 10:36 ` Bruno Haible
2020-07-23 10:56 ` Marc Nieper-Wißkirchen
@ 2020-10-07 9:01 ` Marc Nieper-Wißkirchen
2020-10-07 11:31 ` Marc Nieper-Wißkirchen
1 sibling, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-10-07 9:01 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
I am finally finishing my work on the stack module.
Am Do., 23. Juli 2020 um 12:36 Uhr schrieb Bruno Haible <bruno@clisp.org>:
[...]
> This is perfectly acceptable for Gnulib. It has debuggability and type safety.
>
> You have precedent e.g. in lib/diffseq.h and lib/aligned-malloc.h.
>
> You can even omit the 'GL_' prefix from the macro names. The user can #undef
> the macros after including the file; therefore there is nearly no risk of
> collision with macros defined by other code.
After I have given it a bit more thought, I see a different type of
collision possibility, namely if some header file uses the stack
header file. It will leak the macro names. Assume that the stack
module accepts the macro name ELEMENT for the element type. A
hypothetical header for the frob type may be implemented as:
#ifndef FROB_H
#define FROB_H
...
#define ELEMENT int
#define STORAGECLASS static inline
#include "stack.h"
...
struct frob
{
stack frob_stack;
...
};
...
#endif /* FROB_H */
Now, user code cannot do:
#define ELEMENT hydrogen
#include "frob.h"
...
(The ELEMENT definition in the first line could in fact be exported by
some other header file.)
Therefore, I think I prefer to use prefixed names.
Cheers,
Marc
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-10-07 9:01 ` Marc Nieper-Wißkirchen
@ 2020-10-07 11:31 ` Marc Nieper-Wißkirchen
2020-10-10 14:06 ` Bruno Haible
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-10-07 11:31 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib, Bruno Haible
[-- Attachment #1: Type: text/plain, Size: 1572 bytes --]
Dear Bruno,
please see the attached patch for the new module.
Thanks,
Marc
Am Mi., 7. Okt. 2020 um 11:01 Uhr schrieb Marc Nieper-Wißkirchen
<marc.nieper+gnu@gmail.com>:
>
> Hi Bruno,
>
> I am finally finishing my work on the stack module.
>
> Am Do., 23. Juli 2020 um 12:36 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> [...]
>
> > This is perfectly acceptable for Gnulib. It has debuggability and type safety.
> >
> > You have precedent e.g. in lib/diffseq.h and lib/aligned-malloc.h.
> >
> > You can even omit the 'GL_' prefix from the macro names. The user can #undef
> > the macros after including the file; therefore there is nearly no risk of
> > collision with macros defined by other code.
>
> After I have given it a bit more thought, I see a different type of
> collision possibility, namely if some header file uses the stack
> header file. It will leak the macro names. Assume that the stack
> module accepts the macro name ELEMENT for the element type. A
> hypothetical header for the frob type may be implemented as:
>
> #ifndef FROB_H
> #define FROB_H
> ...
> #define ELEMENT int
> #define STORAGECLASS static inline
> #include "stack.h"
> ...
> struct frob
> {
> stack frob_stack;
> ...
> };
> ...
> #endif /* FROB_H */
>
> Now, user code cannot do:
>
> #define ELEMENT hydrogen
> #include "frob.h"
> ...
>
> (The ELEMENT definition in the first line could in fact be exported by
> some other header file.)
>
> Therefore, I think I prefer to use prefixed names.
>
> Cheers,
>
> Marc
[-- Attachment #2: 0001-Type-safe-stack-data-type.patch --]
[-- Type: text/x-patch, Size: 10525 bytes --]
From c449d60058f4a5806729ec76779fbb050890ddaf Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Marc=20Nieper-Wi=C3=9Fkirchen?= <marc@nieper-wisskirchen.de>
Date: Wed, 7 Oct 2020 13:29:10 +0200
Subject: [PATCH] Type-safe stack data type. * MODULES.html.sh: Add entry for
the stack module. * modules/stack: New file. * modules/stack-tests: New file.
* lib/stack.h: New file. * tests/test-stack.c: New file.
---
ChangeLog | 9 +++
MODULES.html.sh | 1 +
lib/stack.h | 163 ++++++++++++++++++++++++++++++++++++++++++++
modules/stack | 25 +++++++
modules/stack-tests | 13 ++++
tests/test-stack.c | 74 ++++++++++++++++++++
6 files changed, 285 insertions(+)
create mode 100644 lib/stack.h
create mode 100644 modules/stack
create mode 100644 modules/stack-tests
create mode 100644 tests/test-stack.c
diff --git a/ChangeLog b/ChangeLog
index 875f3551a..b64689f73 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2020-10-07 Marc nieper-Wißkirchen <marc@nieper-wisskirchen.de>
+
+ stack: New module.
+ * MODULES.html.sh: Add entry for the stack module.
+ * modules/stack: New file.
+ * modules/stack-tests: New file.
+ * lib/stack.h: New file.
+ * tests/test-stack.c: New file.
+
2020-10-05 Paul Eggert <eggert@cs.ucla.edu>
thread: pacify GCC on Solaris 10
diff --git a/MODULES.html.sh b/MODULES.html.sh
index a8a629e29..7e7cdae3e 100755
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -2031,6 +2031,7 @@ func_all_modules ()
func_module readline
func_module readtokens
func_module readtokens0
+ func_module stack
func_module strverscmp
func_module filevercmp
func_end_table
diff --git a/lib/stack.h b/lib/stack.h
new file mode 100644
index 000000000..22e976952
--- /dev/null
+++ b/lib/stack.h
@@ -0,0 +1,163 @@
+/* Type-safe stack data type.
+ Copyright (C) 2020 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* Written by Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>, 2020. */
+
+/* This header file does not have include-guards as it is meant to be
+ includeable multiple times as long as the necessary defines have
+ been set up.
+
+ A stack is implemented with a homogenous array of elements in
+ memory, which will be resized (and moved) as needed. Elements are
+ passed by value and it is the responsibility of the user-code to
+ free any allocate and free any resources associated with individual
+ elements.
+
+ The exported names are all prefixed by ‘stack’ (e.g. stack_init),
+ but this can be changed by setting an appropriate define.
+ Type: stack_type
+ Initialization: stack_init (&stack);
+ De-initialization: stack_destroy (&stack);
+ Predicate: bool res = stack_empty (&stack);
+ Introspection: ELEMENT *base = stack_base (&stack);
+ Pushing: stack_push (&stack, element);
+ Popping: ELEMENT element = stack_pop (&stack);
+ Discarding: stack_discard (&stack);
+ Top-of-stack: ELEMENT element = stack_top (&stack);
+ Size: size_t size = stack_size (&stack);
+*/
+
+/* Before including this file, you need to define:
+ GL_STACK_ELEMENT The type of the elements on the stack..
+ GL_STACK_STORAGECLASS (Optional) The storage class specifier (e.g. static)
+ to use in the function definitions.
+ GL_STACK_NAME (Optional) The prefix to use for the type names
+ and functions definitions instead of the default
+ ‘stack’.
+
+ After including this file, these names will be undefined.
+
+ Before including this file, you also need to include:
+ #include "<stdbool.h>"
+ #include "<stdlib.h>"
+ #include "assure.h"
+ #include "xalloc.h"
+*/
+
+#ifndef GL_STACK_ELEMENT
+# error "Please define GL_STACK_ELEMENT first."
+#endif
+
+#ifndef GL_STACK_STORAGECLASS
+# define GL_STACK_STORAGECLASS
+#endif
+
+#ifndef GL_STACK_NAME
+# define GL_STACK_NAME stack
+#endif
+
+#define _GL_STACK_PREFIX(name) _GL_CONCAT(GL_STACK_NAME, _GL_CONCAT(_, name))
+#define _GL_STACK_TYPE _GL_STACK_PREFIX(type)
+
+typedef struct
+{
+ GL_STACK_ELEMENT *base;
+ size_t size;
+ size_t allocated;
+} _GL_STACK_TYPE;
+
+/* Initialize a stack. */
+GL_STACK_STORAGECLASS void
+_GL_STACK_PREFIX (init) (_GL_STACK_TYPE *stack)
+{
+ stack->base = NULL;
+ stack->size = 0;
+ stack->allocated = 0;
+}
+
+/* Destroy a stack by freeing the allocated space. */
+GL_STACK_STORAGECLASS void
+_GL_STACK_PREFIX (destroy) (_GL_STACK_TYPE *stack)
+{
+ free (stack->base);
+}
+
+/* Return true if the stack currently holds no element. */
+GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE bool
+_GL_STACK_PREFIX (empty) (const _GL_STACK_TYPE *stack)
+{
+ return stack->size == 0;
+}
+
+/* Return the current address of the array of stack elements.
+
+ The result is invalidated as soon as an element is added or removed
+ from the stack. */
+GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE GL_STACK_ELEMENT *
+_GL_STACK_PREFIX (current_base) (const _GL_STACK_TYPE *stack)
+{
+ return stack->base;
+}
+
+/* Push an element to the top of the stack. */
+GL_STACK_STORAGECLASS void
+_GL_STACK_PREFIX (push) (_GL_STACK_TYPE *stack, GL_STACK_ELEMENT item)
+{
+ if (stack->size == stack->allocated)
+ stack->base = x2nrealloc (stack->base, &stack->allocated,
+ sizeof (GL_STACK_ELEMENT));
+ stack->base [stack->size++] = item;
+}
+
+/* Pop the element from the top of the stack, which must be non-empty,
+ and return it. */
+GL_STACK_STORAGECLASS GL_STACK_ELEMENT
+_GL_STACK_PREFIX (pop) (_GL_STACK_TYPE *stack)
+{
+ affirm (!_GL_STACK_PREFIX (empty) (stack));
+ return stack->base [--stack->size];
+}
+
+/* Pop the element from the top of the stack, which must be
+ non-empty. */
+GL_STACK_STORAGECLASS void
+_GL_STACK_PREFIX (discard) (_GL_STACK_TYPE *stack)
+{
+ affirm (!_GL_STACK_PREFIX (empty) (stack));
+ --stack->size;
+}
+
+/* Return the element from the top of the stack, which must be
+ non-empty. */
+GL_STACK_STORAGECLASS GL_STACK_ELEMENT
+_GL_STACK_PREFIX (top) (const _GL_STACK_TYPE *stack)
+{
+ affirm (!_GL_STACK_PREFIX (empty) (stack));
+ return stack->base [stack->size - 1];
+}
+
+/* Return the currently stored number of elements in the stack. */
+GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE size_t
+_GL_STACK_PREFIX (size) (const _GL_STACK_TYPE *stack)
+{
+ return stack->size;
+}
+
+#undef GL_STACK_ELEMENT
+#undef GL_STACK_STORAGECLASS
+#undef GL_STACK_NAME
+#undef _GL_STACK_PREFIX
+#undef _GL_STACK_TYPE
diff --git a/modules/stack b/modules/stack
new file mode 100644
index 000000000..95f2ce9b9
--- /dev/null
+++ b/modules/stack
@@ -0,0 +1,25 @@
+Description:
+Type-safe stack data type.
+
+Files:
+lib/stack.h
+
+Depends-on:
+assure
+stdbool
+stdlib
+xalloc
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += stack.h
+
+Include:
+"stack.h"
+
+License:
+GPL
+
+Maintainer:
+Marc Nieper-Wißkirchen
diff --git a/modules/stack-tests b/modules/stack-tests
new file mode 100644
index 000000000..308d7258e
--- /dev/null
+++ b/modules/stack-tests
@@ -0,0 +1,13 @@
+Files:
+tests/test-stack.c
+tests/macros.h
+
+Depends-on:
+string
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-stack
+check_PROGRAMS += test-stack
+test_stack_SOURCES = test-stack.c
diff --git a/tests/test-stack.c b/tests/test-stack.c
new file mode 100644
index 000000000..dbf4e19a3
--- /dev/null
+++ b/tests/test-stack.c
@@ -0,0 +1,74 @@
+/* Test of the type-safe stack data type.
+ Copyright (C) 2020 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* Written by Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>, 2020. */
+
+#include <config.h>
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include "assure.h"
+#include "xalloc.h"
+
+#include "macros.h"
+
+#define GL_STACK_ELEMENT int
+#define GL_STACK_STORAGECLASS static
+#include "stack.h"
+
+#define GL_STACK_ELEMENT const char *
+#define GL_STACK_STORAGECLASS static
+#define GL_STACK_NAME string_stack
+#include "stack.h"
+
+int
+main (void)
+{
+ stack_type int_stack;
+ stack_init (&int_stack);
+ ASSERT (stack_size (&int_stack) == 0);
+ ASSERT (stack_empty (&int_stack));
+ stack_push (&int_stack, 0);
+ stack_push (&int_stack, 1);
+ stack_push (&int_stack, 2);
+ stack_push (&int_stack, 3);
+ stack_push (&int_stack, 4);
+ stack_push (&int_stack, 5);
+ stack_push (&int_stack, 6);
+ stack_push (&int_stack, 7);
+ stack_push (&int_stack, 8);
+ stack_push (&int_stack, 9);
+ ASSERT (stack_size (&int_stack) == 10);
+ ASSERT (!stack_empty (&int_stack));
+ ASSERT (stack_top (&int_stack) == 9);
+ ASSERT (stack_size (&int_stack) == 10);
+ ASSERT (stack_pop (&int_stack) == 9);
+ ASSERT (stack_size (&int_stack) == 9);
+ stack_discard (&int_stack);
+ ASSERT (stack_size (&int_stack) == 8);
+ ASSERT (stack_top (&int_stack) == 7);
+ stack_destroy (&int_stack);
+
+ string_stack_type string_stack [1];
+ string_stack_init (string_stack);
+ string_stack_push (string_stack, "foo");
+ ASSERT (STREQ (string_stack_pop (string_stack), "foo"));
+ ASSERT (string_stack_empty (string_stack));
+ string_stack_destroy (string_stack);
+
+ return EXIT_SUCCESS;
+}
--
2.25.1
^ permalink raw reply related [flat|nested] 43+ messages in thread
* Re: stack module
2020-10-07 11:31 ` Marc Nieper-Wißkirchen
@ 2020-10-10 14:06 ` Bruno Haible
2020-10-10 14:35 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 43+ messages in thread
From: Bruno Haible @ 2020-10-10 14:06 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Hi Marc,
> please see the attached patch for the new module.
Very nice. Looks all good, except for some nit-picking in the comments:
> + Introspection: ELEMENT *base = stack_base (&stack);
I would add a comment here:
Where ELEMENT is the type to which GL_STACK_ELEMENT was defined when
this file was included.
(It would be tempting to write
GL_STACK_ELEMENT *base = stack_base (&stack);
but GL_STACK_ELEMENT is no longer defined after the file was included...)
Other than that, please feel free to commit and push this. Thanks!!
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: stack module
2020-10-10 14:06 ` Bruno Haible
@ 2020-10-10 14:35 ` Marc Nieper-Wißkirchen
2020-10-10 15:10 ` ChangeLog entries Bruno Haible
0 siblings, 1 reply; 43+ messages in thread
From: Marc Nieper-Wißkirchen @ 2020-10-10 14:35 UTC (permalink / raw)
To: Bruno Haible; +Cc: Marc Nieper-Wißkirchen, bug-gnulib
Hi Bruno,
Am Sa., 10. Okt. 2020 um 16:06 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> Hi Marc,
>
> > please see the attached patch for the new module.
>
> Very nice. Looks all good, except for some nit-picking in the comments:
Thanks.
>
> > + Introspection: ELEMENT *base = stack_base (&stack);
>
> I would add a comment here:
> Where ELEMENT is the type to which GL_STACK_ELEMENT was defined when
> this file was included.
> (It would be tempting to write
> GL_STACK_ELEMENT *base = stack_base (&stack);
> but GL_STACK_ELEMENT is no longer defined after the file was included...)
I will add this comment.
> Other than that, please feel free to commit and push this. Thanks!!
I will do this as soon as I have been approved by Paul. (Do I have to
do something about the ChangeLog entry or will it be auto-generated
from my Git commit message?)
Marc
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: ChangeLog entries
2020-10-10 14:35 ` Marc Nieper-Wißkirchen
@ 2020-10-10 15:10 ` Bruno Haible
0 siblings, 0 replies; 43+ messages in thread
From: Bruno Haible @ 2020-10-10 15:10 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen; +Cc: bug-gnulib
Hi Marc,
> (Do I have to
> do something about the ChangeLog entry or will it be auto-generated
> from my Git commit message?)
The ChangeLog entries are not auto-generated, no. We want the ChangeLog
entries to be essentially in sync with the git commits. This means, you
typically prepare the ChangeLog entry and reuse it for the git commit.
Or you prepare a git commit message (with line width <= 72) and use
it in the ChangeLog entry.
To avoid conflicts in ChangeLog during "git pull", I recomment to use the
git-merge-changelog program (see the comments in lib/git-merge-changelog.c).
Bruno
^ permalink raw reply [flat|nested] 43+ messages in thread
end of thread, other threads:[~2020-10-10 15:11 UTC | newest]
Thread overview: 43+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-04-28 7:08 Add gl_list_remove_last to list/xlist Marc Nieper-Wißkirchen
2020-05-02 0:07 ` Bruno Haible
2020-05-02 7:16 ` Marc Nieper-Wißkirchen
2020-05-02 12:07 ` Bruno Haible
2020-05-02 12:49 ` Marc Nieper-Wißkirchen
2020-05-02 15:49 ` Bruno Haible
2020-05-02 16:04 ` Marc Nieper-Wißkirchen
2020-05-22 15:59 ` Marc Nieper-Wißkirchen
2020-05-23 12:30 ` stack module Bruno Haible
2020-05-23 12:42 ` Marc Nieper-Wißkirchen
2020-05-23 14:02 ` Bruno Haible
2020-05-23 14:36 ` Marc Nieper-Wißkirchen
2020-05-23 15:39 ` Paul Eggert
2020-05-23 15:55 ` Marc Nieper-Wißkirchen
2020-05-23 16:44 ` Paul Eggert
2020-05-23 16:54 ` Marc Nieper-Wißkirchen
2020-05-23 17:33 ` Paul Eggert
2020-05-23 17:38 ` Marc Nieper-Wißkirchen
2020-05-23 20:51 ` Paul Eggert
2020-05-23 21:07 ` Marc Nieper-Wißkirchen
2020-05-23 22:06 ` Bruno Haible
2020-05-24 2:14 ` Paul Eggert
2020-05-24 8:17 ` Marc Nieper-Wißkirchen
2020-05-24 19:07 ` Paul Eggert
2020-05-24 19:26 ` Bruno Haible
2020-06-02 13:44 ` Marc Nieper-Wißkirchen
2020-05-23 17:19 ` Bruno Haible
2020-07-22 20:17 ` Marc Nieper-Wißkirchen
2020-07-23 10:36 ` Bruno Haible
2020-07-23 10:56 ` Marc Nieper-Wißkirchen
2020-10-07 9:01 ` Marc Nieper-Wißkirchen
2020-10-07 11:31 ` Marc Nieper-Wißkirchen
2020-10-10 14:06 ` Bruno Haible
2020-10-10 14:35 ` Marc Nieper-Wißkirchen
2020-10-10 15:10 ` ChangeLog entries Bruno Haible
2020-05-02 21:24 ` Add gl_list_remove_last to list/xlist Bruno Haible
2020-05-03 11:14 ` Bruno Haible
2020-05-05 8:37 ` Marc Nieper-Wißkirchen
2020-05-08 17:28 ` Bruno Haible
2020-06-03 16:32 ` Marc Nieper-Wißkirchen
2020-06-03 21:08 ` Bruno Haible
2020-06-03 21:22 ` Marc Nieper-Wißkirchen
-- strict thread matches above, loose matches on Subject: below --
2016-11-12 16:22 [PATCH] Avoid having GNULIB_NAMESPACE::func always inject references to rpl_func Pedro Alves
2016-11-20 12:26 ` Bruno Haible
2016-11-21 20:24 ` Pedro Alves
2016-11-21 23:34 ` ChangeLog entries Bruno Haible
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).