Re: My thoughts on GRing

[Tim Janik <timj gtk org>]

On Thu, 14 Nov 2002, Owen Taylor wrote:

> The arguments in favor of GRing seem to be:
>
>  - Saves space. True, but not significant amounts ... just
>    a 12-byte constant overhead.

over GQueue that is.

>  - It is more efficient. I dont think it matters for cases where
>    you are keeping a permanent queue around. It is true.
>
>     GSList *foo = NULL;
>
>     foo = g_slist_prepend (list, a);
>     foo = g_slist_prepend (list, b);
>     foo = g_slist_prepend (list, c);
>
>     foo = g_slist_reverse (foo);
>
>    Would be more efficient and less confusing with GRing... but
>    the problem with this is that if you are going to then pass
>    the list, say, into GTK+, then you have to convert the
>    GRing to a GList/GSList, losing all the advantages.

ring to/from slist/list is on my TODO to make this at least somewhat
convenient.

>  - Has the same API as GList/GSList.
>
>    Sort, of, but not exactly;
>    [You can't use node->next, node->prev, as almost all G[L]ist
>    code does, g_ring_prev() is named differently than g_list_previous(), and
>    takes another argument, g_ring_insert_sorted() takes an extra user
>    data pointer, g_ring_insert_before() is missing, g_ring_first()
>    does something completely different, g_ring_nth_prev() does
>    something completely different]

you're probably referring to joshua's API version which i had a couple
gnits with as well. the ring version i'm currently maintaining (kept
in beast CVS) mirrors the GList API more closely and really just differs
in walking a ring, where you have to do:

SfiRing *tmp, *head = return_a_ring (); /* Sfi being it's current namespace */

for (tmp = head; tmp; tmp = sfi_ring_walk (tmp, head))
  ...;

>    Now, it could be argued that a lot of the above differences
>    are just implementation details, and also, that a "GRing" that
>    was more like GList could be done by using the
>    node->next->prev != NULL trick for reverse iteration (though
>    "Ring" wouldn't be a good name then.)

i'm not sure how that is meant to work. a ring always
has ->prev and ->next != NULL for all nodes.

>  - Has the complete GList/GSList API, as opposed to GQueue,
>    which has only a subset. How is this an advantage?
>    We could trivially add the complete API to GQueue...

if you're going to extend GQueue to cover all of GList, we can just
as well do the work for GRing (which is already more complete than
GQueue).

>  - Is easier to use than GQueue. Well, only by virtue of similarity
>    to GList/GSList ... newbies generally find GList utterly
>    puzzling (try to use g_list_alloc() to allocate a new one,
>    forget to assign the results of g_list_remove() or whatever
>    back to the list point)

hm, sfi_ring_alloc() i've actually left out so far. i never quite got
the point in g_list_alloc(), considering that g_list_append (NULL, data)
gives you exactly this. i'd rather see g_(s)list_alloc() be deprecated
in future APIs.

> Is something like GRing a better way of implementing a double-ended
> list than GQueue? Probably.
>
> Would it make sense to have both GQueue and GRing as non-deprecated
> API's in GLib? No. It would be silly. If we add GRing, we have
> to plan on deprecating GQueue.

yep, and long term, it'd even be better to use GRing instead of GList
in standard API (i'm not saying that'd be an easy transition to make
though ;)

> Is it worth the pain of deprecating GQueue and adding GRing?
> I don't think so. Deprecation is expensive both in terms of:
>
>  - Requiring people to change their code
>  - Confusing people until all vestiges of the deprecated method
>    are removed.
>
> I just don't see the benefits of GRing as being worth these
> costs.

you simply haven't been infected by it's convenience even over normal
lists yet ;)
i've been using rings for over a year now, and i'm gradually migrating
beasts internal API to use only rings because they're much more
convenient to use and more efficient than lists.

i'll try to give a brief summary on why rings are better to
use than our current lists (and GQueue):

efficiency reasons:
- sfi_ring_append() is O(1)
- sfi_ring_insert_sorted() also is O(1) for tail insertions (takes
  extra logic in the implementation of this function, but is really
  worth the effort since a significant amount of sorted lists insert
  head or tail most of the time)
- sfi_ring_remove_node() and sfi_ring_remove() are both O(1) for
  tail as well (same reasoning as for sfi_ring_insert_sorted)
