1 /* 2 * GLIB - Library of useful routines for C programming 3 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald 4 * 5 * SPDX-License-Identifier: LGPL-2.1-or-later 6 * 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. 11 * 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. 16 * 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/>. 19 */ 20 21 /* 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/. 26 */ 27 28 /* 29 * MT safe 30 */ 31 32 #include "qemu/osdep.h" 33 #include "qemu/qtree.h" 34 35 /** 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 40 * 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)). 47 * 48 * To create a new #QTree use q_tree_new(). 49 * 50 * To insert a key/value pair into a #QTree use q_tree_insert() 51 * (O(n log(n))). 52 * 53 * To remove a key/value pair use q_tree_remove() (O(n log(n))). 54 * 55 * To look up the value corresponding to a given key, use 56 * q_tree_lookup() and q_tree_lookup_extended(). 57 * 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(). 60 * 61 * To traverse a #QTree, calling a function for each node visited in 62 * the traversal, use q_tree_foreach(). 63 * 64 * To destroy a #QTree, use q_tree_destroy(). 65 **/ 66 67 #define MAX_GTREE_HEIGHT 40 68 69 /** 70 * QTree: 71 * 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. 75 */ 76 struct _QTree { 77 QTreeNode *root; 78 GCompareDataFunc key_compare; 79 GDestroyNotify key_destroy_func; 80 GDestroyNotify value_destroy_func; 81 gpointer key_compare_data; 82 guint nnodes; 83 gint ref_count; 84 }; 85 86 struct _QTreeNode { 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) */ 92 guint8 left_child; 93 guint8 right_child; 94 }; 95 96 97 static QTreeNode *q_tree_node_new(gpointer key, 98 gpointer value); 99 static QTreeNode *q_tree_insert_internal(QTree *tree, 100 gpointer key, 101 gpointer value, 102 gboolean replace); 103 static gboolean q_tree_remove_internal(QTree *tree, 104 gconstpointer key, 105 gboolean steal); 106 static QTreeNode *q_tree_node_balance(QTreeNode *node); 107 static QTreeNode *q_tree_find_node(QTree *tree, 108 gconstpointer key); 109 static QTreeNode *q_tree_node_search(QTreeNode *node, 110 GCompareFunc search_func, 111 gconstpointer data); 112 static QTreeNode *q_tree_node_rotate_left(QTreeNode *node); 113 static QTreeNode *q_tree_node_rotate_right(QTreeNode *node); 114 #ifdef Q_TREE_DEBUG 115 static void q_tree_node_check(QTreeNode *node); 116 #endif 117 118 static QTreeNode* 119 q_tree_node_new(gpointer key, 120 gpointer value) 121 { 122 QTreeNode *node = g_new(QTreeNode, 1); 123 124 node->balance = 0; 125 node->left = NULL; 126 node->right = NULL; 127 node->left_child = FALSE; 128 node->right_child = FALSE; 129 node->key = key; 130 node->value = value; 131 132 return node; 133 } 134 135 /** 136 * q_tree_new: 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 141 * after the second. 142 * 143 * Creates a new #QTree. 144 * 145 * Returns: a newly allocated #QTree 146 */ 147 QTree * 148 q_tree_new(GCompareFunc key_compare_func) 149 { 150 g_return_val_if_fail(key_compare_func != NULL, NULL); 151 152 return q_tree_new_full((GCompareDataFunc) key_compare_func, NULL, 153 NULL, NULL); 154 } 155 156 /** 157 * q_tree_new_with_data: 158 * @key_compare_func: qsort()-style comparison function 159 * @key_compare_data: data to pass to comparison function 160 * 161 * Creates a new #QTree with a comparison function that accepts user data. 162 * See q_tree_new() for more details. 163 * 164 * Returns: a newly allocated #QTree 165 */ 166 QTree * 167 q_tree_new_with_data(GCompareDataFunc key_compare_func, 168 gpointer key_compare_data) 169 { 170 g_return_val_if_fail(key_compare_func != NULL, NULL); 171 172 return q_tree_new_full(key_compare_func, key_compare_data, 173 NULL, NULL); 174 } 175 176 /** 177 * q_tree_new_full: 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 186 * 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. 190 * 191 * Returns: a newly allocated #QTree 192 */ 193 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) 198 { 199 QTree *tree; 200 201 g_return_val_if_fail(key_compare_func != NULL, NULL); 202 203 tree = g_new(QTree, 1); 204 tree->root = NULL; 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; 209 tree->nnodes = 0; 210 tree->ref_count = 1; 211 212 return tree; 213 } 214 215 /** 216 * q_tree_node_first: 217 * @tree: a #QTree 218 * 219 * Returns the first in-order node of the tree, or %NULL 220 * for an empty tree. 221 * 222 * Returns: (nullable) (transfer none): the first node in the tree 223 * 224 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. 225 */ 226 static QTreeNode * 227 q_tree_node_first(QTree *tree) 228 { 229 QTreeNode *tmp; 230 231 g_return_val_if_fail(tree != NULL, NULL); 232 233 if (!tree->root) { 234 return NULL; 235 } 236 237 tmp = tree->root; 238 239 while (tmp->left_child) { 240 tmp = tmp->left; 241 } 242 243 return tmp; 244 } 245 246 /** 247 * q_tree_node_previous 248 * @node: a #QTree node 249 * 250 * Returns the previous in-order node of the tree, or %NULL 251 * if the passed node was already the first one. 252 * 253 * Returns: (nullable) (transfer none): the previous node in the tree 254 * 255 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. 256 */ 257 static QTreeNode * 258 q_tree_node_previous(QTreeNode *node) 259 { 260 QTreeNode *tmp; 261 262 g_return_val_if_fail(node != NULL, NULL); 263 264 tmp = node->left; 265 266 if (node->left_child) { 267 while (tmp->right_child) { 268 tmp = tmp->right; 269 } 270 } 271 272 return tmp; 273 } 274 275 /** 276 * q_tree_node_next 277 * @node: a #QTree node 278 * 279 * Returns the next in-order node of the tree, or %NULL 280 * if the passed node was already the last one. 281 * 282 * Returns: (nullable) (transfer none): the next node in the tree 283 * 284 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. 285 */ 286 static QTreeNode * 287 q_tree_node_next(QTreeNode *node) 288 { 289 QTreeNode *tmp; 290 291 g_return_val_if_fail(node != NULL, NULL); 292 293 tmp = node->right; 294 295 if (node->right_child) { 296 while (tmp->left_child) { 297 tmp = tmp->left; 298 } 299 } 300 301 return tmp; 302 } 303 304 /** 305 * q_tree_remove_all: 306 * @tree: a #QTree 307 * 308 * Removes all nodes from a #QTree and destroys their keys and values, 309 * then resets the #QTree’s root to %NULL. 310 * 311 * Since: 2.70 in GLib. Internal in Qtree, i.e. not in the public API. 312 */ 313 static void QEMU_DISABLE_CFI 314 q_tree_remove_all(QTree *tree) 315 { 316 QTreeNode *node; 317 QTreeNode *next; 318 319 g_return_if_fail(tree != NULL); 320 321 node = q_tree_node_first(tree); 322 323 while (node) { 324 next = q_tree_node_next(node); 325 326 if (tree->key_destroy_func) { 327 tree->key_destroy_func(node->key); 328 } 329 if (tree->value_destroy_func) { 330 tree->value_destroy_func(node->value); 331 } 332 g_free(node); 333 334 #ifdef Q_TREE_DEBUG 335 g_assert(tree->nnodes > 0); 336 tree->nnodes--; 337 #endif 338 339 node = next; 340 } 341 342 #ifdef Q_TREE_DEBUG 343 g_assert(tree->nnodes == 0); 344 #endif 345 346 tree->root = NULL; 347 #ifndef Q_TREE_DEBUG 348 tree->nnodes = 0; 349 #endif 350 } 351 352 /** 353 * q_tree_ref: 354 * @tree: a #QTree 355 * 356 * Increments the reference count of @tree by one. 357 * 358 * It is safe to call this function from any thread. 359 * 360 * Returns: the passed in #QTree 361 * 362 * Since: 2.22 363 */ 364 QTree * 365 q_tree_ref(QTree *tree) 366 { 367 g_return_val_if_fail(tree != NULL, NULL); 368 369 g_atomic_int_inc(&tree->ref_count); 370 371 return tree; 372 } 373 374 /** 375 * q_tree_unref: 376 * @tree: a #QTree 377 * 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. 382 * 383 * It is safe to call this function from any thread. 384 * 385 * Since: 2.22 386 */ 387 void 388 q_tree_unref(QTree *tree) 389 { 390 g_return_if_fail(tree != NULL); 391 392 if (g_atomic_int_dec_and_test(&tree->ref_count)) { 393 q_tree_remove_all(tree); 394 g_free(tree); 395 } 396 } 397 398 /** 399 * q_tree_destroy: 400 * @tree: a #QTree 401 * 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 407 * the #QTree. 408 */ 409 void 410 q_tree_destroy(QTree *tree) 411 { 412 g_return_if_fail(tree != NULL); 413 414 q_tree_remove_all(tree); 415 q_tree_unref(tree); 416 } 417 418 /** 419 * q_tree_insert_node: 420 * @tree: a #QTree 421 * @key: the key to insert 422 * @value: the value corresponding to the key 423 * 424 * Inserts a key/value pair into a #QTree. 425 * 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. 431 * 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 436 * are O(log(n)). 437 * 438 * Returns: (transfer none): the inserted (or set) node. 439 * 440 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. 441 */ 442 static QTreeNode * 443 q_tree_insert_node(QTree *tree, 444 gpointer key, 445 gpointer value) 446 { 447 QTreeNode *node; 448 449 g_return_val_if_fail(tree != NULL, NULL); 450 451 node = q_tree_insert_internal(tree, key, value, FALSE); 452 453 #ifdef Q_TREE_DEBUG 454 q_tree_node_check(tree->root); 455 #endif 456 457 return node; 458 } 459 460 /** 461 * q_tree_insert: 462 * @tree: a #QTree 463 * @key: the key to insert 464 * @value: the value corresponding to the key 465 * 466 * Inserts a key/value pair into a #QTree. 467 * 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. 470 */ 471 void 472 q_tree_insert(QTree *tree, 473 gpointer key, 474 gpointer value) 475 { 476 q_tree_insert_node(tree, key, value); 477 } 478 479 /** 480 * q_tree_replace_node: 481 * @tree: a #QTree 482 * @key: the key to insert 483 * @value: the value corresponding to the key 484 * 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. 491 * 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. 494 * 495 * Returns: (transfer none): the inserted (or set) node. 496 * 497 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. 498 */ 499 static QTreeNode * 500 q_tree_replace_node(QTree *tree, 501 gpointer key, 502 gpointer value) 503 { 504 QTreeNode *node; 505 506 g_return_val_if_fail(tree != NULL, NULL); 507 508 node = q_tree_insert_internal(tree, key, value, TRUE); 509 510 #ifdef Q_TREE_DEBUG 511 q_tree_node_check(tree->root); 512 #endif 513 514 return node; 515 } 516 517 /** 518 * q_tree_replace: 519 * @tree: a #QTree 520 * @key: the key to insert 521 * @value: the value corresponding to the key 522 * 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. 525 */ 526 void 527 q_tree_replace(QTree *tree, 528 gpointer key, 529 gpointer value) 530 { 531 q_tree_replace_node(tree, key, value); 532 } 533 534 /* internal insert routine */ 535 static QTreeNode * QEMU_DISABLE_CFI 536 q_tree_insert_internal(QTree *tree, 537 gpointer key, 538 gpointer value, 539 gboolean replace) 540 { 541 QTreeNode *node, *retnode; 542 QTreeNode *path[MAX_GTREE_HEIGHT]; 543 int idx; 544 545 g_return_val_if_fail(tree != NULL, NULL); 546 547 if (!tree->root) { 548 tree->root = q_tree_node_new(key, value); 549 tree->nnodes++; 550 return tree->root; 551 } 552 553 idx = 0; 554 path[idx++] = NULL; 555 node = tree->root; 556 557 while (1) { 558 int cmp = tree->key_compare(key, node->key, tree->key_compare_data); 559 560 if (cmp == 0) { 561 if (tree->value_destroy_func) { 562 tree->value_destroy_func(node->value); 563 } 564 565 node->value = value; 566 567 if (replace) { 568 if (tree->key_destroy_func) { 569 tree->key_destroy_func(node->key); 570 } 571 572 node->key = key; 573 } else { 574 /* free the passed key */ 575 if (tree->key_destroy_func) { 576 tree->key_destroy_func(key); 577 } 578 } 579 580 return node; 581 } else if (cmp < 0) { 582 if (node->left_child) { 583 path[idx++] = node; 584 node = node->left; 585 } else { 586 QTreeNode *child = q_tree_node_new(key, value); 587 588 child->left = node->left; 589 child->right = node; 590 node->left = child; 591 node->left_child = TRUE; 592 node->balance -= 1; 593 594 tree->nnodes++; 595 596 retnode = child; 597 break; 598 } 599 } else { 600 if (node->right_child) { 601 path[idx++] = node; 602 node = node->right; 603 } else { 604 QTreeNode *child = q_tree_node_new(key, value); 605 606 child->right = node->right; 607 child->left = node; 608 node->right = child; 609 node->right_child = TRUE; 610 node->balance += 1; 611 612 tree->nnodes++; 613 614 retnode = child; 615 break; 616 } 617 } 618 } 619 620 /* 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. 624 */ 625 while (1) { 626 QTreeNode *bparent = path[--idx]; 627 gboolean left_node = (bparent && node == bparent->left); 628 g_assert(!bparent || bparent->left == node || bparent->right == node); 629 630 if (node->balance < -1 || node->balance > 1) { 631 node = q_tree_node_balance(node); 632 if (bparent == NULL) { 633 tree->root = node; 634 } else if (left_node) { 635 bparent->left = node; 636 } else { 637 bparent->right = node; 638 } 639 } 640 641 if (node->balance == 0 || bparent == NULL) { 642 break; 643 } 644 645 if (left_node) { 646 bparent->balance -= 1; 647 } else { 648 bparent->balance += 1; 649 } 650 651 node = bparent; 652 } 653 654 return retnode; 655 } 656 657 /** 658 * q_tree_remove: 659 * @tree: a #QTree 660 * @key: the key to remove 661 * 662 * Removes a key/value pair from a #QTree. 663 * 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. 668 * 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 671 * are O(log(n)). 672 * 673 * Returns: %TRUE if the key was found (prior to 2.8, this function 674 * returned nothing) 675 */ 676 gboolean 677 q_tree_remove(QTree *tree, 678 gconstpointer key) 679 { 680 gboolean removed; 681 682 g_return_val_if_fail(tree != NULL, FALSE); 683 684 removed = q_tree_remove_internal(tree, key, FALSE); 685 686 #ifdef Q_TREE_DEBUG 687 q_tree_node_check(tree->root); 688 #endif 689 690 return removed; 691 } 692 693 /** 694 * q_tree_steal: 695 * @tree: a #QTree 696 * @key: the key to remove 697 * 698 * Removes a key and its associated value from a #QTree without calling 699 * the key and value destroy functions. 700 * 701 * If the key does not exist in the #QTree, the function does nothing. 702 * 703 * Returns: %TRUE if the key was found (prior to 2.8, this function 704 * returned nothing) 705 */ 706 gboolean 707 q_tree_steal(QTree *tree, 708 gconstpointer key) 709 { 710 gboolean removed; 711 712 g_return_val_if_fail(tree != NULL, FALSE); 713 714 removed = q_tree_remove_internal(tree, key, TRUE); 715 716 #ifdef Q_TREE_DEBUG 717 q_tree_node_check(tree->root); 718 #endif 719 720 return removed; 721 } 722 723 /* internal remove routine */ 724 static gboolean QEMU_DISABLE_CFI 725 q_tree_remove_internal(QTree *tree, 726 gconstpointer key, 727 gboolean steal) 728 { 729 QTreeNode *node, *parent, *balance; 730 QTreeNode *path[MAX_GTREE_HEIGHT]; 731 int idx; 732 gboolean left_node; 733 734 g_return_val_if_fail(tree != NULL, FALSE); 735 736 if (!tree->root) { 737 return FALSE; 738 } 739 740 idx = 0; 741 path[idx++] = NULL; 742 node = tree->root; 743 744 while (1) { 745 int cmp = tree->key_compare(key, node->key, tree->key_compare_data); 746 747 if (cmp == 0) { 748 break; 749 } else if (cmp < 0) { 750 if (!node->left_child) { 751 return FALSE; 752 } 753 754 path[idx++] = node; 755 node = node->left; 756 } else { 757 if (!node->right_child) { 758 return FALSE; 759 } 760 761 path[idx++] = node; 762 node = node->right; 763 } 764 } 765 766 /* 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. 769 */ 770 balance = parent = path[--idx]; 771 g_assert(!parent || parent->left == node || parent->right == node); 772 left_node = (parent && node == parent->left); 773 774 if (!node->left_child) { 775 if (!node->right_child) { 776 if (!parent) { 777 tree->root = NULL; 778 } else if (left_node) { 779 parent->left_child = FALSE; 780 parent->left = node->left; 781 parent->balance += 1; 782 } else { 783 parent->right_child = FALSE; 784 parent->right = node->right; 785 parent->balance -= 1; 786 } 787 } else { 788 /* node has a right child */ 789 QTreeNode *tmp = q_tree_node_next(node); 790 tmp->left = node->left; 791 792 if (!parent) { 793 tree->root = node->right; 794 } else if (left_node) { 795 parent->left = node->right; 796 parent->balance += 1; 797 } else { 798 parent->right = node->right; 799 parent->balance -= 1; 800 } 801 } 802 } else { 803 /* node has a left child */ 804 if (!node->right_child) { 805 QTreeNode *tmp = q_tree_node_previous(node); 806 tmp->right = node->right; 807 808 if (parent == NULL) { 809 tree->root = node->left; 810 } else if (left_node) { 811 parent->left = node->left; 812 parent->balance += 1; 813 } else { 814 parent->right = node->left; 815 parent->balance -= 1; 816 } 817 } else { 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; 823 idx++; 824 825 /* path[idx] == parent */ 826 /* find the immediately next node (and its parent) */ 827 while (next->left_child) { 828 path[++idx] = nextp = next; 829 next = next->left; 830 } 831 832 path[old_idx] = next; 833 balance = path[idx]; 834 835 /* remove 'next' from the tree */ 836 if (nextp != node) { 837 if (next->right_child) { 838 nextp->left = next->right; 839 } else { 840 nextp->left_child = FALSE; 841 } 842 nextp->balance += 1; 843 844 next->right_child = TRUE; 845 next->right = node->right; 846 } else { 847 node->balance -= 1; 848 } 849 850 /* set the prev to point to the right place */ 851 while (prev->right_child) { 852 prev = prev->right; 853 } 854 prev->right = next; 855 856 /* prepare 'next' to replace 'node' */ 857 next->left_child = TRUE; 858 next->left = node->left; 859 next->balance = node->balance; 860 861 if (!parent) { 862 tree->root = next; 863 } else if (left_node) { 864 parent->left = next; 865 } else { 866 parent->right = next; 867 } 868 } 869 } 870 871 /* restore balance */ 872 if (balance) { 873 while (1) { 874 QTreeNode *bparent = path[--idx]; 875 g_assert(!bparent || 876 bparent->left == balance || 877 bparent->right == balance); 878 left_node = (bparent && balance == bparent->left); 879 880 if (balance->balance < -1 || balance->balance > 1) { 881 balance = q_tree_node_balance(balance); 882 if (!bparent) { 883 tree->root = balance; 884 } else if (left_node) { 885 bparent->left = balance; 886 } else { 887 bparent->right = balance; 888 } 889 } 890 891 if (balance->balance != 0 || !bparent) { 892 break; 893 } 894 895 if (left_node) { 896 bparent->balance += 1; 897 } else { 898 bparent->balance -= 1; 899 } 900 901 balance = bparent; 902 } 903 } 904 905 if (!steal) { 906 if (tree->key_destroy_func) { 907 tree->key_destroy_func(node->key); 908 } 909 if (tree->value_destroy_func) { 910 tree->value_destroy_func(node->value); 911 } 912 } 913 914 g_free(node); 915 916 tree->nnodes--; 917 918 return TRUE; 919 } 920 921 /** 922 * q_tree_lookup_node: 923 * @tree: a #QTree 924 * @key: the key to look up 925 * 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). 929 * 930 * Returns: (nullable) (transfer none): the tree node corresponding to 931 * the key, or %NULL if the key was not found 932 * 933 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. 934 */ 935 static QTreeNode * 936 q_tree_lookup_node(QTree *tree, 937 gconstpointer key) 938 { 939 g_return_val_if_fail(tree != NULL, NULL); 940 941 return q_tree_find_node(tree, key); 942 } 943 944 /** 945 * q_tree_lookup: 946 * @tree: a #QTree 947 * @key: the key to look up 948 * 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). 952 * 953 * Returns: the value corresponding to the key, or %NULL 954 * if the key was not found 955 */ 956 gpointer 957 q_tree_lookup(QTree *tree, 958 gconstpointer key) 959 { 960 QTreeNode *node; 961 962 node = q_tree_lookup_node(tree, key); 963 964 return node ? node->value : NULL; 965 } 966 967 /** 968 * q_tree_lookup_extended: 969 * @tree: a #QTree 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 973 * the key 974 * 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 978 * q_tree_remove(). 979 * 980 * Returns: %TRUE if the key was found in the #QTree 981 */ 982 gboolean 983 q_tree_lookup_extended(QTree *tree, 984 gconstpointer lookup_key, 985 gpointer *orig_key, 986 gpointer *value) 987 { 988 QTreeNode *node; 989 990 g_return_val_if_fail(tree != NULL, FALSE); 991 992 node = q_tree_find_node(tree, lookup_key); 993 994 if (node) { 995 if (orig_key) { 996 *orig_key = node->key; 997 } 998 if (value) { 999 *value = node->value; 1000 } 1001 return TRUE; 1002 } else { 1003 return FALSE; 1004 } 1005 } 1006 1007 /** 1008 * q_tree_foreach: 1009 * @tree: a #QTree 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 1013 * 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. 1017 * 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. 1022 */ 1023 void 1024 q_tree_foreach(QTree *tree, 1025 GTraverseFunc func, 1026 gpointer user_data) 1027 { 1028 QTreeNode *node; 1029 1030 g_return_if_fail(tree != NULL); 1031 1032 if (!tree->root) { 1033 return; 1034 } 1035 1036 node = q_tree_node_first(tree); 1037 1038 while (node) { 1039 if ((*func)(node->key, node->value, user_data)) { 1040 break; 1041 } 1042 1043 node = q_tree_node_next(node); 1044 } 1045 } 1046 1047 /** 1048 * q_tree_search_node: 1049 * @tree: a #QTree 1050 * @search_func: a function used to search the #QTree 1051 * @user_data: the data passed as the second argument to @search_func 1052 * 1053 * Searches a #QTree using @search_func. 1054 * 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. 1062 * 1063 * Returns: (nullable) (transfer none): the node corresponding to the 1064 * found key, or %NULL if the key was not found 1065 * 1066 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. 1067 */ 1068 static QTreeNode * 1069 q_tree_search_node(QTree *tree, 1070 GCompareFunc search_func, 1071 gconstpointer user_data) 1072 { 1073 g_return_val_if_fail(tree != NULL, NULL); 1074 1075 if (!tree->root) { 1076 return NULL; 1077 } 1078 1079 return q_tree_node_search(tree->root, search_func, user_data); 1080 } 1081 1082 /** 1083 * q_tree_search: 1084 * @tree: a #QTree 1085 * @search_func: a function used to search the #QTree 1086 * @user_data: the data passed as the second argument to @search_func 1087 * 1088 * Searches a #QTree using @search_func. 1089 * 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. 1097 * 1098 * Returns: the value corresponding to the found key, or %NULL 1099 * if the key was not found 1100 */ 1101 gpointer 1102 q_tree_search(QTree *tree, 1103 GCompareFunc search_func, 1104 gconstpointer user_data) 1105 { 1106 QTreeNode *node; 1107 1108 node = q_tree_search_node(tree, search_func, user_data); 1109 1110 return node ? node->value : NULL; 1111 } 1112 1113 /** 1114 * q_tree_height: 1115 * @tree: a #QTree 1116 * 1117 * Gets the height of a #QTree. 1118 * 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. 1122 * 1123 * Returns: the height of @tree 1124 */ 1125 gint 1126 q_tree_height(QTree *tree) 1127 { 1128 QTreeNode *node; 1129 gint height; 1130 1131 g_return_val_if_fail(tree != NULL, 0); 1132 1133 if (!tree->root) { 1134 return 0; 1135 } 1136 1137 height = 0; 1138 node = tree->root; 1139 1140 while (1) { 1141 height += 1 + MAX(node->balance, 0); 1142 1143 if (!node->left_child) { 1144 return height; 1145 } 1146 1147 node = node->left; 1148 } 1149 } 1150 1151 /** 1152 * q_tree_nnodes: 1153 * @tree: a #QTree 1154 * 1155 * Gets the number of nodes in a #QTree. 1156 * 1157 * Returns: the number of nodes in @tree 1158 */ 1159 gint 1160 q_tree_nnodes(QTree *tree) 1161 { 1162 g_return_val_if_fail(tree != NULL, 0); 1163 1164 return tree->nnodes; 1165 } 1166 1167 static QTreeNode * 1168 q_tree_node_balance(QTreeNode *node) 1169 { 1170 if (node->balance < -1) { 1171 if (node->left->balance > 0) { 1172 node->left = q_tree_node_rotate_left(node->left); 1173 } 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); 1178 } 1179 node = q_tree_node_rotate_left(node); 1180 } 1181 1182 return node; 1183 } 1184 1185 static QTreeNode * QEMU_DISABLE_CFI 1186 q_tree_find_node(QTree *tree, 1187 gconstpointer key) 1188 { 1189 QTreeNode *node; 1190 gint cmp; 1191 1192 node = tree->root; 1193 if (!node) { 1194 return NULL; 1195 } 1196 1197 while (1) { 1198 cmp = tree->key_compare(key, node->key, tree->key_compare_data); 1199 if (cmp == 0) { 1200 return node; 1201 } else if (cmp < 0) { 1202 if (!node->left_child) { 1203 return NULL; 1204 } 1205 1206 node = node->left; 1207 } else { 1208 if (!node->right_child) { 1209 return NULL; 1210 } 1211 1212 node = node->right; 1213 } 1214 } 1215 } 1216 1217 static QTreeNode * 1218 q_tree_node_search(QTreeNode *node, 1219 GCompareFunc search_func, 1220 gconstpointer data) 1221 { 1222 gint dir; 1223 1224 if (!node) { 1225 return NULL; 1226 } 1227 1228 while (1) { 1229 dir = (*search_func)(node->key, data); 1230 if (dir == 0) { 1231 return node; 1232 } else if (dir < 0) { 1233 if (!node->left_child) { 1234 return NULL; 1235 } 1236 1237 node = node->left; 1238 } else { 1239 if (!node->right_child) { 1240 return NULL; 1241 } 1242 1243 node = node->right; 1244 } 1245 } 1246 } 1247 1248 static QTreeNode * 1249 q_tree_node_rotate_left(QTreeNode *node) 1250 { 1251 QTreeNode *right; 1252 gint a_bal; 1253 gint b_bal; 1254 1255 right = node->right; 1256 1257 if (right->left_child) { 1258 node->right = right->left; 1259 } else { 1260 node->right_child = FALSE; 1261 right->left_child = TRUE; 1262 } 1263 right->left = node; 1264 1265 a_bal = node->balance; 1266 b_bal = right->balance; 1267 1268 if (b_bal <= 0) { 1269 if (a_bal >= 1) { 1270 right->balance = b_bal - 1; 1271 } else { 1272 right->balance = a_bal + b_bal - 2; 1273 } 1274 node->balance = a_bal - 1; 1275 } else { 1276 if (a_bal <= b_bal) { 1277 right->balance = a_bal - 2; 1278 } else { 1279 right->balance = b_bal - 1; 1280 } 1281 node->balance = a_bal - b_bal - 1; 1282 } 1283 1284 return right; 1285 } 1286 1287 static QTreeNode * 1288 q_tree_node_rotate_right(QTreeNode *node) 1289 { 1290 QTreeNode *left; 1291 gint a_bal; 1292 gint b_bal; 1293 1294 left = node->left; 1295 1296 if (left->right_child) { 1297 node->left = left->right; 1298 } else { 1299 node->left_child = FALSE; 1300 left->right_child = TRUE; 1301 } 1302 left->right = node; 1303 1304 a_bal = node->balance; 1305 b_bal = left->balance; 1306 1307 if (b_bal <= 0) { 1308 if (b_bal > a_bal) { 1309 left->balance = b_bal + 1; 1310 } else { 1311 left->balance = a_bal + 2; 1312 } 1313 node->balance = a_bal - b_bal + 1; 1314 } else { 1315 if (a_bal <= -1) { 1316 left->balance = b_bal + 1; 1317 } else { 1318 left->balance = a_bal + b_bal + 2; 1319 } 1320 node->balance = a_bal + 1; 1321 } 1322 1323 return left; 1324 } 1325 1326 #ifdef Q_TREE_DEBUG 1327 static gint 1328 q_tree_node_height(QTreeNode *node) 1329 { 1330 gint left_height; 1331 gint right_height; 1332 1333 if (node) { 1334 left_height = 0; 1335 right_height = 0; 1336 1337 if (node->left_child) { 1338 left_height = q_tree_node_height(node->left); 1339 } 1340 1341 if (node->right_child) { 1342 right_height = q_tree_node_height(node->right); 1343 } 1344 1345 return MAX(left_height, right_height) + 1; 1346 } 1347 1348 return 0; 1349 } 1350 1351 static void q_tree_node_check(QTreeNode *node) 1352 { 1353 gint left_height; 1354 gint right_height; 1355 gint balance; 1356 QTreeNode *tmp; 1357 1358 if (node) { 1359 if (node->left_child) { 1360 tmp = q_tree_node_previous(node); 1361 g_assert(tmp->right == node); 1362 } 1363 1364 if (node->right_child) { 1365 tmp = q_tree_node_next(node); 1366 g_assert(tmp->left == node); 1367 } 1368 1369 left_height = 0; 1370 right_height = 0; 1371 1372 if (node->left_child) { 1373 left_height = q_tree_node_height(node->left); 1374 } 1375 if (node->right_child) { 1376 right_height = q_tree_node_height(node->right); 1377 } 1378 1379 balance = right_height - left_height; 1380 g_assert(balance == node->balance); 1381 1382 if (node->left_child) { 1383 q_tree_node_check(node->left); 1384 } 1385 if (node->right_child) { 1386 q_tree_node_check(node->right); 1387 } 1388 } 1389 } 1390 #endif 1391