Patch from David Benson <daveb@idealab.com> to add user_data support to

Mon Nov 20 18:55:17 2000  Jonathan Blandford  <jrb@redhat.com>

	* gtree.[hc]: Patch from David Benson <daveb@idealab.com> to add
	user_data support to gtree functions.

Mon Nov 13 18:35:52 2000  Jonathan Blandford  <jrb@redhat.com>

	* gtypes.h (GCompareFuncData): new func type to let you use user
	data when comparing nodes.

	* gslist.c (g_list_sort_with_data): new function to sort with
	user_data.

	* glist.c (g_list_sort_with_data): new function to sort with
	user_data.

	* garray.[ch]: Added convenience functions to sort arrays.

34 files changed, 1584 insertions, 442 deletions

diff --git a/ChangeLog b/ChangeLog
index c01c529f7..cd91325b2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,21 @@
+Mon Nov 20 18:55:17 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtree.[hc]: Patch from David Benson <daveb@idealab.com> to add
+	user_data support to gtree functions.
+
+Mon Nov 13 18:35:52 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtypes.h (GCompareFuncData): new func type to let you use user
+	data when comparing nodes.
+
+	* gslist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* glist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* garray.[ch]: Added convenience functions to sort arrays.
+
 2000-11-16  Havoc Pennington  <hp@redhat.com>
 
 	* guniprop.c (g_unichar_isspace): Use a switch here, maybe helps 
diff --git a/ChangeLog.pre-2-0 b/ChangeLog.pre-2-0
index c01c529f7..cd91325b2 100644
--- a/ChangeLog.pre-2-0
+++ b/ChangeLog.pre-2-0
@@ -1,3 +1,21 @@
+Mon Nov 20 18:55:17 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtree.[hc]: Patch from David Benson <daveb@idealab.com> to add
+	user_data support to gtree functions.
+
+Mon Nov 13 18:35:52 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtypes.h (GCompareFuncData): new func type to let you use user
+	data when comparing nodes.
+
+	* gslist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* glist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* garray.[ch]: Added convenience functions to sort arrays.
+
 2000-11-16  Havoc Pennington  <hp@redhat.com>
 
 	* guniprop.c (g_unichar_isspace): Use a switch here, maybe helps 
diff --git a/ChangeLog.pre-2-10 b/ChangeLog.pre-2-10
index c01c529f7..cd91325b2 100644
--- a/ChangeLog.pre-2-10
+++ b/ChangeLog.pre-2-10
@@ -1,3 +1,21 @@
+Mon Nov 20 18:55:17 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtree.[hc]: Patch from David Benson <daveb@idealab.com> to add
+	user_data support to gtree functions.
+
+Mon Nov 13 18:35:52 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtypes.h (GCompareFuncData): new func type to let you use user
+	data when comparing nodes.
+
+	* gslist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* glist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* garray.[ch]: Added convenience functions to sort arrays.
+
 2000-11-16  Havoc Pennington  <hp@redhat.com>
 
 	* guniprop.c (g_unichar_isspace): Use a switch here, maybe helps 
diff --git a/ChangeLog.pre-2-12 b/ChangeLog.pre-2-12
index c01c529f7..cd91325b2 100644
--- a/ChangeLog.pre-2-12
+++ b/ChangeLog.pre-2-12
@@ -1,3 +1,21 @@
+Mon Nov 20 18:55:17 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtree.[hc]: Patch from David Benson <daveb@idealab.com> to add
+	user_data support to gtree functions.
+
+Mon Nov 13 18:35:52 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtypes.h (GCompareFuncData): new func type to let you use user
+	data when comparing nodes.
+
+	* gslist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* glist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* garray.[ch]: Added convenience functions to sort arrays.
+
 2000-11-16  Havoc Pennington  <hp@redhat.com>
 
 	* guniprop.c (g_unichar_isspace): Use a switch here, maybe helps 
diff --git a/ChangeLog.pre-2-2 b/ChangeLog.pre-2-2
index c01c529f7..cd91325b2 100644
--- a/ChangeLog.pre-2-2
+++ b/ChangeLog.pre-2-2
@@ -1,3 +1,21 @@
+Mon Nov 20 18:55:17 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtree.[hc]: Patch from David Benson <daveb@idealab.com> to add
+	user_data support to gtree functions.
+
+Mon Nov 13 18:35:52 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtypes.h (GCompareFuncData): new func type to let you use user
+	data when comparing nodes.
+
+	* gslist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* glist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* garray.[ch]: Added convenience functions to sort arrays.
+
 2000-11-16  Havoc Pennington  <hp@redhat.com>
 
 	* guniprop.c (g_unichar_isspace): Use a switch here, maybe helps 
diff --git a/ChangeLog.pre-2-4 b/ChangeLog.pre-2-4
index c01c529f7..cd91325b2 100644
--- a/ChangeLog.pre-2-4
+++ b/ChangeLog.pre-2-4
@@ -1,3 +1,21 @@
+Mon Nov 20 18:55:17 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtree.[hc]: Patch from David Benson <daveb@idealab.com> to add
+	user_data support to gtree functions.
+
+Mon Nov 13 18:35:52 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtypes.h (GCompareFuncData): new func type to let you use user
+	data when comparing nodes.
+
+	* gslist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* glist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* garray.[ch]: Added convenience functions to sort arrays.
+
 2000-11-16  Havoc Pennington  <hp@redhat.com>
 
 	* guniprop.c (g_unichar_isspace): Use a switch here, maybe helps 
diff --git a/ChangeLog.pre-2-6 b/ChangeLog.pre-2-6
index c01c529f7..cd91325b2 100644
--- a/ChangeLog.pre-2-6
+++ b/ChangeLog.pre-2-6
@@ -1,3 +1,21 @@
+Mon Nov 20 18:55:17 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtree.[hc]: Patch from David Benson <daveb@idealab.com> to add
+	user_data support to gtree functions.
+
+Mon Nov 13 18:35:52 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtypes.h (GCompareFuncData): new func type to let you use user
+	data when comparing nodes.
+
+	* gslist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* glist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* garray.[ch]: Added convenience functions to sort arrays.
+
 2000-11-16  Havoc Pennington  <hp@redhat.com>
 
 	* guniprop.c (g_unichar_isspace): Use a switch here, maybe helps 
diff --git a/ChangeLog.pre-2-8 b/ChangeLog.pre-2-8
index c01c529f7..cd91325b2 100644
--- a/ChangeLog.pre-2-8
+++ b/ChangeLog.pre-2-8
@@ -1,3 +1,21 @@
+Mon Nov 20 18:55:17 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtree.[hc]: Patch from David Benson <daveb@idealab.com> to add
+	user_data support to gtree functions.
+
+Mon Nov 13 18:35:52 2000  Jonathan Blandford  <jrb@redhat.com>
+
+	* gtypes.h (GCompareFuncData): new func type to let you use user
+	data when comparing nodes.
+
+	* gslist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* glist.c (g_list_sort_with_data): new function to sort with
+	user_data. 
+
+	* garray.[ch]: Added convenience functions to sort arrays.
+
 2000-11-16  Havoc Pennington  <hp@redhat.com>
 
 	* guniprop.c (g_unichar_isspace): Use a switch here, maybe helps 
diff --git a/Makefile.am b/Makefile.am
index 9c436a630..172b44896 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -66,6 +66,7 @@ libglib_1_3_la_SOURCES = 	\
 	gmessages.c		\
 	gnode.c			\
 	gprimes.c		\
+	gqsort.c		\
 	gqueue.c		\
 	grel.c			\
 	grand.c			\
@@ -115,6 +116,7 @@ glibinclude_HEADERS =   \
 	gmessages.h	\
 	gnode.h		\
 	gprimes.h	\
+	gqsort.h	\
 	gquark.h	\
 	gqueue.h	\
 	grand.h		\
diff --git a/garray.c b/garray.c
index 50cfac27e..7bcb2201e 100644
--- a/garray.c
+++ b/garray.c
@@ -29,6 +29,7 @@
  */
 
 #include <string.h>
+#include <stdlib.h>
 #include "glib.h"
 
 
@@ -264,6 +265,39 @@ g_array_remove_index_fast (GArray* farray,
   return farray;
 }
 
+void
+g_array_sort (GArray       *farray,
+	      GCompareFunc  compare_func)
+{
+  GRealArray *array = (GRealArray*) farray;
+
+  g_return_if_fail (array != NULL);
+  g_return_if_fail (array->data != NULL);
+
+  qsort (array->data,
+	 array->len,
+	 array->elt_size,
+	 compare_func);
+}
+
+void
+g_array_sort_with_data (GArray           *farray,
+			GCompareFuncData  compare_func,
+			gpointer          user_data)
+{
+  GRealArray *array = (GRealArray*) farray;
+
+  g_return_if_fail (array != NULL);
+  g_return_if_fail (array->data != NULL);
+
+  g_qsort_with_data (array->data,
+		     array->len,
+		     array->elt_size,
+		     compare_func,
+		     user_data);
+}
+
+
 static gint
 g_nearest_pow (gint num)
 {
@@ -527,6 +561,34 @@ g_ptr_array_add (GPtrArray* farray,
   array->pdata[array->len++] = data;
 }
 
+void
+g_ptr_array_sort (GPtrArray    *array,
+		  GCompareFunc  compare_func)
+{
+  g_return_if_fail (array != NULL);
+  g_return_if_fail (array->pdata != NULL);
+
+  qsort (array->pdata,
+	 array->len,
+	 sizeof (gpointer),
+	 compare_func);
+}
+
+void
+g_ptr_array_sort_with_data (GPtrArray        *array,
+			    GCompareFuncData  compare_func,
+			    gpointer          user_data)
+{
+  g_return_if_fail (array != NULL);
+  g_return_if_fail (array->pdata != NULL);
+
+  g_qsort_with_data (array->pdata,
+		     array->len,
+		     sizeof (gpointer),
+		     compare_func,
+		     user_data);
+}
+
 /* Byte arrays 
  */
 
@@ -581,9 +643,24 @@ GByteArray* g_byte_array_remove_index (GByteArray *array,
 }
 
 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
-						   guint index)
+					    guint index)
 {
   g_array_remove_index_fast((GArray*) array, index);
 
   return array;
 }
+
+void
+g_byte_array_sort (GByteArray   *array,
+		   GCompareFunc  compare_func)
+{
+  g_array_sort ((GArray *) array, compare_func);
+}
+
+void
+g_byte_array_sort_with_data (GByteArray       *array,
+			     GCompareFuncData  compare_func,
+			     gpointer          user_data)
+{
+  g_array_sort_with_data ((GArray *) array, compare_func, user_data);
+}
diff --git a/garray.h b/garray.h
index 5ea9de6d5..4359c88ac 100644
--- a/garray.h
+++ b/garray.h
@@ -63,75 +63,92 @@ struct _GPtrArray
 #define g_array_insert_val(a,i,v) g_array_insert_vals (a, i, &v, 1)
 #define g_array_index(a,t,i)      (((t*) (a)->data) [(i)])
 
-GArray* g_array_new	          (gboolean	    zero_terminated,
-				   gboolean	    clear,
-				   guint	    element_size);
-GArray* g_array_sized_new         (gboolean	    zero_terminated,
-				   gboolean	    clear,
-				   guint	    element_size,
-				   guint            reserved_size);
-gchar*  g_array_free	          (GArray	   *array,
-				   gboolean	    free_segment);
-GArray* g_array_append_vals       (GArray	   *array,
-				   gconstpointer    data,
-				   guint	    len);
-GArray* g_array_prepend_vals      (GArray	   *array,
-				   gconstpointer    data,
-				   guint	    len);
-GArray* g_array_insert_vals       (GArray          *array,
-				   guint            index,
-				   gconstpointer    data,
-				   guint            len);
-GArray* g_array_set_size          (GArray	   *array,
-				   guint	    length);
-GArray* g_array_remove_index	  (GArray	   *array,
-				   guint	    index);
-GArray* g_array_remove_index_fast (GArray	   *array,
-				   guint	    index);
+GArray* g_array_new               (gboolean          zero_terminated,
+				   gboolean          clear,
+				   guint             element_size);
+GArray* g_array_sized_new         (gboolean          zero_terminated,
+				   gboolean          clear,
+				   guint             element_size,
+				   guint             reserved_size);
+gchar*  g_array_free              (GArray           *array,
+				   gboolean          free_segment);
+GArray* g_array_append_vals       (GArray           *array,
+				   gconstpointer     data,
+				   guint             len);
+GArray* g_array_prepend_vals      (GArray           *array,
+				   gconstpointer     data,
+				   guint             len);
+GArray* g_array_insert_vals       (GArray           *array,
+				   guint             index,
+				   gconstpointer     data,
+				   guint             len);
+GArray* g_array_set_size          (GArray           *array,
+				   guint             length);
+GArray* g_array_remove_index      (GArray           *array,
+				   guint             index);
+GArray* g_array_remove_index_fast (GArray           *array,
+				   guint             index);
+void    g_array_sort              (GArray           *array,
+				   GCompareFunc      compare_func);
+void    g_array_sort_with_data    (GArray           *array,
+				   GCompareFuncData  compare_func,
+				   gpointer          user_data);
 
 /* Resizable pointer array.  This interface is much less complicated
  * than the above.  Add appends appends a pointer.  Remove fills any
  * cleared spot and shortens the array. remove_fast will again distort
  * order.  
  */
