/* * GLIB - Library of useful routines for C programming * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald * * SPDX-License-Identifier: LGPL-2.1-or-later * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 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 * 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, see . */ /* * 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 */ #include "qemu/osdep.h" #include "qemu/qtree.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 #QTree structure and its associated functions provide a sorted * collection of key/value pairs optimized for searching and traversing * in order. This means that most of the operations (access, search, * insertion, deletion, ...) on #QTree are O(log(n)) in average and O(n) * in worst case for time complexity. But, note that maintaining a * balanced sorted #QTree of n elements is done in time O(n log(n)). * * To create a new #QTree use q_tree_new(). * * To insert a key/value pair into a #QTree use q_tree_insert() * (O(n log(n))). * * To remove a key/value pair use q_tree_remove() (O(n log(n))). * * To look up the value corresponding to a given key, use * q_tree_lookup() and q_tree_lookup_extended(). * * To find out the number of nodes in a #QTree, use q_tree_nnodes(). To * get the height of a #QTree, use q_tree_height(). * * To traverse a #QTree, calling a function for each node visited in * the traversal, use q_tree_foreach(). * * To destroy a #QTree, use q_tree_destroy(). **/ #define MAX_GTREE_HEIGHT 40 /** * QTree: * * The QTree 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 _QTree { QTreeNode *root; GCompareDataFunc key_compare; GDestroyNotify key_destroy_func; GDestroyNotify value_destroy_func; gpointer key_compare_data; guint nnodes; gint ref_count; }; struct _QTreeNode { gpointer key; /* key for this node */ gpointer value; /* value stored at this node */ QTreeNode *left; /* left subtree */ QTreeNode *right; /* right subtree */ gint8 balance; /* height (right) - height (left) */ guint8 left_child; guint8 right_child; }; static QTreeNode *q_tree_node_new(gpointer key, gpointer value); static QTreeNode *q_tree_insert_internal(QTree *tree, gpointer key, gpointer value, gboolean replace); static gboolean q_tree_remove_internal(QTree *tree, gconstpointer key, gboolean steal); static QTreeNode *q_tree_node_balance(QTreeNode *node); static QTreeNode *q_tree_find_node(QTree *tree, gconstpointer key); static QTreeNode *q_tree_node_search(QTreeNode *node, GCompareFunc search_func, gconstpointer data); static QTreeNode *q_tree_node_rotate_left(QTreeNode *node); static QTreeNode *q_tree_node_rotate_right(QTreeNode *node); #ifdef Q_TREE_DEBUG static void q_tree_node_check(QTreeNode *node); #endif static QTreeNode* q_tree_node_new(gpointer key, gpointer value) { QTreeNode *node = g_new(QTreeNode, 1); 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; } /** * q_tree_new: * @key_compare_func: the function used to order the nodes in the #QTree. * 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 #QTree. * * Returns: a newly allocated #QTree */ QTree * q_tree_new(GCompareFunc key_compare_func) { g_return_val_if_fail(key_compare_func != NULL, NULL); return q_tree_new_full((GCompareDataFunc) key_compare_func, NULL, NULL, NULL); } /** * q_tree_new_with_data: * @key_compare_func: qsort()-style comparison function * @key_compare_data: data to pass to comparison function * * Creates a new #QTree with a comparison function that accepts user data. * See q_tree_new() for more details. * * Returns: a newly allocated #QTree */ QTree * q_tree_new_with_data(GCompareDataFunc key_compare_func, gpointer key_compare_data) { g_return_val_if_fail(key_compare_func != NULL, NULL); return q_tree_new_full(key_compare_func, key_compare_data, NULL, NULL); } /** * q_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 #QTree 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 #QTree or %NULL if you * don't want to supply such a function * * Creates a new #QTree like q_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 #QTree. * * Returns: a newly allocated #QTree */ QTree * q_tree_new_full(GCompareDataFunc key_compare_func, gpointer key_compare_data, GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func) { QTree *tree; g_return_val_if_fail(key_compare_func != NULL, NULL); tree = g_new(QTree, 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; tree->nnodes = 0; tree->ref_count = 1; return tree; } /** * q_tree_node_first: * @tree: a #QTree * * Returns the first in-order node of the tree, or %NULL * for an empty tree. * * Returns: (nullable) (transfer none): the first node in the tree * * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. */ static QTreeNode * q_tree_node_first(QTree *tree) { QTreeNode *tmp; g_return_val_if_fail(tree != NULL, NULL); if (!tree->root) { return NULL; } tmp = tree->root; while (tmp->left_child) { tmp = tmp->left; } return tmp; } /** * q_tree_node_previous * @node: a #QTree node * * Returns the previous in-order node of the tree, or %NULL * if the passed node was already the first one. * * Returns: (nullable) (transfer none): the previous node in the tree * * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. */ static QTreeNode * q_tree_node_previous(QTreeNode *node) { QTreeNode *tmp; g_return_val_if_fail(node != NULL, NULL); tmp = node->left; if (node->left_child) { while (tmp->right_child) { tmp = tmp->right; } } return tmp; } /** * q_tree_node_next * @node: a #QTree node * * Returns the next in-order node of the tree, or %NULL * if the passed node was already the last one. * * Returns: (nullable) (transfer none): the next node in the tree * * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. */ static QTreeNode * q_tree_node_next(QTreeNode *node) { QTreeNode *tmp; g_return_val_if_fail(node != NULL, NULL); tmp = node->right; if (node->right_child) { while (tmp->left_child) { tmp = tmp->left; } } return tmp; } /** * q_tree_remove_all: * @tree: a #QTree * * Removes all nodes from a #QTree and destroys their keys and values, * then resets the #QTree’s root to %NULL. * * Since: 2.70 in GLib. Internal in Qtree, i.e. not in the public API. */ static void q_tree_remove_all(QTree *tree) { QTreeNode *node; QTreeNode *next; g_return_if_fail(tree != NULL); node = q_tree_node_first(tree); while (node) { next = q_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_free(node); #ifdef Q_TREE_DEBUG g_assert(tree->nnodes > 0); tree->nnodes--; #endif node = next; } #ifdef Q_TREE_DEBUG g_assert(tree->nnodes == 0); #endif tree->root = NULL; #ifndef Q_TREE_DEBUG tree->nnodes = 0; #endif } /** * q_tree_ref: * @tree: a #QTree * * Increments the reference count of @tree by one. * * It is safe to call this function from any thread. * * Returns: the passed in #QTree * * Since: 2.22 */ QTree * q_tree_ref(QTree *tree) { g_return_val_if_fail(tree != NULL, NULL); g_atomic_int_inc(&tree->ref_count); return tree; } /** * q_tree_unref: * @tree: a #QTree * * 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 q_tree_unref(QTree *tree) { g_return_if_fail(tree != NULL); if (g_atomic_int_dec_and_test(&tree->ref_count)) { q_tree_remove_all(tree); g_free(tree); } } /** * q_tree_destroy: * @tree: a #QTree * * Removes all keys and values from the #QTree and decreases its * reference count by one. If keys and/or values are dynamically * allocated, you should either free them first or create the #QTree * using q_tree_new_full(). In the latter case the destroy functions * you supplied will be called on all keys and values before destroying * the #QTree. */ void q_tree_destroy(QTree *tree) { g_return_if_fail(tree != NULL); q_tree_remove_all(tree); q_tree_unref(tree); } /** * q_tree_insert_node: * @tree: a #QTree * @key: the key to insert * @value: the value corresponding to the key * * Inserts a key/value pair into a #QTree. * * If the given key already exists in the #QTree its corresponding value * is set to the new value. If you supplied a @value_destroy_func when * creating the #QTree, the old value is freed using that function. If * you supplied a @key_destroy_func when creating the #QTree, 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. * The cost of maintaining a balanced tree while inserting new key/value * result in a O(n log(n)) operation where most of the other operations * are O(log(n)). * * Returns: (transfer none): the inserted (or set) node. * * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. */ static QTreeNode * q_tree_insert_node(QTree *tree, gpointer key, gpointer value) { QTreeNode *node; g_return_val_if_fail(tree != NULL, NULL); node = q_tree_insert_internal(tree, key, value, FALSE); #ifdef Q_TREE_DEBUG q_tree_node_check(tree->root); #endif return node; } /** * q_tree_insert: * @tree: a #QTree * @key: the key to insert * @value: the value corresponding to the key * * Inserts a key/value pair into a #QTree. * * Inserts a new key and value into a #QTree as q_tree_insert_node() does, * only this function does not return the inserted or set node. */ void q_tree_insert(QTree *tree, gpointer key, gpointer value) { q_tree_insert_node(tree, key, value); } /** * q_tree_replace_node: * @tree: a #QTree * @key: the key to insert * @value: the value corresponding to the key * * Inserts a new key and value into a #QTree similar to q_tree_insert_node(). * The difference is that if the key already exists in the #QTree, it gets * replaced by the new key. If you supplied a @value_destroy_func when * creating the #QTree, the old value is freed using that function. If you * supplied a @key_destroy_func when creating the #QTree, 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. * * Returns: (transfer none): the inserted (or set) node. * * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. */ static QTreeNode * q_tree_replace_node(QTree *tree, gpointer key, gpointer value) { QTreeNode *node; g_return_val_if_fail(tree != NULL, NULL); node = q_tree_insert_internal(tree, key, value, TRUE); #ifdef Q_TREE_DEBUG q_tree_node_check(tree->root); #endif return node; } /** * q_tree_replace: * @tree: a #QTree * @key: the key to insert * @value: the value corresponding to the key * * Inserts a new key and value into a #QTree as q_tree_replace_node() does, * only this function does not return the inserted or set node. */ void q_tree_replace(QTree *tree, gpointer key, gpointer value) { q_tree_replace_node(tree, key, value); } /* internal insert routine */ static QTreeNode * q_tree_insert_internal(QTree *tree, gpointer key, gpointer value, gboolean replace) { QTreeNode *node, *retnode; QTreeNode *path[MAX_GTREE_HEIGHT]; int idx; g_return_val_if_fail(tree != NULL, NULL); if (!tree->root) { tree->root = q_tree_node_new(key, value); tree->nnodes++; return tree->root; } idx = 0; path[idx++] = NULL; node = tree->root; while (1) { 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 node; } else if (cmp < 0) { if (node->left_child) { path[idx++] = node; node = node->left; } else { QTreeNode *child = q_tree_node_new(key, value); child->left = node->left; child->right = node; node->left = child; node->left_child = TRUE; node->balance -= 1; tree->nnodes++; retnode = child; break; } } else { if (node->right_child) { path[idx++] = node; node = node->right; } else { QTreeNode *child = q_tree_node_new(key, value); child->right = node->right; child->left = node; node->right = child; node->right_child = TRUE; node->balance += 1; tree->nnodes++; retnode = child; 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) { QTreeNode *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 = q_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; } node = bparent; } return retnode; } /** * q_tree_remove: * @tree: a #QTree * @key: the key to remove * * Removes a key/value pair from a #QTree. * * If the #QTree was created using q_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 #QTree, the function does nothing. * * The cost of maintaining a balanced tree while removing a key/value * result in a O(n log(n)) operation where most of the other operations * are O(log(n)). * * Returns: %TRUE if the key was found (prior to 2.8, this function * returned nothing) */ gboolean q_tree_remove(QTree *tree, gconstpointer key) { gboolean removed; g_return_val_if_fail(tree != NULL, FALSE); removed = q_tree_remove_internal(tree, key, FALSE); #ifdef Q_TREE_DEBUG q_tree_node_check(tree->root); #endif return removed; } /** * q_tree_steal: * @tree: a #QTree * @key: the key to remove * * Removes a key and its associated value from a #QTree without calling * the key and value destroy functions. * * If the key does not exist in the #QTree, the function does nothing. * * Returns: %TRUE if the key was found (prior to 2.8, this function * returned nothing) */ gboolean q_tree_steal(QTree *tree, gconstpointer key) { gboolean removed; g_return_val_if_fail(tree != NULL, FALSE); removed = q_tree_remove_internal(tree, key, TRUE); #ifdef Q_TREE_DEBUG q_tree_node_check(tree->root); #endif return removed; } /* internal remove routine */ static gboolean q_tree_remove_internal(QTree *tree, gconstpointer key, gboolean steal) { QTreeNode *node, *parent, *balance; QTreeNode *path[MAX_GTREE_HEIGHT]; int idx; gboolean left_node; g_return_val_if_fail(tree != NULL, FALSE); if (!tree->root) { return FALSE; } idx = 0; path[idx++] = NULL; node = tree->root; while (1) { 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; } path[idx++] = node; node = node->right; } } /* * The following code is almost equal to q_tree_remove_node, * except that we do not have to call q_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->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 */ QTreeNode *tmp = q_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 { /* node has a left child */ if (!node->right_child) { QTreeNode *tmp = q_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!) */ QTreeNode *prev = node->left; QTreeNode *next = node->right; QTreeNode *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; } } } /* restore balance */ if (balance) { while (1) { QTreeNode *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 = q_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 (tree->key_destroy_func) { tree->key_destroy_func(node->key); } if (tree->value_destroy_func) { tree->value_destroy_func(node->value); } } g_free(node); tree->nnodes--; return TRUE; } /** * q_tree_lookup_node: * @tree: a #QTree * @key: the key to look up * * Gets the tree node corresponding to the given key. Since a #QTree 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: (nullable) (transfer none): the tree node corresponding to * the key, or %NULL if the key was not found * * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. */ static QTreeNode * q_tree_lookup_node(QTree *tree, gconstpointer key) { g_return_val_if_fail(tree != NULL, NULL); return q_tree_find_node(tree, key); } /** * q_tree_lookup: * @tree: a #QTree * @key: the key to look up * * Gets the value corresponding to the given key. Since a #QTree 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 q_tree_lookup(QTree *tree, gconstpointer key) { QTreeNode *node; node = q_tree_lookup_node(tree, key); return node ? node->value : NULL; } /** * q_tree_lookup_extended: * @tree: a #QTree * @lookup_key: the key to look up * @orig_key: (out) (optional) (nullable): returns the original key * @value: (out) (optional) (nullable): returns the value associated with * the key * * Looks up a key in the #QTree, 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 * q_tree_remove(). * * Returns: %TRUE if the key was found in the #QTree */ gboolean q_tree_lookup_extended(QTree *tree, gconstpointer lookup_key, gpointer *orig_key, gpointer *value) { QTreeNode *node; g_return_val_if_fail(tree != NULL, FALSE); node = q_tree_find_node(tree, lookup_key); if (node) { if (orig_key) { *orig_key = node->key; } if (value) { *value = node->value; } return TRUE; } else { return FALSE; } } /** * q_tree_foreach: * @tree: a #QTree * @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 #QTree. * 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 q_tree_foreach(QTree *tree, GTraverseFunc func, gpointer user_data) { QTreeNode *node; g_return_if_fail(tree != NULL); if (!tree->root) { return; } node = q_tree_node_first(tree); while (node) { if ((*func)(node->key, node->value, user_data)) { break; } node = q_tree_node_next(node); } } /** * q_tree_search_node: * @tree: a #QTree * @search_func: a function used to search the #QTree * @user_data: the data passed as the second argument to @search_func * * Searches a #QTree 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 node is returned as * the result of q_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: (nullable) (transfer none): the node corresponding to the * found key, or %NULL if the key was not found * * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. */ static QTreeNode * q_tree_search_node(QTree *tree, GCompareFunc search_func, gconstpointer user_data) { g_return_val_if_fail(tree != NULL, NULL); if (!tree->root) { return NULL; } return q_tree_node_search(tree->root, search_func, user_data); } /** * q_tree_search: * @tree: a #QTree * @search_func: a function used to search the #QTree * @user_data: the data passed as the second argument to @search_func * * Searches a #QTree 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 q_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 q_tree_search(QTree *tree, GCompareFunc search_func, gconstpointer user_data) { QTreeNode *node; node = q_tree_search_node(tree, search_func, user_data); return node ? node->value : NULL; } /** * q_tree_height: * @tree: a #QTree * * Gets the height of a #QTree. * * If the #QTree contains no nodes, the height is 0. * If the #QTree 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 q_tree_height(QTree *tree) { QTreeNode *node; gint height; 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; } } /** * q_tree_nnodes: * @tree: a #QTree * * Gets the number of nodes in a #QTree. * * Returns: the number of nodes in @tree */ gint q_tree_nnodes(QTree *tree) { g_return_val_if_fail(tree != NULL, 0); return tree->nnodes; } static QTreeNode * q_tree_node_balance(QTreeNode *node) { if (node->balance < -1) { if (node->left->balance > 0) { node->left = q_tree_node_rotate_left(node->left); } node = q_tree_node_rotate_right(node); } else if (node->balance > 1) { if (node->right->balance < 0) { node->right = q_tree_node_rotate_right(node->right); } node = q_tree_node_rotate_left(node); } return node; } static QTreeNode * q_tree_find_node(QTree *tree, gconstpointer key) { QTreeNode *node; gint cmp; node = tree->root; if (!node) { return NULL; } 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 QTreeNode * q_tree_node_search(QTreeNode *node, GCompareFunc search_func, gconstpointer data) { gint dir; if (!node) { return NULL; } while (1) { dir = (*search_func)(node->key, data); if (dir == 0) { return node; } else if (dir < 0) { if (!node->left_child) { return NULL; } node = node->left; } else { if (!node->right_child) { return NULL; } node = node->right; } } } static QTreeNode * q_tree_node_rotate_left(QTreeNode *node) { QTreeNode *right; gint a_bal; gint b_bal; right = node->right; if (right->left_child) { node->right = right->left; } else { node->right_child = FALSE; right->left_child = TRUE; } 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 QTreeNode * q_tree_node_rotate_right(QTreeNode *node) { QTreeNode *left; gint a_bal; gint b_bal; left = node->left; if (left->right_child) { node->left = left->right; } else { node->left_child = FALSE; left->right_child = TRUE; } 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; } #ifdef Q_TREE_DEBUG static gint q_tree_node_height(QTreeNode *node) { gint left_height; gint right_height; if (node) { left_height = 0; right_height = 0; if (node->left_child) { left_height = q_tree_node_height(node->left); } if (node->right_child) { right_height = q_tree_node_height(node->right); } return MAX(left_height, right_height) + 1; } return 0; } static void q_tree_node_check(QTreeNode *node) { gint left_height; gint right_height; gint balance; QTreeNode *tmp; if (node) { if (node->left_child) { tmp = q_tree_node_previous(node); g_assert(tmp->right == node); } if (node->right_child) { tmp = q_tree_node_next(node); g_assert(tmp->left == node); } left_height = 0; right_height = 0; if (node->left_child) { left_height = q_tree_node_height(node->left); } if (node->right_child) { right_height = q_tree_node_height(node->right); } balance = right_height - left_height; g_assert(balance == node->balance); if (node->left_child) { q_tree_node_check(node->left); } if (node->right_child) { q_tree_node_check(node->right); } } } #endif