* 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 Library General Public
+ * 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
- * Library General Public License for more details.
+ * Lesser General Public License for more details.
*
- * You should have received a copy of the GNU Library General Public
+ * 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/.
+ */
+
+/*
+ * MT safe
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
#include "glib.h"
struct _GRealTree
{
GTreeNode *root;
- GCompareFunc key_compare;
+ GCompareDataFunc key_compare;
+ gpointer key_compare_data;
};
struct _GTreeNode
gpointer value);
static void g_tree_node_destroy (GTreeNode *node);
static GTreeNode* g_tree_node_insert (GTreeNode *node,
- GCompareFunc compare,
+ GCompareDataFunc compare,
+ gpointer comp_data,
gpointer key,
gpointer value,
gint *inserted);
static GTreeNode* g_tree_node_remove (GTreeNode *node,
- GCompareFunc compare,
- gpointer key);
+ 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);
gint old_balance);
static GTreeNode* g_tree_node_restore_right_balance (GTreeNode *node,
gint old_balance);
-static gpointer g_tree_node_lookup (GTreeNode *node,
- GCompareFunc compare,
- gpointer key);
+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,
GTraverseFunc traverse_func,
gpointer data);
static gpointer g_tree_node_search (GTreeNode *node,
- GSearchFunc search_func,
- gpointer data);
+ 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);
static GMemChunk *node_mem_chunk = NULL;
-static GSList *node_free_list = NULL;
+static GTreeNode *node_free_list = NULL;
-GTree*
-g_tree_new (GCompareFunc key_compare_func)
+static GTreeNode*
+g_tree_node_new (gpointer key,
+ gpointer value)
+{
+ GTreeNode *node;
+
+ G_LOCK (g_tree_global);
+ if (node_free_list)
+ {
+ node = node_free_list;
+ node_free_list = node->right;
+ }
+ else
+ {
+ if (!node_mem_chunk)
+ node_mem_chunk = g_mem_chunk_new ("GLib GTreeNode mem chunk",
+ sizeof (GTreeNode),
+ 1024,
+ G_ALLOC_ONLY);
+
+ node = g_chunk_new (GTreeNode, node_mem_chunk);
+ }
+ G_UNLOCK (g_tree_global);
+
+ node->balance = 0;
+ node->left = NULL;
+ node->right = NULL;
+ node->key = key;
+ node->value = value;
+
+ return node;
+}
+
+static void
+g_tree_node_destroy (GTreeNode *node)
+{
+ if (node)
+ {
+ g_tree_node_destroy (node->right);
+ g_tree_node_destroy (node->left);
+
+#ifdef ENABLE_GC_FRIENDLY
+ node->left = NULL;
+ node->key = NULL;
+ node->value = NULL;
+#endif /* ENABLE_GC_FRIENDLY */
+
+ G_LOCK (g_tree_global);
+ node->right = node_free_list;
+ node_free_list = node;
+ G_UNLOCK (g_tree_global);
+ }
+}
+
+GTree* g_tree_new_udata(GCompareDataFunc key_compare_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;
return (GTree*) rtree;
}
+GTree*
+g_tree_new (GCompareFunc key_compare_func)
+{
+ return g_tree_new_udata ((GCompareDataFunc) key_compare_func, NULL);
+}
+
+
void
g_tree_destroy (GTree *tree)
{
inserted = FALSE;
rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
+ rtree->key_compare_data,
key, value, &inserted);
}
void
-g_tree_remove (GTree *tree,
- gpointer key)
+g_tree_remove (GTree *tree,
+ gconstpointer key)
{
GRealTree *rtree;
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
-g_tree_lookup (GTree *tree,
- gpointer key)
+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, key);
+ 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
rtree = (GRealTree*) tree;
- g_return_if_fail (rtree->root != NULL);
+ if (!rtree->root)
+ return;
switch (traverse_type)
{
}
gpointer
-g_tree_search (GTree *tree,
- GSearchFunc search_func,
- gpointer data)
+g_tree_search (GTree *tree,
+ GCompareFunc search_func,
+ gconstpointer data)
{
GRealTree *rtree;
if (rtree->root)
return g_tree_node_search (rtree->root, search_func, data);
- return NULL;
+ else
+ return NULL;
}
gint
if (rtree->root)
return g_tree_node_height (rtree->root);
- return 0;
+ else
+ return 0;
}
gint
if (rtree->root)
return g_tree_node_count (rtree->root);
- return 0;
-}
-
-
-static GTreeNode*
-g_tree_node_new (gpointer key,
- gpointer value)
-{
- GTreeNode *node;
- GSList *tmp_list;
-
- if (node_free_list)
- {
- tmp_list = node_free_list;
- node_free_list = node_free_list->next;
-
- node = tmp_list->data;
-
- {
- GListAllocator *tmp_allocator = g_list_set_allocator (NULL);
- g_slist_free_1 (tmp_list);
- g_list_set_allocator (tmp_allocator);
- }
- }
else
- {
- if (!node_mem_chunk)
- node_mem_chunk = g_mem_chunk_new ("tree node mem chunk", sizeof (GTreeNode), 1024, G_ALLOC_ONLY);
-
- node = g_chunk_new (GTreeNode, node_mem_chunk);
- }
-
- node->balance = 0;
- node->left = NULL;
- node->right = NULL;
- node->key = key;
- node->value = value;
-
- return node;
-}
-
-static void
-g_tree_node_destroy (GTreeNode *node)
-{
- if (node)
- {
- node_free_list = g_slist_prepend (node_free_list, node);
- g_tree_node_destroy (node->right);
- g_tree_node_destroy (node->left);
- }
+ return 0;
}
static GTreeNode*
-g_tree_node_insert (GTreeNode *node,
- GCompareFunc compare,
- gpointer key,
- gpointer value,
- gint *inserted)
+g_tree_node_insert (GTreeNode *node,
+ GCompareDataFunc compare,
+ gpointer compare_data,
+ gpointer key,
+ gpointer value,
+ gint *inserted)
{
gint old_balance;
gint cmp;
return g_tree_node_new (key, value);
}
- cmp = (* compare) (key, node->key);
+ cmp = (* compare) (key, node->key, compare_data);
if (cmp == 0)
{
*inserted = FALSE;
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;
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;
}
static GTreeNode*
-g_tree_node_remove (GTreeNode *node,
- GCompareFunc compare,
- gpointer key)
+g_tree_node_remove (GTreeNode *node,
+ GCompareDataFunc compare,
+ gpointer compare_data,
+ gconstpointer key)
{
- GTreeNode *garbage;
GTreeNode *new_root;
gint old_balance;
gint cmp;
if (!node)
return NULL;
- cmp = (* compare) (key, node->key);
+ cmp = (* compare) (key, node->key, compare_data);
if (cmp == 0)
{
+ GTreeNode *garbage;
+
garbage = node;
if (!node->right)
node = g_tree_node_restore_right_balance (new_root, old_balance);
}
- node_free_list = g_slist_prepend (node_free_list, garbage);
- }
+#ifdef ENABLE_GC_FRIENDLY
+ garbage->left = NULL;
+ garbage->key = NULL;
+ garbage->value = NULL;
+#endif /* ENABLE_GC_FRIENDLY */
+
+ G_LOCK (g_tree_global);
+ garbage->right = node_free_list;
+ node_free_list = garbage;
+ G_UNLOCK (g_tree_global);
+ }
else if (cmp < 0)
{
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);
}
}
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);
}
}
return node;
}
-static gpointer
-g_tree_node_lookup (GTreeNode *node,
- GCompareFunc compare,
- gpointer key)
+static GTreeNode *
+g_tree_node_lookup (GTreeNode *node,
+ GCompareDataFunc 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;
+ return node;
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;
}
static gpointer
-g_tree_node_search (GTreeNode *node,
- GSearchFunc search_func,
- gpointer data)
+g_tree_node_search (GTreeNode *node,
+ GCompareFunc search_func,
+ gconstpointer data)
{
gint dir;
node = node->left;
else if (dir > 0)
node = node->right;
- } while (node && (dir != 0));
+ } while (node);
return NULL;
}
static GTreeNode*
g_tree_node_rotate_left (GTreeNode *node)
{
- GTreeNode *left;
GTreeNode *right;
gint a_bal;
gint b_bal;
- left = node->left;
right = node->right;
node->right = right->left;
g_tree_node_rotate_right (GTreeNode *node)
{
GTreeNode *left;
- GTreeNode *right;
gint a_bal;
gint b_bal;
left = node->left;
- right = node->right;
node->left = left->right;
left->right = node;
gint left_height;
gint right_height;
gint balance;
-
+
if (node)
{
left_height = 0;
right_height = 0;
-
+
if (node->left)
left_height = g_tree_node_height (node->left);
if (node->right)
right_height = g_tree_node_height (node->right);
-
+
balance = right_height - left_height;
if (balance != node->balance)
- g_print ("g_tree_node_check: failed: %d ( %d )\n",
- balance, node->balance);
-
+ g_log (g_log_domain_glib, G_LOG_LEVEL_INFO,
+ "g_tree_node_check: failed: %d ( %d )\n",
+ balance, node->balance);
+
if (node->left)
g_tree_node_check (node->left);
if (node->right)
projects / platform / upstream / glib.git / blobdiff