Re: Add gl_list_remove_last to list/xlist

[Marc Nieper-Wißkirchen]

Am Mi., 3. Juni 2020 um 23:08 Uhr schrieb Bruno Haible :

> 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. :)

Re: Add gl_list_remove_last to list/xlist

[Bruno Haible]

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

Re: Add gl_list_remove_last to list/xlist

[Marc Nieper-Wißkirchen]

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 :
>
> 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  
>
> 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  
>
> 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.
>

Re: Add gl_list_remove_last to list/xlist

[Marc Nieper-Wißkirchen]

Hi Bruno,

Am Sa., 2. Mai 2020 um 17:49 Uhr schrieb Bruno Haible :
>
> 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 
#include 
#include 

#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 */

Re: Add gl_list_remove_last to list/xlist

[Bruno Haible]

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  

list: Update documentation.
Reported by Marc Nieper-Wißkirchen  in
.
* 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)}

Re: Add gl_list_remove_last to list/xlist

[Marc Nieper-Wißkirchen]

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 :
>
> 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  
>
> 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  
>
> 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.
>

Re: Add gl_list_remove_last to list/xlist

[Bruno Haible]

> Done through the two attached patches.

And another patch, for the C++ interface.


2020-05-03  Bruno Haible  

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(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(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(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)

Re: Add gl_list_remove_last to list/xlist

[Bruno Haible]

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  

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  

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.

>From 3abe3e9a03a481163e4141e7defd30df051b42ca Mon Sep 17 00:00:00 2001
From: Bruno Haible 
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  
 
+	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  
+
 	bison-i18n: Add support for cross-compilation.
 	Reported by Hongxu Jia  in
 	
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 = >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 

Re: Add gl_list_remove_last to list/xlist

[Marc Nieper-Wißkirchen]

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.

Re: Add gl_list_remove_last to list/xlist

[Bruno Haible]

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:
.

> 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

Re: Add gl_list_remove_last to list/xlist

[Marc Nieper-Wißkirchen]

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

Re: Add gl_list_remove_last to list/xlist

[Bruno Haible]

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

Re: Add gl_list_remove_last to list/xlist

[Marc Nieper-Wißkirchen]

Hi Bruno,

thanks again very much!

Am Sa., 2. Mai 2020 um 02:07 Uhr schrieb Bruno Haible :
>
> 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  
>
> list: Add remove_first and remove_last operations.
> Suggested by Marc Nieper-Wißkirchen  in
> .
> * lib/gl_list.h (struct gl_list_implementation): Add fields
> remove_first, remove_last.
> (gl_list_remove_first, gl_list_remove_last): New functions.
> * lib/gl_array_list.c (gl_array_remove_first, gl_array_remove_last): 
> New
> functions, based on gl_array_remove_at.
> (gl_array_list_implementation): Implement the new operations.
> * lib/gl_carray_list.c (gl_carray_remove_first, 
> gl_carray_remove_last):
> New functions, based on gl_carray_remove_at.
> (gl_carray_list_implementation): Implement the new operations.
> * lib/gl_anylinked_list2.h (gl_linked_remove_first,
> gl_linked_remove_last): New functions, based on gl_linked_remove_at.
> * lib/gl_linked_list.c (gl_linked_list_implementation): Implement the
> new operations.
> * lib/gl_linkedhash_list.c (gl_linkedhash_list_implementation):
> Likewise.
> * lib/gl_anytree_list2.h (gl_tree_remove_first, gl_tree_remove_last):
> New functions, based on gl_tree_remove_at.
> * lib/gl_avltree_list.c (gl_avltree_list_implementation): Implement 
> the
> new operations.
> * lib/gl_avltreehash_list.c (gl_avltreehash_list_implementation):
> Likewise.
> * lib/gl_rbtree_list.c (gl_rbtree_list_implementation): Likewise.
> * lib/gl_rbtreehash_list.c (gl_rbtreehash_list_implementation):
> Likewise.
> * lib/gl_sublist.c (gl_sublist_remove_first, gl_sublist_remove_last):
> New functions, based on gl_sublist_remove_at.
> (gl_sublist_list_implementation): Implement the new operations.
> * lib/gl_list.hh (class gl_List): Add methods remove_first,
> remove_last.
> * tests/test-array_list.c (main): Test also gl_list_remove_first and
> gl_list_remove_last.
> * tests/test-avltree_list.c (main): Likewise.
> * tests/test-avltreehash_list.c (main): Likewise.
> * tests/test-carray_list.c (main): Likewise.
> * tests/test-linked_list.c (main): Likewise.
> * tests/test-linkedhash_list.c (main): Likewise.
> * tests/test-rbtree_list.c (main): Likewise.
> * tests/test-rbtreehash_list.c (main): Likewise.
>
> 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)
> 

Re: Add gl_list_remove_last to list/xlist

[Bruno Haible]

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  

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

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_iteratorO(1) O(1)   O(log n)O(1)   O(log n)
gl_list_iterator_from_toO(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.  
*/

Add gl_list_remove_last to list/xlist

[Marc Nieper-Wißkirchen]

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