Re: GLib queue and stack, alloca discussion

[Havoc Pennington <hp Mcs Net>]

On Fri, 22 Jan 1999, Jeff Garzik wrote:
> 
> I think GStack is a bit of a red herring here.  It could probably be
> implemented completely with macros.
>

Good point.
 
> Consider GQueue, whose implementation isn't quite as a simple as
> GStack's.  The purpose of GQueue, in my mind, is to cache list_end,
> making operations at the tail as fast as operations at the head.  It
> also caches list_size (since a lot of Gtk and GNOME code asks for a list
> count before performing certain operations), but the value of doing so
> is debateable.
> 
> GtkCList is an example of why I am adding GQueue; a clist stores
> row_list, row_list_end, and rows, and maintains those three variables
> for each row list addition or removal.  But due to the nature of clist
> operations, one must have the capability to insert before a specific row
> number, or delete a specific row number.
> 

I see. So it is analagous to deque instead, as you say.

> If GtkCList was implemented using GQueue, you would either need to
> manipulate the list yourself, or create g_queue_insert and the other
> g_list_* wrapper functions, so that the list_end and list_size vars are
> maintained.
> 
> If the programmer manipulates the list themselves, a g_queue_update()
> function may be needed to notify GQueue that it needs to possibly
> recalculate list_end and list_size.
> 

I think g_queue_update() sucks a lot, so I'd vote for the wrappers.  (I'm
sure we'd all forget to call g_queue_update, and it would be a nightmare
bug to find since the segfault would come at some mysterious future
time...) 

For this purpose it might be nice to be even more like deque:  implement
it as a vector. Then you save memory and get fast subscripting, at the
expense of slower insertions. But one almost always appends or prepends to
a CList, or sets the value of some particular row. Inserts are relatively
uncommon. Since there can be thousands of rows, the memory overhead of a
list is not insignificant, seems more important than fast insertions.

If slow insertions/removals make us nervous, the ability to insert or
remove an entire block at once would solve that.

Havoc