[gtk-list] sort-functions for GList and GSList

[Sven Over <sven over ob kamp net>]

Hello!

My name is Sven Over, I am from Bottrop/Germany.

This is the first time that I write to a this mailing-list as well as
that I write to a mailing-list in general.

I am using Linux since Eastern '97. Before that I used Windoze and OS/2
and I say: never again! Right now - after developing simple console
applications (or lets say "executables"...) for some months I am now
doing my very first steps in using X and gtk...

So far so good. The point of this message: I want to contribute two
useful functions to gtk, or to glib to be exact.
g_list_sort and g_slist_sort. Both sort linked lists of the glib, the
first does it with doubly linked lists, the second with singly linked.

To sort a singly linked list just do a

slist = g_slist_sort( slist, compar );

with slist being the list (GSList *slist;) and compar being the
comparing function.

e.g:
gint compar (gpointer a, gpointer b)
{
return strcmp( (char*)a, (char*)b );
}

while a and b contain the adresses provided in the data-fields of the
GSList-structure. It's rather like qsort. For doubly linked lists:

list= g_list_sort( list, compar );

You can use exactly the same compar for both g_list_sort and
g_slist_sort.

I hope you know now what it's about and how you can use it. As I don't
know who is exactly responsible for keeping and maintaining the sources
of gtk I am posting it to this mailing list.


And know the code. Unfortunately I am not familar with tools like patch
or diff....


1. add these prototypes to glib/glib.h
=== (CUT HERE) ===================================================
GList* g_list_sort        (GList   *list,
                           GCompareFunc compare_func);

GSList* g_slist_sort        (GSList   *list,
                             GCompareFunc compare_func);
=== (CUT HERE) ===================================================

2. this is for glib/glist.c
=== (CUT HERE) ===================================================
GList* g_list_sort_merge  (GList *l1, GList *l2,
                             GCompareFunc compare_func)
{
GList list, *l, *lprev;

l=&list; lprev=NULL;

while (l1&&l2)
{
        if ( compare_func(l1->data,l2->data)<0 )
        {
                l=l->next=l1;
                l->prev=lprev; lprev=l;
                l1=l1->next;
        } else {
                l=l->next=l2;
                l->prev=lprev; lprev=l;
                l2=l2->next;
        }
}
l->next=(l1) ? (l1):(l2);
l->next->prev=l;

return list.next;
}

GList* g_list_sort        (GList   *list,
                             GCompareFunc compare_func)
{
GList *l1, *l2;

if (!list) return NULL;
if (!list->next) return list;

l1=list; l2=list->next;

while ((l2=l2->next)!=NULL)
{
        if ((l2=l2->next)==NULL) break;
        l1=l1->next;
}
l2=l1->next; l1->next=NULL; // l2->prev=NULL;

return g_list_sort_merge(       g_list_sort(list,compare_func),
                                g_list_sort(l2,  compare_func),
                                compare_func );

}
=== (CUT HERE) ======================================================

3. and this is finally for glib/gslist.c
=== (CUT HERE) ======================================================
GSList* g_slist_sort_merge  (GSList *l1, GSList *l2,
                             GCompareFunc compare_func)
{
GSList list, *l;

l=&list;

while (l1&&l2)
{
        if ( compare_func(l1->data,l2->data)<0 )
        {
                l=l->next=l1;
                l1=l1->next;
        } else {
                l=l->next=l2;
                l2=l2->next;
        }
}
l->next=(l1) ? (l1):(l2);

return list.next;
}

GSList* g_slist_sort        (GSList   *list,
                             GCompareFunc compare_func)
{
GSList *l1, *l2;

if (!list) return NULL;
if (!list->next) return list;

l1=list; l2=list->next;

while ((l2=l2->next)!=NULL)
{
        if ((l2=l2->next)==NULL) break;
        l1=l1->next;
}
l2=l1->next; l1->next=NULL;

return g_slist_sort_merge(      g_slist_sort(list,compare_func),
                                g_slist_sort(l2,  compare_func),
                                compare_func );

}
=== (CUT HERE) ======================================================


And here is a sample that uses g_list_sort. Firstly it generates a list
containing a couple of elements. It dumps them, then it sorts them and
dumps them then again. After that information about the consistency of
the list is given. g_list_sort does not use the prev-field at all,
however after finished sorting the prev-field of each element points
correctly to the previous element.

testlistsort.c
=== (CUT HERE) =====================================================
/* testlistsort.c
   by Sven Over (Sun 19th Oct 1997)
   sven.over@ob.kamp.net
*/

#include <stdio.h>
#include <stdlib.h>
#include <gtk/gtk.h>

GList *list;

void func(gpointer data, gpointer user_data)
{
printf("%p %p - %s\n",data,user_data, (char*) data);
return ;
}

/* this compar sorts alphabetically case-sensitive */
gint compar(gpointer a, gpointer b)
{ return strcasecmp( (char*)a, (char*)b ); }

/* use the following instead to sort by length:
gint compar(gpointer a, gpointer b)
{ return strlen( (char*)a )-strlen( (char*)b ); }
*/

int main(int argc, char *argv[])
{
list=g_list_alloc();

list->data="zTEST 0";
g_list_append(list,(gpointer) "Test 1");
g_list_append(list,(gpointer) "Test 2");
g_list_append(list,(gpointer) "Test 3");
g_list_append(list,(gpointer) "Test 4");
g_list_append(list,(gpointer) "another test");
g_list_append(list,(gpointer) "---*---");
g_list_append(list,(gpointer) " 1");
g_list_append(list,(gpointer) " 2");
g_list_append(list,(gpointer) " 3");
g_list_append(list,(gpointer) "1");
g_list_append(list,(gpointer) " 2");
g_list_append(list,(gpointer) "  3");
g_list_append(list,(gpointer) "a------> 11");
g_list_append(list,(gpointer) "b-------> 12");
g_list_append(list,(gpointer) "d--------> 13");
g_list_append(list,(gpointer) "c  -------> 14");
g_list_append(list,(gpointer) "f       ---> 15");
g_list_append(list,(gpointer) "e        ---> 16");



g_list_foreach(list,func,NULL);

puts("\nafter running g_list_sort:");

/* TRY THIS: after g_list_sort all prevs are correct again!
list->next->prev=NULL;
list->next->next->prev=NULL;
list->next->next->next->prev=NULL;
*/

list=g_list_sort(list,compar);
g_list_foreach(list,func,NULL);

puts("\nfeel free to check the consistency:");

for(;list;list=list->next)
{
printf("adr: %p   next: %p   prev: %p   data:
%p\n",list,list->next,list->prev,list->data);

if (list->next)
if (list->next->prev!=list) puts("\nnext-prev-consistency-error!!!");
}

return 0;
}
=== CUT HERE =========================================================

I hope I have been of help!

Ciao, Sven...

(that was it! My first contribution...!)