-#define	    g_ptr_array_index(array,index) (array->pdata)[index]
-GPtrArray*  g_ptr_array_new		   (void);
-GPtrArray*  g_ptr_array_sized_new	   (guint        reserved_size);
-gpointer*   g_ptr_array_free		   (GPtrArray	*array,
-					    gboolean	 free_seg);
-void	    g_ptr_array_set_size	   (GPtrArray	*array,
-					    gint	 length);
-gpointer    g_ptr_array_remove_index	   (GPtrArray	*array,
-					    guint	 index);
-gpointer    g_ptr_array_remove_index_fast  (GPtrArray	*array,
-					    guint	 index);
-gboolean    g_ptr_array_remove		   (GPtrArray	*array,
-					    gpointer	 data);
-gboolean    g_ptr_array_remove_fast        (GPtrArray	*array,
-					    gpointer	 data);
-void	    g_ptr_array_add		   (GPtrArray	*array,
-					    gpointer	 data);
+#define    g_ptr_array_index(array,index) (array->pdata)[index]
+GPtrArray* g_ptr_array_new                (void);
+GPtrArray* g_ptr_array_sized_new          (guint             reserved_size);
+gpointer*  g_ptr_array_free               (GPtrArray        *array,
+					   gboolean          free_seg);
+void       g_ptr_array_set_size           (GPtrArray        *array,
+					   gint              length);
+gpointer   g_ptr_array_remove_index       (GPtrArray        *array,
+					   guint             index);
+gpointer   g_ptr_array_remove_index_fast  (GPtrArray        *array,
+					   guint             index);
+gboolean   g_ptr_array_remove             (GPtrArray        *array,
+					   gpointer          data);
+gboolean   g_ptr_array_remove_fast        (GPtrArray        *array,
+					   gpointer          data);
+void       g_ptr_array_add                (GPtrArray        *array,
+					   gpointer          data);
+void       g_ptr_array_sort               (GPtrArray        *array,
+					   GCompareFunc      compare_func);
+void       g_ptr_array_sort_with_data     (GPtrArray        *array,
+					   GCompareFuncData  compare_func,
+					   gpointer          user_data);
+
 
 /* Byte arrays, an array of guint8.  Implemented as a GArray,
  * but type-safe.
  */
 
-GByteArray* g_byte_array_new	           (void);
-GByteArray* g_byte_array_sized_new	   (guint        reserved_size);
-guint8*	    g_byte_array_free	           (GByteArray	 *array,
-					    gboolean	  free_segment);
-GByteArray* g_byte_array_append	           (GByteArray	 *array,
-					    const guint8 *data,
-					    guint	  len);
-GByteArray* g_byte_array_prepend           (GByteArray	 *array,
-					    const guint8 *data,
-					    guint	  len);
-GByteArray* g_byte_array_set_size          (GByteArray	 *array,
-					    guint	  length);
-GByteArray* g_byte_array_remove_index	   (GByteArray	 *array,
-					    guint	  index);
-GByteArray* g_byte_array_remove_index_fast (GByteArray	 *array,
-					    guint	  index);
+GByteArray* g_byte_array_new               (void);
+GByteArray* g_byte_array_sized_new         (guint             reserved_size);
+guint8*     g_byte_array_free              (GByteArray       *array,
+					    gboolean          free_segment);
+GByteArray* g_byte_array_append            (GByteArray       *array,
+					    const guint8     *data,
+					    guint             len);
+GByteArray* g_byte_array_prepend           (GByteArray       *array,
+					    const guint8     *data,
+					    guint             len);
+GByteArray* g_byte_array_set_size          (GByteArray       *array,
+					    guint             length);
+GByteArray* g_byte_array_remove_index      (GByteArray       *array,
+					    guint             index);
+GByteArray* g_byte_array_remove_index_fast (GByteArray       *array,
+					    guint             index);
+void        g_byte_array_sort              (GByteArray       *array,
+					    GCompareFunc      compare_func);
+void        g_byte_array_sort_with_data    (GByteArray       *array,
+					    GCompareFuncData  compare_func,
+					    gpointer          user_data);
+
 
 G_END_DECLS
 
diff --git a/glib.h b/glib.h
index 68f9ee900..b85bac04e 100644
--- a/glib.h
+++ b/glib.h
@@ -49,6 +49,7 @@
 #include <gmessages.h>
 #include <gnode.h>
 #include <gprimes.h>
+#include <gqsort.h>
 #include <gquark.h>
 #include <gqueue.h>
 #include <grand.h>
diff --git a/glib/Makefile.am b/glib/Makefile.am
index 9c436a630..172b44896 100644
--- a/glib/Makefile.am
+++ b/glib/Makefile.am
@@ -66,6 +66,7 @@ libglib_1_3_la_SOURCES = 	\
 	gmessages.c		\
 	gnode.c			\
 	gprimes.c		\
+	gqsort.c		\
 	gqueue.c		\
 	grel.c			\
 	grand.c			\
@@ -115,6 +116,7 @@ glibinclude_HEADERS =   \
 	gmessages.h	\
 	gnode.h		\
 	gprimes.h	\
+	gqsort.h	\
 	gquark.h	\
 	gqueue.h	\
 	grand.h		\
diff --git a/glib/garray.c b/glib/garray.c
index 50cfac27e..7bcb2201e 100644
--- a/glib/garray.c
+++ b/glib/garray.c
@@ -29,6 +29,7 @@
  */
 
 #include <string.h>
+#include <stdlib.h>
 #include "glib.h"
 
 
@@ -264,6 +265,39 @@ g_array_remove_index_fast (GArray* farray,
   return farray;
 }
 
+void
+g_array_sort (GArray       *farray,
+	      GCompareFunc  compare_func)
+{
+  GRealArray *array = (GRealArray*) farray;
+
+  g_return_if_fail (array != NULL);
+  g_return_if_fail (array->data != NULL);
+
+  qsort (array->data,
+	 array->len,
+	 array->elt_size,
+	 compare_func);
+}
+
+void
+g_array_sort_with_data (GArray           *farray,
+			GCompareFuncData  compare_func,
+			gpointer          user_data)
+{
+  GRealArray *array = (GRealArray*) farray;
+
+  g_return_if_fail (array != NULL);
+  g_return_if_fail (array->data != NULL);
+
+  g_qsort_with_data (array->data,
+		     array->len,
+		     array->elt_size,
+		     compare_func,
+		     user_data);
+}
+
+
 static gint
 g_nearest_pow (gint num)
 {
@@ -527,6 +561,34 @@ g_ptr_array_add (GPtrArray* farray,
   array->pdata[array->len++] = data;
 }
 
+void
+g_ptr_array_sort (GPtrArray    *array,
+		  GCompareFunc  compare_func)
+{
+  g_return_if_fail (array != NULL);
+  g_return_if_fail (array->pdata != NULL);
+
+  qsort (array->pdata,
+	 array->len,
+	 sizeof (gpointer),
+	 compare_func);
+}
+
+void
+g_ptr_array_sort_with_data (GPtrArray        *array,
+			    GCompareFuncData  compare_func,
+			    gpointer          user_data)
+{
+  g_return_if_fail (array != NULL);
+  g_return_if_fail (array->pdata != NULL);
+
+  g_qsort_with_data (array->pdata,
+		     array->len,
+		     sizeof (gpointer),
+		     compare_func,
+		     user_data);
+}
+
 /* Byte arrays 
  */
 
@@ -581,9 +643,24 @@ GByteArray* g_byte_array_remove_index (GByteArray *array,
 }
 
 GByteArray* g_byte_array_remove_index_fast (GByteArray *array,
-						   guint index)
+					    guint index)
 {
   g_array_remove_index_fast((GArray*) array, index);
 
   return array;
 }
+
+void
+g_byte_array_sort (GByteArray   *array,
+		   GCompareFunc  compare_func)
+{
+  g_array_sort ((GArray *) array, compare_func);
+}
+
+void
+g_byte_array_sort_with_data (GByteArray       *array,
+			     GCompareFuncData  compare_func,
+			     gpointer          user_data)
+{
+  g_array_sort_with_data ((GArray *) array, compare_func, user_data);
+}
diff --git a/glib/garray.h b/glib/garray.h
index 5ea9de6d5..4359c88ac 100644
--- a/glib/garray.h
+++ b/glib/garray.h
@@ -63,75 +63,92 @@ struct _GPtrArray
 #define g_array_insert_val(a,i,v) g_array_insert_vals (a, i, &v, 1)
 #define g_array_index(a,t,i)      (((t*) (a)->data) [(i)])
 
-GArray* g_array_new	          (gboolean	    zero_terminated,
-				   gboolean	    clear,
-				   guint	    element_size);
-GArray* g_array_sized_new         (gboolean	    zero_terminated,
-				   gboolean	    clear,
-				   guint	    element_size,
-				   guint            reserved_size);
-gchar*  g_array_free	          (GArray	   *array,
-				   gboolean	    free_segment);
-GArray* g_array_append_vals       (GArray	   *array,
-				   gconstpointer    data,
-				   guint	    len);
-GArray* g_array_prepend_vals      (GArray	   *array,
-				   gconstpointer    data,
-				   guint	    len);
-GArray* g_array_insert_vals       (GArray          *array,
-				   guint            index,
-				   gconstpointer    data,
-				   guint            len);
-GArray* g_array_set_size          (GArray	   *array,
-				   guint	    length);
-GArray* g_array_remove_index	  (GArray	   *array,
-				   guint	    index);
-GArray* g_array_remove_index_fast (GArray	   *array,
-				   guint	    index);
+GArray* g_array_new               (gboolean          zero_terminated,
+				   gboolean          clear,
+				   guint             element_size);
+GArray* g_array_sized_new         (gboolean          zero_terminated,
+				   gboolean          clear,
+				   guint             element_size,
+				   guint             reserved_size);
+gchar*  g_array_free              (GArray           *array,
+				   gboolean          free_segment);
+GArray* g_array_append_vals       (GArray           *array,
+				   gconstpointer     data,
+				   guint             len);
+GArray* g_array_prepend_vals      (GArray           *array,
+				   gconstpointer     data,
+				   guint             len);
+GArray* g_array_insert_vals       (GArray           *array,
+				   guint             index,
+				   gconstpointer     data,
+				   guint             len);
+GArray* g_array_set_size          (GArray           *array,
+				   guint             length);
+GArray* g_array_remove_index      (GArray           *array,
+				   guint             index);
+GArray* g_array_remove_index_fast (GArray           *array,
+				   guint             index);
+void    g_array_sort              (GArray           *array,
+				   GCompareFunc      compare_func);
+void    g_array_sort_with_data    (GArray           *array,
+				   GCompareFuncData  compare_func,
+				   gpointer          user_data);
 
 /* Resizable pointer array.  This interface is much less complicated
  * than the above.  Add appends appends a pointer.  Remove fills any
  * cleared spot and shortens the array. remove_fast will again distort
  * order.  
  */
