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

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

        next prev aux
Head  { NEXT, 0, PREV }
Body  { NEXT, PREV, 0 }
Tail  { 0, PREV, NEXT }

Only a handful of the functions in g_list need to be modified
to use this and as it changes none of the user code, I think
it should be the default.  g_list_first and g_list_last become
O(1) from the head and tail (but remain O(n) in general).

Unfortunately, Owen has been very clear that he does not want 
this implementation.  The glib crew wants you to track your
own tails, but as the list abstraction has no hooks to
do so you can't use the g_list methods and track the tail 
at the same time.  (This gives fits to the gtk-- wrapper which
tries to provide STL wrappers which requires and uses O(1) 
tail operations.)  You can not track the tail unless you only
use non g_list_* operations and never pass it to out to 
any other part of the system.  

Unless a large group of programmers can convince the glib 
crew otherwise, you should avoid append and never count on being able 
to cache the end.  I spent enough time and effort but failed.


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]