[patch] adding destroy_notifiers to GTree
- From: Sven Neumann <sven gimp org>
- To: gtk-devel-list gnome org
- Subject: [patch] adding destroy_notifiers to GTree
- Date: 02 Apr 2001 20:15:27 +0200
Hi,
here's a patch that adds the new functions g_tree_new_full,
g_tree_replace and g_tree_steal to the GTree API similar to
the extensions the GHashTable API has seen lately. I'd like
you to have a look at this and would like to receive an OK
for commit. Of course I'll add inline docs then.
There's one issue with this patch. GTree used to have
g_tree_new_with_user_data() defined in the header but there was
no implementation. Actually there was, but it was called
g_tree_new_udata(). My patch corrects this error, but I'm not
sure if it makes sense at all. I'd vote for removing this
feature. If you agree I'll change my patch accordingly.
Salut, Sven
Index: gtree.c
===================================================================
RCS file: /cvs/gnome/glib/gtree.c,v
retrieving revision 1.21
diff -u -r1.21 gtree.c
--- gtree.c 2001/03/08 18:18:16 1.21
+++ gtree.c 2001/04/02 18:03:41
@@ -42,7 +42,9 @@
{
GTreeNode *root;
GCompareDataFunc key_compare;
- gpointer key_compare_data;
+ GDestroyNotify key_destroy_func;
+ GDestroyNotify value_destroy_func;
+ gpointer key_compare_data;
};
struct _GTreeNode
@@ -55,47 +57,54 @@
};
-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,
- GCompareDataFunc compare,
- gpointer comp_data,
- gpointer key,
- gpointer value,
- gint *inserted);
-static GTreeNode* g_tree_node_remove (GTreeNode *node,
- GCompareDataFunc compare,
- gpointer comp_data,
- gconstpointer key);
-static GTreeNode* g_tree_node_balance (GTreeNode *node);
-static GTreeNode* g_tree_node_remove_leftmost (GTreeNode *node,
- GTreeNode **leftmost);
-static GTreeNode* g_tree_node_restore_left_balance (GTreeNode *node,
- gint old_balance);
-static GTreeNode* g_tree_node_restore_right_balance (GTreeNode *node,
- gint old_balance);
-static GTreeNode* g_tree_node_lookup (GTreeNode *node,
- GCompareDataFunc compare,
- gpointer comp_data,
- gconstpointer key);
-static gint g_tree_node_count (GTreeNode *node);
-static gint g_tree_node_pre_order (GTreeNode *node,
- GTraverseFunc traverse_func,
- gpointer data);
-static gint g_tree_node_in_order (GTreeNode *node,
- GTraverseFunc traverse_func,
- gpointer data);
-static gint g_tree_node_post_order (GTreeNode *node,
- GTraverseFunc traverse_func,
- gpointer data);
-static gpointer g_tree_node_search (GTreeNode *node,
- GCompareFunc search_func,
- gconstpointer data);
-static gint g_tree_node_height (GTreeNode *node);
-static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
-static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
-static void g_tree_node_check (GTreeNode *node);
+static GTreeNode* g_tree_node_new (gpointer key,
+ gpointer value);
+static void g_tree_node_destroy (GTreeNode *node,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func);
+static GTreeNode* g_tree_node_insert (GTreeNode *node,
+ GCompareDataFunc compare,
+ gpointer comp_data,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func,
+ gpointer key,
+ gpointer value,
+ gboolean replace,
+ gboolean *inserted);
+static GTreeNode* g_tree_node_remove (GTreeNode *node,
+ GCompareDataFunc compare,
+ gpointer comp_data,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func,
+ gconstpointer key);
+static GTreeNode* g_tree_node_balance (GTreeNode *node);
+static GTreeNode* g_tree_node_remove_leftmost (GTreeNode *node,
+ GTreeNode **leftmost);
+static GTreeNode* g_tree_node_restore_left_balance (GTreeNode *node,
+ gint old_balance);
+static GTreeNode* g_tree_node_restore_right_balance (GTreeNode *node,
+ gint old_balance);
+static GTreeNode* g_tree_node_lookup (GTreeNode *node,
+ GCompareDataFunc compare,
+ gpointer comp_data,
+ gconstpointer key);
+static gint g_tree_node_count (GTreeNode *node);
+static gint g_tree_node_pre_order (GTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data);
+static gint g_tree_node_in_order (GTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data);
+static gint g_tree_node_post_order (GTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data);
+static gpointer g_tree_node_search (GTreeNode *node,
+ GCompareFunc search_func,
+ gconstpointer data);
+static gint g_tree_node_height (GTreeNode *node);
+static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
+static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
+static void g_tree_node_check (GTreeNode *node);
G_LOCK_DEFINE_STATIC (g_tree_global);
@@ -137,13 +146,22 @@
}
static void
-g_tree_node_destroy (GTreeNode *node)
+g_tree_node_destroy (GTreeNode *node,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func)
{
if (node)
{
- g_tree_node_destroy (node->right);
- g_tree_node_destroy (node->left);
-
+ g_tree_node_destroy (node->right,
+ key_destroy_func, value_destroy_func);
+ g_tree_node_destroy (node->left,
+ key_destroy_func, value_destroy_func);
+
+ if (key_destroy_func)
+ key_destroy_func (node->key);
+ if (value_destroy_func)
+ value_destroy_func (node->value);
+
#ifdef ENABLE_GC_FRIENDLY
node->left = NULL;
node->key = NULL;
@@ -157,27 +175,44 @@
}
}
-GTree* g_tree_new_udata(GCompareDataFunc key_compare_func,
- gpointer key_compare_data)
+GTree*
+g_tree_new (GCompareFunc key_compare_func)
{
- GRealTree *rtree;
-
g_return_val_if_fail (key_compare_func != NULL, NULL);
-
- rtree = g_new (GRealTree, 1);
- rtree->root = NULL;
- rtree->key_compare = key_compare_func;
- rtree->key_compare_data = key_compare_data;
- return (GTree*) rtree;
+ return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
+ NULL, NULL);
}
-
+
GTree*
-g_tree_new (GCompareFunc key_compare_func)
+g_tree_new_with_data (GCompareDataFunc key_compare_func,
+ gpointer key_compare_data)
{
- return g_tree_new_udata ((GCompareDataFunc) key_compare_func, NULL);
+ g_return_val_if_fail (key_compare_func != NULL, NULL);
+
+ return g_tree_new_full (key_compare_func, key_compare_data,
+ NULL, NULL);
}
+GTree*
+g_tree_new_full (GCompareDataFunc key_compare_func,
+ gpointer key_compare_data,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func)
+{
+ GRealTree *rtree;
+
+ g_return_val_if_fail (key_compare_func != NULL, NULL);
+
+ rtree = g_new (GRealTree, 1);
+ rtree->root = NULL;
+ rtree->key_compare = key_compare_func;
+ rtree->key_destroy_func = key_destroy_func;
+ rtree->value_destroy_func = value_destroy_func;
+ rtree->key_compare_data = key_compare_data;
+
+ return (GTree*) rtree;
+}
void
g_tree_destroy (GTree *tree)
@@ -188,7 +223,10 @@
rtree = (GRealTree*) tree;
- g_tree_node_destroy (rtree->root);
+ g_tree_node_destroy (rtree->root,
+ rtree->key_destroy_func,
+ rtree->value_destroy_func);
+
g_free (rtree);
}
@@ -198,19 +236,45 @@
gpointer value)
{
GRealTree *rtree;
- gint inserted;
+ gboolean inserted;
g_return_if_fail (tree != NULL);
rtree = (GRealTree*) tree;
inserted = FALSE;
- rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
+ rtree->root = g_tree_node_insert (rtree->root,
+ rtree->key_compare,
rtree->key_compare_data,
- key, value, &inserted);
+ rtree->key_destroy_func,
+ rtree->value_destroy_func,
+ key, value,
+ FALSE, &inserted);
}
void
+g_tree_replace (GTree *tree,
+ gpointer key,
+ gpointer value)
+{
+ GRealTree *rtree;
+ gboolean inserted;
+
+ g_return_if_fail (tree != NULL);
+
+ rtree = (GRealTree*) tree;
+
+ inserted = FALSE;
+ rtree->root = g_tree_node_insert (rtree->root,
+ rtree->key_compare,
+ rtree->key_compare_data,
+ rtree->key_destroy_func,
+ rtree->value_destroy_func,
+ key, value,
+ TRUE, &inserted);
+}
+
+void
g_tree_remove (GTree *tree,
gconstpointer key)
{
@@ -219,9 +283,30 @@
g_return_if_fail (tree != NULL);
rtree = (GRealTree*) tree;
+
+ rtree->root = g_tree_node_remove (rtree->root,
+ rtree->key_compare,
+ rtree->key_compare_data,
+ rtree->key_destroy_func,
+ rtree->value_destroy_func,
+ key);
+}
+
+void
+g_tree_steal (GTree *tree,
+ gconstpointer key)
+{
+ GRealTree *rtree;
+
+ g_return_if_fail (tree != NULL);
+
+ rtree = (GRealTree*) tree;
- rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare,
- rtree->key_compare_data, key);
+ rtree->root = g_tree_node_remove (rtree->root,
+ rtree->key_compare,
+ rtree->key_compare_data,
+ NULL, NULL,
+ key);
}
gpointer
@@ -354,12 +439,15 @@
}
static GTreeNode*
-g_tree_node_insert (GTreeNode *node,
- GCompareDataFunc compare,
- gpointer compare_data,
- gpointer key,
- gpointer value,
- gint *inserted)
+g_tree_node_insert (GTreeNode *node,
+ GCompareDataFunc compare,
+ gpointer compare_data,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func,
+ gpointer key,
+ gpointer value,
+ gboolean replace,
+ gboolean *inserted)
{
gint old_balance;
gint cmp;
@@ -374,7 +462,26 @@
if (cmp == 0)
{
*inserted = FALSE;
+
+ if (value_destroy_func)
+ value_destroy_func (node->value);
+
node->value = value;
+
+ if (replace)
+ {
+ if (key_destroy_func)
+ key_destroy_func (node->key);
+
+ node->key = key;
+ }
+ else
+ {
+ /* free the passed key */
+ if (key_destroy_func)
+ key_destroy_func (key);
+ }
+
return node;
}
@@ -384,7 +491,10 @@
{
old_balance = node->left->balance;
node->left = g_tree_node_insert (node->left, compare, compare_data,
- key, value, inserted);
+ key_destroy_func,
+ value_destroy_func,
+ key, value,
+ replace, inserted);
if ((old_balance != node->left->balance) && node->left->balance)
node->balance -= 1;
@@ -402,7 +512,10 @@
{
old_balance = node->right->balance;
node->right = g_tree_node_insert (node->right, compare, compare_data,
- key, value, inserted);
+ key_destroy_func,
+ value_destroy_func,
+ key, value,
+ replace, inserted);
if ((old_balance != node->right->balance) && node->right->balance)
node->balance += 1;
@@ -425,10 +538,12 @@
}
static GTreeNode*
-g_tree_node_remove (GTreeNode *node,
- GCompareDataFunc compare,
- gpointer compare_data,
- gconstpointer key)
+g_tree_node_remove (GTreeNode *node,
+ GCompareDataFunc compare,
+ gpointer compare_data,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func,
+ gconstpointer key)
{
GTreeNode *new_root;
gint old_balance;
@@ -458,6 +573,11 @@
node = g_tree_node_restore_right_balance (new_root, old_balance);
}
+ if (key_destroy_func)
+ key_destroy_func (garbage->key);
+ if (value_destroy_func)
+ value_destroy_func (garbage->value);
+
#ifdef ENABLE_GC_FRIENDLY
garbage->left = NULL;
garbage->key = NULL;
@@ -474,7 +594,11 @@
if (node->left)
{
old_balance = node->left->balance;
- node->left = g_tree_node_remove (node->left, compare, compare_data, key);
+ node->left = g_tree_node_remove (node->left,
+ compare, compare_data,
+ key_destroy_func,
+ value_destroy_func,
+ key);
node = g_tree_node_restore_left_balance (node, old_balance);
}
}
@@ -483,7 +607,11 @@
if (node->right)
{
old_balance = node->right->balance;
- node->right = g_tree_node_remove (node->right, compare, compare_data, key);
+ node->right = g_tree_node_remove (node->right,
+ compare, compare_data,
+ key_destroy_func,
+ value_destroy_func,
+ key);
node = g_tree_node_restore_right_balance (node, old_balance);
}
}
@@ -558,10 +686,10 @@
}
static GTreeNode *
-g_tree_node_lookup (GTreeNode *node,
- GCompareDataFunc compare,
- gpointer compare_data,
- gconstpointer key)
+g_tree_node_lookup (GTreeNode *node,
+ GCompareDataFunc compare,
+ gpointer compare_data,
+ gconstpointer key)
{
gint cmp;
Index: gtree.h
===================================================================
RCS file: /cvs/gnome/glib/gtree.h,v
retrieving revision 1.4
diff -u -r1.4 gtree.h
--- gtree.h 2001/03/08 17:51:38 1.4
+++ gtree.h 2001/04/02 18:03:41
@@ -42,11 +42,20 @@
GTree* g_tree_new (GCompareFunc key_compare_func);
GTree* g_tree_new_with_data (GCompareDataFunc key_compare_func,
gpointer user_data);
+GTree* g_tree_new_full (GCompareDataFunc key_compare_func,
+ gpointer user_data,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func);
void g_tree_destroy (GTree *tree);
void g_tree_insert (GTree *tree,
gpointer key,
gpointer value);
+void g_tree_replace (GTree *tree,
+ gpointer key,
+ gpointer value);
void g_tree_remove (GTree *tree,
+ gconstpointer key);
+void g_tree_steal (GTree *tree,
gconstpointer key);
gpointer g_tree_lookup (GTree *tree,
gconstpointer key);
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
