[gtk-list] Re: g_[s]list_qsort suggestion

[dramboz imaginet fr]

Tim Janik writes:

 > >     qsort( base, size, sizeof( gpointer), func);
 > >     
 > >     tmp = base;
 > >     item = list;
 > >     while ( item) {
 > >	item->data = *tmp++;
 > > 	item = item->next;
 > >     }
 > 
 > though just changing the ->data portion of all the GList structures is
 > an efficient solution, this is not always what's needed. we loose the
 > ability to hold GList pointers across g_list_qsort() invokations with this.


  Here's a fix to this problem : Instead of replacing the ->data
field of GLists, I changed the ->next and ->prev fields to 
restore the order of the list so that the relation between
a GList pointer and its associated data is not broken.
 
  I've also changed the prototype for this function :
it returns an integer equal to 1 if the list was 
sorted and 0 otherwise. I thinks it's better like that
since this function doesn't allocate or free any "item"
in the list.


/* Headers */
typedef gint (*GQSortFunc) ( const GList **item1,
			     const GList **item2); 

gint g_list_qsort  ( GList *list,  GQSortFunc func);

/* Implementation */

typedef gint (*QSortFunc) ( const void *p1,
			    const void *p2);

gint
g_list_qsort( GList *list, GQSortFunc func) {
    GList *item;
    GList **tmp;
    gpointer *base;
    guint size;

    g_return_val_if_fail( list != NULL, FALSE);
    g_return_val_if_fail( func != NULL, FALSE);

    size = g_list_length( list);

    base = g_malloc( 2+size*sizeof( GList*));
    g_return_val_if_fail( base != NULL, FALSE);
	
    tmp = (GList**) base;
    item = list;
    *tmp++ = NULL;
    while ( item) {
	*tmp++ = item;
	item = item->next;
    }
    *tmp = NULL;

    qsort( base + 1, size, sizeof( gpointer), (QSortFunc) func);
    
    tmp  = (GList**) base + 1;
    while ( size--) {
	(*tmp)->next = *(tmp + 1);
	(*tmp)->prev = *(tmp - 1);
	tmp++;
    }
    
    g_free( base);
    
    return TRUE;
}