Lines Matching +full:key +full:- +full:value
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
22 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
36 * SECTION:trees-binary
38 * @short_description: a sorted collection of key/value pairs optimized
42 * collection of key/value pairs optimized for searching and traversing
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
73 * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be
87 gpointer key; /* key for this node */ member
88 gpointer value; /* value stored at this node */ member
91 gint8 balance; /* height (right) - height (left) */
97 static QTreeNode *q_tree_node_new(gpointer key,
98 gpointer value);
100 gpointer key,
101 gpointer value,
104 gconstpointer key,
108 gconstpointer key);
119 q_tree_node_new(gpointer key, in q_tree_node_new() argument
120 gpointer value) in q_tree_node_new() argument
124 node->balance = 0; in q_tree_node_new()
125 node->left = NULL; in q_tree_node_new()
126 node->right = NULL; in q_tree_node_new()
127 node->left_child = FALSE; in q_tree_node_new()
128 node->right_child = FALSE; in q_tree_node_new()
129 node->key = key; in q_tree_node_new()
130 node->value = value; in q_tree_node_new()
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
158 * @key_compare_func: qsort()-style comparison function
178 * @key_compare_func: qsort()-style comparison function
180 * @key_destroy_func: a function to free the memory allocated for the key
184 * value used when removing the entry from the #QTree or %NULL if you
188 * to free the memory allocated for the key and value that get called when
204 tree->root = NULL; in q_tree_new_full()
205 tree->key_compare = key_compare_func; in q_tree_new_full()
206 tree->key_destroy_func = key_destroy_func; in q_tree_new_full()
207 tree->value_destroy_func = value_destroy_func; in q_tree_new_full()
208 tree->key_compare_data = key_compare_data; in q_tree_new_full()
209 tree->nnodes = 0; in q_tree_new_full()
210 tree->ref_count = 1; in q_tree_new_full()
219 * Returns the first in-order node of the tree, or %NULL
233 if (!tree->root) { in q_tree_node_first()
237 tmp = tree->root; in q_tree_node_first()
239 while (tmp->left_child) { in q_tree_node_first()
240 tmp = tmp->left; in q_tree_node_first()
250 * Returns the previous in-order node of the tree, or %NULL
264 tmp = node->left; in q_tree_node_previous()
266 if (node->left_child) { in q_tree_node_previous()
267 while (tmp->right_child) { in q_tree_node_previous()
268 tmp = tmp->right; in q_tree_node_previous()
279 * Returns the next in-order node of the tree, or %NULL
293 tmp = node->right; in q_tree_node_next()
295 if (node->right_child) { in q_tree_node_next()
296 while (tmp->left_child) { in q_tree_node_next()
297 tmp = tmp->left; in q_tree_node_next()
326 if (tree->key_destroy_func) { in q_tree_remove_all()
327 tree->key_destroy_func(node->key); in q_tree_remove_all()
329 if (tree->value_destroy_func) { in q_tree_remove_all()
330 tree->value_destroy_func(node->value); in q_tree_remove_all()
335 g_assert(tree->nnodes > 0); in q_tree_remove_all()
336 tree->nnodes--; in q_tree_remove_all()
343 g_assert(tree->nnodes == 0); in q_tree_remove_all()
346 tree->root = NULL; in q_tree_remove_all()
348 tree->nnodes = 0; in q_tree_remove_all()
369 g_atomic_int_inc(&tree->ref_count); in q_tree_ref()
392 if (g_atomic_int_dec_and_test(&tree->ref_count)) { in q_tree_unref()
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
430 * key is freed using that function.
432 * The tree is automatically 'balanced' as new key/value pairs are added,
434 * The cost of maintaining a balanced tree while inserting new key/value
444 gpointer key, in q_tree_insert_node() argument
445 gpointer value) in q_tree_insert_node() argument
451 node = q_tree_insert_internal(tree, key, value, FALSE); in q_tree_insert_node()
454 q_tree_node_check(tree->root); in q_tree_insert_node()
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,
473 gpointer key, in q_tree_insert() argument
474 gpointer value) in q_tree_insert() argument
476 q_tree_insert_node(tree, key, value); in q_tree_insert()
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
492 * The tree is automatically 'balanced' as new key/value pairs are added,
501 gpointer key, in q_tree_replace_node() argument
502 gpointer value) in q_tree_replace_node() argument
508 node = q_tree_insert_internal(tree, key, value, TRUE); in q_tree_replace_node()
511 q_tree_node_check(tree->root); in q_tree_replace_node()
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,
528 gpointer key, in q_tree_replace() argument
529 gpointer value) in q_tree_replace() argument
531 q_tree_replace_node(tree, key, value); in q_tree_replace()
537 gpointer key, in q_tree_insert_internal() argument
538 gpointer value, in q_tree_insert_internal() argument
547 if (!tree->root) { in q_tree_insert_internal()
548 tree->root = q_tree_node_new(key, value); in q_tree_insert_internal()
549 tree->nnodes++; in q_tree_insert_internal()
550 return tree->root; in q_tree_insert_internal()
555 node = tree->root; in q_tree_insert_internal()
558 int cmp = tree->key_compare(key, node->key, tree->key_compare_data); in q_tree_insert_internal()
561 if (tree->value_destroy_func) { in q_tree_insert_internal()
562 tree->value_destroy_func(node->value); in q_tree_insert_internal()
565 node->value = value; in q_tree_insert_internal()
568 if (tree->key_destroy_func) { in q_tree_insert_internal()
569 tree->key_destroy_func(node->key); in q_tree_insert_internal()
572 node->key = key; in q_tree_insert_internal()
574 /* free the passed key */ in q_tree_insert_internal()
575 if (tree->key_destroy_func) { in q_tree_insert_internal()
576 tree->key_destroy_func(key); in q_tree_insert_internal()
582 if (node->left_child) { in q_tree_insert_internal()
584 node = node->left; in q_tree_insert_internal()
586 QTreeNode *child = q_tree_node_new(key, value); in q_tree_insert_internal()
588 child->left = node->left; in q_tree_insert_internal()
589 child->right = node; in q_tree_insert_internal()
590 node->left = child; in q_tree_insert_internal()
591 node->left_child = TRUE; in q_tree_insert_internal()
592 node->balance -= 1; in q_tree_insert_internal()
594 tree->nnodes++; in q_tree_insert_internal()
600 if (node->right_child) { in q_tree_insert_internal()
602 node = node->right; in q_tree_insert_internal()
604 QTreeNode *child = q_tree_node_new(key, value); in q_tree_insert_internal()
606 child->right = node->right; in q_tree_insert_internal()
607 child->left = node; in q_tree_insert_internal()
608 node->right = child; in q_tree_insert_internal()
609 node->right_child = TRUE; in q_tree_insert_internal()
610 node->balance += 1; in q_tree_insert_internal()
612 tree->nnodes++; in q_tree_insert_internal()
621 * Restore balance. This is the goodness of a non-recursive in q_tree_insert_internal()
626 QTreeNode *bparent = path[--idx]; in q_tree_insert_internal()
627 gboolean left_node = (bparent && node == bparent->left); in q_tree_insert_internal()
628 g_assert(!bparent || bparent->left == node || bparent->right == node); in q_tree_insert_internal()
630 if (node->balance < -1 || node->balance > 1) { in q_tree_insert_internal()
633 tree->root = node; in q_tree_insert_internal()
635 bparent->left = node; in q_tree_insert_internal()
637 bparent->right = node; in q_tree_insert_internal()
641 if (node->balance == 0 || bparent == NULL) { in q_tree_insert_internal()
646 bparent->balance -= 1; in q_tree_insert_internal()
648 bparent->balance += 1; in q_tree_insert_internal()
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
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
673 * Returns: %TRUE if the key was found (prior to 2.8, this function
678 gconstpointer key) in q_tree_remove() argument
684 removed = q_tree_remove_internal(tree, key, FALSE); in q_tree_remove()
687 q_tree_node_check(tree->root); in q_tree_remove()
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
708 gconstpointer key) in q_tree_steal() argument
714 removed = q_tree_remove_internal(tree, key, TRUE); in q_tree_steal()
717 q_tree_node_check(tree->root); in q_tree_steal()
726 gconstpointer key, in q_tree_remove_internal() argument
736 if (!tree->root) { in q_tree_remove_internal()
742 node = tree->root; in q_tree_remove_internal()
745 int cmp = tree->key_compare(key, node->key, tree->key_compare_data); in q_tree_remove_internal()
750 if (!node->left_child) { in q_tree_remove_internal()
755 node = node->left; in q_tree_remove_internal()
757 if (!node->right_child) { in q_tree_remove_internal()
762 node = node->right; in q_tree_remove_internal()
770 balance = parent = path[--idx]; in q_tree_remove_internal()
771 g_assert(!parent || parent->left == node || parent->right == node); in q_tree_remove_internal()
772 left_node = (parent && node == parent->left); in q_tree_remove_internal()
774 if (!node->left_child) { in q_tree_remove_internal()
775 if (!node->right_child) { in q_tree_remove_internal()
777 tree->root = NULL; in q_tree_remove_internal()
779 parent->left_child = FALSE; in q_tree_remove_internal()
780 parent->left = node->left; in q_tree_remove_internal()
781 parent->balance += 1; in q_tree_remove_internal()
783 parent->right_child = FALSE; in q_tree_remove_internal()
784 parent->right = node->right; in q_tree_remove_internal()
785 parent->balance -= 1; in q_tree_remove_internal()
790 tmp->left = node->left; in q_tree_remove_internal()
793 tree->root = node->right; in q_tree_remove_internal()
795 parent->left = node->right; in q_tree_remove_internal()
796 parent->balance += 1; in q_tree_remove_internal()
798 parent->right = node->right; in q_tree_remove_internal()
799 parent->balance -= 1; in q_tree_remove_internal()
804 if (!node->right_child) { in q_tree_remove_internal()
806 tmp->right = node->right; in q_tree_remove_internal()
809 tree->root = node->left; in q_tree_remove_internal()
811 parent->left = node->left; in q_tree_remove_internal()
812 parent->balance += 1; in q_tree_remove_internal()
814 parent->right = node->left; in q_tree_remove_internal()
815 parent->balance -= 1; in q_tree_remove_internal()
819 QTreeNode *prev = node->left; in q_tree_remove_internal()
820 QTreeNode *next = node->right; in q_tree_remove_internal()
827 while (next->left_child) { in q_tree_remove_internal()
829 next = next->left; in q_tree_remove_internal()
837 if (next->right_child) { in q_tree_remove_internal()
838 nextp->left = next->right; in q_tree_remove_internal()
840 nextp->left_child = FALSE; in q_tree_remove_internal()
842 nextp->balance += 1; in q_tree_remove_internal()
844 next->right_child = TRUE; in q_tree_remove_internal()
845 next->right = node->right; in q_tree_remove_internal()
847 node->balance -= 1; in q_tree_remove_internal()
851 while (prev->right_child) { in q_tree_remove_internal()
852 prev = prev->right; in q_tree_remove_internal()
854 prev->right = next; in q_tree_remove_internal()
857 next->left_child = TRUE; in q_tree_remove_internal()
858 next->left = node->left; in q_tree_remove_internal()
859 next->balance = node->balance; in q_tree_remove_internal()
862 tree->root = next; in q_tree_remove_internal()
864 parent->left = next; in q_tree_remove_internal()
866 parent->right = next; in q_tree_remove_internal()
874 QTreeNode *bparent = path[--idx]; in q_tree_remove_internal()
876 bparent->left == balance || in q_tree_remove_internal()
877 bparent->right == balance); in q_tree_remove_internal()
878 left_node = (bparent && balance == bparent->left); in q_tree_remove_internal()
880 if (balance->balance < -1 || balance->balance > 1) { in q_tree_remove_internal()
883 tree->root = balance; in q_tree_remove_internal()
885 bparent->left = balance; in q_tree_remove_internal()
887 bparent->right = balance; in q_tree_remove_internal()
891 if (balance->balance != 0 || !bparent) { in q_tree_remove_internal()
896 bparent->balance += 1; in q_tree_remove_internal()
898 bparent->balance -= 1; in q_tree_remove_internal()
906 if (tree->key_destroy_func) { in q_tree_remove_internal()
907 tree->key_destroy_func(node->key); in q_tree_remove_internal()
909 if (tree->value_destroy_func) { in q_tree_remove_internal()
910 tree->value_destroy_func(node->value); in q_tree_remove_internal()
916 tree->nnodes--; in q_tree_remove_internal()
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).
931 * the key, or %NULL if the key was not found
937 gconstpointer key) in q_tree_lookup_node() argument
941 return q_tree_find_node(tree, key); in q_tree_lookup_node()
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
958 gconstpointer key) in q_tree_lookup() argument
962 node = q_tree_lookup_node(tree, key); in q_tree_lookup()
964 return node ? node->value : NULL; in q_tree_lookup()
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
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
986 gpointer *value) in q_tree_lookup_extended() argument
996 *orig_key = node->key; in q_tree_lookup_extended()
998 if (value) { in q_tree_lookup_extended()
999 *value = node->value; in q_tree_lookup_extended()
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
1032 if (!tree->root) { in q_tree_foreach()
1039 if ((*func)(node->key, node->value, user_data)) { in q_tree_foreach()
1055 * The @search_func is called with a pointer to the key of a key/value
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.
1064 * found key, or %NULL if the key was not found
1075 if (!tree->root) { in q_tree_search_node()
1079 return q_tree_node_search(tree->root, search_func, user_data); in q_tree_search_node()
1090 * The @search_func is called with a pointer to the key of a key/value
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
1110 return node ? node->value : NULL; in q_tree_search()
1133 if (!tree->root) { in q_tree_height()
1138 node = tree->root; in q_tree_height()
1141 height += 1 + MAX(node->balance, 0); in q_tree_height()
1143 if (!node->left_child) { in q_tree_height()
1147 node = node->left; in q_tree_height()
1164 return tree->nnodes; in q_tree_nnodes()
1170 if (node->balance < -1) { in q_tree_node_balance()
1171 if (node->left->balance > 0) { in q_tree_node_balance()
1172 node->left = q_tree_node_rotate_left(node->left); in q_tree_node_balance()
1175 } else if (node->balance > 1) { in q_tree_node_balance()
1176 if (node->right->balance < 0) { in q_tree_node_balance()
1177 node->right = q_tree_node_rotate_right(node->right); in q_tree_node_balance()
1187 gconstpointer key) in q_tree_find_node() argument
1192 node = tree->root; in q_tree_find_node()
1198 cmp = tree->key_compare(key, node->key, tree->key_compare_data); in q_tree_find_node()
1202 if (!node->left_child) { in q_tree_find_node()
1206 node = node->left; in q_tree_find_node()
1208 if (!node->right_child) { in q_tree_find_node()
1212 node = node->right; in q_tree_find_node()
1229 dir = (*search_func)(node->key, data); in q_tree_node_search()
1233 if (!node->left_child) { in q_tree_node_search()
1237 node = node->left; in q_tree_node_search()
1239 if (!node->right_child) { in q_tree_node_search()
1243 node = node->right; in q_tree_node_search()
1255 right = node->right; in q_tree_node_rotate_left()
1257 if (right->left_child) { in q_tree_node_rotate_left()
1258 node->right = right->left; in q_tree_node_rotate_left()
1260 node->right_child = FALSE; in q_tree_node_rotate_left()
1261 right->left_child = TRUE; in q_tree_node_rotate_left()
1263 right->left = node; in q_tree_node_rotate_left()
1265 a_bal = node->balance; in q_tree_node_rotate_left()
1266 b_bal = right->balance; in q_tree_node_rotate_left()
1270 right->balance = b_bal - 1; in q_tree_node_rotate_left()
1272 right->balance = a_bal + b_bal - 2; in q_tree_node_rotate_left()
1274 node->balance = a_bal - 1; in q_tree_node_rotate_left()
1277 right->balance = a_bal - 2; in q_tree_node_rotate_left()
1279 right->balance = b_bal - 1; in q_tree_node_rotate_left()
1281 node->balance = a_bal - b_bal - 1; in q_tree_node_rotate_left()
1294 left = node->left; in q_tree_node_rotate_right()
1296 if (left->right_child) { in q_tree_node_rotate_right()
1297 node->left = left->right; in q_tree_node_rotate_right()
1299 node->left_child = FALSE; in q_tree_node_rotate_right()
1300 left->right_child = TRUE; in q_tree_node_rotate_right()
1302 left->right = node; in q_tree_node_rotate_right()
1304 a_bal = node->balance; in q_tree_node_rotate_right()
1305 b_bal = left->balance; in q_tree_node_rotate_right()
1309 left->balance = b_bal + 1; in q_tree_node_rotate_right()
1311 left->balance = a_bal + 2; in q_tree_node_rotate_right()
1313 node->balance = a_bal - b_bal + 1; in q_tree_node_rotate_right()
1315 if (a_bal <= -1) { in q_tree_node_rotate_right()
1316 left->balance = b_bal + 1; in q_tree_node_rotate_right()
1318 left->balance = a_bal + b_bal + 2; in q_tree_node_rotate_right()
1320 node->balance = a_bal + 1; in q_tree_node_rotate_right()
1337 if (node->left_child) { in q_tree_node_height()
1338 left_height = q_tree_node_height(node->left); in q_tree_node_height()
1341 if (node->right_child) { in q_tree_node_height()
1342 right_height = q_tree_node_height(node->right); in q_tree_node_height()
1359 if (node->left_child) { in q_tree_node_check()
1361 g_assert(tmp->right == node); in q_tree_node_check()
1364 if (node->right_child) { in q_tree_node_check()
1366 g_assert(tmp->left == node); in q_tree_node_check()
1372 if (node->left_child) { in q_tree_node_check()
1373 left_height = q_tree_node_height(node->left); in q_tree_node_check()
1375 if (node->right_child) { in q_tree_node_check()
1376 right_height = q_tree_node_height(node->right); in q_tree_node_check()
1379 balance = right_height - left_height; in q_tree_node_check()
1380 g_assert(balance == node->balance); in q_tree_node_check()
1382 if (node->left_child) { in q_tree_node_check()
1383 q_tree_node_check(node->left); in q_tree_node_check()
1385 if (node->right_child) { in q_tree_node_check()
1386 q_tree_node_check(node->right); in q_tree_node_check()