Re: CList glitch (some kind o off-topic response)

[Owen Taylor <otaylor redhat com>]

leon@udmnet.ru writes:

> Karl Nelson wrote:
> > 
> > I have a fully compatible implementation of glist that does track
> > tails.  (There does not need to be a new structure the current
> > system could easily have been expanded.)
> > 
> > It changes the glist structure to
> > 
> >   struct GList
> >     { void * data;
> >       GList *next,*prev,*aux
> >     };
> > 
> > Heads and tails are represented as before with NULLs in the next and
> > prev,  however, now the aux pointer completes the circular linked list.
> > All the algorithms for working through the lists still work without
> > modification.
> > 
> >         next prev aux
> > Head  { NEXT, 0, PREV }
> > Body  { NEXT, PREV, 0 }
> > Tail  { 0, PREV, NEXT }
> 
> Why simply not to link the head of the list to the tail, so making 
> it circular, not linear? Have someone suggested this idea to glib 
> maintainers? No structure change in list items at all. The only
> (possibly) bad thing is if someone counts on NULLs in head and 
> tail of list. But IMHO such programs are very few, and it is 
> bad style to rely on internal representation. So I see no obstacles.

Any guesses to how many times code like:

 tmp_list = foo;
 while (tmp_list) 
   {
     MyStruct *x = tmpl_list->data;
     tmp_list = tmp_list->next;

      /* do something with x */
   }

Occurs within GTK+? I don't have an exact count - but its certainly
in more than 100 places; there is no way we could change GLists
to be circular without breaking massive amounts of library
and application code.

If you want a tail pointer, IMO, you should store a tail pointer
for the list.

GLib-1.3 already includes a GQueue data structure which does
this.

Regards,
                                        Owen