Re: GList changes

[Owen Taylor <otaylor redhat com>]

Karl Nelson <kenelson@ece.ucdavis.edu> writes:

> > On Tue, 10 Aug 1999, Karl Nelson wrote:
> > 
> > > 
> > > These functions simplify the 3 cases of insert to 2, and 
> > > allow the user to not need to deal with head and iter at
> > > the same time.
> > > 
> > > New functions 
> > >   g_list_insert_link(GList *head,gpointer data,GList* iter); 
> > >   g_list_insert_after_link(GList *head,gpointer data,GList* iter); 
> > > 
> > > The other functions are converted to use these.
> > 
> > hi karl.
> > 
> > first off, i couldn't apply your patch to either glib-1-2 nor HEAD,
> > some hunks failed both trees.
> 
> Hmm.  They ere both taken from head.  It seems most likely that
> my mailer killed something when I tried to include it in the 
> message.  

Without even context diffs, it's pretty hard to figure
out what is going on or read the diffs. ;-)
 
> > on actuall matters, i'm not exactly sure what functionality you want
> > to provide, especially why you proposed addition of two functions.
> > if we want to provide an interface for random insertion, relative
> > to specific list nodes, we should probably follow the GNode example:
> 
> I was just trying to make seperate the head of the list argument
> from the iterator to which the insertion should occur.  It makes
> some code much more understandable if the head and iterator are
> not the same.  Especially the case of a tail insertion where
> the tail must be kept.  (C++ iterators)
 
Is there a difference between what you want and 
what Tim proposed? I don't really see how Tim's
interfaces confuse the head and "iterator".
But very possibly, I don't understand what
you mean by "iterator" here.
 
> > 
> > GNode*   g_node_insert_before   (GNode            *parent,
> >                                  GNode            *sibling,
> >                                  GNode            *node);
> > 
> > for GList and GSList this would pretty much be:
> > 
> > GSList* g_slist_insert_before        (GSList        *slist,
> >                                       GSList        *sibling,
> >                                       gpointer       data);
> > GList*  g_list_insert_before         (GList         *list,
> >                                       GList         *sibling,
> >                                       gpointer       data);
> > GSList* g_slist_insert_link_before   (GSList        *slist,
> >                                       GSList        *sibling,
> >                                       GSList        *new_node);
> > GList*  g_list_insert_link_before    (GList         *list,
> >                                       GList         *sibling,
> >                                       GList         *new_node);
> 
> Renamed as such.  The name _link was added because of the 
> function named remove_link.  STL uses seperate words for the 
> concepts (erase and remove) so I was trying to follow the convention
> of glib as I read it.
> 
> > also, changing the implementation of the existing insertion functions
> > in terms of the new sibling-relative-insertion variants is not neccessary,
> > this just imposes an extra function indirection (performance impact)
> > and the existing implementation are probably better optimized for the
> > specific cases (i did actually go through the implementations in Dec 97
> > to optimize them as much as possible).
> 
> Well, I am not sure that is the impact of the changes.  The
> code certianly became cleaner and cases folded on top, but I
> will let you judge for yourself.  It is certianly not necessary
> to fold the other cases in.

If I was writing the code in an app, I would certainly
make other calls wrappers for g_[s]list_insert_[before/after]. 
For GLib, it's more of a close call, since it is code that needs
only to be written once, and performance is a big factor for GTK+.

But for cases where the difference is _only_ the extra
function call overhead, then I think we should fold
the calls. In fact, if function call overhead is a big concern, 
we could always make a statically inline _g_list_insert_before
and make everything call that. [ That does assume
that the function isn't complex enough to prevent
it from being inlined. ]
 
> > FYI, i have appended implementations of g_slist_insert_before() and
> > g_list_insert_before() to this mail, they can easily be adapted for the
> > insert_link case. you can also find them in the beast module in
> > beast/bse/glib-extra.c, i intend to merge most of that stuff after more
> > thorough testing and optimization into glib HEAD.
> 
> Mine was exactly the same as what you included below optimized
> for code size. (differed only on case of tail insertion where
> tracing through list dominates over checks.)
> 
> Since you were already adding the functionality that I was
> feel free to use either version.  I would also
> pefer having both a before and after version as it 
> simplifies list wrapping.  
> 
> (ie.  I can do this
> 
>   GList *list,*last;
> 
>   ...
>  
>   list = g_list_insert_after (list, last=g_list_last(list), data);
>   /* do something with last like make more insertions */
>   
> which is what the patch was for.  Without it the same concept 
> ends up written as 
> 
>   GList *list,*last;
> 
>   last=g_list_last(list);
>   if (last == list) 
>     list=g_list_append (list, data);
>   else
>     g_list_append (last, data);
> 
> Which is less clear and multicase for what should be a simple
> action (insert to end of list).

With the insert_before() as Tim coded it, you can do:

 last = g_list_last(list);
 list = g_list_insert_before (list, last->next, data);

Because the code takes

  insert_before(NULL) => append.

Admittedly, the above looks confusingly like buggy code
to the casual reader, and I'd be tempted to put
a insert_after() in for that reason.

Regards,
                                        Owen