Re: GHashTable suggestions
- From: Sven Neumann <sven gimp org>
- To: <gtk-devel-list gnome org>
- Subject: Re: GHashTable suggestions
- Date: 07 Jan 2001 21:48:29 +0100
Hi,
Havoc Pennington <hp redhat com> writes:
> I thought the proposal was to have _insert() destroy the existing
> key. You're right, if it destroys the passed key then things aren't
> more complicated. That seems OK.
I have gone through my patches again and post new versions here
which will hopefully make it into glib.
ghash.patch adds the new function g_hash_table_new_full() which
allows to pass GFreeFuncs to allow the hash_table to take care of
freeing the memory allocated for the key and value when removing
an entry. If an existing entry is replaced using g_hash_table_insert,
the passed key is freed. The new function g_hash_table_replace()
puts the passed key in place of the old one and frees the old key.
g_hash_table_remove_no_notify() allows to remove an entry without
calling the key_destroy and value_destroy functions.
gtree.patch adds the same functionality to GTree's (using a similar
API). Additionally it adds the g_tree_lookup_extended() function
(comparabale to g_hash_table_lookup_extended) which was missing
from Gtree.
Please comment.
Salut, Sven
Index: ghash.c
===================================================================
RCS file: /cvs/gnome/glib/ghash.c,v
retrieving revision 1.23
diff -u -r1.23 ghash.c
--- ghash.c 2000/12/19 15:40:30 1.23
+++ ghash.c 2001/01/07 20:34:45
@@ -55,6 +55,8 @@
GHashNode **nodes;
GHashFunc hash_func;
GEqualFunc key_equal_func;
+ GFreeFunc key_destroy_func;
+ GFreeFunc value_destroy_func;
};
@@ -63,8 +65,12 @@
gconstpointer key);
static GHashNode* g_hash_node_new (gpointer key,
gpointer value);
-static void g_hash_node_destroy (GHashNode *hash_node);
-static void g_hash_nodes_destroy (GHashNode *hash_node);
+static void g_hash_node_destroy (GHashNode *hash_node,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func);
+static void g_hash_nodes_destroy (GHashNode *hash_node,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func);
G_LOCK_DEFINE_STATIC (g_hash_global);
@@ -77,6 +83,15 @@
g_hash_table_new (GHashFunc hash_func,
GEqualFunc key_equal_func)
{
+ return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
+}
+
+GHashTable*
+g_hash_table_new_full (GHashFunc hash_func,
+ GEqualFunc key_equal_func,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func)
+{
GHashTable *hash_table;
guint i;
@@ -85,6 +100,8 @@
hash_table->nnodes = 0;
hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
hash_table->key_equal_func = key_equal_func;
+ hash_table->key_destroy_func = key_destroy_func;
+ hash_table->value_destroy_func = value_destroy_func;
hash_table->nodes = g_new (GHashNode*, hash_table->size);
for (i = 0; i < hash_table->size; i++)
@@ -101,7 +118,9 @@
g_return_if_fail (hash_table != NULL);
for (i = 0; i < hash_table->size; i++)
- g_hash_nodes_destroy (hash_table->nodes[i]);
+ g_hash_nodes_destroy (hash_table->nodes[i],
+ hash_table->key_destroy_func,
+ hash_table->value_destroy_func);
g_free (hash_table->nodes);
g_free (hash_table);
@@ -158,11 +177,47 @@
if (*node)
{
/* do not reset node->key in this place, keeping
- * the old key might be intended.
- * a g_hash_table_remove/g_hash_table_insert pair
- * can be used otherwise.
- *
- * node->key = key; */
+ * the old key is the intended behaviour.
+ * g_hash_table_replace() can be used instead.
+ */
+
+ /* free the passed key */
+ if (hash_table->key_destroy_func)
+ hash_table->key_destroy_func (key);
+
+ if (hash_table->value_destroy_func)
+ hash_table->value_destroy_func ((*node)->value);
+
+ (*node)->value = value;
+ }
+ else
+ {
+ *node = g_hash_node_new (key, value);
+ hash_table->nnodes++;
+ g_hash_table_resize (hash_table);
+ }
+}
+
+void
+g_hash_table_replace (GHashTable *hash_table,
+ gpointer key,
+ gpointer value)
+{
+ GHashNode **node;
+
+ g_return_if_fail (hash_table != NULL);
+
+ node = g_hash_table_lookup_node (hash_table, key);
+
+ if (*node)
+ {
+ if (hash_table->key_destroy_func)
+ hash_table->key_destroy_func ((*node)->key);
+
+ if (hash_table->value_destroy_func)
+ hash_table->value_destroy_func ((*node)->value);
+
+ (*node)->key = key;
(*node)->value = value;
}
else
@@ -174,8 +229,34 @@
}
gboolean
-g_hash_table_remove (GHashTable *hash_table,
- gconstpointer key)
+g_hash_table_remove (GHashTable *hash_table,
+ gconstpointer key)
+{
+ GHashNode **node, *dest;
+
+ g_return_val_if_fail (hash_table != NULL, FALSE);
+
+ node = g_hash_table_lookup_node (hash_table, key);
+ if (*node)
+ {
+ dest = *node;
+ (*node) = dest->next;
+ g_hash_node_destroy (dest,
+ hash_table->key_destroy_func,
+ hash_table->value_destroy_func);
+ hash_table->nnodes--;
+
+ g_hash_table_resize (hash_table);
+
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+gboolean
+g_hash_table_remove_no_notify (GHashTable *hash_table,
+ gconstpointer key)
{
GHashNode **node, *dest;
@@ -186,7 +267,7 @@
{
dest = *node;
(*node) = dest->next;
- g_hash_node_destroy (dest);
+ g_hash_node_destroy (dest, NULL, NULL);
hash_table->nnodes--;
g_hash_table_resize (hash_table);
@@ -198,10 +279,10 @@
}
gboolean
-g_hash_table_lookup_extended (GHashTable *hash_table,
- gconstpointer lookup_key,
- gpointer *orig_key,
- gpointer *value)
+g_hash_table_lookup_extended (GHashTable *hash_table,
+ gconstpointer lookup_key,
+ gpointer *orig_key,
+ gpointer *value)
{
GHashNode *node;
@@ -269,13 +350,17 @@
if (prev)
{
prev->next = node->next;
- g_hash_node_destroy (node);
+ g_hash_node_destroy (node,
+ hash_table->key_destroy_func,
+ hash_table->value_destroy_func);
node = prev;
}
else
{
hash_table->nodes[i] = node->next;
- g_hash_node_destroy (node);
+ g_hash_node_destroy (node,
+ hash_table->key_destroy_func,
+ hash_table->value_destroy_func);
goto restart;
}
}
@@ -381,9 +466,15 @@
}
static void
-g_hash_node_destroy (GHashNode *hash_node)
-{
-
+g_hash_node_destroy (GHashNode *hash_node,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func)
+{
+ if (key_destroy_func)
+ key_destroy_func (hash_node->key);
+ if (value_destroy_func)
+ value_destroy_func (hash_node->value);
+
#ifdef ENABLE_GC_FRIENDLY
hash_node->key = NULL;
hash_node->value = NULL;
@@ -396,7 +487,9 @@
}
static void
-g_hash_nodes_destroy (GHashNode *hash_node)
+g_hash_nodes_destroy (GHashNode *hash_node,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func)
{
if (hash_node)
{
@@ -404,12 +497,23 @@
while (node->next)
{
+ if (key_destroy_func)
+ key_destroy_func (node->key);
+ if (value_destroy_func)
+ value_destroy_func (node->value);
+
#ifdef ENABLE_GC_FRIENDLY
node->key = NULL;
node->value = NULL;
#endif /* ENABLE_GC_FRIENDLY */
+
node = node->next;
}
+
+ if (key_destroy_func)
+ key_destroy_func (node->key);
+ if (value_destroy_func)
+ value_destroy_func (node->value);
#ifdef ENABLE_GC_FRIENDLY
node->key = NULL;
Index: ghash.h
===================================================================
RCS file: /cvs/gnome/glib/ghash.h,v
retrieving revision 1.3
diff -u -r1.3 ghash.h
--- ghash.h 2000/12/13 00:44:18 1.3
+++ ghash.h 2001/01/07 20:34:45
@@ -31,40 +31,49 @@
G_BEGIN_DECLS
-typedef struct _GHashTable GHashTable;
+typedef struct _GHashTable GHashTable;
-typedef gboolean (*GHRFunc) (gpointer key,
- gpointer value,
- gpointer user_data);
+typedef gboolean (*GHRFunc) (gpointer key,
+ gpointer value,
+ gpointer user_data);
/* Hash tables
*/
-GHashTable* g_hash_table_new (GHashFunc hash_func,
- GEqualFunc key_equal_func);
-void g_hash_table_destroy (GHashTable *hash_table);
-void g_hash_table_insert (GHashTable *hash_table,
- gpointer key,
- gpointer value);
-gboolean g_hash_table_remove (GHashTable *hash_table,
- gconstpointer key);
-gpointer g_hash_table_lookup (GHashTable *hash_table,
- gconstpointer key);
-gboolean g_hash_table_lookup_extended(GHashTable *hash_table,
- gconstpointer lookup_key,
- gpointer *orig_key,
- gpointer *value);
-void g_hash_table_foreach (GHashTable *hash_table,
- GHFunc func,
- gpointer user_data);
-guint g_hash_table_foreach_remove (GHashTable *hash_table,
- GHRFunc func,
- gpointer user_data);
-guint g_hash_table_size (GHashTable *hash_table);
+GHashTable* g_hash_table_new (GHashFunc hash_func,
+ GEqualFunc key_equal_func);
+GHashTable* g_hash_table_new_full (GHashFunc hash_func,
+ GEqualFunc key_equal_func,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func);
+void g_hash_table_destroy (GHashTable *hash_table);
+void g_hash_table_insert (GHashTable *hash_table,
+ gpointer key,
+ gpointer value);
+void g_hash_table_replace (GHashTable *hash_table,
+ gpointer key,
+ gpointer value);
+gboolean g_hash_table_remove (GHashTable *hash_table,
+ gconstpointer key);
+gboolean g_hash_table_remove_no_notify (GHashTable *hash_table,
+ gconstpointer key);
+gpointer g_hash_table_lookup (GHashTable *hash_table,
+ gconstpointer key);
+gboolean g_hash_table_lookup_extended (GHashTable *hash_table,
+ gconstpointer lookup_key,
+ gpointer *orig_key,
+ gpointer *value);
+void g_hash_table_foreach (GHashTable *hash_table,
+ GHFunc func,
+ gpointer user_data);
+guint g_hash_table_foreach_remove (GHashTable *hash_table,
+ GHRFunc func,
+ gpointer user_data);
+guint g_hash_table_size (GHashTable *hash_table);
/* The following two functions are deprecated and will be removed in
* the next major release. They do no good. */
-void g_hash_table_freeze (GHashTable *hash_table);
-void g_hash_table_thaw (GHashTable *hash_table);
+void g_hash_table_freeze (GHashTable *hash_table);
+void g_hash_table_thaw (GHashTable *hash_table);
/* Hash Functions
*/
Index: gtree.c
===================================================================
RCS file: /cvs/gnome/glib/gtree.c,v
retrieving revision 1.17
diff -u -r1.17 gtree.c
--- gtree.c 2000/12/19 15:40:30 1.17
+++ gtree.c 2001/01/07 20:34:58
@@ -40,62 +40,71 @@
struct _GRealTree
{
- GTreeNode *root;
- GCompareFuncData key_compare;
- gpointer key_compare_data;
+ GTreeNode *root;
+ GCompareFuncData key_compare;
+ GFreeFunc key_destroy_func;
+ GFreeFunc value_destroy_func;
+ gpointer key_compare_data;
};
struct _GTreeNode
{
- gint balance; /* height (left) - height (right) */
- GTreeNode *left; /* left subtree */
- GTreeNode *right; /* right subtree */
- gpointer key; /* key for this node */
- gpointer value; /* value stored at this node */
+ gint balance; /* height (left) - height (right) */
+ GTreeNode *left; /* left subtree */
+ GTreeNode *right; /* right subtree */
+ gpointer key; /* key for this node */
+ gpointer value; /* value stored at this node */
};
-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,
- GCompareFuncData compare,
- gpointer comp_data,
- gpointer key,
- gpointer value,
- gint *inserted);
-static GTreeNode* g_tree_node_remove (GTreeNode *node,
- GCompareFuncData 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 gpointer g_tree_node_lookup (GTreeNode *node,
- GCompareFuncData 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,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func);
+static GTreeNode* g_tree_node_insert (GTreeNode *node,
+ GCompareFuncData compare,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func,
+ gpointer comp_data,
+ gpointer key,
+ gpointer value,
+ gboolean replace,
+ gboolean *inserted);
+static GTreeNode* g_tree_node_remove (GTreeNode *node,
+ GCompareFuncData compare,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func,
+ 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,
+ GCompareFuncData 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,
+ GFreeFunc key_destroy_func,
+ GFreeFunc 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,28 +175,43 @@
}
}
-GTree* g_tree_new_udata(GCompareFuncData key_compare_func,
- gpointer key_compare_data)
+GTree*
+g_tree_new (GCompareFunc key_compare_func)
{
+ return g_tree_new_full ((GCompareFuncData) key_compare_func,
+ NULL, NULL,
+ NULL);
+}
+
+GTree*
+g_tree_new_with_data (GCompareFuncData key_compare_func,
+ gpointer key_compare_data)
+{
+ return g_tree_new_full ((GCompareFuncData) key_compare_func,
+ NULL, NULL,
+ key_compare_data);
+}
+
+GTree*
+g_tree_new_full (GCompareFuncData key_compare_func,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func,
+ gpointer key_compare_data)
+{
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;
+ 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;
}
-GTree*
-g_tree_new (GCompareFunc key_compare_func)
-{
- return g_tree_new_udata ((GCompareFuncData) key_compare_func, NULL);
-}
-
-
void
g_tree_destroy (GTree *tree)
{
@@ -188,7 +221,9 @@
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);
}
@@ -197,8 +232,29 @@
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_destroy_func,
+ rtree->value_destroy_func,
+ rtree->key_compare_data,
+ key, value,
+ FALSE, &inserted);
+}
+
+void
+g_tree_replace (GTree *tree,
+ gpointer key,
+ gpointer value)
+{
GRealTree *rtree;
- gint inserted;
+ gboolean inserted;
g_return_if_fail (tree != NULL);
@@ -206,8 +262,11 @@
inserted = FALSE;
rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
+ rtree->key_destroy_func,
+ rtree->value_destroy_func,
rtree->key_compare_data,
- key, value, &inserted);
+ key, value,
+ TRUE, &inserted);
}
void
@@ -221,23 +280,71 @@
rtree = (GRealTree*) tree;
rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare,
+ rtree->key_destroy_func,
+ rtree->value_destroy_func,
rtree->key_compare_data, key);
}
+void
+g_tree_remove_no_notify (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,
+ NULL, NULL,
+ rtree->key_compare_data, key);
+}
+
gpointer
g_tree_lookup (GTree *tree,
gconstpointer key)
{
GRealTree *rtree;
+ GTreeNode *node;
g_return_val_if_fail (tree != NULL, NULL);
rtree = (GRealTree*) tree;
- return g_tree_node_lookup (rtree->root, rtree->key_compare,
+ node = g_tree_node_lookup (rtree->root, rtree->key_compare,
rtree->key_compare_data, key);
+
+ return node ? node->value : NULL;
}
+gboolean
+g_tree_lookup_extended (GTree *tree,
+ gconstpointer lookup_key,
+ gpointer *orig_key,
+ gpointer *value)
+{
+ GRealTree *rtree;
+ GTreeNode *node;
+
+ g_return_val_if_fail (tree != NULL, FALSE);
+
+ rtree = (GRealTree*) tree;
+
+ node = g_tree_node_lookup (rtree->root, rtree->key_compare,
+ rtree->key_compare_data, lookup_key);
+
+ if (node)
+ {
+ if (orig_key)
+ *orig_key = node->key;
+ if (value)
+ *value = node->value;
+ return TRUE;
+ }
+ else
+ return FALSE;
+}
+
void
g_tree_traverse (GTree *tree,
GTraverseFunc traverse_func,
@@ -321,12 +428,15 @@
}
static GTreeNode*
-g_tree_node_insert (GTreeNode *node,
- GCompareFuncData compare,
- gpointer compare_data,
- gpointer key,
- gpointer value,
- gint *inserted)
+g_tree_node_insert (GTreeNode *node,
+ GCompareFuncData compare,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func,
+ gpointer compare_data,
+ gpointer key,
+ gpointer value,
+ gboolean replace,
+ gboolean *inserted)
{
gint old_balance;
gint cmp;
@@ -341,7 +451,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;
}
@@ -351,7 +480,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;
@@ -369,7 +501,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;
@@ -392,10 +527,12 @@
}
static GTreeNode*
-g_tree_node_remove (GTreeNode *node,
- GCompareFuncData compare,
- gpointer compare_data,
- gconstpointer key)
+g_tree_node_remove (GTreeNode *node,
+ GCompareFuncData compare,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func,
+ gpointer compare_data,
+ gconstpointer key)
{
GTreeNode *new_root;
gint old_balance;
@@ -425,6 +562,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;
@@ -441,7 +583,10 @@
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,
+ key_destroy_func,
+ value_destroy_func,
+ compare_data, key);
node = g_tree_node_restore_left_balance (node, old_balance);
}
}
@@ -450,7 +595,10 @@
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,
+ key_destroy_func,
+ value_destroy_func,
+ compare_data, key);
node = g_tree_node_restore_right_balance (node, old_balance);
}
}
@@ -524,11 +672,11 @@
return node;
}
-static gpointer
-g_tree_node_lookup (GTreeNode *node,
- GCompareFuncData compare,
- gpointer compare_data,
- gconstpointer key)
+static GTreeNode *
+g_tree_node_lookup (GTreeNode *node,
+ GCompareFuncData compare,
+ gpointer compare_data,
+ gconstpointer key)
{
gint cmp;
@@ -537,7 +685,7 @@
cmp = (* compare) (key, node->key, compare_data);
if (cmp == 0)
- return node->value;
+ return node;
if (cmp < 0)
{
Index: gtree.h
===================================================================
RCS file: /cvs/gnome/glib/gtree.h,v
retrieving revision 1.2
diff -u -r1.2 gtree.h
--- gtree.h 2000/11/20 23:59:32 1.2
+++ gtree.h 2001/01/07 20:34:58
@@ -39,27 +39,39 @@
/* Balanced binary trees
*/
-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);
-
+GTree* g_tree_new (GCompareFunc key_compare_func);
+GTree* g_tree_new_with_data (GCompareFuncData key_compare_func,
+ gpointer user_data);
+GTree* g_tree_new_full (GCompareFuncData key_compare_func,
+ GFreeFunc key_destroy_func,
+ GFreeFunc value_destroy_func,
+ gpointer user_data);
+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_remove_no_notify (GTree *tree,
+ gconstpointer key);
+gpointer g_tree_lookup (GTree *tree,
+ gconstpointer key);
+gboolean g_tree_lookup_extended (GTree *tree,
+ gconstpointer lookup_key,
+ gpointer *orig_key,
+ gpointer *value);
+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
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
