diff options
Diffstat (limited to 'glib')
| -rw-r--r-- | glib/Makefile.am | 2 | ||||
| -rw-r--r-- | glib/garray.c | 79 | ||||
| -rw-r--r-- | glib/garray.h | 133 | ||||
| -rw-r--r-- | glib/glib.h | 1 | ||||
| -rw-r--r-- | glib/glist.c | 49 | ||||
| -rw-r--r-- | glib/glist.h | 96 | ||||
| -rw-r--r-- | glib/gqsort.c | 269 | ||||
| -rw-r--r-- | glib/gqsort.h | 44 | ||||
| -rw-r--r-- | glib/gslist.c | 49 | ||||
| -rw-r--r-- | glib/gslist.h | 99 | ||||
| -rw-r--r-- | glib/gtree.c | 77 | ||||
| -rw-r--r-- | glib/gtree.h | 40 | ||||
| -rw-r--r-- | glib/gtypes.h | 3 |
13 files changed, 720 insertions, 221 deletions
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); |