-#define	    g_ptr_array_index(array,index) (array->pdata)[index]
-GPtrArray*  g_ptr_array_new		   (void);
-GPtrArray*  g_ptr_array_sized_new	   (guint        reserved_size);
-gpointer*   g_ptr_array_free		   (GPtrArray	*array,
-					    gboolean	 free_seg);
-void	    g_ptr_array_set_size	   (GPtrArray	*array,
-					    gint	 length);
-gpointer    g_ptr_array_remove_index	   (GPtrArray	*array,
-					    guint	 index);
-gpointer    g_ptr_array_remove_index_fast  (GPtrArray	*array,
-					    guint	 index);
-gboolean    g_ptr_array_remove		   (GPtrArray	*array,
-					    gpointer	 data);
-gboolean    g_ptr_array_remove_fast        (GPtrArray	*array,
-					    gpointer	 data);
-void	    g_ptr_array_add		   (GPtrArray	*array,
-					    gpointer	 data);
+#define    g_ptr_array_index(array,index) (array->pdata)[index]
+GPtrArray* g_ptr_array_new                (void);
+GPtrArray* g_ptr_array_sized_new          (guint             reserved_size);
+gpointer*  g_ptr_array_free               (GPtrArray        *array,
+					   gboolean          free_seg);
+void       g_ptr_array_set_size           (GPtrArray        *array,
+					   gint              length);
+gpointer   g_ptr_array_remove_index       (GPtrArray        *array,
+					   guint             index);
+gpointer   g_ptr_array_remove_index_fast  (GPtrArray        *array,
+					   guint             index);
+gboolean   g_ptr_array_remove             (GPtrArray        *array,
+					   gpointer          data);
+gboolean   g_ptr_array_remove_fast        (GPtrArray        *array,
+					   gpointer          data);
+void       g_ptr_array_add                (GPtrArray        *array,
+					   gpointer          data);
+void       g_ptr_array_sort               (GPtrArray        *array,
+					   GCompareFunc      compare_func);
+void       g_ptr_array_sort_with_data     (GPtrArray        *array,
+					   GCompareFuncData  compare_func,
+					   gpointer          user_data);
+
 
 /* Byte arrays, an array of guint8.  Implemented as a GArray,
  * but type-safe.
  */
 
-GByteArray* g_byte_array_new	           (void);
-GByteArray* g_byte_array_sized_new	   (guint        reserved_size);
-guint8*	    g_byte_array_free	           (GByteArray	 *array,
-					    gboolean	  free_segment);
-GByteArray* g_byte_array_append	           (GByteArray	 *array,
-					    const guint8 *data,
-					    guint	  len);
-GByteArray* g_byte_array_prepend           (GByteArray	 *array,
-					    const guint8 *data,
-					    guint	  len);
-GByteArray* g_byte_array_set_size          (GByteArray	 *array,
-					    guint	  length);
-GByteArray* g_byte_array_remove_index	   (GByteArray	 *array,
-					    guint	  index);
-GByteArray* g_byte_array_remove_index_fast (GByteArray	 *array,
-					    guint	  index);
+GByteArray* g_byte_array_new               (void);
+GByteArray* g_byte_array_sized_new         (guint             reserved_size);
+guint8*     g_byte_array_free              (GByteArray       *array,
+					    gboolean          free_segment);
+GByteArray* g_byte_array_append            (GByteArray       *array,
+					    const guint8     *data,
+					    guint             len);
+GByteArray* g_byte_array_prepend           (GByteArray       *array,
+					    const guint8     *data,
+					    guint             len);
+GByteArray* g_byte_array_set_size          (GByteArray       *array,
+					    guint             length);
+GByteArray* g_byte_array_remove_index      (GByteArray       *array,
+					    guint             index);
+GByteArray* g_byte_array_remove_index_fast (GByteArray       *array,
+					    guint             index);
+void        g_byte_array_sort              (GByteArray       *array,
+					    GCompareFunc      compare_func);
+void        g_byte_array_sort_with_data    (GByteArray       *array,
+					    GCompareFuncData  compare_func,
+					    gpointer          user_data);
+
 
 G_END_DECLS
 
diff --git a/glib/glib.h b/glib/glib.h
index 68f9ee900..b85bac04e 100644
--- a/glib/glib.h
+++ b/glib/glib.h
@@ -49,6 +49,7 @@
 #include <gmessages.h>
 #include <gnode.h>
 #include <gprimes.h>
+#include <gqsort.h>
 #include <gquark.h>
 #include <gqueue.h>
 #include <grand.h>
diff --git a/glib/glist.c b/glib/glist.c
index 04232129a..4b5934432 100644
--- a/glib/glist.c
+++ b/glib/glist.c
@@ -596,18 +596,26 @@ g_list_insert_sorted (GList        *list,
 }
 
 static GList *