- sfi_ring_concat() is O(1)
- sfi_ring_split() is O(1) (reverses effect of concat)
- push/pop head/tail can all be O(1) (i.e. the queueing API)
- sfi_ring_tail() is O(1)
- rotations by r nodes are O(r) (as opposed to O(length) for lists)
- if the new head is known in advance, rotations are actually O(1) since
  any node may be used as head

convenience:
the code to construct an ordered ring from hand is much easier to write
and read than for lists, because you don't need to spend extra thoughts
on using _prepend and doing _reverse at the right time, or reorder loops
to e.g. walk a string array backwards because you could only efficiently
prepend.

the two disadvantages i see for GRing over GList are:
- GList is widely deployed and nailed in API where GRing isn't
- you run code into endless loops if you do ring = ring->next instead
  of ring = ring_walk (ring, head) in a loop. however this should be
  easy to diagnose and fix (and i personally haven't run into this
  accident even once yet).

GQueue, in contrast to GList, isn't widely used, so even if
we can't switch our huge GList using APIs to GRings, for GQueue
there's moderately little to replace, and GRing is already far
easier to use for queues than GQueue ever will be.

>
> Regards,
>                                         Owen
>
>
> Even the Perl slogan "there's more than one way to do it",
> doesn't mean that you should have multiple almost identical
> API's, but that if you have a flexible set of primitives, there
> will be multiple ways of accomplishing the same end task.

right, i'm not advocating adding GRing to widen the amount of
fundamental data structures supported, but a long term migration
with significant benefits in a) code readability, b) ease of
writing code (complexity reduction), c) efficiency.

anyway, we can still discuss this for the next devel tree or
even 3.0. i've appended the current incarnation of the ring API,
so you can pinpoint things you dislike nevertheless and have
me fix them, since i need to maintain a ring API for beast anyway.

---
ciaoTJ


typedef gpointer (*SfiRingDataFunc)     (gpointer        data,
                                         gpointer        func_data);
struct _SfiRing
{
  SfiRing  *next;
  SfiRing  *prev;
  gpointer  data;
};

SfiRing*        sfi_ring_prepend        (SfiRing        *head,
                                         gpointer        data);
SfiRing*        sfi_ring_prepend_uniq   (SfiRing        *head,
                                         gpointer        data);
SfiRing*        sfi_ring_append         (SfiRing        *head,
                                         gpointer        data);
SfiRing*        sfi_ring_insert_sorted  (SfiRing        *head,
                                         gpointer        data,
                                         GCompareFunc    func);
SfiRing*        sfi_ring_remove_node    (SfiRing        *head,
                                         SfiRing        *node);
SfiRing*        sfi_ring_remove         (SfiRing        *head,
                                         gpointer        data);
guint           sfi_ring_length         (SfiRing        *head);
SfiRing*        sfi_ring_copy           (SfiRing        *head);
SfiRing*        sfi_ring_copy_deep      (SfiRing        *head,
                                         SfiRingDataFunc copy,
                                         gpointer        func_data);
SfiRing*        sfi_ring_concat         (SfiRing        *head1,
                                         SfiRing        *head2);
SfiRing*        sfi_ring_find           (SfiRing        *head,
                                         gconstpointer   data);
SfiRing*        sfi_ring_nth            (SfiRing        *head,
                                         guint           n);
gpointer        sfi_ring_nth_data       (SfiRing        *head,
                                         guint           n);
SfiRing*        sfi_ring_split          (SfiRing        *head1,
                                         SfiRing        *head2);
SfiRing*        sfi_ring_sort           (SfiRing        *head,
                                         GCompareFunc    func);
SfiRing*        sfi_ring_reverse        (SfiRing        *head);
gpointer        sfi_ring_pop_head       (SfiRing       **head);
gpointer        sfi_ring_pop_tail       (SfiRing       **head);
#define         sfi_ring_push_head      sfi_ring_prepend
#define         sfi_ring_push_tail      sfi_ring_append
void            sfi_ring_free_deep      (SfiRing        *head,
                                         SfiRingDataFunc free_func,
                                         gpointer        func_data);
void            sfi_ring_free           (SfiRing        *head);
#define sfi_ring_tail(head)             ((head) ? (head)->prev : NULL)
#define sfi_ring_walk(node,head_bound)  ((node)->next != (head_bound) ? (node)->next : NULL)