2 * GLIB - Library of useful routines for C programming
3 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
5 * SPDX-License-Identifier: LGPL-2.1-or-later
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
22 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
23 * file for a list of people on the GLib Team. See the ChangeLog
24 * files for a list of changes. These files are distributed with
25 * GLib at ftp://ftp.gtk.org/pub/gtk/.
32 #include "qemu/osdep.h"
33 #include "qemu/qtree.h"
36 * SECTION:trees-binary
37 * @title: Balanced Binary Trees
38 * @short_description: a sorted collection of key/value pairs optimized
39 * for searching and traversing in order
41 * The #QTree structure and its associated functions provide a sorted
42 * collection of key/value pairs optimized for searching and traversing
43 * in order. This means that most of the operations (access, search,
44 * insertion, deletion, ...) on #QTree are O(log(n)) in average and O(n)
45 * in worst case for time complexity. But, note that maintaining a
46 * balanced sorted #QTree of n elements is done in time O(n log(n)).
48 * To create a new #QTree use q_tree_new().
50 * To insert a key/value pair into a #QTree use q_tree_insert()
53 * To remove a key/value pair use q_tree_remove() (O(n log(n))).
55 * To look up the value corresponding to a given key, use
56 * q_tree_lookup() and q_tree_lookup_extended().
58 * To find out the number of nodes in a #QTree, use q_tree_nnodes(). To
59 * get the height of a #QTree, use q_tree_height().
61 * To traverse a #QTree, calling a function for each node visited in
62 * the traversal, use q_tree_foreach().
64 * To destroy a #QTree, use q_tree_destroy().
67 #define MAX_GTREE_HEIGHT 40
72 * The QTree struct is an opaque data structure representing a
73 * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be
74 * accessed only by using the following functions.
78 GCompareDataFunc key_compare;
79 GDestroyNotify key_destroy_func;
80 GDestroyNotify value_destroy_func;
81 gpointer key_compare_data;
87 gpointer key; /* key for this node */
88 gpointer value; /* value stored at this node */
89 QTreeNode *left; /* left subtree */
90 QTreeNode *right; /* right subtree */
91 gint8 balance; /* height (right) - height (left) */
97 static QTreeNode *q_tree_node_new(gpointer key,
99 static QTreeNode *q_tree_insert_internal(QTree *tree,
103 static gboolean q_tree_remove_internal(QTree *tree,
106 static QTreeNode *q_tree_node_balance(QTreeNode *node);
107 static QTreeNode *q_tree_find_node(QTree *tree,
109 static QTreeNode *q_tree_node_search(QTreeNode *node,
110 GCompareFunc search_func,
112 static QTreeNode *q_tree_node_rotate_left(QTreeNode *node);
113 static QTreeNode *q_tree_node_rotate_right(QTreeNode *node);
115 static void q_tree_node_check(QTreeNode *node);
119 q_tree_node_new(gpointer key,
122 QTreeNode *node = g_new(QTreeNode, 1);
127 node->left_child = FALSE;
128 node->right_child = FALSE;
137 * @key_compare_func: the function used to order the nodes in the #QTree.
138 * It should return values similar to the standard strcmp() function -
139 * 0 if the two arguments are equal, a negative value if the first argument
140 * comes before the second, or a positive value if the first argument comes
143 * Creates a new #QTree.
145 * Returns: a newly allocated #QTree
148 q_tree_new(GCompareFunc key_compare_func)
150 g_return_val_if_fail(key_compare_func != NULL, NULL);
152 return q_tree_new_full((GCompareDataFunc) key_compare_func, NULL,
157 * q_tree_new_with_data:
158 * @key_compare_func: qsort()-style comparison function
159 * @key_compare_data: data to pass to comparison function
161 * Creates a new #QTree with a comparison function that accepts user data.
162 * See q_tree_new() for more details.
164 * Returns: a newly allocated #QTree
167 q_tree_new_with_data(GCompareDataFunc key_compare_func,
168 gpointer key_compare_data)
170 g_return_val_if_fail(key_compare_func != NULL, NULL);
172 return q_tree_new_full(key_compare_func, key_compare_data,
178 * @key_compare_func: qsort()-style comparison function
179 * @key_compare_data: data to pass to comparison function
180 * @key_destroy_func: a function to free the memory allocated for the key
181 * used when removing the entry from the #QTree or %NULL if you don't
182 * want to supply such a function
183 * @value_destroy_func: a function to free the memory allocated for the
184 * value used when removing the entry from the #QTree or %NULL if you
185 * don't want to supply such a function
187 * Creates a new #QTree like q_tree_new() and allows to specify functions
188 * to free the memory allocated for the key and value that get called when
189 * removing the entry from the #QTree.
191 * Returns: a newly allocated #QTree
194 q_tree_new_full(GCompareDataFunc key_compare_func,
195 gpointer key_compare_data,
196 GDestroyNotify key_destroy_func,
197 GDestroyNotify value_destroy_func)
201 g_return_val_if_fail(key_compare_func != NULL, NULL);
203 tree = g_new(QTree, 1);
205 tree->key_compare = key_compare_func;
206 tree->key_destroy_func = key_destroy_func;
207 tree->value_destroy_func = value_destroy_func;
208 tree->key_compare_data = key_compare_data;
219 * Returns the first in-order node of the tree, or %NULL
222 * Returns: (nullable) (transfer none): the first node in the tree
224 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
227 q_tree_node_first(QTree *tree)
231 g_return_val_if_fail(tree != NULL, NULL);
239 while (tmp->left_child) {
247 * q_tree_node_previous
248 * @node: a #QTree node
250 * Returns the previous in-order node of the tree, or %NULL
251 * if the passed node was already the first one.
253 * Returns: (nullable) (transfer none): the previous node in the tree
255 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
258 q_tree_node_previous(QTreeNode *node)
262 g_return_val_if_fail(node != NULL, NULL);
266 if (node->left_child) {
267 while (tmp->right_child) {
277 * @node: a #QTree node
279 * Returns the next in-order node of the tree, or %NULL
280 * if the passed node was already the last one.
282 * Returns: (nullable) (transfer none): the next node in the tree
284 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
287 q_tree_node_next(QTreeNode *node)
291 g_return_val_if_fail(node != NULL, NULL);
295 if (node->right_child) {
296 while (tmp->left_child) {
308 * Removes all nodes from a #QTree and destroys their keys and values,
309 * then resets the #QTree’s root to %NULL.
311 * Since: 2.70 in GLib. Internal in Qtree, i.e. not in the public API.
313 static void QEMU_DISABLE_CFI
314 q_tree_remove_all(QTree *tree)
319 g_return_if_fail(tree != NULL);
321 node = q_tree_node_first(tree);
324 next = q_tree_node_next(node);
326 if (tree->key_destroy_func) {
327 tree->key_destroy_func(node->key);
329 if (tree->value_destroy_func) {
330 tree->value_destroy_func(node->value);
335 g_assert(tree->nnodes > 0);
343 g_assert(tree->nnodes == 0);
356 * Increments the reference count of @tree by one.
358 * It is safe to call this function from any thread.
360 * Returns: the passed in #QTree
365 q_tree_ref(QTree *tree)
367 g_return_val_if_fail(tree != NULL, NULL);
369 g_atomic_int_inc(&tree->ref_count);
378 * Decrements the reference count of @tree by one.
379 * If the reference count drops to 0, all keys and values will
380 * be destroyed (if destroy functions were specified) and all
381 * memory allocated by @tree will be released.
383 * It is safe to call this function from any thread.
388 q_tree_unref(QTree *tree)
390 g_return_if_fail(tree != NULL);
392 if (g_atomic_int_dec_and_test(&tree->ref_count)) {
393 q_tree_remove_all(tree);
402 * Removes all keys and values from the #QTree and decreases its
403 * reference count by one. If keys and/or values are dynamically
404 * allocated, you should either free them first or create the #QTree
405 * using q_tree_new_full(). In the latter case the destroy functions
406 * you supplied will be called on all keys and values before destroying
410 q_tree_destroy(QTree *tree)
412 g_return_if_fail(tree != NULL);
414 q_tree_remove_all(tree);
419 * q_tree_insert_node:
421 * @key: the key to insert
422 * @value: the value corresponding to the key
424 * Inserts a key/value pair into a #QTree.
426 * If the given key already exists in the #QTree its corresponding value
427 * is set to the new value. If you supplied a @value_destroy_func when
428 * creating the #QTree, the old value is freed using that function. If
429 * you supplied a @key_destroy_func when creating the #QTree, the passed
430 * key is freed using that function.
432 * The tree is automatically 'balanced' as new key/value pairs are added,
433 * so that the distance from the root to every leaf is as small as possible.
434 * The cost of maintaining a balanced tree while inserting new key/value
435 * result in a O(n log(n)) operation where most of the other operations
438 * Returns: (transfer none): the inserted (or set) node.
440 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
443 q_tree_insert_node(QTree *tree,
449 g_return_val_if_fail(tree != NULL, NULL);
451 node = q_tree_insert_internal(tree, key, value, FALSE);
454 q_tree_node_check(tree->root);
463 * @key: the key to insert
464 * @value: the value corresponding to the key
466 * Inserts a key/value pair into a #QTree.
468 * Inserts a new key and value into a #QTree as q_tree_insert_node() does,
469 * only this function does not return the inserted or set node.
472 q_tree_insert(QTree *tree,
476 q_tree_insert_node(tree, key, value);
480 * q_tree_replace_node:
482 * @key: the key to insert
483 * @value: the value corresponding to the key
485 * Inserts a new key and value into a #QTree similar to q_tree_insert_node().
486 * The difference is that if the key already exists in the #QTree, it gets
487 * replaced by the new key. If you supplied a @value_destroy_func when
488 * creating the #QTree, the old value is freed using that function. If you
489 * supplied a @key_destroy_func when creating the #QTree, the old key is
490 * freed using that function.
492 * The tree is automatically 'balanced' as new key/value pairs are added,
493 * so that the distance from the root to every leaf is as small as possible.
495 * Returns: (transfer none): the inserted (or set) node.
497 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
500 q_tree_replace_node(QTree *tree,
506 g_return_val_if_fail(tree != NULL, NULL);
508 node = q_tree_insert_internal(tree, key, value, TRUE);
511 q_tree_node_check(tree->root);
520 * @key: the key to insert
521 * @value: the value corresponding to the key
523 * Inserts a new key and value into a #QTree as q_tree_replace_node() does,
524 * only this function does not return the inserted or set node.
527 q_tree_replace(QTree *tree,
531 q_tree_replace_node(tree, key, value);
534 /* internal insert routine */
535 static QTreeNode * QEMU_DISABLE_CFI
536 q_tree_insert_internal(QTree *tree,
541 QTreeNode *node, *retnode;
542 QTreeNode *path[MAX_GTREE_HEIGHT];
545 g_return_val_if_fail(tree != NULL, NULL);
548 tree->root = q_tree_node_new(key, value);
558 int cmp = tree->key_compare(key, node->key, tree->key_compare_data);
561 if (tree->value_destroy_func) {
562 tree->value_destroy_func(node->value);
568 if (tree->key_destroy_func) {
569 tree->key_destroy_func(node->key);
574 /* free the passed key */
575 if (tree->key_destroy_func) {
576 tree->key_destroy_func(key);
581 } else if (cmp < 0) {
582 if (node->left_child) {
586 QTreeNode *child = q_tree_node_new(key, value);
588 child->left = node->left;
591 node->left_child = TRUE;
600 if (node->right_child) {
604 QTreeNode *child = q_tree_node_new(key, value);
606 child->right = node->right;
609 node->right_child = TRUE;
621 * Restore balance. This is the goodness of a non-recursive
622 * implementation, when we are done with balancing we 'break'
623 * the loop and we are done.
626 QTreeNode *bparent = path[--idx];
627 gboolean left_node = (bparent && node == bparent->left);
628 g_assert(!bparent || bparent->left == node || bparent->right == node);
630 if (node->balance < -1 || node->balance > 1) {
631 node = q_tree_node_balance(node);
632 if (bparent == NULL) {
634 } else if (left_node) {
635 bparent->left = node;
637 bparent->right = node;
641 if (node->balance == 0 || bparent == NULL) {
646 bparent->balance -= 1;
648 bparent->balance += 1;
660 * @key: the key to remove
662 * Removes a key/value pair from a #QTree.
664 * If the #QTree was created using q_tree_new_full(), the key and value
665 * are freed using the supplied destroy functions, otherwise you have to
666 * make sure that any dynamically allocated values are freed yourself.
667 * If the key does not exist in the #QTree, the function does nothing.
669 * The cost of maintaining a balanced tree while removing a key/value
670 * result in a O(n log(n)) operation where most of the other operations
673 * Returns: %TRUE if the key was found (prior to 2.8, this function
677 q_tree_remove(QTree *tree,
682 g_return_val_if_fail(tree != NULL, FALSE);
684 removed = q_tree_remove_internal(tree, key, FALSE);
687 q_tree_node_check(tree->root);
696 * @key: the key to remove
698 * Removes a key and its associated value from a #QTree without calling
699 * the key and value destroy functions.
701 * If the key does not exist in the #QTree, the function does nothing.
703 * Returns: %TRUE if the key was found (prior to 2.8, this function
707 q_tree_steal(QTree *tree,
712 g_return_val_if_fail(tree != NULL, FALSE);
714 removed = q_tree_remove_internal(tree, key, TRUE);
717 q_tree_node_check(tree->root);
723 /* internal remove routine */
724 static gboolean QEMU_DISABLE_CFI
725 q_tree_remove_internal(QTree *tree,
729 QTreeNode *node, *parent, *balance;
730 QTreeNode *path[MAX_GTREE_HEIGHT];
734 g_return_val_if_fail(tree != NULL, FALSE);
745 int cmp = tree->key_compare(key, node->key, tree->key_compare_data);
749 } else if (cmp < 0) {
750 if (!node->left_child) {
757 if (!node->right_child) {
767 * The following code is almost equal to q_tree_remove_node,
768 * except that we do not have to call q_tree_node_parent.
770 balance = parent = path[--idx];
771 g_assert(!parent || parent->left == node || parent->right == node);
772 left_node = (parent && node == parent->left);
774 if (!node->left_child) {
775 if (!node->right_child) {
778 } else if (left_node) {
779 parent->left_child = FALSE;
780 parent->left = node->left;
781 parent->balance += 1;
783 parent->right_child = FALSE;
784 parent->right = node->right;
785 parent->balance -= 1;
788 /* node has a right child */
789 QTreeNode *tmp = q_tree_node_next(node);
790 tmp->left = node->left;
793 tree->root = node->right;
794 } else if (left_node) {
795 parent->left = node->right;
796 parent->balance += 1;
798 parent->right = node->right;
799 parent->balance -= 1;
803 /* node has a left child */
804 if (!node->right_child) {
805 QTreeNode *tmp = q_tree_node_previous(node);
806 tmp->right = node->right;
808 if (parent == NULL) {
809 tree->root = node->left;
810 } else if (left_node) {
811 parent->left = node->left;
812 parent->balance += 1;
814 parent->right = node->left;
815 parent->balance -= 1;
818 /* node has a both children (pant, pant!) */
819 QTreeNode *prev = node->left;
820 QTreeNode *next = node->right;
821 QTreeNode *nextp = node;
822 int old_idx = idx + 1;
825 /* path[idx] == parent */
826 /* find the immediately next node (and its parent) */
827 while (next->left_child) {
828 path[++idx] = nextp = next;
832 path[old_idx] = next;
835 /* remove 'next' from the tree */
837 if (next->right_child) {
838 nextp->left = next->right;
840 nextp->left_child = FALSE;
844 next->right_child = TRUE;
845 next->right = node->right;
850 /* set the prev to point to the right place */
851 while (prev->right_child) {
856 /* prepare 'next' to replace 'node' */
857 next->left_child = TRUE;
858 next->left = node->left;
859 next->balance = node->balance;
863 } else if (left_node) {
866 parent->right = next;
871 /* restore balance */
874 QTreeNode *bparent = path[--idx];
876 bparent->left == balance ||
877 bparent->right == balance);
878 left_node = (bparent && balance == bparent->left);
880 if (balance->balance < -1 || balance->balance > 1) {
881 balance = q_tree_node_balance(balance);
883 tree->root = balance;
884 } else if (left_node) {
885 bparent->left = balance;
887 bparent->right = balance;
891 if (balance->balance != 0 || !bparent) {
896 bparent->balance += 1;
898 bparent->balance -= 1;
906 if (tree->key_destroy_func) {
907 tree->key_destroy_func(node->key);
909 if (tree->value_destroy_func) {
910 tree->value_destroy_func(node->value);
922 * q_tree_lookup_node:
924 * @key: the key to look up
926 * Gets the tree node corresponding to the given key. Since a #QTree is
927 * automatically balanced as key/value pairs are added, key lookup
928 * is O(log n) (where n is the number of key/value pairs in the tree).
930 * Returns: (nullable) (transfer none): the tree node corresponding to
931 * the key, or %NULL if the key was not found
933 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
936 q_tree_lookup_node(QTree *tree,
939 g_return_val_if_fail(tree != NULL, NULL);
941 return q_tree_find_node(tree, key);
947 * @key: the key to look up
949 * Gets the value corresponding to the given key. Since a #QTree is
950 * automatically balanced as key/value pairs are added, key lookup
951 * is O(log n) (where n is the number of key/value pairs in the tree).
953 * Returns: the value corresponding to the key, or %NULL
954 * if the key was not found
957 q_tree_lookup(QTree *tree,
962 node = q_tree_lookup_node(tree, key);
964 return node ? node->value : NULL;
968 * q_tree_lookup_extended:
970 * @lookup_key: the key to look up
971 * @orig_key: (out) (optional) (nullable): returns the original key
972 * @value: (out) (optional) (nullable): returns the value associated with
975 * Looks up a key in the #QTree, returning the original key and the
976 * associated value. This is useful if you need to free the memory
977 * allocated for the original key, for example before calling
980 * Returns: %TRUE if the key was found in the #QTree
983 q_tree_lookup_extended(QTree *tree,
984 gconstpointer lookup_key,
990 g_return_val_if_fail(tree != NULL, FALSE);
992 node = q_tree_find_node(tree, lookup_key);
996 *orig_key = node->key;
999 *value = node->value;
1010 * @func: the function to call for each node visited.
1011 * If this function returns %TRUE, the traversal is stopped.
1012 * @user_data: user data to pass to the function
1014 * Calls the given function for each of the key/value pairs in the #QTree.
1015 * The function is passed the key and value of each pair, and the given
1016 * @data parameter. The tree is traversed in sorted order.
1018 * The tree may not be modified while iterating over it (you can't
1019 * add/remove items). To remove all items matching a predicate, you need
1020 * to add each item to a list in your #GTraverseFunc as you walk over
1021 * the tree, then walk the list and remove each item.
1024 q_tree_foreach(QTree *tree,
1030 g_return_if_fail(tree != NULL);
1036 node = q_tree_node_first(tree);
1039 if ((*func)(node->key, node->value, user_data)) {
1043 node = q_tree_node_next(node);
1048 * q_tree_search_node:
1050 * @search_func: a function used to search the #QTree
1051 * @user_data: the data passed as the second argument to @search_func
1053 * Searches a #QTree using @search_func.
1055 * The @search_func is called with a pointer to the key of a key/value
1056 * pair in the tree, and the passed in @user_data. If @search_func returns
1057 * 0 for a key/value pair, then the corresponding node is returned as
1058 * the result of q_tree_search(). If @search_func returns -1, searching
1059 * will proceed among the key/value pairs that have a smaller key; if
1060 * @search_func returns 1, searching will proceed among the key/value
1061 * pairs that have a larger key.
1063 * Returns: (nullable) (transfer none): the node corresponding to the
1064 * found key, or %NULL if the key was not found
1066 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
1069 q_tree_search_node(QTree *tree,
1070 GCompareFunc search_func,
1071 gconstpointer user_data)
1073 g_return_val_if_fail(tree != NULL, NULL);
1079 return q_tree_node_search(tree->root, search_func, user_data);
1085 * @search_func: a function used to search the #QTree
1086 * @user_data: the data passed as the second argument to @search_func
1088 * Searches a #QTree using @search_func.
1090 * The @search_func is called with a pointer to the key of a key/value
1091 * pair in the tree, and the passed in @user_data. If @search_func returns
1092 * 0 for a key/value pair, then the corresponding value is returned as
1093 * the result of q_tree_search(). If @search_func returns -1, searching
1094 * will proceed among the key/value pairs that have a smaller key; if
1095 * @search_func returns 1, searching will proceed among the key/value
1096 * pairs that have a larger key.
1098 * Returns: the value corresponding to the found key, or %NULL
1099 * if the key was not found
1102 q_tree_search(QTree *tree,
1103 GCompareFunc search_func,
1104 gconstpointer user_data)
1108 node = q_tree_search_node(tree, search_func, user_data);
1110 return node ? node->value : NULL;
1117 * Gets the height of a #QTree.
1119 * If the #QTree contains no nodes, the height is 0.
1120 * If the #QTree contains only one root node the height is 1.
1121 * If the root node has children the height is 2, etc.
1123 * Returns: the height of @tree
1126 q_tree_height(QTree *tree)
1131 g_return_val_if_fail(tree != NULL, 0);
1141 height += 1 + MAX(node->balance, 0);
1143 if (!node->left_child) {
1155 * Gets the number of nodes in a #QTree.
1157 * Returns: the number of nodes in @tree
1160 q_tree_nnodes(QTree *tree)
1162 g_return_val_if_fail(tree != NULL, 0);
1164 return tree->nnodes;
1168 q_tree_node_balance(QTreeNode *node)
1170 if (node->balance < -1) {
1171 if (node->left->balance > 0) {
1172 node->left = q_tree_node_rotate_left(node->left);
1174 node = q_tree_node_rotate_right(node);
1175 } else if (node->balance > 1) {
1176 if (node->right->balance < 0) {
1177 node->right = q_tree_node_rotate_right(node->right);
1179 node = q_tree_node_rotate_left(node);
1185 static QTreeNode * QEMU_DISABLE_CFI
1186 q_tree_find_node(QTree *tree,
1198 cmp = tree->key_compare(key, node->key, tree->key_compare_data);
1201 } else if (cmp < 0) {
1202 if (!node->left_child) {
1208 if (!node->right_child) {
1218 q_tree_node_search(QTreeNode *node,
1219 GCompareFunc search_func,
1229 dir = (*search_func)(node->key, data);
1232 } else if (dir < 0) {
1233 if (!node->left_child) {
1239 if (!node->right_child) {
1249 q_tree_node_rotate_left(QTreeNode *node)
1255 right = node->right;
1257 if (right->left_child) {
1258 node->right = right->left;
1260 node->right_child = FALSE;
1261 right->left_child = TRUE;
1265 a_bal = node->balance;
1266 b_bal = right->balance;
1270 right->balance = b_bal - 1;
1272 right->balance = a_bal + b_bal - 2;
1274 node->balance = a_bal - 1;
1276 if (a_bal <= b_bal) {
1277 right->balance = a_bal - 2;
1279 right->balance = b_bal - 1;
1281 node->balance = a_bal - b_bal - 1;
1288 q_tree_node_rotate_right(QTreeNode *node)
1296 if (left->right_child) {
1297 node->left = left->right;
1299 node->left_child = FALSE;
1300 left->right_child = TRUE;
1304 a_bal = node->balance;
1305 b_bal = left->balance;
1308 if (b_bal > a_bal) {
1309 left->balance = b_bal + 1;
1311 left->balance = a_bal + 2;
1313 node->balance = a_bal - b_bal + 1;
1316 left->balance = b_bal + 1;
1318 left->balance = a_bal + b_bal + 2;
1320 node->balance = a_bal + 1;
1328 q_tree_node_height(QTreeNode *node)
1337 if (node->left_child) {
1338 left_height = q_tree_node_height(node->left);
1341 if (node->right_child) {
1342 right_height = q_tree_node_height(node->right);
1345 return MAX(left_height, right_height) + 1;
1351 static void q_tree_node_check(QTreeNode *node)
1359 if (node->left_child) {
1360 tmp = q_tree_node_previous(node);
1361 g_assert(tmp->right == node);
1364 if (node->right_child) {
1365 tmp = q_tree_node_next(node);
1366 g_assert(tmp->left == node);
1372 if (node->left_child) {
1373 left_height = q_tree_node_height(node->left);
1375 if (node->right_child) {
1376 right_height = q_tree_node_height(node->right);
1379 balance = right_height - left_height;
1380 g_assert(balance == node->balance);
1382 if (node->left_child) {
1383 q_tree_node_check(node->left);
1385 if (node->right_child) {
1386 q_tree_node_check(node->right);