g_list_prepend() vs g_list_append()

[Mark Mielke <mark mark mielke cc>]

I assume that g_list_prepend() and g_list_append() are functions that
only function reliably, and intuitively, if they are passed the 'first
element in the list', however, their implementations cause me to suspect
that either this limitation was not intended, or else, the implementation
of g_list_prepend() can be optimized slightly.

g_list_append() uses g_list_last() to (slowly) follow all the next pointers
until it reaches the final list item. It then appends to this item.

g_list_prepend() does:

  GList *new_list = _g_list_alloc();
  ...

  if (list)
    {
      if (list->prev)
        {
          list->prev->next = new_list;
          new_list->prev = list->prev;
        }
      list->prev = new_list;
      new_list->next = list;
    }

  return new_list;

So, if g_list_prepend() is used on the fourth element, the new_list becomes
the fourth element, and the fourth element is bumped into being the fifth
element.

In other words, g_list_prepend() functions with respect to the current
element, wheras g_list_append() functions with respect to the last
element. I found this behaviour unobvious.

I stumbled on this while trying to find a GLib data structure that
could efficiently append to the end of the list (i.e. not GList), but
that provided a method to traverse the list (like g_list_foreach(), i.e.
not GQueue()).

As it turns out, I believe I may live with using g_list_prepend() as an
'append' function, and scan the list in reverse order when traversing. (Gah!)
(I want the 'append' function to be optimized - the 'traverse' function can
take a little more time to run if necessary)

The normal solution to this sort of problem is to use a circular
doubly-linked list. Then, g_list_last() is list->prev, and g_list_foreach()
just needs to scan:

    if (list) do { ...; list = list->next } while (list != first)

Would it be prudent to add circular lists, or a foreach method to
'double-ended queues'? (it seems as if 'double-ended queues' were
really created due to a lack of functionality in GList)

Should g_list_prepend() use g_list_first(), as g_list_append() uses
g_list_last()?

Cheers,
mark

-- 
mark mielke cc/markm ncf ca/markm nortelnetworks com __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/