Re: patch: g_[s]list_sort_udata, g_tree_new_udata
- From: Jonathan Blandford <jrb redhat com>
- To: David Benson <daveb idealab com>
- Cc: gtk-devel-list gnome org
- Subject: Re: patch: g_[s]list_sort_udata, g_tree_new_udata
- Date: 13 Nov 2000 18:55:06 -0500
Hi Dave,
David Benson <daveb idealab com> writes:
> This implements user-data bearing versions of the functions:
> g_slist_sort
> g_list_sort
> g_tree_new
I have a patch here that took a slightly modified version of your
g_{s,}list_sort functions, added a g_qsort_with_udata function (from
Maciej), and added sorting to GArray. Does anyone object if I commit?
Also, I was going to add the GTree patch, but was curious what the right
way to manage the udata memory is? Should it just be up to the user to
free, or do we want to do something else?
Thanks,
-Jonathan
Index: ChangeLog
===================================================================
RCS file: /cvs/gnome/glib/ChangeLog,v
retrieving revision 1.535
diff -u -r1.535 ChangeLog
--- ChangeLog 2000/11/13 19:01:26 1.535
+++ ChangeLog 2000/11/13 23:37:33
@@ -1,3 +1,16 @@
+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_udata): new function to sort with
+ user_data.
+
+ * glist.c (g_list_sort_udata): new function to sort with
+ user_data.
+
+ * garray.c: Added convenience functions to sort arrays.
+
Mon Nov 13 14:00:20 2000 Owen Taylor <otaylor redhat com>
* configure.in: Up version to 1.3.2
Index: Makefile.am
===================================================================
RCS file: /cvs/gnome/glib/Makefile.am,v
retrieving revision 1.66
diff -u -r1.66 Makefile.am
--- Makefile.am 2000/11/12 23:44:27 1.66
+++ Makefile.am 2000/11/13 23:37:33
@@ -66,6 +66,7 @@
gmessages.c \
gnode.c \
gprimes.c \
+ gqsort.c \
gqueue.c \
grel.c \
grand.c \
@@ -115,6 +116,7 @@
gmessages.h \
gnode.h \
gprimes.h \
+ gqsort.h \
gquark.h \
gqueue.h \
grand.h \
Index: garray.c
===================================================================
RCS file: /cvs/gnome/glib/garray.c,v
retrieving revision 1.21
diff -u -r1.21 garray.c
--- garray.c 2000/09/25 21:28:13 1.21
+++ garray.c 2000/11/13 23:37:33
@@ -29,6 +29,7 @@
*/
#include <string.h>
+#include <stdlib.h>
#include "glib.h"
@@ -264,6 +265,39 @@
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_udata (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_udata (array->data,
+ array->len,
+ array->elt_size,
+ compare_func,
+ user_data);
+}
+
+
static gint
g_nearest_pow (gint num)
{
@@ -527,6 +561,34 @@
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_udata (GPtrArray *array,
+ GCompareFuncData compare_func,
+ gpointer user_data)
+{
+ g_return_if_fail (array != NULL);
+ g_return_if_fail (array->pdata != NULL);
+
+ g_qsort_with_udata (array->pdata,
+ array->len,
+ sizeof (gpointer),
+ compare_func,
+ user_data);
+}
+
/* Byte arrays
*/
@@ -581,9 +643,24 @@
}
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_udata (GByteArray *array,
+ GCompareFuncData compare_func,
+ gpointer user_data)
+{
+ g_array_sort_udata ((GArray *) array, compare_func, user_data);
}
Index: garray.h
===================================================================
RCS file: /cvs/gnome/glib/garray.h,v
retrieving revision 1.1
diff -u -r1.1 garray.h
--- garray.h 2000/10/12 11:52:07 1.1
+++ garray.h 2000/11/13 23:37:33
@@ -63,75 +63,92 @@
#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_udata (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_udata (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);
+void g_byte_array_sort (GByteArray *array,
+ GCompareFunc compare_func);
+void g_byte_array_sort_udata (GByteArray *array,
+ GCompareFuncData compare_func,
+ gpointer user_data);
-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);
G_END_DECLS
Index: glib.h
===================================================================
RCS file: /cvs/gnome/glib/glib.h,v
retrieving revision 1.211
diff -u -r1.211 glib.h
--- glib.h 2000/10/27 02:46:03 1.211
+++ glib.h 2000/11/13 23:37:33
@@ -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>
Index: glist.c
===================================================================
RCS file: /cvs/gnome/glib/glist.c,v
retrieving revision 1.17
diff -u -r1.17 glist.c
--- glist.c 2000/07/26 11:01:59 1.17
+++ glist.c 2000/11/13 23:37:33
@@ -596,18 +596,26 @@
}
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_udata,
+ 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_udata)
+ 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 @@
}
GList*
-g_list_sort (GList *list,
- GCompareFunc compare_func)
+g_list_sort_real (GList *list,
+ GFunc compare_func,
+ gboolean use_udata,
+ gpointer user_data)
{
GList *l1, *l2;
@@ -652,10 +662,28 @@
}
l2 = l1->next;
l1->next = NULL;
+
+ return g_list_sort_merge (g_list_sort_real (list, compare_func, use_udata, user_data),
+ g_list_sort_real (l2, compare_func, use_udata, user_data),
+ compare_func,
+ use_udata,
+ user_data);
+}
- return g_list_sort_merge (g_list_sort (list, compare_func),
- g_list_sort (l2, compare_func),
- compare_func);
+GList *
+g_list_sort (GList *list,
+ GCompareFunc compare_func)
+{
+ return g_list_sort_real (list, (GFunc) compare_func, FALSE, NULL);
+
+}
+
+GList *
+g_list_sort_udata (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 @@
{
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;
Index: glist.h
===================================================================
RCS file: /cvs/gnome/glib/glist.h,v
retrieving revision 1.1
diff -u -r1.1 glist.h
--- glist.h 2000/10/12 11:52:07 1.1
+++ glist.h 2000/11/13 23:37:33
@@ -42,52 +42,56 @@
/* 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_udata (GList *list,
+ GCompareFuncData compare_func,
+ gpointer udata);
+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)
Index: gqsort.c
===================================================================
RCS file: gqsort.c
diff -N gqsort.c
--- /dev/null Tue May 5 16:32:27 1998
+++ gqsort.c Mon Nov 13 18:37:33 2000
@@ -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_udata (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;
+ }
+ }
+ }
+ }
+}
Index: gqsort.h
===================================================================
RCS file: gqsort.h
diff -N gqsort.h
--- /dev/null Tue May 5 16:32:27 1998
+++ gqsort.h Mon Nov 13 18:37:33 2000
@@ -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_udata (gconstpointer pbase,
+ gint total_elems,
+ size_t size,
+ GCompareFuncData compare_func,
+ gpointer user_data);
+
+G_END_DECLS
+
+#endif /* __G_QSORT_H__ */
+
Index: gslist.c
===================================================================
RCS file: /cvs/gnome/glib/gslist.c,v
retrieving revision 1.17
diff -u -r1.17 gslist.c
--- gslist.c 2000/07/26 11:01:59 1.17
+++ gslist.c 2000/11/13 23:37:33
@@ -580,18 +580,26 @@
}
}
-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_udata,
+ gpointer user_data)
{
GSList list, *l;
+ gint cmp;
l=&list;
while (l1 && l2)
{
- if (compare_func(l1->data,l2->data) < 0)
+ if (use_udata)
+ 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 @@
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_udata,
+ gpointer user_data)
{
GSList *l1, *l2;
@@ -630,7 +640,24 @@
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_udata, user_data),
+ g_slist_sort_real (l2, compare_func, use_udata, user_data),
+ compare_func,
+ use_udata,
+ 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_udata (GSList *list,
+ GCompareFuncData compare_func,
+ gpointer user_data)
+{
+ return g_slist_sort_real (list, (GFunc) compare_func, TRUE, user_data);
}
Index: gslist.h
===================================================================
RCS file: /cvs/gnome/glib/gslist.h,v
retrieving revision 1.1
diff -u -r1.1 gslist.h
--- gslist.h 2000/10/12 11:52:07 1.1
+++ gslist.h 2000/11/13 23:37:33
@@ -41,54 +41,57 @@
/* 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_udata (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
Index: gtypes.h
===================================================================
RCS file: /cvs/gnome/glib/gtypes.h,v
retrieving revision 1.3
diff -u -r1.3 gtypes.h
--- gtypes.h 2000/10/30 14:34:52 1.3
+++ gtypes.h 2000/11/13 23:37:33
@@ -69,6 +69,9 @@
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);
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
