Re: GLib queue and stack, alloca discussion

[Jeff Garzik <jgarzik pobox com>]

On Fri, 22 Jan 1999, Havoc Pennington wrote:
> For precedent, see the STL - a queue or stack is just a vector, but you
> can't do vector operations on them. You can't iterate over a stack. 

In the STL, the stack is an adaptor on top of deque, which has the
properties you say.

However, deque itself has full vector and iteration operations.

	deque<int> qi;

	qi.push_back (1234);
	printf ("%d\n", qi[0]);

> The whole point of using a queue or stack instead of a list is to place
> limits on what you can do with it and thus simplify the code, no? I mean,
> it's not like g_list_prepend() is any harder than g_stack_push(). 
> The whole point of the wrapper is to make it a stack rather than a list.

I think GStack is a bit of a red herring here.  It could probably be
implemented completely with macros.

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.

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.

	Jeff