#include "config.h"
#include "glib.h"
typedef struct _GTreeNode GTreeNode;
struct _GTree
{
GTreeNode *root;
GCompareDataFunc key_compare;
GDestroyNotify key_destroy_func;
GDestroyNotify value_destroy_func;
gpointer key_compare_data;
};
struct _GTreeNode
{
gint balance;
GTreeNode *left;
GTreeNode *right;
gpointer key;
gpointer value;
};
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 (GTree *tree,
GTreeNode *node,
gpointer key,
gpointer value,
gboolean replace,
gboolean *inserted);
static GTreeNode* g_tree_node_remove (GTree *tree,
GTreeNode *node,
gconstpointer key,
gboolean notify);
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);
static GMemChunk *node_mem_chunk = NULL;
static GTreeNode *node_free_list = NULL;
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,
GDestroyNotify key_destroy_func,
GDestroyNotify value_destroy_func)
{
if (node)
{
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;
node->value = NULL;
#endif
G_LOCK (g_tree_global);
node->right = node_free_list;
node_free_list = node;
G_UNLOCK (g_tree_global);
}
}
GTree*
g_tree_new (GCompareFunc key_compare_func)
{
g_return_val_if_fail (key_compare_func != NULL, NULL);
return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
NULL, NULL);
}
GTree*
g_tree_new_with_data (GCompareDataFunc key_compare_func,
gpointer key_compare_data)
{
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)
{
GTree *tree;
g_return_val_if_fail (key_compare_func != NULL, NULL);
tree = g_new (GTree, 1);
tree->root = NULL;
tree->key_compare = key_compare_func;
tree->key_destroy_func = key_destroy_func;
tree->value_destroy_func = value_destroy_func;
tree->key_compare_data = key_compare_data;
return tree;
}
void
g_tree_destroy (GTree *tree)
{
g_return_if_fail (tree != NULL);
g_tree_node_destroy (tree->root,
tree->key_destroy_func,
tree->value_destroy_func);
g_free (tree);
}
void
g_tree_insert (GTree *tree,
gpointer key,
gpointer value)
{
gboolean inserted;
g_return_if_fail (tree != NULL);
inserted = FALSE;
tree->root = g_tree_node_insert (tree,
tree->root,
key, value,
FALSE, &inserted);
}
void
g_tree_replace (GTree *tree,
gpointer key,
gpointer value)
{
gboolean inserted;
g_return_if_fail (tree != NULL);
inserted = FALSE;
tree->root = g_tree_node_insert (tree,
tree->root,
key, value,
TRUE, &inserted);
}
void
g_tree_remove (GTree *tree,
gconstpointer key)
{
g_return_if_fail (tree != NULL);
tree->root = g_tree_node_remove (tree, tree->root, key, TRUE);
}
void
g_tree_steal (GTree *tree,
gconstpointer key)
{
g_return_if_fail (tree != NULL);
tree->root = g_tree_node_remove (tree, tree->root, key, FALSE);
}
gpointer
g_tree_lookup (GTree *tree,
gconstpointer key)
{
GTreeNode *node;
g_return_val_if_fail (tree != NULL, NULL);
node = g_tree_node_lookup (tree->root,
tree->key_compare, tree->key_compare_data, key);
return node ? node->value : NULL;
}
gboolean
g_tree_lookup_extended (GTree *tree,
gconstpointer lookup_key,
gpointer *orig_key,
gpointer *value)
{
GTreeNode *node;
g_return_val_if_fail (tree != NULL, FALSE);
node = g_tree_node_lookup (tree->root,
tree->key_compare, tree->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_foreach (GTree *tree,
GTraverseFunc func,
gpointer user_data)
{
g_return_if_fail (tree != NULL);
if (!tree->root)
return;
g_tree_node_in_order (tree->root, func, user_data);
}
void
g_tree_traverse (GTree *tree,
GTraverseFunc traverse_func,
GTraverseType traverse_type,
gpointer user_data)
{
g_return_if_fail (tree != NULL);
if (!tree->root)
return;
switch (traverse_type)
{
case G_PRE_ORDER:
g_tree_node_pre_order (tree->root, traverse_func, user_data);
break;
case G_IN_ORDER:
g_tree_node_in_order (tree->root, traverse_func, user_data);
break;
case G_POST_ORDER:
g_tree_node_post_order (tree->root, traverse_func, user_data);
break;
case G_LEVEL_ORDER:
g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
break;
}
}
gpointer
g_tree_search (GTree *tree,
GCompareFunc search_func,
gconstpointer user_data)
{
g_return_val_if_fail (tree != NULL, NULL);
if (tree->root)
return g_tree_node_search (tree->root, search_func, user_data);
else
return NULL;
}
gint
g_tree_height (GTree *tree)
{
g_return_val_if_fail (tree != NULL, 0);
if (tree->root)
return g_tree_node_height (tree->root);
else
return 0;
}
gint
g_tree_nnodes (GTree *tree)
{
g_return_val_if_fail (tree != NULL, 0);
if (tree->root)
return g_tree_node_count (tree->root);
else
return 0;
}
static GTreeNode*
g_tree_node_insert (GTree *tree,
GTreeNode *node,
gpointer key,
gpointer value,
gboolean replace,
gboolean *inserted)
{
gint old_balance;
gint cmp;
if (!node)
{
*inserted = TRUE;
return g_tree_node_new (key, value);
}
cmp = tree->key_compare (key, node->key, tree->key_compare_data);
if (cmp == 0)
{
*inserted = FALSE;
if (tree->value_destroy_func)
tree->value_destroy_func (node->value);
node->value = value;
if (replace)
{
if (tree->key_destroy_func)
tree->key_destroy_func (node->key);
node->key = key;
}
else
{
if (tree->key_destroy_func)
tree->key_destroy_func (key);
}
return node;
}
if (cmp < 0)
{
if (node->left)
{
old_balance = node->left->balance;
node->left = g_tree_node_insert (tree,
node->left,
key, value,
replace, inserted);
if ((old_balance != node->left->balance) && node->left->balance)
node->balance -= 1;
}
else
{
*inserted = TRUE;
node->left = g_tree_node_new (key, value);
node->balance -= 1;
}
}
else if (cmp > 0)
{
if (node->right)
{
old_balance = node->right->balance;
node->right = g_tree_node_insert (tree,
node->right,
key, value,
replace, inserted);
if ((old_balance != node->right->balance) && node->right->balance)
node->balance += 1;
}
else
{
*inserted = TRUE;
node->right = g_tree_node_new (key, value);
node->balance += 1;
}
}
if (*inserted)
{
if ((node->balance < -1) || (node->balance > 1))
node = g_tree_node_balance (node);
}
return node;
}
static GTreeNode*
g_tree_node_remove (GTree *tree,
GTreeNode *node,
gconstpointer key,
gboolean notify)
{
GTreeNode *new_root;
gint old_balance;
gint cmp;
if (!node)
return NULL;
cmp = tree->key_compare (key, node->key, tree->key_compare_data);
if (cmp == 0)
{
GTreeNode *garbage;
garbage = node;
if (!node->right)
{
node = node->left;
}
else
{
old_balance = node->right->balance;
node->right = g_tree_node_remove_leftmost (node->right, &new_root);
new_root->left = node->left;
new_root->right = node->right;
new_root->balance = node->balance;
node = g_tree_node_restore_right_balance (new_root, old_balance);
}
if (notify)
{
if (tree->key_destroy_func)
tree->key_destroy_func (garbage->key);
if (tree->value_destroy_func)
tree->value_destroy_func (garbage->value);
}
#ifdef ENABLE_GC_FRIENDLY
garbage->left = NULL;
garbage->key = NULL;
garbage->value = NULL;
#endif
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 (tree, node->left, key, notify);
node = g_tree_node_restore_left_balance (node, old_balance);
}
}
else if (cmp > 0)
{
if (node->right)
{
old_balance = node->right->balance;
node->right = g_tree_node_remove (tree, node->right, key, notify);
node = g_tree_node_restore_right_balance (node, old_balance);
}
}
return node;
}
static GTreeNode*
g_tree_node_balance (GTreeNode *node)
{
if (node->balance < -1)
{
if (node->left->balance > 0)
node->left = g_tree_node_rotate_left (node->left);
node = g_tree_node_rotate_right (node);
}
else if (node->balance > 1)
{
if (node->right->balance < 0)
node->right = g_tree_node_rotate_right (node->right);
node = g_tree_node_rotate_left (node);
}
return node;
}
static GTreeNode*
g_tree_node_remove_leftmost (GTreeNode *node,
GTreeNode **leftmost)
{
gint old_balance;
if (!node->left)
{
*leftmost = node;
return node->right;
}
old_balance = node->left->balance;
node->left = g_tree_node_remove_leftmost (node->left, leftmost);
return g_tree_node_restore_left_balance (node, old_balance);
}
static GTreeNode*
g_tree_node_restore_left_balance (GTreeNode *node,
gint old_balance)
{
if (!node->left)
node->balance += 1;
else if ((node->left->balance != old_balance) &&
(node->left->balance == 0))
node->balance += 1;
if (node->balance > 1)
return g_tree_node_balance (node);
return node;
}
static GTreeNode*
g_tree_node_restore_right_balance (GTreeNode *node,
gint old_balance)
{
if (!node->right)
node->balance -= 1;
else if ((node->right->balance != old_balance) &&
(node->right->balance == 0))
node->balance -= 1;
if (node->balance < -1)
return g_tree_node_balance (node);
return node;
}
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, compare_data);
if (cmp == 0)
return node;
if (cmp < 0)
{
if (node->left)
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, compare_data, key);
}
return NULL;
}
static gint
g_tree_node_count (GTreeNode *node)
{
gint count;
count = 1;
if (node->left)
count += g_tree_node_count (node->left);
if (node->right)
count += g_tree_node_count (node->right);
return count;
}
static gint
g_tree_node_pre_order (GTreeNode *node,
GTraverseFunc traverse_func,
gpointer data)
{
if ((*traverse_func) (node->key, node->value, data))
return TRUE;
if (node->left)
{
if (g_tree_node_pre_order (node->left, traverse_func, data))
return TRUE;
}
if (node->right)
{
if (g_tree_node_pre_order (node->right, traverse_func, data))
return TRUE;
}
return FALSE;
}
static gint
g_tree_node_in_order (GTreeNode *node,
GTraverseFunc traverse_func,
gpointer data)
{
if (node->left)
{
if (g_tree_node_in_order (node->left, traverse_func, data))
return TRUE;
}
if ((*traverse_func) (node->key, node->value, data))
return TRUE;
if (node->right)
{
if (g_tree_node_in_order (node->right, traverse_func, data))
return TRUE;
}
return FALSE;
}
static gint
g_tree_node_post_order (GTreeNode *node,
GTraverseFunc traverse_func,
gpointer data)
{
if (node->left)
{
if (g_tree_node_post_order (node->left, traverse_func, data))
return TRUE;
}
if (node->right)
{
if (g_tree_node_post_order (node->right, traverse_func, data))
return TRUE;
}
if ((*traverse_func) (node->key, node->value, data))
return TRUE;
return FALSE;
}
static gpointer
g_tree_node_search (GTreeNode *node,
GCompareFunc search_func,
gconstpointer data)
{
gint dir;
if (!node)
return NULL;
do {
dir = (* search_func) (node->key, data);
if (dir == 0)
return node->value;
if (dir < 0)
node = node->left;
else if (dir > 0)
node = node->right;
} while (node);
return NULL;
}
static gint
g_tree_node_height (GTreeNode *node)
{
gint left_height;
gint right_height;
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);
return MAX (left_height, right_height) + 1;
}
return 0;
}
static GTreeNode*
g_tree_node_rotate_left (GTreeNode *node)
{
GTreeNode *right;
gint a_bal;
gint b_bal;
right = node->right;
node->right = right->left;
right->left = node;
a_bal = node->balance;
b_bal = right->balance;
if (b_bal <= 0)
{
if (a_bal >= 1)
right->balance = b_bal - 1;
else
right->balance = a_bal + b_bal - 2;
node->balance = a_bal - 1;
}
else
{
if (a_bal <= b_bal)
right->balance = a_bal - 2;
else
right->balance = b_bal - 1;
node->balance = a_bal - b_bal - 1;
}
return right;
}
static GTreeNode*
g_tree_node_rotate_right (GTreeNode *node)
{
GTreeNode *left;
gint a_bal;
gint b_bal;
left = node->left;
node->left = left->right;
left->right = node;
a_bal = node->balance;
b_bal = left->balance;
if (b_bal <= 0)
{
if (b_bal > a_bal)
left->balance = b_bal + 1;
else
left->balance = a_bal + 2;
node->balance = a_bal - b_bal + 1;
}
else
{
if (a_bal <= -1)
left->balance = b_bal + 1;
else
left->balance = a_bal + b_bal + 2;
node->balance = a_bal + 1;
}
return left;
}
static void
g_tree_node_check (GTreeNode *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_log (G_LOG_DOMAIN, 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)
g_tree_node_check (node->right);
}
}