Re: invasive doubly linked list

[Tim Janik <timj gtk org>]

On Mon, 6 Aug 2001, Joshua N Pritikin wrote:

> Is there any interest in this whatsoever?

basically yes, but not for 2.0 since we're in API freeze already.

> An implementation and test suite are attached.  i can write documentation, but
> for now you can study the ringtest.c for usage.  Shall i file a bugzilla
> enhancement request?
> 
> Please comment!

your ring implementation gixes up an interesting property of GList that
i'd like to see maintained, i.e. NULL is a valid ring of zero-length.
also the API is somewhat different from what we have for glist/gslist,
and i'm missing a facility to do custom ring walks (let alone freeing
a ring), i.e. users will have to take care of not walking the ring
endlessly in a for() loop themselves.
here's the API of a ring implementation i implemented at
one point, modelled after the GList API. basically it is a GList
with head and tail linked just as yours and users just need to
use gsl_ring_walk() instead of ring = ring->next in for() constructs:

struct _GslRing
{
  GslRing  *next;
  GslRing  *prev;
  gpointer  data;
};
GslRing*        gsl_ring_prepend        (GslRing        *head,
                                         gpointer        data); /* O(1) */
GslRing*        gsl_ring_prepend_uniq   (GslRing        *head,
                                         gpointer        data);
GslRing*        gsl_ring_append         (GslRing        *head,
                                         gpointer        data); /* O(1) */
GslRing*        gsl_ring_concat         (GslRing        *head1,
                                         GslRing        *head2);
GslRing*        gsl_ring_remove_node    (GslRing        *head,
                                         GslRing        *node);
GslRing*        gsl_ring_remove         (GslRing        *head,
                                         gpointer        data); /* head&tail: O(1) */
gpointer        gsl_ring_pop_head       (GslRing       **head); /* O(1) */
gpointer        gsl_ring_pop_tail       (GslRing       **head); /* O(1) */
void            gsl_ring_free           (GslRing        *head); /* O(1) */
#define gsl_ring_walk(head,node)        ((node) != (head)->prev ? (node)->next : NULL)

though gsl_ring_pop_head() and gsl_ring_pop_tail() are somewhat non-standard,
they are nice to have since 1) they exactly fit a ring's purpose and
2) eliminate the need for GQueue.

> 
> -- 
> Get self-realization at <http://sahajayoga.org> ... <http://why-compete.org> ?
>   Victory to the Divine Mother!!
> 

---
ciaoTJ