X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=glib%2Fgtree.c;h=7fb41c24f79cf9377ab1d61cde069b4ae132a088;hb=d0083f7e2dd621c6b78496bdb6ecf5d580c5e110;hp=aeeb467ddc6857e2d6c6919872e7f39e111ab9ab;hpb=2645aaf59c540e25915da43eb1cb7fff6f445e6d;p=platform%2Fupstream%2Fglib.git diff --git a/glib/gtree.c b/glib/gtree.c index aeeb467..7fb41c2 100644 --- a/glib/gtree.c +++ b/glib/gtree.c @@ -12,9 +12,7 @@ * Lesser General Public License for more details. * * 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. + * License along with this library; if not, see . */ /* @@ -28,557 +26,1121 @@ * MT safe */ -#include "glib.h" +#include "config.h" +#include "gtree.h" + +#include "gatomic.h" +#include "gtestutils.h" +#include "gslice.h" + +/** + * SECTION:trees-binary + * @title: Balanced Binary Trees + * @short_description: a sorted collection of key/value pairs optimized + * for searching and traversing in order + * + * The #GTree structure and its associated functions provide a sorted + * collection of key/value pairs optimized for searching and traversing + * in order. + * + * To create a new #GTree use g_tree_new(). + * + * To insert a key/value pair into a #GTree use g_tree_insert(). + * + * To lookup the value corresponding to a given key, use + * g_tree_lookup() and g_tree_lookup_extended(). + * + * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To + * get the height of a #GTree, use g_tree_height(). + * + * To traverse a #GTree, calling a function for each node visited in + * the traversal, use g_tree_foreach(). + * + * To remove a key/value pair use g_tree_remove(). + * + * To destroy a #GTree, use g_tree_destroy(). + **/ + +#undef G_TREE_DEBUG + +#define MAX_GTREE_HEIGHT 40 -typedef struct _GRealTree GRealTree; typedef struct _GTreeNode GTreeNode; -struct _GRealTree +/** + * GTree: + * + * The GTree struct is an opaque data structure representing a + * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be + * accessed only by using the following functions. + */ +struct _GTree { - GTreeNode *root; - GCompareFuncData key_compare; - gpointer key_compare_data; + GTreeNode *root; + GCompareDataFunc key_compare; + GDestroyNotify key_destroy_func; + GDestroyNotify value_destroy_func; + gpointer key_compare_data; + guint nnodes; + gint ref_count; }; 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 */ + gpointer key; /* key for this node */ + gpointer value; /* value stored at this node */ + GTreeNode *left; /* left subtree */ + GTreeNode *right; /* right subtree */ + gint8 balance; /* height (right) - height (left) */ + guint8 left_child; + guint8 right_child; }; -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); - - -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); +static void g_tree_insert_internal (GTree *tree, + gpointer key, + gpointer value, + gboolean replace); +static gboolean g_tree_remove_internal (GTree *tree, + gconstpointer key, + gboolean steal); +static GTreeNode* g_tree_node_balance (GTreeNode *node); +static GTreeNode *g_tree_find_node (GTree *tree, + gconstpointer key); +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 GTreeNode* g_tree_node_rotate_left (GTreeNode *node); +static GTreeNode* g_tree_node_rotate_right (GTreeNode *node); +#ifdef G_TREE_DEBUG +static void g_tree_node_check (GTreeNode *node); +#endif static GTreeNode* g_tree_node_new (gpointer key, - gpointer value) + 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); + GTreeNode *node = g_slice_new (GTreeNode); node->balance = 0; node->left = NULL; node->right = NULL; + node->left_child = FALSE; + node->right_child = FALSE; node->key = key; node->value = value; return node; } -static void -g_tree_node_destroy (GTreeNode *node) +/** + * g_tree_new: + * @key_compare_func: the function used to order the nodes in the #GTree. + * It should return values similar to the standard strcmp() function - + * 0 if the two arguments are equal, a negative value if the first argument + * comes before the second, or a positive value if the first argument comes + * after the second. + * + * Creates a new #GTree. + * + * Returns: a newly allocated #GTree + */ +GTree * +g_tree_new (GCompareFunc key_compare_func) { - 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_return_val_if_fail (key_compare_func != NULL, NULL); - G_LOCK (g_tree_global); - node->right = node_free_list; - node_free_list = node; - G_UNLOCK (g_tree_global); - } + return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL, + NULL, NULL); } -GTree* g_tree_new_udata(GCompareFuncData key_compare_func, - gpointer key_compare_data) +/** + * g_tree_new_with_data: + * @key_compare_func: qsort()-style comparison function + * @key_compare_data: data to pass to comparison function + * + * Creates a new #GTree with a comparison function that accepts user data. + * See g_tree_new() for more details. + * + * Returns: a newly allocated #GTree + */ +GTree * +g_tree_new_with_data (GCompareDataFunc key_compare_func, + gpointer key_compare_data) { - GRealTree *rtree; + g_return_val_if_fail (key_compare_func != NULL, NULL); + + return g_tree_new_full (key_compare_func, key_compare_data, + NULL, NULL); +} +/** + * g_tree_new_full: + * @key_compare_func: qsort()-style comparison function + * @key_compare_data: data to pass to comparison function + * @key_destroy_func: a function to free the memory allocated for the key + * used when removing the entry from the #GTree or %NULL if you don't + * want to supply such a function + * @value_destroy_func: a function to free the memory allocated for the + * value used when removing the entry from the #GTree or %NULL if you + * don't want to supply such a function + * + * Creates a new #GTree like g_tree_new() and allows to specify functions + * to free the memory allocated for the key and value that get called when + * removing the entry from the #GTree. + * + * Returns: a newly allocated #GTree + */ +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_slice_new (GTree); + 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; + tree->nnodes = 0; + tree->ref_count = 1; + + return tree; +} - rtree = g_new (GRealTree, 1); - rtree->root = NULL; - rtree->key_compare = key_compare_func; - rtree->key_compare_data = key_compare_data; +static inline GTreeNode * +g_tree_first_node (GTree *tree) +{ + GTreeNode *tmp; - return (GTree*) rtree; -} + if (!tree->root) + return NULL; -GTree* -g_tree_new (GCompareFunc key_compare_func) + tmp = tree->root; + + while (tmp->left_child) + tmp = tmp->left; + + return tmp; +} + +static inline GTreeNode * +g_tree_node_previous (GTreeNode *node) { - return g_tree_new_udata ((GCompareFuncData) key_compare_func, NULL); + GTreeNode *tmp; + + tmp = node->left; + + if (node->left_child) + while (tmp->right_child) + tmp = tmp->right; + + return tmp; } +static inline GTreeNode * +g_tree_node_next (GTreeNode *node) +{ + GTreeNode *tmp; + + tmp = node->right; -void -g_tree_destroy (GTree *tree) + if (node->right_child) + while (tmp->left_child) + tmp = tmp->left; + + return tmp; +} + +static void +g_tree_remove_all (GTree *tree) { - GRealTree *rtree; + GTreeNode *node; + GTreeNode *next; g_return_if_fail (tree != NULL); - rtree = (GRealTree*) tree; + node = g_tree_first_node (tree); - g_tree_node_destroy (rtree->root); - g_free (rtree); + while (node) + { + next = g_tree_node_next (node); + + if (tree->key_destroy_func) + tree->key_destroy_func (node->key); + if (tree->value_destroy_func) + tree->value_destroy_func (node->value); + g_slice_free (GTreeNode, node); + + node = next; + } + + tree->root = NULL; + tree->nnodes = 0; } -void -g_tree_insert (GTree *tree, - gpointer key, - gpointer value) +/** + * g_tree_ref: + * @tree: a #GTree + * + * Increments the reference count of @tree by one. + * + * It is safe to call this function from any thread. + * + * Returns: the passed in #GTree + * + * Since: 2.22 + */ +GTree * +g_tree_ref (GTree *tree) { - GRealTree *rtree; - gint inserted; + g_return_val_if_fail (tree != NULL, NULL); - g_return_if_fail (tree != NULL); + g_atomic_int_inc (&tree->ref_count); + + return tree; +} - rtree = (GRealTree*) tree; +/** + * g_tree_unref: + * @tree: a #GTree + * + * Decrements the reference count of @tree by one. + * If the reference count drops to 0, all keys and values will + * be destroyed (if destroy functions were specified) and all + * memory allocated by @tree will be released. + * + * It is safe to call this function from any thread. + * + * Since: 2.22 + */ +void +g_tree_unref (GTree *tree) +{ + g_return_if_fail (tree != NULL); - inserted = FALSE; - rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare, - rtree->key_compare_data, - key, value, &inserted); + if (g_atomic_int_dec_and_test (&tree->ref_count)) + { + g_tree_remove_all (tree); + g_slice_free (GTree, tree); + } } +/** + * g_tree_destroy: + * @tree: a #GTree + * + * Removes all keys and values from the #GTree and decreases its + * reference count by one. If keys and/or values are dynamically + * allocated, you should either free them first or create the #GTree + * using g_tree_new_full(). In the latter case the destroy functions + * you supplied will be called on all keys and values before destroying + * the #GTree. + */ void -g_tree_remove (GTree *tree, - gconstpointer key) +g_tree_destroy (GTree *tree) { - GRealTree *rtree; + g_return_if_fail (tree != NULL); + g_tree_remove_all (tree); + g_tree_unref (tree); +} + +/** + * g_tree_insert: + * @tree: a #GTree + * @key: the key to insert + * @value: the value corresponding to the key + * + * Inserts a key/value pair into a #GTree. + * + * If the given key already exists in the #GTree its corresponding value + * is set to the new value. If you supplied a @value_destroy_func when + * creating the #GTree, the old value is freed using that function. If + * you supplied a @key_destroy_func when creating the #GTree, the passed + * key is freed using that function. + * + * The tree is automatically 'balanced' as new key/value pairs are added, + * so that the distance from the root to every leaf is as small as possible. + */ +void +g_tree_insert (GTree *tree, + gpointer key, + gpointer value) +{ g_return_if_fail (tree != NULL); - rtree = (GRealTree*) tree; + g_tree_insert_internal (tree, key, value, FALSE); - rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare, - rtree->key_compare_data, key); +#ifdef G_TREE_DEBUG + g_tree_node_check (tree->root); +#endif } -gpointer -g_tree_lookup (GTree *tree, - gconstpointer key) +/** + * g_tree_replace: + * @tree: a #GTree + * @key: the key to insert + * @value: the value corresponding to the key + * + * Inserts a new key and value into a #GTree similar to g_tree_insert(). + * The difference is that if the key already exists in the #GTree, it gets + * replaced by the new key. If you supplied a @value_destroy_func when + * creating the #GTree, the old value is freed using that function. If you + * supplied a @key_destroy_func when creating the #GTree, the old key is + * freed using that function. + * + * The tree is automatically 'balanced' as new key/value pairs are added, + * so that the distance from the root to every leaf is as small as possible. + */ +void +g_tree_replace (GTree *tree, + gpointer key, + gpointer value) { - GRealTree *rtree; - - g_return_val_if_fail (tree != NULL, NULL); + g_return_if_fail (tree != NULL); - rtree = (GRealTree*) tree; + g_tree_insert_internal (tree, key, value, TRUE); - return g_tree_node_lookup (rtree->root, rtree->key_compare, - rtree->key_compare_data, key); +#ifdef G_TREE_DEBUG + g_tree_node_check (tree->root); +#endif } -void -g_tree_traverse (GTree *tree, - GTraverseFunc traverse_func, - GTraverseType traverse_type, - gpointer data) +/* internal insert routine */ +static void +g_tree_insert_internal (GTree *tree, + gpointer key, + gpointer value, + gboolean replace) { - GRealTree *rtree; + GTreeNode *node; + GTreeNode *path[MAX_GTREE_HEIGHT]; + int idx; g_return_if_fail (tree != NULL); - rtree = (GRealTree*) tree; + if (!tree->root) + { + tree->root = g_tree_node_new (key, value); + tree->nnodes++; + return; + } - if (!rtree->root) - return; + idx = 0; + path[idx++] = NULL; + node = tree->root; - switch (traverse_type) + while (1) { - case G_PRE_ORDER: - g_tree_node_pre_order (rtree->root, traverse_func, data); - break; + int cmp = tree->key_compare (key, node->key, tree->key_compare_data); + + if (cmp == 0) + { + 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 + { + /* free the passed key */ + if (tree->key_destroy_func) + tree->key_destroy_func (key); + } + + return; + } + else if (cmp < 0) + { + if (node->left_child) + { + path[idx++] = node; + node = node->left; + } + else + { + GTreeNode *child = g_tree_node_new (key, value); + + child->left = node->left; + child->right = node; + node->left = child; + node->left_child = TRUE; + node->balance -= 1; + + tree->nnodes++; + + break; + } + } + else + { + if (node->right_child) + { + path[idx++] = node; + node = node->right; + } + else + { + GTreeNode *child = g_tree_node_new (key, value); + + child->right = node->right; + child->left = node; + node->right = child; + node->right_child = TRUE; + node->balance += 1; + + tree->nnodes++; + + break; + } + } + } - case G_IN_ORDER: - g_tree_node_in_order (rtree->root, traverse_func, data); - break; + /* Restore balance. This is the goodness of a non-recursive + * implementation, when we are done with balancing we 'break' + * the loop and we are done. + */ + while (1) + { + GTreeNode *bparent = path[--idx]; + gboolean left_node = (bparent && node == bparent->left); + g_assert (!bparent || bparent->left == node || bparent->right == node); + + if (node->balance < -1 || node->balance > 1) + { + node = g_tree_node_balance (node); + if (bparent == NULL) + tree->root = node; + else if (left_node) + bparent->left = node; + else + bparent->right = node; + } + + if (node->balance == 0 || bparent == NULL) + break; + + if (left_node) + bparent->balance -= 1; + else + bparent->balance += 1; - case G_POST_ORDER: - g_tree_node_post_order (rtree->root, traverse_func, data); - break; - - case G_LEVEL_ORDER: - g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented."); - break; + node = bparent; } } -gpointer -g_tree_search (GTree *tree, - GCompareFunc search_func, - gconstpointer data) +/** + * g_tree_remove: + * @tree: a #GTree + * @key: the key to remove + * + * Removes a key/value pair from a #GTree. + * + * If the #GTree was created using g_tree_new_full(), the key and value + * are freed using the supplied destroy functions, otherwise you have to + * make sure that any dynamically allocated values are freed yourself. + * If the key does not exist in the #GTree, the function does nothing. + * + * Returns: %TRUE if the key was found (prior to 2.8, this function + * returned nothing) + */ +gboolean +g_tree_remove (GTree *tree, + gconstpointer key) { - GRealTree *rtree; + gboolean removed; - g_return_val_if_fail (tree != NULL, NULL); + g_return_val_if_fail (tree != NULL, FALSE); - rtree = (GRealTree*) tree; + removed = g_tree_remove_internal (tree, key, FALSE); - if (rtree->root) - return g_tree_node_search (rtree->root, search_func, data); - else - return NULL; +#ifdef G_TREE_DEBUG + g_tree_node_check (tree->root); +#endif + + return removed; } -gint -g_tree_height (GTree *tree) +/** + * g_tree_steal: + * @tree: a #GTree + * @key: the key to remove + * + * Removes a key and its associated value from a #GTree without calling + * the key and value destroy functions. + * + * If the key does not exist in the #GTree, the function does nothing. + * + * Returns: %TRUE if the key was found (prior to 2.8, this function + * returned nothing) + */ +gboolean +g_tree_steal (GTree *tree, + gconstpointer key) { - GRealTree *rtree; + gboolean removed; - g_return_val_if_fail (tree != NULL, 0); + g_return_val_if_fail (tree != NULL, FALSE); - rtree = (GRealTree*) tree; + removed = g_tree_remove_internal (tree, key, TRUE); - if (rtree->root) - return g_tree_node_height (rtree->root); - else - return 0; +#ifdef G_TREE_DEBUG + g_tree_node_check (tree->root); +#endif + + return removed; } -gint -g_tree_nnodes (GTree *tree) +/* internal remove routine */ +static gboolean +g_tree_remove_internal (GTree *tree, + gconstpointer key, + gboolean steal) { - GRealTree *rtree; + GTreeNode *node, *parent, *balance; + GTreeNode *path[MAX_GTREE_HEIGHT]; + int idx; + gboolean left_node; - g_return_val_if_fail (tree != NULL, 0); + g_return_val_if_fail (tree != NULL, FALSE); - rtree = (GRealTree*) tree; + if (!tree->root) + return FALSE; - if (rtree->root) - return g_tree_node_count (rtree->root); - else - return 0; -} - -static GTreeNode* -g_tree_node_insert (GTreeNode *node, - GCompareFuncData compare, - gpointer compare_data, - gpointer key, - gpointer value, - gint *inserted) -{ - gint old_balance; - gint cmp; + idx = 0; + path[idx++] = NULL; + node = tree->root; - if (!node) + while (1) { - *inserted = TRUE; - return g_tree_node_new (key, value); - } + int cmp = tree->key_compare (key, node->key, tree->key_compare_data); + + if (cmp == 0) + break; + else if (cmp < 0) + { + if (!node->left_child) + return FALSE; + + path[idx++] = node; + node = node->left; + } + else + { + if (!node->right_child) + return FALSE; - cmp = (* compare) (key, node->key, compare_data); - if (cmp == 0) - { - *inserted = FALSE; - node->value = value; - return node; + path[idx++] = node; + node = node->right; + } } - if (cmp < 0) + /* The following code is almost equal to g_tree_remove_node, + * except that we do not have to call g_tree_node_parent. + */ + balance = parent = path[--idx]; + g_assert (!parent || parent->left == node || parent->right == node); + left_node = (parent && node == parent->left); + + if (!node->left_child) { - if (node->left) - { - old_balance = node->left->balance; - 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; - } - else - { - *inserted = TRUE; - node->left = g_tree_node_new (key, value); - node->balance -= 1; - } + if (!node->right_child) + { + if (!parent) + tree->root = NULL; + else if (left_node) + { + parent->left_child = FALSE; + parent->left = node->left; + parent->balance += 1; + } + else + { + parent->right_child = FALSE; + parent->right = node->right; + parent->balance -= 1; + } + } + else /* node has a right child */ + { + GTreeNode *tmp = g_tree_node_next (node); + tmp->left = node->left; + + if (!parent) + tree->root = node->right; + else if (left_node) + { + parent->left = node->right; + parent->balance += 1; + } + else + { + parent->right = node->right; + parent->balance -= 1; + } + } } - else if (cmp > 0) + else /* node has a left child */ { - if (node->right) - { - old_balance = node->right->balance; - 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; - } - else - { - *inserted = TRUE; - node->right = g_tree_node_new (key, value); - node->balance += 1; - } + if (!node->right_child) + { + GTreeNode *tmp = g_tree_node_previous (node); + tmp->right = node->right; + + if (parent == NULL) + tree->root = node->left; + else if (left_node) + { + parent->left = node->left; + parent->balance += 1; + } + else + { + parent->right = node->left; + parent->balance -= 1; + } + } + else /* node has a both children (pant, pant!) */ + { + GTreeNode *prev = node->left; + GTreeNode *next = node->right; + GTreeNode *nextp = node; + int old_idx = idx + 1; + idx++; + + /* path[idx] == parent */ + /* find the immediately next node (and its parent) */ + while (next->left_child) + { + path[++idx] = nextp = next; + next = next->left; + } + + path[old_idx] = next; + balance = path[idx]; + + /* remove 'next' from the tree */ + if (nextp != node) + { + if (next->right_child) + nextp->left = next->right; + else + nextp->left_child = FALSE; + nextp->balance += 1; + + next->right_child = TRUE; + next->right = node->right; + } + else + node->balance -= 1; + + /* set the prev to point to the right place */ + while (prev->right_child) + prev = prev->right; + prev->right = next; + + /* prepare 'next' to replace 'node' */ + next->left_child = TRUE; + next->left = node->left; + next->balance = node->balance; + + if (!parent) + tree->root = next; + else if (left_node) + parent->left = next; + else + parent->right = next; + } } - if (*inserted) + /* restore balance */ + if (balance) + while (1) + { + GTreeNode *bparent = path[--idx]; + g_assert (!bparent || bparent->left == balance || bparent->right == balance); + left_node = (bparent && balance == bparent->left); + + if(balance->balance < -1 || balance->balance > 1) + { + balance = g_tree_node_balance (balance); + if (!bparent) + tree->root = balance; + else if (left_node) + bparent->left = balance; + else + bparent->right = balance; + } + + if (balance->balance != 0 || !bparent) + break; + + if (left_node) + bparent->balance += 1; + else + bparent->balance -= 1; + + balance = bparent; + } + + if (!steal) { - if ((node->balance < -1) || (node->balance > 1)) - node = g_tree_node_balance (node); + if (tree->key_destroy_func) + tree->key_destroy_func (node->key); + if (tree->value_destroy_func) + tree->value_destroy_func (node->value); } - return node; + g_slice_free (GTreeNode, node); + + tree->nnodes--; + + return TRUE; } -static GTreeNode* -g_tree_node_remove (GTreeNode *node, - GCompareFuncData compare, - gpointer compare_data, - gconstpointer key) +/** + * g_tree_lookup: + * @tree: a #GTree + * @key: the key to look up + * + * Gets the value corresponding to the given key. Since a #GTree is + * automatically balanced as key/value pairs are added, key lookup + * is O(log n) (where n is the number of key/value pairs in the tree). + * + * Returns: the value corresponding to the key, or %NULL + * if the key was not found + */ +gpointer +g_tree_lookup (GTree *tree, + gconstpointer key) { - GTreeNode *new_root; - gint old_balance; - gint cmp; - - if (!node) - return NULL; + GTreeNode *node; - cmp = (* compare) (key, node->key, compare_data); - if (cmp == 0) - { - GTreeNode *garbage; + g_return_val_if_fail (tree != NULL, NULL); - garbage = node; + node = g_tree_find_node (tree, key); + + return node ? node->value : NULL; +} - 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); - } - -#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, compare_data, key); - node = g_tree_node_restore_left_balance (node, old_balance); - } - } - else if (cmp > 0) +/** + * g_tree_lookup_extended: + * @tree: a #GTree + * @lookup_key: the key to look up + * @orig_key: returns the original key + * @value: returns the value associated with the key + * + * Looks up a key in the #GTree, returning the original key and the + * associated value. This is useful if you need to free the memory + * allocated for the original key, for example before calling + * g_tree_remove(). + * + * Returns: %TRUE if the key was found in the #GTree + */ +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_find_node (tree, lookup_key); + + if (node) { - if (node->right) - { - old_balance = node->right->balance; - node->right = g_tree_node_remove (node->right, compare, compare_data, key); - node = g_tree_node_restore_right_balance (node, old_balance); - } + if (orig_key) + *orig_key = node->key; + if (value) + *value = node->value; + return TRUE; } - - return node; + else + return FALSE; } -static GTreeNode* -g_tree_node_balance (GTreeNode *node) +/** + * g_tree_foreach: + * @tree: a #GTree + * @func: the function to call for each node visited. + * If this function returns %TRUE, the traversal is stopped. + * @user_data: user data to pass to the function + * + * Calls the given function for each of the key/value pairs in the #GTree. + * The function is passed the key and value of each pair, and the given + * @data parameter. The tree is traversed in sorted order. + * + * The tree may not be modified while iterating over it (you can't + * add/remove items). To remove all items matching a predicate, you need + * to add each item to a list in your #GTraverseFunc as you walk over + * the tree, then walk the list and remove each item. + */ +void +g_tree_foreach (GTree *tree, + GTraverseFunc func, + gpointer user_data) { - 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) + GTreeNode *node; + + g_return_if_fail (tree != NULL); + + if (!tree->root) + return; + + node = g_tree_first_node (tree); + + while (node) { - if (node->right->balance < 0) - node->right = g_tree_node_rotate_right (node->right); - node = g_tree_node_rotate_left (node); + if ((*func) (node->key, node->value, user_data)) + break; + + node = g_tree_node_next (node); } - - return node; } -static GTreeNode* -g_tree_node_remove_leftmost (GTreeNode *node, - GTreeNode **leftmost) +/** + * g_tree_traverse: + * @tree: a #GTree + * @traverse_func: the function to call for each node visited. If this + * function returns %TRUE, the traversal is stopped. + * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER, + * %G_PRE_ORDER and %G_POST_ORDER + * @user_data: user data to pass to the function + * + * Calls the given function for each node in the #GTree. + * + * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. + * If you just want to visit all nodes in sorted order, use + * g_tree_foreach() instead. If you really need to visit nodes in + * a different order, consider using an [n-ary tree][glib-N-ary-Trees]. + */ +/** + * GTraverseFunc: + * @key: a key of a #GTree node + * @value: the value corresponding to the key + * @data: user data passed to g_tree_traverse() + * + * Specifies the type of function passed to g_tree_traverse(). It is + * passed the key and value of each node, together with the @user_data + * parameter passed to g_tree_traverse(). If the function returns + * %TRUE, the traversal is stopped. + * + * Returns: %TRUE to stop the traversal + */ +void +g_tree_traverse (GTree *tree, + GTraverseFunc traverse_func, + GTraverseType traverse_type, + gpointer user_data) { - gint old_balance; + g_return_if_fail (tree != NULL); - if (!node->left) + if (!tree->root) + return; + + switch (traverse_type) { - *leftmost = node; - return node->right; - } + 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; - 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); + 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; + } } -static GTreeNode* -g_tree_node_restore_left_balance (GTreeNode *node, - gint old_balance) +/** + * g_tree_search: + * @tree: a #GTree + * @search_func: a function used to search the #GTree + * @user_data: the data passed as the second argument to @search_func + * + * Searches a #GTree using @search_func. + * + * The @search_func is called with a pointer to the key of a key/value + * pair in the tree, and the passed in @user_data. If @search_func returns + * 0 for a key/value pair, then the corresponding value is returned as + * the result of g_tree_search(). If @search_func returns -1, searching + * will proceed among the key/value pairs that have a smaller key; if + * @search_func returns 1, searching will proceed among the key/value + * pairs that have a larger key. + * + * Returns: the value corresponding to the found key, or %NULL + * if the key was not found + */ +gpointer +g_tree_search (GTree *tree, + GCompareFunc search_func, + gconstpointer user_data) { - if (!node->left) - node->balance += 1; - else if ((node->left->balance != old_balance) && - (node->left->balance == 0)) - node->balance += 1; + g_return_val_if_fail (tree != NULL, NULL); - if (node->balance > 1) - return g_tree_node_balance (node); - return node; + if (tree->root) + return g_tree_node_search (tree->root, search_func, user_data); + else + return NULL; } -static GTreeNode* -g_tree_node_restore_right_balance (GTreeNode *node, - gint old_balance) +/** + * g_tree_height: + * @tree: a #GTree + * + * Gets the height of a #GTree. + * + * If the #GTree contains no nodes, the height is 0. + * If the #GTree contains only one root node the height is 1. + * If the root node has children the height is 2, etc. + * + * Returns: the height of @tree + */ +gint +g_tree_height (GTree *tree) { - if (!node->right) - node->balance -= 1; - else if ((node->right->balance != old_balance) && - (node->right->balance == 0)) - node->balance -= 1; + GTreeNode *node; + gint height; - if (node->balance < -1) - return g_tree_node_balance (node); - return node; + g_return_val_if_fail (tree != NULL, 0); + + if (!tree->root) + return 0; + + height = 0; + node = tree->root; + + while (1) + { + height += 1 + MAX(node->balance, 0); + + if (!node->left_child) + return height; + + node = node->left; + } } -static gpointer -g_tree_node_lookup (GTreeNode *node, - GCompareFuncData compare, - gpointer compare_data, - gconstpointer key) +/** + * g_tree_nnodes: + * @tree: a #GTree + * + * Gets the number of nodes in a #GTree. + * + * Returns: the number of nodes in @tree + */ +gint +g_tree_nnodes (GTree *tree) { - gint cmp; - - if (!node) - return NULL; + g_return_val_if_fail (tree != NULL, 0); - cmp = (* compare) (key, node->key, compare_data); - if (cmp == 0) - return node->value; + return tree->nnodes; +} - if (cmp < 0) +static GTreeNode * +g_tree_node_balance (GTreeNode *node) +{ + if (node->balance < -1) { - if (node->left) - return g_tree_node_lookup (node->left, compare, compare_data, key); + if (node->left->balance > 0) + node->left = g_tree_node_rotate_left (node->left); + node = g_tree_node_rotate_right (node); } - else if (cmp > 0) + else if (node->balance > 1) { - if (node->right) - return g_tree_node_lookup (node->right, compare, compare_data, key); + if (node->right->balance < 0) + node->right = g_tree_node_rotate_right (node->right); + node = g_tree_node_rotate_left (node); } - return NULL; + return node; } -static gint -g_tree_node_count (GTreeNode *node) +static GTreeNode * +g_tree_find_node (GTree *tree, + gconstpointer key) { - gint count; + GTreeNode *node; + gint cmp; - count = 1; - if (node->left) - count += g_tree_node_count (node->left); - if (node->right) - count += g_tree_node_count (node->right); + node = tree->root; + if (!node) + return NULL; - return count; + while (1) + { + cmp = tree->key_compare (key, node->key, tree->key_compare_data); + if (cmp == 0) + return node; + else if (cmp < 0) + { + if (!node->left_child) + return NULL; + + node = node->left; + } + else + { + if (!node->right_child) + return NULL; + + node = node->right; + } + } } static gint g_tree_node_pre_order (GTreeNode *node, - GTraverseFunc traverse_func, - gpointer data) + GTraverseFunc traverse_func, + gpointer data) { if ((*traverse_func) (node->key, node->value, data)) return TRUE; - if (node->left) + + if (node->left_child) { if (g_tree_node_pre_order (node->left, traverse_func, data)) - return TRUE; + return TRUE; } - if (node->right) + + if (node->right_child) { if (g_tree_node_pre_order (node->right, traverse_func, data)) - return TRUE; + return TRUE; } return FALSE; @@ -586,40 +1148,44 @@ g_tree_node_pre_order (GTreeNode *node, static gint g_tree_node_in_order (GTreeNode *node, - GTraverseFunc traverse_func, - gpointer data) + GTraverseFunc traverse_func, + gpointer data) { - if (node->left) + if (node->left_child) { if (g_tree_node_in_order (node->left, traverse_func, data)) - return TRUE; + return TRUE; } + if ((*traverse_func) (node->key, node->value, data)) return TRUE; - if (node->right) + + if (node->right_child) { if (g_tree_node_in_order (node->right, traverse_func, data)) - return TRUE; + return TRUE; } - + return FALSE; } static gint g_tree_node_post_order (GTreeNode *node, - GTraverseFunc traverse_func, - gpointer data) + GTraverseFunc traverse_func, + gpointer data) { - if (node->left) + if (node->left_child) { if (g_tree_node_post_order (node->left, traverse_func, data)) - return TRUE; + return TRUE; } - if (node->right) + + if (node->right_child) { if (g_tree_node_post_order (node->right, traverse_func, data)) - return TRUE; + return TRUE; } + if ((*traverse_func) (node->key, node->value, data)) return TRUE; @@ -628,52 +1194,37 @@ g_tree_node_post_order (GTreeNode *node, static gpointer g_tree_node_search (GTreeNode *node, - GCompareFunc search_func, - gconstpointer data) + 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 && (dir != 0)); - - return NULL; -} - -static gint -g_tree_node_height (GTreeNode *node) -{ - gint left_height; - gint right_height; - - if (node) + while (1) { - 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); + dir = (* search_func) (node->key, data); + if (dir == 0) + return node->value; + else if (dir < 0) + { + if (!node->left_child) + return NULL; + + node = node->left; + } + else + { + if (!node->right_child) + return NULL; - return MAX (left_height, right_height) + 1; + node = node->right; + } } - - return 0; } -static GTreeNode* +static GTreeNode * g_tree_node_rotate_left (GTreeNode *node) { GTreeNode *right; @@ -682,7 +1233,13 @@ g_tree_node_rotate_left (GTreeNode *node) right = node->right; - node->right = right->left; + if (right->left_child) + node->right = right->left; + else + { + node->right_child = FALSE; + right->left_child = TRUE; + } right->left = node; a_bal = node->balance; @@ -691,24 +1248,24 @@ g_tree_node_rotate_left (GTreeNode *node) if (b_bal <= 0) { if (a_bal >= 1) - right->balance = b_bal - 1; + right->balance = b_bal - 1; else - right->balance = a_bal + b_bal - 2; + right->balance = a_bal + b_bal - 2; node->balance = a_bal - 1; } else { if (a_bal <= b_bal) - right->balance = a_bal - 2; + right->balance = a_bal - 2; else - right->balance = b_bal - 1; + right->balance = b_bal - 1; node->balance = a_bal - b_bal - 1; } return right; } -static GTreeNode* +static GTreeNode * g_tree_node_rotate_right (GTreeNode *node) { GTreeNode *left; @@ -717,7 +1274,13 @@ g_tree_node_rotate_right (GTreeNode *node) left = node->left; - node->left = left->right; + if (left->right_child) + node->left = left->right; + else + { + node->left_child = FALSE; + left->right_child = TRUE; + } left->right = node; a_bal = node->balance; @@ -726,49 +1289,109 @@ g_tree_node_rotate_right (GTreeNode *node) if (b_bal <= 0) { if (b_bal > a_bal) - left->balance = b_bal + 1; + left->balance = b_bal + 1; else - left->balance = a_bal + 2; + left->balance = a_bal + 2; node->balance = a_bal - b_bal + 1; } else { if (a_bal <= -1) - left->balance = b_bal + 1; + left->balance = b_bal + 1; else - left->balance = a_bal + b_bal + 2; + left->balance = a_bal + b_bal + 2; node->balance = a_bal + 1; } return left; } +#ifdef G_TREE_DEBUG +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_child) + left_height = g_tree_node_height (node->left); + + if (node->right_child) + right_height = g_tree_node_height (node->right); + + return MAX (left_height, right_height) + 1; + } + + return 0; +} + static void g_tree_node_check (GTreeNode *node) { gint left_height; gint right_height; gint balance; - + GTreeNode *tmp; + if (node) { + if (node->left_child) + { + tmp = g_tree_node_previous (node); + g_assert (tmp->right == node); + } + + if (node->right_child) + { + tmp = g_tree_node_next (node); + g_assert (tmp->left == 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); + if (node->left_child) + left_height = g_tree_node_height (node->left); + if (node->right_child) + right_height = g_tree_node_height (node->right); balance = right_height - left_height; - if (balance != node->balance) - g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, - "g_tree_node_check: failed: %d ( %d )\n", - balance, node->balance); + g_assert (balance == node->balance); - if (node->left) - g_tree_node_check (node->left); - if (node->right) - g_tree_node_check (node->right); + if (node->left_child) + g_tree_node_check (node->left); + if (node->right_child) + g_tree_node_check (node->right); } } + +static void +g_tree_node_dump (GTreeNode *node, + gint indent) +{ + g_print ("%*s%c\n", indent, "", *(char *)node->key); + + if (node->left_child) + g_tree_node_dump (node->left, indent + 2); + else if (node->left) + g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key); + + if (node->right_child) + g_tree_node_dump (node->right, indent + 2); + else if (node->right) + g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key); +} + + +void +g_tree_dump (GTree *tree) +{ + if (tree->root) + g_tree_node_dump (tree->root, 0); +} +#endif