Re: New GQueue API

[Owen Taylor <otaylor redhat com>]

The new API looks reasonable to me. There is a little more deviation
from the GList than I'd like for the goal we went into this with,
but at least we wont' get an eternal stream of "add g_queue_blah_*"

On Wed, 2003-10-01 at 17:06, Soeren Sandmann wrote:

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

I think that's just confusing. THere are plenty of other things
you can do in GLib which are completley wrong, but GLib can't
catch. 

* If @link_ is not part of @queue, the result of calling this function
 * is undefined. Unlike most other functions in GLib this will not produce
 * any warnings or assertion failures.
 * 

Should simply be:
 
 * @link_ must be part of @queue.

Using "undefined" to mean "illegal, but might not to be caught" is
standards jargon.

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

I'd really suggest link_index() instead. 

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

Hmm, the obvious (though not possible at this point)

 GList *g_queue_free (GQueue *queue, gboolean free_links);

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


====
void
+g_queue_reverse (GQueue *queue)
+{
+  g_return_if_fail (queue != NULL);
+
+  queue->head = g_list_reverse (queue->head);
+  queue->tail = g_list_last (queue->head);
+}
===

How about

  queue->tail = queue->head;
  queue->head = g_list_reverse (queue->head);

====
GQueue *
+g_queue_copy (GQueue *queue)
+{
+  GQueue *result;
+
+  g_return_val_if_fail (queue != NULL, NULL);
+
+  result = g_queue_new ();
+  
+  result->head = g_list_copy (queue->head);
+  result->tail = g_list_last (result->head);
+  result->length = g_list_length (result->head);
+
+  return result;
+
====

This walks the list three times! Very simple way
of implementing in one pass would be:

 GList *l;

 for (l = queue->head; l; l = l->next)
   g_queue_append (result, l->data);

You could also write a helper 'g_list_copy_return_tail'
function and do it that way (result->length = queue->length).

General: 

 - You can and should wrap lines in parameter descriptions 
   in inline doc comments.

 - I think it might be nice if all the functions that take
   an index 'n' were O(1) for n == queue->length - 1.

   (In theory, you could make them walk the list backwards
   for any n > queue->length / 2. That might be overcomplex,
   though it would be easy enough to do if you wrote 
   everything in terms of a g_queue_nth_link())

Regards,
						Owen