patch: g_[s]list_sort_udata, g_tree_new_udata
- From: David Benson <daveb idealab com>
- To: gtk-devel-list gnome org
- Subject: patch: g_[s]list_sort_udata, g_tree_new_udata
- Date: Thu, 2 Nov 2000 06:55:34 -0800 (PST)
This implements user-data bearing versions of the functions:
g_slist_sort
g_list_sort
g_tree_new
The new versions are suffixed with _udata.
- Dave
============================================================
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/02 14:53:18
@@ -86,6 +86,9 @@
gpointer user_data);
GList* g_list_sort (GList *list,
GCompareFunc compare_func);
+GList* g_list_sort_udata (GList *list,
+ GComparatorFunc compare_func,
+ gpointer compare_func_data);
gpointer g_list_nth_data (GList *list,
guint n);
#define g_list_previous(list) ((list) ? (((GList *)(list))->prev) : NULL)
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/02 14:53:18
@@ -85,8 +85,11 @@
void g_slist_foreach (GSList *list,
GFunc func,
gpointer user_data);
-GSList* g_slist_sort (GSList *list,
+GSList* g_slist_sort (GSList *list,
GCompareFunc compare_func);
+GSList* g_slist_sort_udata (GSList *list,
+ GComparatorFunc compare_func,
+ gpointer compare_func_data);
gpointer g_slist_nth_data (GSList *list,
guint n);
#define g_slist_next(slist) ((slist) ? (((GSList *)(slist))->next) : NULL)
Index: gtree.h
===================================================================
RCS file: /cvs/gnome/glib/gtree.h,v
retrieving revision 1.1
diff -u -r1.1 gtree.h
--- gtree.h 2000/10/12 11:52:07 1.1
+++ gtree.h 2000/11/02 14:53:18
@@ -39,24 +39,26 @@
/* 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_udata (GComparatorFunc key_compare_func,
+ gpointer key_compare_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
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/02 14:53:18
@@ -69,6 +69,9 @@
typedef gint (*GCompareFunc) (gconstpointer a,
gconstpointer b);
+typedef gint (*GComparatorFunc) (gconstpointer a,
+ gconstpointer b,
+ gpointer user_data);
typedef gboolean (*GEqualFunc) (gconstpointer a,
gconstpointer b);
typedef void (*GDestroyNotify) (gpointer data);
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/02 14:53:18
@@ -596,9 +596,10 @@
}
static GList *
-g_list_sort_merge (GList *l1,
- GList *l2,
- GCompareFunc compare_func)
+g_list_sort_merge (GList *l1,
+ GList *l2,
+ GComparatorFunc comparator_func,
+ gpointer user_data)
{
GList list, *l, *lprev;
@@ -607,7 +608,7 @@
while (l1 && l2)
{
- if (compare_func (l1->data, l2->data) < 0)
+ if (comparator_func (l1->data, l2->data, user_data) < 0)
{
l->next = l1;
l = l->next;
@@ -631,8 +632,9 @@
}
GList*
-g_list_sort (GList *list,
- GCompareFunc compare_func)
+g_list_sort_udata (GList *list,
+ GComparatorFunc comparator_func,
+ gpointer user_data)
{
GList *l1, *l2;
@@ -653,14 +655,16 @@
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_udata (list, comparator_func, user_data),
+ g_list_sort_udata (l2, comparator_func, user_data),
+ comparator_func,
+ user_data);
}
GList*
-g_list_sort2 (GList *list,
- GCompareFunc compare_func)
+g_list_sort2 (GList *list,
+ GComparatorFunc comparator_func,
+ gpointer user_data)
{
GSList *runs = NULL;
GList *tmp;
@@ -673,7 +677,8 @@
{
GList *tmp2;
for (tmp2 = tmp;
- tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
+ tmp2->next
+ && comparator_func (tmp2->data, tmp2->next->data, user_data) <= 0;
tmp2 = tmp2->next)
/* Nothing */;
runs = g_slist_append (runs, tmp);
@@ -691,7 +696,8 @@
{
dst->data = g_list_sort_merge (src->data,
src->next->data,
- compare_func);
+ comparator_func,
+ user_data);
dstprev = dst;
dst = dst->next;
src = src->next->next;
@@ -715,4 +721,11 @@
list = runs->data;
g_slist_free (runs);
return list;
+}
+
+GList*
+g_list_sort (GList *list,
+ GCompareFunc compare_func)
+{
+ return g_list_sort_udata (list, (GComparatorFunc) compare_func, NULL);
}
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/02 14:53:18
@@ -581,9 +581,10 @@
}
static GSList*
-g_slist_sort_merge (GSList *l1,
- GSList *l2,
- GCompareFunc compare_func)
+g_slist_sort_merge (GSList *l1,
+ GSList *l2,
+ GComparatorFunc comparator_func,
+ gpointer user_data)
{
GSList list, *l;
@@ -591,7 +592,7 @@
while (l1 && l2)
{
- if (compare_func(l1->data,l2->data) < 0)
+ if (comparator_func(l1->data,l2->data, user_data) < 0)
{
l=l->next=l1;
l1=l1->next;
@@ -608,8 +609,9 @@
}
GSList*
-g_slist_sort (GSList *list,
- GCompareFunc compare_func)
+g_slist_sort_udata (GSList *list,
+ GComparatorFunc comparator_func,
+ gpointer user_data)
{
GSList *l1, *l2;
@@ -629,8 +631,16 @@
}
l2 = l1->next;
l1->next = NULL;
+
+ return g_slist_sort_merge (g_slist_sort_udata (list, comparator_func, user_data),
+ g_slist_sort_udata (l2, comparator_func, user_data),
+ comparator_func,
+ user_data);
+}
- return g_slist_sort_merge (g_slist_sort (list, compare_func),
- g_slist_sort (l2, compare_func),
- compare_func);
+GSList*
+g_slist_sort (GSList *list,
+ GCompareFunc compare_func)
+{
+ return g_slist_sort_udata (list, (GComparatorFunc) compare_func, NULL);
}
Index: gtree.c
===================================================================
RCS file: /cvs/gnome/glib/gtree.c,v
retrieving revision 1.15
diff -u -r1.15 gtree.c
--- gtree.c 2000/07/26 11:01:59 1.15
+++ gtree.c 2000/11/02 14:53:18
@@ -37,7 +37,8 @@
struct _GRealTree
{
GTreeNode *root;
- GCompareFunc key_compare;
+ GComparatorFunc key_compare;
+ gpointer key_compare_data;
};
struct _GTreeNode
@@ -54,12 +55,14 @@
gpointer value);
static void g_tree_node_destroy (GTreeNode *node);
static GTreeNode* g_tree_node_insert (GTreeNode *node,
- GCompareFunc compare,
+ GComparatorFunc compare,
+ gpointer comp_data,
gpointer key,
gpointer value,
gint *inserted);
static GTreeNode* g_tree_node_remove (GTreeNode *node,
- GCompareFunc compare,
+ GComparatorFunc 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_right_balance (GTreeNode *node,
gint old_balance);
static gpointer g_tree_node_lookup (GTreeNode *node,
- GCompareFunc compare,
+ GComparatorFunc 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 @@
}
}
-
-GTree*
-g_tree_new (GCompareFunc key_compare_func)
+GTree* g_tree_new_udata(GComparatorFunc key_compare_func,
+ gpointer key_compare_data)
{
GRealTree *rtree;
@@ -160,10 +163,18 @@
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 ((GComparatorFunc) key_compare_func, NULL);
+}
+
+
void
g_tree_destroy (GTree *tree)
{
@@ -191,6 +202,7 @@
inserted = FALSE;
rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
+ rtree->key_compare_data,
key, value, &inserted);
}
@@ -204,7 +216,8 @@
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 @@
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 @@
}
static GTreeNode*
-g_tree_node_insert (GTreeNode *node,
- GCompareFunc compare,
- gpointer key,
- gpointer value,
- gint *inserted)
+g_tree_node_insert (GTreeNode *node,
+ GComparatorFunc compare,
+ gpointer compare_data,
+ gpointer key,
+ gpointer value,
+ gint *inserted)
{
gint old_balance;
gint cmp;
@@ -318,7 +333,7 @@
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 @@
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 @@
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 @@
}
static GTreeNode*
-g_tree_node_remove (GTreeNode *node,
- GCompareFunc compare,
- gconstpointer key)
+g_tree_node_remove (GTreeNode *node,
+ GComparatorFunc compare,
+ gpointer compare_data,
+ gconstpointer key)
{
GTreeNode *new_root;
gint old_balance;
@@ -382,7 +400,7 @@
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 @@
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 @@
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 @@
}
static gpointer
-g_tree_node_lookup (GTreeNode *node,
- GCompareFunc compare,
- gconstpointer key)
+g_tree_node_lookup (GTreeNode *node,
+ GComparatorFunc 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;
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
