Re: behavior of g_list_insert_sorted()

[Manish Singh <yosh gimp org>]

On Fri, Feb 13, 1998 at 01:32:43PM -0500, Owen Taylor wrote:
> 
> Marc Ewing <marc@redhat.com> writes:
> 
> > The way g_list_insert_sorted() interprets the results of the compare
> > function seem non-intuitive to me.  From looking at glist.c it
> > appears that if the compare function returns 0, the data is not
> > inserted into the list at all.  "Standard" compare function
> > behavior (ie, those used for qsort and bsearch) is to return 0
> > if the elements are equal.
> > 
> > This is either a bug in g_list_insert_sorted(), or there is an
> > unstated "if the element is already in the list it won't be added"
> > behavior.
> 
> Besides the non-standard part, there is another problem with this
> behavior - you can't tell if the item got inserted or not. (And
> thus, unless you are inserting ints casted to gpointer, you
> risk leaking memory).
> 
> I'd say we should change g_list_insert_sorted to act "normally".
> If someone really needs the unique behavior, we could add another
> function
> 
>   gboolean g_list_insert_sorted_uniq (GList     **list, 
>                                      gpointer     data,
>                                      GCompareFunc func);
> 
> or
> 
>   GList *g_list_insert_sorted_uniq (GList       *list, 
>                                     gpointer     data,
>                                     GCompareFunc func,
>                                     gboolean    *inserted);
> 
> But this probably can be left out until someone asks for it.
> 
> > Any thoughts on this?  (I notice that g_list_insert_sorted() isn't
> > used anywhere in gtk, gimp, or gnome, so I guess nobody has run
> > across this before).
> 
> Looking at the ChangeLog:
> 
> Wed Jan  7 02:14:30 PST 1998 Manish Singh <yosh@gimp.org>
> 
>         * glib/glib.h
>         * glib/glist.c
>         * glib/gslist.c
>         * glib/testglib.c: Added g_[s]list_insert_sorted function
>         and appropriate tests in testglib
> 
> So I assume Yosh had some use for it in mind. Perhaps he'll 
> enlighten us on the original intent.

Current CVS gimp uses it, since I replaced app/linked.[ch] with GSLists.
There was insertion sort code duplicated 3 times.

The current behavior duplicates what used to be in app/text_tool.c in
text_insert_field. I'm not sure if it was done for a reason though...

Anyway, yeah, your comments make sense, and changing the sort functions
to "normal" behavior won't break the brushes and patterns stuff. I'll look
into the text_tool stuff later, but if someone wants to fix the sort
stuff, go right ahead.

-Yosh