Re: New GQueue API

[Soeren Sandmann <sandmann daimi au dk>]

Owen Taylor <otaylor redhat com> writes:

> On Thu, 2003-09-18 at 14:46, Soeren Sandmann wrote:
> > In 
> > 
> >         http://bugzilla.gnome.org/show_bug.cgi?id=78414
> > 
> > Owen says he thinks it makes sense to complete GQueue to get a full
> > GList/GSList equivalent API. So here is the list of GList API with my
> > comments on their appropriateness for GQueue:

I have attached a patch to the bug now.

The new API:

guint    g_queue_get_length     (GQueue           *queue);
void     g_queue_reverse        (GQueue           *queue);
GQueue * g_queue_copy           (GQueue           *queue);
void     g_queue_foreach        (GQueue           *queue,
				 GFunc             func,
				 gpointer          user_data);
GList *  g_queue_find           (GQueue           *queue,
				 gconstpointer     data);
GList *  g_queue_find_custom    (GQueue           *queue,
				 gconstpointer     data,
				 GCompareFunc      func);
void     g_queue_sort           (GQueue           *queue,
				 GCompareDataFunc  compare_func,
				 gpointer          user_data);
void     g_queue_push_nth       (GQueue           *queue,
				 gpointer          data,
				 gint              n);
void     g_queue_push_nth_link  (GQueue           *queue,
				 gint              n,
				 GList            *link_);
GList*   g_queue_peek_head_link (GQueue           *queue);
GList*   g_queue_peek_tail_link (GQueue           *queue);
gpointer g_queue_pop_nth        (GQueue           *queue,
				 guint             n);
GList*   g_queue_pop_nth_link   (GQueue           *queue,
				 guint             n);
GList *  g_queue_peek_nth_link  (GQueue           *queue,
				 guint             n);
gint     g_queue_index_link     (GQueue           *queue,
				 GList            *link_);
void     g_queue_unlink         (GQueue           *queue,
				 GList            *link_);
void     g_queue_delete_link    (GQueue           *queue,
				 GList            *link_);
gpointer g_queue_peek_nth       (GQueue           *queue,
				 guint             n);
gint     g_queue_index          (GQueue           *queue,
				 gconstpointer     data);
void     g_queue_remove         (GQueue           *queue,
				 gconstpointer     data);
void     g_queue_remove_all     (GQueue           *queue,
				 gconstpointer     data);
void     g_queue_insert_before  (GQueue           *queue,
				 GList            *sibling,
				 gpointer          data);
void     g_queue_insert_after   (GQueue           *queue,
				 GList            *sibling,
				 gpointer          data);
void     g_queue_insert_sorted  (GQueue           *queue,
				 gpointer          data,
				 GCompareDataFunc  func,
				 gpointer          user_data);

> >     GList*   g_list_insert         (GList            *list,
> >                                     gpointer          data,
> >                                     gint              position);
> >     GList*   g_list_remove         (GList            *list,
> >                                     gconstpointer     data);
> >     GList*   g_list_remove_all     (GList            *list,
> >                                     gconstpointer     data);
> >     GList*   g_list_reverse        (GList            *list);
> >     GList*   g_list_copy           (GList            *list);
> >     gint     g_list_index          (GList            *list,
> >                                     gconstpointer     data);
> >     guint    g_list_length         (GList            *list);
> >     void     g_list_foreach        (GList            *list,
> >                                     GFunc             func,
> >                                     gpointer          user_data);
> >     gpointer g_list_nth_data       (GList            *list,
> >                                     guint             n);
> > 
> > These make sense and have an obvious counterpart for GQueue, though
> > the function g_list_nth_data() should probably be called
> > g_queue_peek_nth() to be consistent with g_queue_peek_front.
> 
> Sounds fine.

The patch contains all those, except that nth_data() and insert() are
called peek_nth() and push_nth() respectively().

> >         void g_queue_insert_sorted (GQueue *queue,
> >                                     gpointer data,
> >                                     GCompareDataFunc func,
> >                                     gpointer sort_data);
[..]
> > Similarly, I think we should only have g_queue_sort() that takes a
> > GCompareDataFunc.
> 
> Sounds OK to me to favor simplicity over consistency here.

Both of those are in the patch.

> >     GList*   g_list_insert_before  (GList            *list,
> >                                     GList            *sibling,
> >                                     gpointer          data);

The patch has both insert_before() and insert_after()

> >     GList*   g_list_remove_link    (GList            *list,
> >                                     GList            *llink);
> >     GList*   g_list_delete_link    (GList            *list,
> >                                     GList            *link_);

I renamed g_list_remove_link() to g_queue_unlink() to avoid confusion
with about g_queue_remove() vs. g_queue_remove_link(). They do two
quite different things.

The API docs for these functions has a note that calling them with
links that are not actually part of the queue silently results in
undefined behavior. The reason is that hese functions are O(1), but
checking the prerequisite is O(n).

> >     GList*   g_list_nth            (GList            *list,
> >                                     guint             n);

In patch as g_queue_peek_nth_link()

> >     GList*   g_list_nth_prev       (GList            *list,
> >                                     guint             n);

I didn't add this, because it seems a bit odd to me.

> >     GList*   g_list_find           (GList            *list,
> >                                     gconstpointer     data);
> >     GList*   g_list_find_custom    (GList            *list,
> >                                     gconstpointer     data,
> >                                     GCompareFunc      func);

Those are in the patch.

> >     gint     g_list_position       (GList            *list,
> >                                     GList            *llink);

I called this one g_queue_index_link() for consistency with the rest
of the link-related API, which is generally g_queue_foo_link().

> >     GList*   g_list_last           (GList            *list);
> >     GList*   g_list_first          (GList            *list);

These are g_queue_peek_head/tail_link().

> See comments about g_queue_push_list_{head|tail} below. I don't
> really think that concatenating queues destructively fits in
> well with the idea of a 'queue' being an object.

I left it out.

> > Some functions that could be useful, but don't correspond to anything
> > in GList:
> > 
> >         GList *g_queue_pop_list (GQueue *queue)
> > 
> > returns the list. When this function returns @queue will be empty.
> 
> When would this be useful?

I can see situations where you want to append to a queue to build a
list in O(n), then convert it to a regular list, but probably not
worth doing until somebody asks for it, so I left it out.

> >         void g_queue_push_list_{head|tail} (GQueue *queue, GList *list);
> > 
> > adds a full list to the queue (taking ownership).
> 
> This might be the more useful replacement of 'concat'

I left those out too. I think if this should be done, it should be
done by lifting the requirement on g_queue_push_head/tail_link() that
the passed in link is a single link, not a list instead of adding new
API.

> >         gpointer g_queue_pop_nth (GQueue *queue, gint nth)
> > 
> > returns and removes the nth element of the queue.
> 
> Fits in well to me.

In patch.

> >         GQueue *g_queue_splice_nth (GQueue *queue, gint nth);
> >         GQueue *g_queue_splice     (GQueue *queue, gpoitner data);
> >         GQueue *g_queue_splice_link (GQueue *queue, GList *link_);
> > 
> > [more dubious, but may be useful if we have g_queue_concat() and
> > g_queue_copy()]
> 
> Hmm, without people asking for them, I'd be hestitant to add these.

I left them out.


Søren