-g_list_sort_merge (GList       *l1, 
-		   GList       *l2,
-		   GCompareFunc compare_func)
+g_list_sort_merge (GList     *l1, 
+		   GList     *l2,
+		   GFunc     compare_func,
+		   gboolean  use_data,
+		   gpointer  user_data)
 {
   GList list, *l, *lprev;
+  gint cmp;
 
   l = &list; 
   lprev = NULL;
 
   while (l1 && l2)
     {
-      if (compare_func (l1->data, l2->data) < 0)
+      if (use_data)
+	cmp = ((GCompareFuncData) compare_func) (l1->data, l2->data, user_data);
+      else
+	cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
+
+      if (cmp <= 0)
         {
 	  l->next = l1;
 	  l = l->next;
@@ -631,8 +639,10 @@ g_list_sort_merge (GList       *l1,
 }
 
 GList* 
-g_list_sort (GList       *list,
-	     GCompareFunc compare_func)
+g_list_sort_real (GList    *list,
+		  GFunc     compare_func,
+		  gboolean  use_data,
+		  gpointer  user_data)
 {
   GList *l1, *l2;
   
@@ -653,9 +663,27 @@ g_list_sort (GList       *list,
   l2 = l1->next; 
   l1->next = NULL; 
 
-  return g_list_sort_merge (g_list_sort (list, compare_func),
-			    g_list_sort (l2,   compare_func),
-			    compare_func);
+  return g_list_sort_merge (g_list_sort_real (list, compare_func, use_data, user_data),
+			    g_list_sort_real (l2, compare_func, use_data, user_data),
+			    compare_func,
+			    use_data,
+			    user_data);
+}
+
+GList *
+g_list_sort (GList        *list,
+	     GCompareFunc  compare_func)
+{
+  return g_list_sort_real (list, (GFunc) compare_func, FALSE, NULL);
+			    
+}
+
+GList *
+g_list_sort_with_data (GList            *list,
+		       GCompareFuncData  compare_func,
+		       gpointer          user_data)
+{
+  return g_list_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 }
 
 GList* 
@@ -691,7 +719,8 @@ g_list_sort2 (GList       *list,
 	{
 	  dst->data = g_list_sort_merge (src->data,
 					 src->next->data,
-					 compare_func);
+					 (GFunc) compare_func,
+					 FALSE, NULL);
 	  dstprev = dst;
 	  dst = dst->next;
 	  src = src->next->next;
diff --git a/glib/glist.h b/glib/glist.h
index ec160c89d..438b89bf6 100644
--- a/glib/glist.h
+++ b/glib/glist.h
@@ -42,52 +42,56 @@ struct _GList
 
 /* Doubly linked lists
  */
-void   g_list_push_allocator    (GAllocator     *allocator);
-void   g_list_pop_allocator     (void);
-GList* g_list_alloc		(void);
-void   g_list_free		(GList		*list);
-void   g_list_free_1		(GList		*list);
-GList* g_list_append		(GList		*list,
-				 gpointer	 data);
-GList* g_list_prepend		(GList		*list,
-				 gpointer	 data);
-GList* g_list_insert		(GList		*list,
-				 gpointer	 data,
-				 gint		 position);
-GList* g_list_insert_sorted	(GList		*list,
-				 gpointer	 data,
-				 GCompareFunc	 func);
-GList* g_list_concat		(GList		*list1,
-				 GList		*list2);
-GList* g_list_remove		(GList		*list,
-				 gconstpointer	 data);
-GList* g_list_remove_link	(GList		*list,
-				 GList		*llink);
-GList* g_list_delete_link     	(GList		*list,
-				 GList		*link);
-GList* g_list_reverse		(GList		*list);
-GList* g_list_copy		(GList		*list);
-GList* g_list_nth		(GList		*list,
-				 guint		 n);
-GList* g_list_find		(GList		*list,
-				 gconstpointer	 data);
-GList* g_list_find_custom	(GList		*list,
-				 gconstpointer	 data,
-				 GCompareFunc	 func);
-gint   g_list_position		(GList		*list,
-				 GList		*llink);
-gint   g_list_index		(GList		*list,
-				 gconstpointer	 data);
-GList* g_list_last		(GList		*list);
-GList* g_list_first		(GList		*list);
-guint  g_list_length		(GList		*list);
-void   g_list_foreach		(GList		*list,
-				 GFunc		 func,
-				 gpointer	 user_data);
-GList* g_list_sort              (GList          *list,
-		                 GCompareFunc    compare_func);
-gpointer g_list_nth_data	(GList		*list,
-				 guint		 n);
+void     g_list_push_allocator (GAllocator       *allocator);
+void     g_list_pop_allocator  (void);
+GList*   g_list_alloc          (void);
+void     g_list_free           (GList            *list);
+void     g_list_free_1         (GList            *list);
+GList*   g_list_append         (GList            *list,
+				gpointer          data);
+GList*   g_list_prepend        (GList            *list,
+				gpointer          data);
+GList*   g_list_insert         (GList            *list,
+				gpointer          data,
+				gint              position);
+GList*   g_list_insert_sorted  (GList            *list,
+				gpointer          data,
+				GCompareFunc      func);
+GList*   g_list_concat         (GList            *list1,
+				GList            *list2);
+GList*   g_list_remove         (GList            *list,
+				gconstpointer     data);
+GList*   g_list_remove_link    (GList            *list,
+				GList            *llink);
+GList*   g_list_delete_link    (GList            *list,
+				GList            *link);
+GList*   g_list_reverse        (GList            *list);
+GList*   g_list_copy           (GList            *list);
+GList*   g_list_nth            (GList            *list,
+				guint             n);
+GList*   g_list_find           (GList            *list,
+				gconstpointer     data);
+GList*   g_list_find_custom    (GList            *list,
+				gconstpointer     data,
+				GCompareFunc      func);
+gint     g_list_position       (GList            *list,
+				GList            *llink);
+gint     g_list_index          (GList            *list,
+				gconstpointer     data);
+GList*   g_list_last           (GList            *list);
+GList*   g_list_first          (GList            *list);
+guint    g_list_length         (GList            *list);
+void     g_list_foreach        (GList            *list,
+				GFunc             func,
+				gpointer          user_data);
+GList*   g_list_sort           (GList            *list,
+				GCompareFunc      compare_func);
+GList*   g_list_sort_with_data (GList            *list,
+				GCompareFuncData  compare_func,
+				gpointer          user_data);
+gpointer g_list_nth_data       (GList            *list,
+				guint             n);
+
 #define g_list_previous(list)	((list) ? (((GList *)(list))->prev) : NULL)
 #define g_list_next(list)	((list) ? (((GList *)(list))->next) : NULL)
 
diff --git a/glib/gqsort.c b/glib/gqsort.c
new file mode 100644
index 000000000..69b63637e
--- /dev/null
+++ b/glib/gqsort.c
@@ -0,0 +1,269 @@
+/* GLIB - Library of useful routines for C programming
+ * Copyright (C) 1991, 1992, 1996, 1997 Free Software Foundation, Inc.
+ * Copyright (C) 2000 Eazel, Inc.
+ * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/*
+ * This file was originally part of the GNU C Library, and was modified to allow
+ * user data to be passed in to the sorting function.
+ *
+ * Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
+ * Modified by Maciej Stachowiak (mjs@eazel.com)
+ *
+ * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
+ * file for a list of people on the GLib Team.  See the ChangeLog
+ * files for a list of changes.  These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/.  */
+
+#include <string.h>
+
+#include "glib.h"
+
+/* Byte-wise swap two items of size SIZE. */
+#define SWAP(a, b, size)						      \
+  do									      \
+    {									      \
+      register size_t __size = (size);					      \
+      register char *__a = (a), *__b = (b);				      \
+      do								      \
+	{								      \
+	  char __tmp = *__a;						      \
+	  *__a++ = *__b;						      \
+	  *__b++ = __tmp;						      \
+	} while (--__size > 0);						      \
+    } while (0)
+
+/* Discontinue quicksort algorithm when partition gets below this size.
+   This particular magic number was chosen to work best on a Sun 4/260. */
+#define MAX_THRESH 4
+
+/* Stack node declarations used to store unfulfilled partition obligations. */
+typedef struct
+{
+  char *lo;
+  char *hi;
+}
+stack_node;
+
+/* The next 4 #defines implement a very fast in-line stack abstraction. */
+#define STACK_SIZE	(8 * sizeof(unsigned long int))
+#define PUSH(low, high)	((void) ((top->lo = (low)), (top->hi = (high)), ++top))
+#define	POP(low, high)	((void) (--top, (low = top->lo), (high = top->hi)))
+#define	STACK_NOT_EMPTY	(stack < top)
+
+
+/* Order size using quicksort.  This implementation incorporates
+ * four optimizations discussed in Sedgewick:
+ *
+ * 1. Non-recursive, using an explicit stack of pointer that store the next
+ *    array partition to sort.  To save time, this maximum amount of space
+ *    required to store an array of MAX_INT is allocated on the stack.  Assuming
+ *    a 32-bit integer, this needs only 32 * sizeof(stack_node) == 136 bits.
+ *    Pretty cheap, actually.
+ *
+ * 2. Chose the pivot element using a median-of-three decision tree.  This
+ *    reduces the probability of selecting a bad pivot value and eliminates
+ *    certain * extraneous comparisons.
+ *
+ * 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving insertion
+ *    sort to order the MAX_THRESH items within each partition.  This is a big
+ *    win, since insertion sort is faster for small, mostly sorted array
+ *    segments.
+ *
+ * 4. The larger of the two sub-partitions is always pushed onto the stack
+ *    first, with the algorithm then concentrating on the smaller partition.
+ *    This *guarantees* no more than log (n) stack size is needed (actually O(1)
+ *    in this case)!
+ */
+
+void
+g_qsort_with_data (gconstpointer    pbase,
+		   gint             total_elems,
+		   size_t           size,
+		   GCompareFuncData compare_func,
+		   gpointer         user_data)
+{
+  register char *base_ptr = (char *) pbase;
+
+  /* Allocating SIZE bytes for a pivot buffer facilitates a better
+   * algorithm below since we can do comparisons directly on the pivot.
+   */
+  char *pivot_buffer = (char *) alloca (size);
+  const size_t max_thresh = MAX_THRESH * size;
+
+  g_return_if_fail (total_elems > 0);
+  g_return_if_fail (pbase != NULL);
+  g_return_if_fail (compare_func != NULL);
+
+  if (total_elems > MAX_THRESH)
+    {
+      char *lo = base_ptr;
+      char *hi = &lo[size * (total_elems - 1)];
+      /* Largest size needed for 32-bit int!!! */
+      stack_node stack[STACK_SIZE];
+      stack_node *top = stack + 1;
+
+      while (STACK_NOT_EMPTY)
+	{
+	  char *left_ptr;
+	  char *right_ptr;
+
+	  char *pivot = pivot_buffer;
+
+	  /* Select median value from among LO, MID, and HI. Rearrange
+	   * LO and HI so the three values are sorted. This lowers the
+	   * probability of picking a pathological pivot value and
+	   * skips a comparison for both the LEFT_PTR and RIGHT_PTR. */
+
+	  char *mid = lo + size * ((hi - lo) / size >> 1);
+
+	  if ((*compare_func) ((void *) mid, (void *) lo, user_data) < 0)
+	    SWAP (mid, lo, size);
+	  if ((*compare_func) ((void *) hi, (void *) mid, user_data) < 0)
+	    SWAP (mid, hi, size);
+	  else
+	    goto jump_over;
+	  if ((*compare_func) ((void *) mid, (void *) lo, user_data) < 0)
+	    SWAP (mid, lo, size);
+	jump_over:;
+	  memcpy (pivot, mid, size);
+	  pivot = pivot_buffer;
+
+	  left_ptr = lo + size;
+	  right_ptr = hi - size;
+
+	  /* Here's the famous ``collapse the walls'' section of quicksort.
+	   * Gotta like those tight inner loops!  They are the main reason
+	   * that this algorithm runs much faster than others. */
+	  do
+	    {
+	      while ((*compare_func)
+		     ((void *) left_ptr, (void *) pivot,
+		      user_data) < 0)
+		left_ptr += size;
+
+	      while ((*compare_func)
+		     ((void *) pivot, (void *) right_ptr,
+		      user_data) < 0)
+		right_ptr -= size;
+
+	      if (left_ptr < right_ptr)
+		{
+		  SWAP (left_ptr, right_ptr, size);
+		  left_ptr += size;
+		  right_ptr -= size;
+		}
+	      else if (left_ptr == right_ptr)
+		{
+		  left_ptr += size;
+		  right_ptr -= size;
+		  break;
+		}
+	    }
+	  while (left_ptr <= right_ptr);
+
+	  /* Set up pointers for next iteration.  First determine whether
+	   * left and right partitions are below the threshold size.  If so,
+	   * ignore one or both.  Otherwise, push the larger partition's
+	   * bounds on the stack and continue sorting the smaller one. */
+
+	  if ((size_t) (right_ptr - lo) <= max_thresh)
+	    {
+	      if ((size_t) (hi - left_ptr) <= max_thresh)
+		/* Ignore both small partitions. */
+		POP (lo, hi);
+	      else
+		/* Ignore small left partition. */
+		lo = left_ptr;
+	    }
+	  else if ((size_t) (hi - left_ptr) <= max_thresh)
+				/* Ignore small right partition. */
+	    hi = right_ptr;
+	  else if ((right_ptr - lo) > (hi - left_ptr))
+	    {
+				/* Push larger left partition indices. */
+	      PUSH (lo, right_ptr);
+	      lo = left_ptr;
+
+	    }
+	  else
+	    {
+				/* Push larger right partition indices. */
+	      PUSH (left_ptr, hi);
+	      hi = right_ptr;
+	    }
+	}
+    }
+
+  /* Once the BASE_PTR array is partially sorted by quicksort the rest
+   * is completely sorted using insertion sort, since this is efficient
+   * for partitions below MAX_THRESH size. BASE_PTR points to the beginning
+   * of the array to sort, and END_PTR points at the very last element in
+   * the array (*not* one beyond it!). */
+
+  {
+    char *const end_ptr = &base_ptr[size * (total_elems - 1)];
+    char *tmp_ptr = base_ptr;
+    char *thresh = MIN (end_ptr, base_ptr + max_thresh);
+    register char *run_ptr;
+
+    /* Find smallest element in first threshold and place it at the
+     * array's beginning.  This is the smallest array element,
+     * and the operation speeds up insertion sort's inner loop. */
+
+    for (run_ptr = tmp_ptr + size; run_ptr <= thresh;
+	 run_ptr +=
+	   size) if ((*compare_func) ((void *) run_ptr, (void *) tmp_ptr,
+				      user_data) < 0)
+	     tmp_ptr = run_ptr;
+
+    if (tmp_ptr != base_ptr)
+      SWAP (tmp_ptr, base_ptr, size);
+
+    /* Insertion sort, running from left-hand-side up to right-hand-side.  */
+
+    run_ptr = base_ptr + size;
+    while ((run_ptr += size) <= end_ptr)
+      {
+	tmp_ptr = run_ptr - size;
+	while ((*compare_func)
+	       ((void *) run_ptr, (void *) tmp_ptr,
+		user_data) < 0)
+	  tmp_ptr -= size;
+
+	tmp_ptr += size;
+	if (tmp_ptr != run_ptr)
+	  {
+	    char *trav;
+
+	    trav = run_ptr + size;
+	    while (--trav >= run_ptr)
+	      {
+		char c = *trav;
+		char *hi, *lo;
+
+		for (hi = lo = trav;
+		     (lo -= size) >= tmp_ptr; hi = lo)
+		  *hi = *lo;
+		*hi = c;
+	      }
+	  }
+      }
+  }
+}
diff --git a/glib/gqsort.h b/glib/gqsort.h
new file mode 100644
index 000000000..f236e04fb
--- /dev/null
+++ b/glib/gqsort.h
@@ -0,0 +1,44 @@
+ /* GLIB - Library of useful routines for C programming
+ * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/*
+ * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
+ * file for a list of people on the GLib Team.  See the ChangeLog
+ * files for a list of changes.  These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/. 
+ */
+
+
+#ifndef __G_QSORT_H__
+#define __G_QSORT_H__
+
+#include <gtypes.h>
+
+G_BEGIN_DECLS
+
+void g_qsort_with_data (gconstpointer    pbase,
+			gint             total_elems,
+			size_t           size,
+			GCompareFuncData compare_func,
+			gpointer         user_data);
+
+G_END_DECLS
+
+#endif /* __G_QSORT_H__ */
+
diff --git a/glib/gslist.c b/glib/gslist.c
index daa182278..d8cc6996a 100644
--- a/glib/gslist.c
+++ b/glib/gslist.c
@@ -580,18 +580,26 @@ g_slist_insert_sorted (GSList       *list,
     }
 }
 
-static GSList* 
-g_slist_sort_merge  (GSList      *l1, 
-		     GSList      *l2,
-		     GCompareFunc compare_func)
+static GSList *
+g_slist_sort_merge (GSList   *l1, 
+		    GSList   *l2,
+		    GFunc     compare_func,
+		    gboolean  use_data,
+		    gpointer  user_data)
 {
   GSList list, *l;
+  gint cmp;
 
   l=&list;
 
   while (l1 && l2)
     {
-      if (compare_func(l1->data,l2->data) < 0)
+      if (use_data)
+	cmp = ((GCompareFuncData) compare_func) (l1->data, l2->data, user_data);
+      else
+	cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
+
+      if (cmp <= 0)
         {
 	  l=l->next=l1;
 	  l1=l1->next;
@@ -607,9 +615,11 @@ g_slist_sort_merge  (GSList      *l1,
   return list.next;
 }
 
-GSList* 
-g_slist_sort (GSList       *list,
-	      GCompareFunc compare_func)
+static GSList *
+g_slist_sort_real (GSList   *list,
+		   GFunc     compare_func,
+		   gboolean  use_data,
+		   gpointer  user_data)
 {
   GSList *l1, *l2;
 
@@ -630,7 +640,24 @@ g_slist_sort (GSList       *list,
   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);
+  return g_slist_sort_merge (g_slist_sort_real (list, compare_func, use_data, user_data),
+			     g_slist_sort_real (l2, compare_func, use_data, user_data),
+			     compare_func,
+			     use_data,
+			     user_data);
+}
+
+GSList *
+g_slist_sort (GSList       *list,
+	      GCompareFunc  compare_func)
+{
+  return g_slist_sort_real (list, (GFunc) compare_func, FALSE, NULL);
+}
+
+GSList *
+g_slist_sort_with_data (GSList           *list,
+			GCompareFuncData  compare_func,
+			gpointer          user_data)
+{
+  return g_slist_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 }
diff --git a/glib/gslist.h b/glib/gslist.h
index 904f04418..446eab43e 100644
--- a/glib/gslist.h
+++ b/glib/gslist.h
@@ -41,54 +41,57 @@ struct _GSList
 
 /* Singly linked lists
  */
-void    g_slist_push_allocator  (GAllocator     *allocator);
-void    g_slist_pop_allocator   (void);
-GSList* g_slist_alloc		(void);
-void	g_slist_free		(GSList		*list);
-void	g_slist_free_1		(GSList		*list);
-GSList* g_slist_append		(GSList		*list,
-				 gpointer	 data);
-GSList* g_slist_prepend		(GSList		*list,
-				 gpointer	 data);
-GSList* g_slist_insert		(GSList		*list,
-				 gpointer	 data,
-				 gint		 position);
-GSList* g_slist_insert_sorted	(GSList		*list,
-				 gpointer	 data,
-				 GCompareFunc	 func);
-GSList* g_slist_insert_before   (GSList         *slist,
-				 GSList         *sibling,
-				 gpointer        data);
-GSList* g_slist_concat		(GSList		*list1,
-				 GSList		*list2);
-GSList* g_slist_remove		(GSList		*list,
-				 gconstpointer	 data);
-GSList* g_slist_remove_link	(GSList		*list,
-				 GSList		*link);
-GSList* g_slist_delete_link     (GSList         *list,
-				 GSList         *link);
-GSList* g_slist_reverse		(GSList		*list);
-GSList*	g_slist_copy		(GSList		*list);
-GSList* g_slist_nth		(GSList		*list,
-				 guint		 n);
-GSList* g_slist_find		(GSList		*list,
-				 gconstpointer	 data);
-GSList* g_slist_find_custom	(GSList		*list,
-				 gconstpointer	 data,
-				 GCompareFunc	 func);
-gint	g_slist_position	(GSList		*list,
-				 GSList		*llink);
-gint	g_slist_index		(GSList		*list,
-				 gconstpointer	 data);
-GSList* g_slist_last		(GSList		*list);
-guint	g_slist_length		(GSList		*list);
-void	g_slist_foreach		(GSList		*list,
-				 GFunc		 func,
-				 gpointer	 user_data);
-GSList*  g_slist_sort           (GSList          *list,
-		                 GCompareFunc    compare_func);
-gpointer g_slist_nth_data	(GSList		*list,
-				 guint		 n);
+void     g_slist_push_allocator (GAllocator       *allocator);
+void     g_slist_pop_allocator  (void);
+GSList*  g_slist_alloc          (void);
+void     g_slist_free           (GSList           *list);
+void     g_slist_free_1         (GSList           *list);
+GSList*  g_slist_append         (GSList           *list,
+				 gpointer          data);
+GSList*  g_slist_prepend        (GSList           *list,
+				 gpointer          data);
+GSList*  g_slist_insert         (GSList           *list,
+				 gpointer          data,
+				 gint              position);
+GSList*  g_slist_insert_sorted  (GSList           *list,
+				 gpointer          data,
+				 GCompareFunc      func);
+GSList*  g_slist_insert_before  (GSList           *slist,
+				 GSList           *sibling,
+				 gpointer          data);
+GSList*  g_slist_concat         (GSList           *list1,
+				 GSList           *list2);
+GSList*  g_slist_remove         (GSList           *list,
+				 gconstpointer     data);
+GSList*  g_slist_remove_link    (GSList           *list,
+				 GSList           *link);
+GSList*  g_slist_delete_link    (GSList           *list,
+				 GSList           *link);
+GSList*  g_slist_reverse        (GSList           *list);
+GSList*  g_slist_copy           (GSList           *list);
+GSList*  g_slist_nth            (GSList           *list,
+				 guint             n);
+GSList*  g_slist_find           (GSList           *list,
+				 gconstpointer     data);
+GSList*  g_slist_find_custom    (GSList           *list,
+				 gconstpointer     data,
+				 GCompareFunc      func);
+gint     g_slist_position       (GSList           *list,
+				 GSList           *llink);
+gint     g_slist_index          (GSList           *list,
+				 gconstpointer     data);
+GSList*  g_slist_last           (GSList           *list);
+guint    g_slist_length         (GSList           *list);
+void     g_slist_foreach        (GSList           *list,
+				 GFunc             func,
+				 gpointer          user_data);
+GSList*  g_slist_sort           (GSList           *list,
+				 GCompareFunc      compare_func);
+GSList*  g_slist_sort_with_data (GSList           *list,
+				 GCompareFuncData  compare_func,
+				 gpointer          user_data);
+gpointer g_slist_nth_data       (GSList           *list,
+				 guint             n);
 #define  g_slist_next(slist)	((slist) ? (((GSList *)(slist))->next) : NULL)
 
 G_END_DECLS
diff --git a/glib/gtree.c b/glib/gtree.c
index 23b3feda8..aeeb467dd 100644
--- a/glib/gtree.c
+++ b/glib/gtree.c
@@ -37,7 +37,8 @@ typedef struct _GTreeNode  GTreeNode;
 struct _GRealTree
 {
   GTreeNode *root;
-  GCompareFunc key_compare;
+  GCompareFuncData key_compare;
+  gpointer key_compare_data;
 };
 
 struct _GTreeNode
@@ -54,12 +55,14 @@ static GTreeNode* g_tree_node_new                   (gpointer        key,
 						     gpointer        value);
 static void       g_tree_node_destroy               (GTreeNode      *node);
 static GTreeNode* g_tree_node_insert                (GTreeNode      *node,
-						     GCompareFunc    compare,
+						     GCompareFuncData compare,
+						     gpointer        comp_data,
 						     gpointer        key,
 						     gpointer        value,
 						     gint           *inserted);
 static GTreeNode* g_tree_node_remove                (GTreeNode      *node,
-						     GCompareFunc    compare,
+						     GCompareFuncData compare,
+						     gpointer        comp_data,
 						     gconstpointer   key);
 static GTreeNode* g_tree_node_balance               (GTreeNode      *node);
 static GTreeNode* g_tree_node_remove_leftmost       (GTreeNode      *node,
@@ -69,7 +72,8 @@ static GTreeNode* g_tree_node_restore_left_balance  (GTreeNode      *node,
 static GTreeNode* g_tree_node_restore_right_balance (GTreeNode      *node,
 						     gint            old_balance);
 static gpointer   g_tree_node_lookup                (GTreeNode      *node,
-						     GCompareFunc    compare,
+						     GCompareFuncData compare,
+						     gpointer        comp_data,
 						     gconstpointer   key);
 static gint       g_tree_node_count                 (GTreeNode      *node);
 static gint       g_tree_node_pre_order             (GTreeNode      *node,
@@ -149,9 +153,8 @@ g_tree_node_destroy (GTreeNode *node)
    }
 }
 
-
-GTree*
-g_tree_new (GCompareFunc key_compare_func)
+GTree*	 g_tree_new_udata(GCompareFuncData key_compare_func,
+                          gpointer        key_compare_data)
 {
   GRealTree *rtree;
 
@@ -160,10 +163,18 @@ g_tree_new (GCompareFunc key_compare_func)
   rtree = g_new (GRealTree, 1);
   rtree->root = NULL;
   rtree->key_compare = key_compare_func;
+  rtree->key_compare_data = key_compare_data;
 
   return (GTree*) rtree;
 }
 
+GTree*
+g_tree_new (GCompareFunc key_compare_func)
+{
+  return g_tree_new_udata ((GCompareFuncData) key_compare_func, NULL);
+}
+
+
 void
 g_tree_destroy (GTree *tree)
 {
@@ -191,6 +202,7 @@ g_tree_insert (GTree    *tree,
 
   inserted = FALSE;
   rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
+				    rtree->key_compare_data,
 				    key, value, &inserted);
 }
 
@@ -204,7 +216,8 @@ g_tree_remove (GTree         *tree,
 
   rtree = (GRealTree*) tree;
 
-  rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare, key);
+  rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare,
+                                    rtree->key_compare_data, key);
 }
 
 gpointer
@@ -217,7 +230,8 @@ g_tree_lookup (GTree         *tree,
 
   rtree = (GRealTree*) tree;
 
-  return g_tree_node_lookup (rtree->root, rtree->key_compare, key);
+  return g_tree_node_lookup (rtree->root, rtree->key_compare, 
+                             rtree->key_compare_data, key);
 }
 
 void
@@ -303,11 +317,12 @@ g_tree_nnodes (GTree *tree)
 }
 
 static GTreeNode*
-g_tree_node_insert (GTreeNode    *node,
-		    GCompareFunc  compare,
-		    gpointer      key,
-		    gpointer      value,
-		    gint         *inserted)
+g_tree_node_insert (GTreeNode      *node,
+		    GCompareFuncData compare,
+		    gpointer        compare_data,
+		    gpointer        key,
+		    gpointer        value,
+		    gint           *inserted)
 {
   gint old_balance;
   gint cmp;
@@ -318,7 +333,7 @@ g_tree_node_insert (GTreeNode    *node,
       return g_tree_node_new (key, value);
     }
 
-  cmp = (* compare) (key, node->key);
+  cmp = (* compare) (key, node->key, compare_data);
   if (cmp == 0)
     {
       *inserted = FALSE;
@@ -331,7 +346,8 @@ g_tree_node_insert (GTreeNode    *node,
       if (node->left)
 	{
 	  old_balance = node->left->balance;
-	  node->left = g_tree_node_insert (node->left, compare, key, value, inserted);
+	  node->left = g_tree_node_insert (node->left, compare, compare_data,
+	                                   key, value, inserted);
 
 	  if ((old_balance != node->left->balance) && node->left->balance)
 	    node->balance -= 1;
@@ -348,7 +364,8 @@ g_tree_node_insert (GTreeNode    *node,
       if (node->right)
 	{
 	  old_balance = node->right->balance;
-	  node->right = g_tree_node_insert (node->right, compare, key, value, inserted);
+	  node->right = g_tree_node_insert (node->right, compare, compare_data,
+	                                    key, value, inserted);
 
 	  if ((old_balance != node->right->balance) && node->right->balance)
 	    node->balance += 1;
@@ -371,9 +388,10 @@ g_tree_node_insert (GTreeNode    *node,
 }
 
 static GTreeNode*
-g_tree_node_remove (GTreeNode     *node,
-		    GCompareFunc   compare,
-		    gconstpointer  key)
+g_tree_node_remove (GTreeNode      *node,
+		    GCompareFuncData compare,
+		    gpointer        compare_data,
+		    gconstpointer   key)
 {
   GTreeNode *new_root;
   gint old_balance;
@@ -382,7 +400,7 @@ g_tree_node_remove (GTreeNode     *node,
   if (!node)
     return NULL;
 
-  cmp = (* compare) (key, node->key);
+  cmp = (* compare) (key, node->key, compare_data);
   if (cmp == 0)
     {
       GTreeNode *garbage;
@@ -419,7 +437,7 @@ g_tree_node_remove (GTreeNode     *node,
       if (node->left)
 	{
 	  old_balance = node->left->balance;
-	  node->left = g_tree_node_remove (node->left, compare, key);
+	  node->left = g_tree_node_remove (node->left, compare, compare_data, key);
 	  node = g_tree_node_restore_left_balance (node, old_balance);
 	}
     }
@@ -428,7 +446,7 @@ g_tree_node_remove (GTreeNode     *node,
       if (node->right)
 	{
 	  old_balance = node->right->balance;
-	  node->right = g_tree_node_remove (node->right, compare, key);
+	  node->right = g_tree_node_remove (node->right, compare, compare_data, key);
 	  node = g_tree_node_restore_right_balance (node, old_balance);
 	}
     }
@@ -503,28 +521,29 @@ g_tree_node_restore_right_balance (GTreeNode *node,
 }
 
 static gpointer
-g_tree_node_lookup (GTreeNode     *node,
-		    GCompareFunc   compare,
-		    gconstpointer  key)
+g_tree_node_lookup (GTreeNode      *node,
+		    GCompareFuncData compare,
+		    gpointer        compare_data,
+		    gconstpointer   key)
 {
   gint cmp;
 
   if (!node)
     return NULL;
 
-  cmp = (* compare) (key, node->key);
+  cmp = (* compare) (key, node->key, compare_data);
   if (cmp == 0)
     return node->value;
 
   if (cmp < 0)
     {
       if (node->left)
-	return g_tree_node_lookup (node->left, compare, key);
+	return g_tree_node_lookup (node->left, compare, compare_data, key);
     }
   else if (cmp > 0)
     {
       if (node->right)
-	return g_tree_node_lookup (node->right, compare, key);
+	return g_tree_node_lookup (node->right, compare, compare_data, key);
     }
 
   return NULL;
diff --git a/glib/gtree.h b/glib/gtree.h
index 207d16c95..3530a6374 100644
--- a/glib/gtree.h
+++ b/glib/gtree.h
@@ -39,24 +39,28 @@ typedef gint		(*GTraverseFunc)	(gpointer	key,
 
 /* Balanced binary trees
  */
-GTree*	 g_tree_new	 (GCompareFunc	 key_compare_func);
-void	 g_tree_destroy	 (GTree		*tree);
-void	 g_tree_insert	 (GTree		*tree,
-			  gpointer	 key,
-			  gpointer	 value);
-void	 g_tree_remove	 (GTree		*tree,
-			  gconstpointer	 key);
-gpointer g_tree_lookup	 (GTree		*tree,
-			  gconstpointer	 key);
-void	 g_tree_traverse (GTree		*tree,
-			  GTraverseFunc	 traverse_func,
-			  GTraverseType	 traverse_type,
-			  gpointer	 data);
-gpointer g_tree_search	 (GTree		*tree,
-			  GCompareFunc	 search_func,
-			  gconstpointer	 data);
-gint	 g_tree_height	 (GTree		*tree);
-gint	 g_tree_nnodes	 (GTree		*tree);
+GTree*   g_tree_new           (GCompareFunc      key_compare_func);
+GTree*   g_tree_new_with_data (GCompareFuncData  key_compare_func,
+			       gpointer          user_data);
+void     g_tree_destroy       (GTree            *tree);
+void     g_tree_insert        (GTree            *tree,
+			       gpointer          key,
+			       gpointer          value);
+void     g_tree_remove        (GTree            *tree,
+			       gconstpointer     key);
+gpointer g_tree_lookup        (GTree            *tree,
+			       gconstpointer     key);
+void     g_tree_traverse      (GTree            *tree,
+			       GTraverseFunc     traverse_func,
+			       GTraverseType     traverse_type,
+			       gpointer          data);
+gpointer g_tree_search        (GTree            *tree,
+			       GCompareFunc      search_func,
+			       gconstpointer     data);
+gint     g_tree_height        (GTree            *tree);
+gint     g_tree_nnodes        (GTree            *tree);
+
+
 
 G_END_DECLS
 
diff --git a/glib/gtypes.h b/glib/gtypes.h
index 5f7d4937f..c43d322a7 100644
--- a/glib/gtypes.h
+++ b/glib/gtypes.h
@@ -69,6 +69,9 @@ typedef const void *gconstpointer;
 
 typedef gint            (*GCompareFunc)         (gconstpointer  a,
                                                  gconstpointer  b);
+typedef gint            (*GCompareFuncData)     (gconstpointer  a,
+                                                 gconstpointer  b,
+						 gpointer       user_data);
 typedef gboolean        (*GEqualFunc)           (gconstpointer  a,
                                                  gconstpointer  b);
 typedef void            (*GDestroyNotify)       (gpointer       data);
diff --git a/glist.c b/glist.c
index 04232129a..4b5934432 100644
--- a/glist.c
+++ b/glist.c
@@ -596,18 +596,26 @@ g_list_insert_sorted (GList        *list,
 }
 
 static GList *
-g_list_sort_merge (GList       *l1, 
-		   GList       *l2,
-		   GCompareFunc compare_func)
+g_list_sort_merge (GList     *l1, 
+		   GList     *l2,
+		   GFunc     compare_func,
+		   gboolean  use_data,
+		   gpointer  user_data)
 {
   GList list, *l, *lprev;
+  gint cmp;
 
   l = &list; 
   lprev = NULL;
 
   while (l1 && l2)
     {
-      if (compare_func (l1->data, l2->data) < 0)
+      if (use_data)
+	cmp = ((GCompareFuncData) compare_func) (l1->data, l2->data, user_data);
+      else
+	cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
+
+      if (cmp <= 0)
         {
 	  l->next = l1;
 	  l = l->next;
@@ -631,8 +639,10 @@ g_list_sort_merge (GList       *l1,
 }
 
 GList* 
-g_list_sort (GList       *list,
-	     GCompareFunc compare_func)
+g_list_sort_real (GList    *list,
+		  GFunc     compare_func,
+		  gboolean  use_data,
+		  gpointer  user_data)
 {
   GList *l1, *l2;
   
@@ -653,9 +663,27 @@ g_list_sort (GList       *list,
   l2 = l1->next; 
   l1->next = NULL; 
 
-  return g_list_sort_merge (g_list_sort (list, compare_func),
-			    g_list_sort (l2,   compare_func),
-			    compare_func);
+  return g_list_sort_merge (g_list_sort_real (list, compare_func, use_data, user_data),
+			    g_list_sort_real (l2, compare_func, use_data, user_data),
+			    compare_func,
+			    use_data,
+			    user_data);
+}
+
+GList *
+g_list_sort (GList        *list,
+	     GCompareFunc  compare_func)
+{
+  return g_list_sort_real (list, (GFunc) compare_func, FALSE, NULL);
+			    
+}
+
+GList *
+g_list_sort_with_data (GList            *list,
+		       GCompareFuncData  compare_func,
+		       gpointer          user_data)
+{
+  return g_list_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 }
 
 GList* 
@@ -691,7 +719,8 @@ g_list_sort2 (GList       *list,
 	{
 	  dst->data = g_list_sort_merge (src->data,
 					 src->next->data,
-					 compare_func);
+					 (GFunc) compare_func,
+					 FALSE, NULL);
 	  dstprev = dst;
 	  dst = dst->next;
 	  src = src->next->next;
diff --git a/glist.h b/glist.h
index ec160c89d..438b89bf6 100644
--- a/glist.h
+++ b/glist.h
@@ -42,52 +42,56 @@ struct _GList
 
 /* Doubly linked lists
  */
-void   g_list_push_allocator    (GAllocator     *allocator);
-void   g_list_pop_allocator     (void);
-GList* g_list_alloc		(void);
-void   g_list_free		(GList		*list);
-void   g_list_free_1		(GList		*list);
-GList* g_list_append		(GList		*list,
-				 gpointer	 data);
-GList* g_list_prepend		(GList		*list,
-				 gpointer	 data);
-GList* g_list_insert		(GList		*list,
-				 gpointer	 data,
-				 gint		 position);
-GList* g_list_insert_sorted	(GList		*list,
-				 gpointer	 data,
-				 GCompareFunc	 func);
-GList* g_list_concat		(GList		*list1,
-				 GList		*list2);
-GList* g_list_remove		(GList		*list,
-				 gconstpointer	 data);
-GList* g_list_remove_link	(GList		*list,
-				 GList		*llink);
-GList* g_list_delete_link     	(GList		*list,
-				 GList		*link);
-GList* g_list_reverse		(GList		*list);
-GList* g_list_copy		(GList		*list);
-GList* g_list_nth		(GList		*list,
-				 guint		 n);
-GList* g_list_find		(GList		*list,
-				 gconstpointer	 data);
-GList* g_list_find_custom	(GList		*list,
-				 gconstpointer	 data,
-				 GCompareFunc	 func);
-gint   g_list_position		(GList		*list,
-				 GList		*llink);
-gint   g_list_index		(GList		*list,
-				 gconstpointer	 data);
-GList* g_list_last		(GList		*list);
-GList* g_list_first		(GList		*list);
-guint  g_list_length		(GList		*list);
-void   g_list_foreach		(GList		*list,
-				 GFunc		 func,
-				 gpointer	 user_data);
-GList* g_list_sort              (GList          *list,
-		                 GCompareFunc    compare_func);
-gpointer g_list_nth_data	(GList		*list,
-				 guint		 n);
+void     g_list_push_allocator (GAllocator       *allocator);
+void     g_list_pop_allocator  (void);
+GList*   g_list_alloc          (void);
+void     g_list_free           (GList            *list);
+void     g_list_free_1         (GList            *list);
+GList*   g_list_append         (GList            *list,
+				gpointer          data);
+GList*   g_list_prepend        (GList            *list,
+				gpointer          data);
+GList*   g_list_insert         (GList            *list,
+				gpointer          data,
+				gint              position);
+GList*   g_list_insert_sorted  (GList            *list,
+				gpointer          data,
+				GCompareFunc      func);
+GList*   g_list_concat         (GList            *list1,
+				GList            *list2);
+GList*   g_list_remove         (GList            *list,
+				gconstpointer     data);
+GList*   g_list_remove_link    (GList            *list,
+				GList            *llink);
+GList*   g_list_delete_link    (GList            *list,
+				GList            *link);
+GList*   g_list_reverse        (GList            *list);
+GList*   g_list_copy           (GList            *list);
+GList*   g_list_nth            (GList            *list,
+				guint             n);
+GList*   g_list_find           (GList            *list,
+				gconstpointer     data);
+GList*   g_list_find_custom    (GList            *list,
+				gconstpointer     data,
+				GCompareFunc      func);
+gint     g_list_position       (GList            *list,
+				GList            *llink);
+gint     g_list_index          (GList            *list,
+				gconstpointer     data);
+GList*   g_list_last           (GList            *list);
+GList*   g_list_first          (GList            *list);
+guint    g_list_length         (GList            *list);
+void     g_list_foreach        (GList            *list,
+				GFunc             func,
+				gpointer          user_data);
+GList*   g_list_sort           (GList            *list,
+				GCompareFunc      compare_func);
+GList*   g_list_sort_with_data (GList            *list,
+				GCompareFuncData  compare_func,
+				gpointer          user_data);
+gpointer g_list_nth_data       (GList            *list,
+				guint             n);
+
 #define g_list_previous(list)	((list) ? (((GList *)(list))->prev) : NULL)
 #define g_list_next(list)	((list) ? (((GList *)(list))->next) : NULL)
 
diff --git a/gqsort.c b/gqsort.c
new file mode 100644
index 000000000..69b63637e
--- /dev/null
+++ b/gqsort.c
@@ -0,0 +1,269 @@
+/* GLIB - Library of useful routines for C programming
+ * Copyright (C) 1991, 1992, 1996, 1997 Free Software Foundation, Inc.
+ * Copyright (C) 2000 Eazel, Inc.
+ * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/*
+ * This file was originally part of the GNU C Library, and was modified to allow
+ * user data to be passed in to the sorting function.
+ *
+ * Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
+ * Modified by Maciej Stachowiak (mjs@eazel.com)
+ *
+ * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
+ * file for a list of people on the GLib Team.  See the ChangeLog
+ * files for a list of changes.  These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/.  */
+
+#include <string.h>
+
+#include "glib.h"
+
+/* Byte-wise swap two items of size SIZE. */
+#define SWAP(a, b, size)						      \
+  do									      \
+    {									      \
+      register size_t __size = (size);					      \
+      register char *__a = (a), *__b = (b);				      \
+      do								      \
+	{								      \
+	  char __tmp = *__a;						      \
+	  *__a++ = *__b;						      \
+	  *__b++ = __tmp;						      \
+	} while (--__size > 0);						      \
+    } while (0)
+
+/* Discontinue quicksort algorithm when partition gets below this size.
+   This particular magic number was chosen to work best on a Sun 4/260. */
+#define MAX_THRESH 4
+
+/* Stack node declarations used to store unfulfilled partition obligations. */
+typedef struct
+{
+  char *lo;
+  char *hi;
+}
+stack_node;
+
+/* The next 4 #defines implement a very fast in-line stack abstraction. */
+#define STACK_SIZE	(8 * sizeof(unsigned long int))
+#define PUSH(low, high)	((void) ((top->lo = (low)), (top->hi = (high)), ++top))
+#define	POP(low, high)	((void) (--top, (low = top->lo), (high = top->hi)))
+#define	STACK_NOT_EMPTY	(stack < top)
+
+
+/* Order size using quicksort.  This implementation incorporates
+ * four optimizations discussed in Sedgewick:
+ *
+ * 1. Non-recursive, using an explicit stack of pointer that store the next
+ *    array partition to sort.  To save time, this maximum amount of space
+ *    required to store an array of MAX_INT is allocated on the stack.  Assuming
+ *    a 32-bit integer, this needs only 32 * sizeof(stack_node) == 136 bits.
+ *    Pretty cheap, actually.
+ *
+ * 2. Chose the pivot element using a median-of-three decision tree.  This
+ *    reduces the probability of selecting a bad pivot value and eliminates
+ *    certain * extraneous comparisons.
+ *
+ * 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving insertion
+ *    sort to order the MAX_THRESH items within each partition.  This is a big
+ *    win, since insertion sort is faster for small, mostly sorted array
+ *    segments.
+ *
+ * 4. The larger of the two sub-partitions is always pushed onto the stack
+ *    first, with the algorithm then concentrating on the smaller partition.
+ *    This *guarantees* no more than log (n) stack size is needed (actually O(1)
+ *    in this case)!
+ */
+
+void
+g_qsort_with_data (gconstpointer    pbase,
+		   gint             total_elems,
+		   size_t           size,
+		   GCompareFuncData compare_func,
+		   gpointer         user_data)
+{
+  register char *base_ptr = (char *) pbase;
+
+  /* Allocating SIZE bytes for a pivot buffer facilitates a better
+   * algorithm below since we can do comparisons directly on the pivot.
+   */
+  char *pivot_buffer = (char *) alloca (size);
+  const size_t max_thresh = MAX_THRESH * size;
+
+  g_return_if_fail (total_elems > 0);
+  g_return_if_fail (pbase != NULL);
+  g_return_if_fail (compare_func != NULL);
+
+  if (total_elems > MAX_THRESH)
+    {
+      char *lo = base_ptr;
+      char *hi = &lo[size * (total_elems - 1)];
+      /* Largest size needed for 32-bit int!!! */
+      stack_node stack[STACK_SIZE];
+      stack_node *top = stack + 1;
+
+      while (STACK_NOT_EMPTY)
+	{
+	  char *left_ptr;
+	  char *right_ptr;
+
+	  char *pivot = pivot_buffer;
+
+	  /* Select median value from among LO, MID, and HI. Rearrange
+	   * LO and HI so the three values are sorted. This lowers the
+	   * probability of picking a pathological pivot value and
+	   * skips a comparison for both the LEFT_PTR and RIGHT_PTR. */
+
+	  char *mid = lo + size * ((hi - lo) / size >> 1);
+
+	  if ((*compare_func) ((void *) mid, (void *) lo, user_data) < 0)
+	    SWAP (mid, lo, size);
+	  if ((*compare_func) ((void *) hi, (void *) mid, user_data) < 0)
+	    SWAP (mid, hi, size);
+	  else
+	    goto jump_over;
+	  if ((*compare_func) ((void *) mid, (void *) lo, user_data) < 0)
+	    SWAP (mid, lo, size);
+	jump_over:;
+	  memcpy (pivot, mid, size);
+	  pivot = pivot_buffer;
+
+	  left_ptr = lo + size;
+	  right_ptr = hi - size;
+
+	  /* Here's the famous ``collapse the walls'' section of quicksort.
+	   * Gotta like those tight inner loops!  They are the main reason
+	   * that this algorithm runs much faster than others. */
+	  do
+	    {
+	      while ((*compare_func)
+		     ((void *) left_ptr, (void *) pivot,
+		      user_data) < 0)
+		left_ptr += size;
+
+	      while ((*compare_func)
+		     ((void *) pivot, (void *) right_ptr,
+		      user_data) < 0)
+		right_ptr -= size;
+
+	      if (left_ptr < right_ptr)
+		{
+		  SWAP (left_ptr, right_ptr, size);
+		  left_ptr += size;
+		  right_ptr -= size;
+		}
+	      else if (left_ptr == right_ptr)
+		{
+		  left_ptr += size;
+		  right_ptr -= size;
+		  break;
+		}
+	    }
+	  while (left_ptr <= right_ptr);
+
+	  /* Set up pointers for next iteration.  First determine whether
+	   * left and right partitions are below the threshold size.  If so,
+	   * ignore one or both.  Otherwise, push the larger partition's
+	   * bounds on the stack and continue sorting the smaller one. */
+
+	  if ((size_t) (right_ptr - lo) <= max_thresh)
+	    {
+	      if ((size_t) (hi - left_ptr) <= max_thresh)
+		/* Ignore both small partitions. */
+		POP (lo, hi);
+	      else
+		/* Ignore small left partition. */
+		lo = left_ptr;
+	    }
+	  else if ((size_t) (hi - left_ptr) <= max_thresh)
+				/* Ignore small right partition. */
+	    hi = right_ptr;
+	  else if ((right_ptr - lo) > (hi - left_ptr))
+	    {
+				/* Push larger left partition indices. */
+	      PUSH (lo, right_ptr);
+	      lo = left_ptr;
+
+	    }
+	  else
+	    {
+				/* Push larger right partition indices. */
+	      PUSH (left_ptr, hi);
+	      hi = right_ptr;
+	    }
+	}
+    }
+
+  /* Once the BASE_PTR array is partially sorted by quicksort the rest
+   * is completely sorted using insertion sort, since this is efficient
+   * for partitions below MAX_THRESH size. BASE_PTR points to the beginning
+   * of the array to sort, and END_PTR points at the very last element in
+   * the array (*not* one beyond it!). */
+
+  {
+    char *const end_ptr = &base_ptr[size * (total_elems - 1)];
+    char *tmp_ptr = base_ptr;
+    char *thresh = MIN (end_ptr, base_ptr + max_thresh);
+    register char *run_ptr;
+
+    /* Find smallest element in first threshold and place it at the
+     * array's beginning.  This is the smallest array element,
+     * and the operation speeds up insertion sort's inner loop. */
+
+    for (run_ptr = tmp_ptr + size; run_ptr <= thresh;
+	 run_ptr +=
+	   size) if ((*compare_func) ((void *) run_ptr, (void *) tmp_ptr,
+				      user_data) < 0)
+	     tmp_ptr = run_ptr;
+
+    if (tmp_ptr != base_ptr)
+      SWAP (tmp_ptr, base_ptr, size);
+
+    /* Insertion sort, running from left-hand-side up to right-hand-side.  */
+
+    run_ptr = base_ptr + size;
+    while ((run_ptr += size) <= end_ptr)
+      {
+	tmp_ptr = run_ptr - size;
+	while ((*compare_func)
+	       ((void *) run_ptr, (void *) tmp_ptr,
+		user_data) < 0)
+	  tmp_ptr -= size;
+
+	tmp_ptr += size;
+	if (tmp_ptr != run_ptr)
+	  {
+	    char *trav;
+
+	    trav = run_ptr + size;
+	    while (--trav >= run_ptr)
+	      {
+		char c = *trav;
+		char *hi, *lo;
+
+		for (hi = lo = trav;
+		     (lo -= size) >= tmp_ptr; hi = lo)
+		  *hi = *lo;
+		*hi = c;
+	      }
+	  }
+      }
+  }
+}
diff --git a/gqsort.h b/gqsort.h
new file mode 100644
index 000000000..f236e04fb
--- /dev/null
+++ b/gqsort.h
@@ -0,0 +1,44 @@
+ /* GLIB - Library of useful routines for C programming
+ * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/*
+ * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
+ * file for a list of people on the GLib Team.  See the ChangeLog
+ * files for a list of changes.  These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/. 
+ */
+
+
+#ifndef __G_QSORT_H__
+#define __G_QSORT_H__
+
+#include <gtypes.h>
+
+G_BEGIN_DECLS
+
+void g_qsort_with_data (gconstpointer    pbase,
+			gint             total_elems,
+			size_t           size,
+			GCompareFuncData compare_func,
+			gpointer         user_data);
+
+G_END_DECLS
+
+#endif /* __G_QSORT_H__ */
+
diff --git a/gslist.c b/gslist.c
index daa182278..d8cc6996a 100644
--- a/gslist.c
+++ b/gslist.c
@@ -580,18 +580,26 @@ g_slist_insert_sorted (GSList       *list,
     }
 }
 
-static GSList* 
-g_slist_sort_merge  (GSList      *l1, 
-		     GSList      *l2,
-		     GCompareFunc compare_func)
+static GSList *
+g_slist_sort_merge (GSList   *l1, 
+		    GSList   *l2,
+		    GFunc     compare_func,
+		    gboolean  use_data,
+		    gpointer  user_data)
 {
   GSList list, *l;
+  gint cmp;
 
   l=&list;
 
   while (l1 && l2)
     {
-      if (compare_func(l1->data,l2->data) < 0)
+      if (use_data)
+	cmp = ((GCompareFuncData) compare_func) (l1->data, l2->data, user_data);
+      else
+	cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
+
+      if (cmp <= 0)
         {
 	  l=l->next=l1;
 	  l1=l1->next;
@@ -607,9 +615,11 @@ g_slist_sort_merge  (GSList      *l1,
   return list.next;
 }
 
-GSList* 
-g_slist_sort (GSList       *list,
-	      GCompareFunc compare_func)
+static GSList *
+g_slist_sort_real (GSList   *list,
+		   GFunc     compare_func,
+		   gboolean  use_data,
+		   gpointer  user_data)
 {
   GSList *l1, *l2;
 
@@ -630,7 +640,24 @@ g_slist_sort (GSList       *list,
   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);
+  return g_slist_sort_merge (g_slist_sort_real (list, compare_func, use_data, user_data),
+			     g_slist_sort_real (l2, compare_func, use_data, user_data),
+			     compare_func,
+			     use_data,
+			     user_data);
+}
+
+GSList *
+g_slist_sort (GSList       *list,
+	      GCompareFunc  compare_func)
+{
+  return g_slist_sort_real (list, (GFunc) compare_func, FALSE, NULL);
+}
+
+GSList *
+g_slist_sort_with_data (GSList           *list,
+			GCompareFuncData  compare_func,
+			gpointer          user_data)
+{
+  return g_slist_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 }
diff --git a/gslist.h b/gslist.h
index 904f04418..446eab43e 100644
--- a/gslist.h
+++ b/gslist.h
@@ -41,54 +41,57 @@ struct _GSList
 
 /* Singly linked lists
  */
-void    g_slist_push_allocator  (GAllocator     *allocator);
-void    g_slist_pop_allocator   (void);
-GSList* g_slist_alloc		(void);
-void	g_slist_free		(GSList		*list);
-void	g_slist_free_1		(GSList		*list);
-GSList* g_slist_append		(GSList		*list,
-				 gpointer	 data);
-GSList* g_slist_prepend		(GSList		*list,
-				 gpointer	 data);
-GSList* g_slist_insert		(GSList		*list,
-				 gpointer	 data,
-				 gint		 position);
-GSList* g_slist_insert_sorted	(GSList		*list,
-				 gpointer	 data,
-				 GCompareFunc	 func);
-GSList* g_slist_insert_before   (GSList         *slist,
-				 GSList         *sibling,
-				 gpointer        data);
-GSList* g_slist_concat		(GSList		*list1,
-				 GSList		*list2);
-GSList* g_slist_remove		(GSList		*list,
-				 gconstpointer	 data);
-GSList* g_slist_remove_link	(GSList		*list,
-				 GSList		*link);
-GSList* g_slist_delete_link     (GSList         *list,
-				 GSList         *link);
-GSList* g_slist_reverse		(GSList		*list);
-GSList*	g_slist_copy		(GSList		*list);
-GSList* g_slist_nth		(GSList		*list,
-				 guint		 n);
-GSList* g_slist_find		(GSList		*list,
-				 gconstpointer	 data);
-GSList* g_slist_find_custom	(GSList		*list,
-				 gconstpointer	 data,
-				 GCompareFunc	 func);
-gint	g_slist_position	(GSList		*list,
-				 GSList		*llink);
-gint	g_slist_index		(GSList		*list,
-				 gconstpointer	 data);
-GSList* g_slist_last		(GSList		*list);
-guint	g_slist_length		(GSList		*list);
-void	g_slist_foreach		(GSList		*list,
-				 GFunc		 func,
-				 gpointer	 user_data);
-GSList*  g_slist_sort           (GSList          *list,
-		                 GCompareFunc    compare_func);
-gpointer g_slist_nth_data	(GSList		*list,
-				 guint		 n);
+void     g_slist_push_allocator (GAllocator       *allocator);
+void     g_slist_pop_allocator  (void);
+GSList*  g_slist_alloc          (void);
+void     g_slist_free           (GSList           *list);
+void     g_slist_free_1         (GSList           *list);
+GSList*  g_slist_append         (GSList           *list,
+				 gpointer          data);
+GSList*  g_slist_prepend        (GSList           *list,
+				 gpointer          data);
+GSList*  g_slist_insert         (GSList           *list,
+				 gpointer          data,
+				 gint              position);
+GSList*  g_slist_insert_sorted  (GSList           *list,
+				 gpointer          data,
+				 GCompareFunc      func);
+GSList*  g_slist_insert_before  (GSList           *slist,
+				 GSList           *sibling,
+				 gpointer          data);
+GSList*  g_slist_concat         (GSList           *list1,
+				 GSList           *list2);
+GSList*  g_slist_remove         (GSList           *list,
+				 gconstpointer     data);
+GSList*  g_slist_remove_link    (GSList           *list,
+				 GSList           *link);
+GSList*  g_slist_delete_link    (GSList           *list,
+				 GSList           *link);
+GSList*  g_slist_reverse        (GSList           *list);
+GSList*  g_slist_copy           (GSList           *list);
+GSList*  g_slist_nth            (GSList           *list,
+				 guint             n);
+GSList*  g_slist_find           (GSList           *list,
+				 gconstpointer     data);
+GSList*  g_slist_find_custom    (GSList           *list,
+				 gconstpointer     data,
+				 GCompareFunc      func);
+gint     g_slist_position       (GSList           *list,
+				 GSList           *llink);
+gint     g_slist_index          (GSList           *list,
+				 gconstpointer     data);
+GSList*  g_slist_last           (GSList           *list);
+guint    g_slist_length         (GSList           *list);
+void     g_slist_foreach        (GSList           *list,
+				 GFunc             func,
+				 gpointer          user_data);
+GSList*  g_slist_sort           (GSList           *list,
+				 GCompareFunc      compare_func);
+GSList*  g_slist_sort_with_data (GSList           *list,
+				 GCompareFuncData  compare_func,
+				 gpointer          user_data);
+gpointer g_slist_nth_data       (GSList           *list,
+				 guint             n);
 #define  g_slist_next(slist)	((slist) ? (((GSList *)(slist))->next) : NULL)
 
 G_END_DECLS
diff --git a/gtree.c b/gtree.c
index 23b3feda8..aeeb467dd 100644
--- a/gtree.c
+++ b/gtree.c
@@ -37,7 +37,8 @@ typedef struct _GTreeNode  GTreeNode;
 struct _GRealTree
 {
   GTreeNode *root;
-  GCompareFunc key_compare;
+  GCompareFuncData key_compare;
+  gpointer key_compare_data;
 };
 
 struct _GTreeNode
@@ -54,12 +55,14 @@ static GTreeNode* g_tree_node_new                   (gpointer        key,
 						     gpointer        value);
 static void       g_tree_node_destroy               (GTreeNode      *node);
 static GTreeNode* g_tree_node_insert                (GTreeNode      *node,
-						     GCompareFunc    compare,
+						     GCompareFuncData compare,
+						     gpointer        comp_data,
 						     gpointer        key,
 						     gpointer        value,
 						     gint           *inserted);
 static GTreeNode* g_tree_node_remove                (GTreeNode      *node,
-						     GCompareFunc    compare,
+						     GCompareFuncData compare,
+						     gpointer        comp_data,
 						     gconstpointer   key);
 static GTreeNode* g_tree_node_balance               (GTreeNode      *node);
 static GTreeNode* g_tree_node_remove_leftmost       (GTreeNode      *node,
@@ -69,7 +72,8 @@ static GTreeNode* g_tree_node_restore_left_balance  (GTreeNode      *node,
 static GTreeNode* g_tree_node_restore_right_balance (GTreeNode      *node,
 						     gint            old_balance);
 static gpointer   g_tree_node_lookup                (GTreeNode      *node,
-						     GCompareFunc    compare,
+						     GCompareFuncData compare,
+						     gpointer        comp_data,
 						     gconstpointer   key);
 static gint       g_tree_node_count                 (GTreeNode      *node);
 static gint       g_tree_node_pre_order             (GTreeNode      *node,
@@ -149,9 +153,8 @@ g_tree_node_destroy (GTreeNode *node)
    }
 }
 
-
-GTree*
-g_tree_new (GCompareFunc key_compare_func)
+GTree*	 g_tree_new_udata(GCompareFuncData key_compare_func,
+                          gpointer        key_compare_data)
 {
   GRealTree *rtree;
 
@@ -160,10 +163,18 @@ g_tree_new (GCompareFunc key_compare_func)
   rtree = g_new (GRealTree, 1);
   rtree->root = NULL;
   rtree->key_compare = key_compare_func;
+  rtree->key_compare_data = key_compare_data;
 
   return (GTree*) rtree;
 }
 
+GTree*
+g_tree_new (GCompareFunc key_compare_func)
+{
+  return g_tree_new_udata ((GCompareFuncData) key_compare_func, NULL);
+}
+
+
 void
 g_tree_destroy (GTree *tree)
 {
@@ -191,6 +202,7 @@ g_tree_insert (GTree    *tree,
 
   inserted = FALSE;
   rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
+				    rtree->key_compare_data,
 				    key, value, &inserted);
 }
 
@@ -204,7 +216,8 @@ g_tree_remove (GTree         *tree,
 
   rtree = (GRealTree*) tree;
 
-  rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare, key);
+  rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare,
+                                    rtree->key_compare_data, key);
 }
 
 gpointer
@@ -217,7 +230,8 @@ g_tree_lookup (GTree         *tree,
 
   rtree = (GRealTree*) tree;
 
-  return g_tree_node_lookup (rtree->root, rtree->key_compare, key);
+  return g_tree_node_lookup (rtree->root, rtree->key_compare, 
+                             rtree->key_compare_data, key);
 }
 
 void
@@ -303,11 +317,12 @@ g_tree_nnodes (GTree *tree)
 }
 
 static GTreeNode*
-g_tree_node_insert (GTreeNode    *node,
-		    GCompareFunc  compare,
-		    gpointer      key,
-		    gpointer      value,
-		    gint         *inserted)
+g_tree_node_insert (GTreeNode      *node,
+		    GCompareFuncData compare,
+		    gpointer        compare_data,
+		    gpointer        key,
+		    gpointer        value,
+		    gint           *inserted)
 {
   gint old_balance;
   gint cmp;
@@ -318,7 +333,7 @@ g_tree_node_insert (GTreeNode    *node,
       return g_tree_node_new (key, value);
     }
 
-  cmp = (* compare) (key, node->key);
+  cmp = (* compare) (key, node->key, compare_data);
   if (cmp == 0)
     {
       *inserted = FALSE;
@@ -331,7 +346,8 @@ g_tree_node_insert (GTreeNode    *node,
       if (node->left)
 	{
 	  old_balance = node->left->balance;
-	  node->left = g_tree_node_insert (node->left, compare, key, value, inserted);
+	  node->left = g_tree_node_insert (node->left, compare, compare_data,
+	                                   key, value, inserted);
 
 	  if ((old_balance != node->left->balance) && node->left->balance)
 	    node->balance -= 1;
@@ -348,7 +364,8 @@ g_tree_node_insert (GTreeNode    *node,
       if (node->right)
 	{
 	  old_balance = node->right->balance;
-	  node->right = g_tree_node_insert (node->right, compare, key, value, inserted);
+	  node->right = g_tree_node_insert (node->right, compare, compare_data,
+	                                    key, value, inserted);
 
 	  if ((old_balance != node->right->balance) && node->right->balance)
 	    node->balance += 1;
@@ -371,9 +388,10 @@ g_tree_node_insert (GTreeNode    *node,
 }
 
 static GTreeNode*
-g_tree_node_remove (GTreeNode     *node,
-		    GCompareFunc   compare,
-		    gconstpointer  key)
+g_tree_node_remove (GTreeNode      *node,
+		    GCompareFuncData compare,
+		    gpointer        compare_data,
+		    gconstpointer   key)
 {
   GTreeNode *new_root;
   gint old_balance;
@@ -382,7 +400,7 @@ g_tree_node_remove (GTreeNode     *node,
   if (!node)
     return NULL;
 
-  cmp = (* compare) (key, node->key);
+  cmp = (* compare) (key, node->key, compare_data);
   if (cmp == 0)
     {
       GTreeNode *garbage;
@@ -419,7 +437,7 @@ g_tree_node_remove (GTreeNode     *node,
       if (node->left)
 	{
 	  old_balance = node->left->balance;
-	  node->left = g_tree_node_remove (node->left, compare, key);
+	  node->left = g_tree_node_remove (node->left, compare, compare_data, key);
 	  node = g_tree_node_restore_left_balance (node, old_balance);
 	}
     }
@@ -428,7 +446,7 @@ g_tree_node_remove (GTreeNode     *node,
       if (node->right)
 	{
 	  old_balance = node->right->balance;
-	  node->right = g_tree_node_remove (node->right, compare, key);
+	  node->right = g_tree_node_remove (node->right, compare, compare_data, key);
 	  node = g_tree_node_restore_right_balance (node, old_balance);
 	}
     }
@@ -503,28 +521,29 @@ g_tree_node_restore_right_balance (GTreeNode *node,
 }
 
 static gpointer
-g_tree_node_lookup (GTreeNode     *node,
-		    GCompareFunc   compare,
-		    gconstpointer  key)
+g_tree_node_lookup (GTreeNode      *node,
+		    GCompareFuncData compare,
+		    gpointer        compare_data,
+		    gconstpointer   key)
 {
   gint cmp;
 
   if (!node)
     return NULL;
 
-  cmp = (* compare) (key, node->key);
+  cmp = (* compare) (key, node->key, compare_data);
   if (cmp == 0)
     return node->value;
 
   if (cmp < 0)
     {
       if (node->left)
-	return g_tree_node_lookup (node->left, compare, key);
+	return g_tree_node_lookup (node->left, compare, compare_data, key);
     }
   else if (cmp > 0)
     {
       if (node->right)
-	return g_tree_node_lookup (node->right, compare, key);
+	return g_tree_node_lookup (node->right, compare, compare_data, key);
     }
 
   return NULL;
diff --git a/gtree.h b/gtree.h
index 207d16c95..3530a6374 100644
--- a/gtree.h
+++ b/gtree.h
@@ -39,24 +39,28 @@ typedef gint		(*GTraverseFunc)	(gpointer	key,
 
 /* Balanced binary trees
  */
-GTree*	 g_tree_new	 (GCompareFunc	 key_compare_func);
-void	 g_tree_destroy	 (GTree		*tree);
-void	 g_tree_insert	 (GTree		*tree,
-			  gpointer	 key,
-			  gpointer	 value);
-void	 g_tree_remove	 (GTree		*tree,
-			  gconstpointer	 key);
-gpointer g_tree_lookup	 (GTree		*tree,
-			  gconstpointer	 key);
-void	 g_tree_traverse (GTree		*tree,
-			  GTraverseFunc	 traverse_func,
-			  GTraverseType	 traverse_type,
-			  gpointer	 data);
-gpointer g_tree_search	 (GTree		*tree,
-			  GCompareFunc	 search_func,
-			  gconstpointer	 data);
-gint	 g_tree_height	 (GTree		*tree);
-gint	 g_tree_nnodes	 (GTree		*tree);
+GTree*   g_tree_new           (GCompareFunc      key_compare_func);
+GTree*   g_tree_new_with_data (GCompareFuncData  key_compare_func,
+			       gpointer          user_data);
+void     g_tree_destroy       (GTree            *tree);
+void     g_tree_insert        (GTree            *tree,
+			       gpointer          key,
+			       gpointer          value);
+void     g_tree_remove        (GTree            *tree,
+			       gconstpointer     key);
+gpointer g_tree_lookup        (GTree            *tree,
+			       gconstpointer     key);
+void     g_tree_traverse      (GTree            *tree,
+			       GTraverseFunc     traverse_func,
+			       GTraverseType     traverse_type,
+			       gpointer          data);
+gpointer g_tree_search        (GTree            *tree,
+			       GCompareFunc      search_func,
+			       gconstpointer     data);
+gint     g_tree_height        (GTree            *tree);
+gint     g_tree_nnodes        (GTree            *tree);
+
+
 
 G_END_DECLS
 
diff --git a/gtypes.h b/gtypes.h
index 5f7d4937f..c43d322a7 100644
--- a/gtypes.h
+++ b/gtypes.h
@@ -69,6 +69,9 @@ typedef const void *gconstpointer;
 
 typedef gint            (*GCompareFunc)         (gconstpointer  a,
                                                  gconstpointer  b);
+typedef gint            (*GCompareFuncData)     (gconstpointer  a,
+                                                 gconstpointer  b,
+						 gpointer       user_data);
 typedef gboolean        (*GEqualFunc)           (gconstpointer  a,
                                                  gconstpointer  b);
 typedef void            (*GDestroyNotify)       (gpointer       data);