Lines Matching full:tree
73 * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be
99 static QTreeNode *q_tree_insert_internal(QTree *tree,
103 static gboolean q_tree_remove_internal(QTree *tree,
107 static QTreeNode *q_tree_find_node(QTree *tree,
199 QTree *tree; in q_tree_new_full() local
203 tree = g_new(QTree, 1); in q_tree_new_full()
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()
212 return tree; in q_tree_new_full()
217 * @tree: a #QTree
219 * Returns the first in-order node of the tree, or %NULL
220 * for an empty tree.
222 * Returns: (nullable) (transfer none): the first node in the tree
227 q_tree_node_first(QTree *tree) in q_tree_node_first() argument
231 g_return_val_if_fail(tree != NULL, NULL); in q_tree_node_first()
233 if (!tree->root) { in q_tree_node_first()
237 tmp = tree->root; in q_tree_node_first()
250 * Returns the previous in-order node of the tree, or %NULL
253 * Returns: (nullable) (transfer none): the previous node in the tree
279 * Returns the next in-order node of the tree, or %NULL
282 * Returns: (nullable) (transfer none): the next node in the tree
306 * @tree: a #QTree
314 q_tree_remove_all(QTree *tree) in q_tree_remove_all() argument
319 g_return_if_fail(tree != NULL); in q_tree_remove_all()
321 node = q_tree_node_first(tree); in q_tree_remove_all()
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()
354 * @tree: a #QTree
356 * Increments the reference count of @tree by one.
365 q_tree_ref(QTree *tree) in q_tree_ref() argument
367 g_return_val_if_fail(tree != NULL, NULL); in q_tree_ref()
369 g_atomic_int_inc(&tree->ref_count); in q_tree_ref()
371 return tree; in q_tree_ref()
376 * @tree: a #QTree
378 * Decrements the reference count of @tree by one.
381 * memory allocated by @tree will be released.
388 q_tree_unref(QTree *tree) in q_tree_unref() argument
390 g_return_if_fail(tree != NULL); in q_tree_unref()
392 if (g_atomic_int_dec_and_test(&tree->ref_count)) { in q_tree_unref()
393 q_tree_remove_all(tree); in q_tree_unref()
394 g_free(tree); in q_tree_unref()
400 * @tree: a #QTree
410 q_tree_destroy(QTree *tree) in q_tree_destroy() argument
412 g_return_if_fail(tree != NULL); in q_tree_destroy()
414 q_tree_remove_all(tree); in q_tree_destroy()
415 q_tree_unref(tree); in q_tree_destroy()
420 * @tree: a #QTree
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
443 q_tree_insert_node(QTree *tree, in q_tree_insert_node() argument
449 g_return_val_if_fail(tree != NULL, NULL); in q_tree_insert_node()
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()
462 * @tree: a #QTree
472 q_tree_insert(QTree *tree, in q_tree_insert() argument
476 q_tree_insert_node(tree, key, value); in q_tree_insert()
481 * @tree: a #QTree
492 * The tree is automatically 'balanced' as new key/value pairs are added,
500 q_tree_replace_node(QTree *tree, in q_tree_replace_node() argument
506 g_return_val_if_fail(tree != NULL, NULL); in q_tree_replace_node()
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()
519 * @tree: a #QTree
527 q_tree_replace(QTree *tree, in q_tree_replace() argument
531 q_tree_replace_node(tree, key, value); in q_tree_replace()
536 q_tree_insert_internal(QTree *tree, in q_tree_insert_internal() argument
545 g_return_val_if_fail(tree != NULL, NULL); in q_tree_insert_internal()
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()
568 if (tree->key_destroy_func) { in q_tree_insert_internal()
569 tree->key_destroy_func(node->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()
594 tree->nnodes++; in q_tree_insert_internal()
612 tree->nnodes++; in q_tree_insert_internal()
633 tree->root = node; in q_tree_insert_internal()
659 * @tree: a #QTree
669 * The cost of maintaining a balanced tree while removing a key/value
677 q_tree_remove(QTree *tree, in q_tree_remove() argument
682 g_return_val_if_fail(tree != NULL, FALSE); in q_tree_remove()
684 removed = q_tree_remove_internal(tree, key, FALSE); in q_tree_remove()
687 q_tree_node_check(tree->root); in q_tree_remove()
695 * @tree: a #QTree
707 q_tree_steal(QTree *tree, in q_tree_steal() argument
712 g_return_val_if_fail(tree != NULL, FALSE); in q_tree_steal()
714 removed = q_tree_remove_internal(tree, key, TRUE); in q_tree_steal()
717 q_tree_node_check(tree->root); in q_tree_steal()
725 q_tree_remove_internal(QTree *tree, in q_tree_remove_internal() argument
734 g_return_val_if_fail(tree != NULL, FALSE); in q_tree_remove_internal()
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()
777 tree->root = NULL; in q_tree_remove_internal()
793 tree->root = node->right; in q_tree_remove_internal()
809 tree->root = node->left; in q_tree_remove_internal()
835 /* remove 'next' from the tree */ in q_tree_remove_internal()
862 tree->root = next; in q_tree_remove_internal()
883 tree->root = balance; 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()
923 * @tree: a #QTree
926 * Gets the tree node corresponding to the given key. Since a #QTree is
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
936 q_tree_lookup_node(QTree *tree, in q_tree_lookup_node() argument
939 g_return_val_if_fail(tree != NULL, NULL); in q_tree_lookup_node()
941 return q_tree_find_node(tree, key); in q_tree_lookup_node()
946 * @tree: a #QTree
951 * is O(log n) (where n is the number of key/value pairs in the tree).
957 q_tree_lookup(QTree *tree, in q_tree_lookup() argument
962 node = q_tree_lookup_node(tree, key); in q_tree_lookup()
969 * @tree: a #QTree
983 q_tree_lookup_extended(QTree *tree, in q_tree_lookup_extended() argument
990 g_return_val_if_fail(tree != NULL, FALSE); in q_tree_lookup_extended()
992 node = q_tree_find_node(tree, lookup_key); in q_tree_lookup_extended()
1009 * @tree: a #QTree
1016 * @data parameter. The tree is traversed in sorted order.
1018 * The tree may not be modified while iterating over it (you can't
1021 * the tree, then walk the list and remove each item.
1024 q_tree_foreach(QTree *tree, in q_tree_foreach() argument
1030 g_return_if_fail(tree != NULL); in q_tree_foreach()
1032 if (!tree->root) { in q_tree_foreach()
1036 node = q_tree_node_first(tree); in q_tree_foreach()
1049 * @tree: a #QTree
1056 * pair in the tree, and the passed in @user_data. If @search_func returns
1069 q_tree_search_node(QTree *tree, in q_tree_search_node() argument
1073 g_return_val_if_fail(tree != NULL, NULL); in q_tree_search_node()
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()
1084 * @tree: a #QTree
1091 * pair in the tree, and the passed in @user_data. If @search_func returns
1102 q_tree_search(QTree *tree, in q_tree_search() argument
1108 node = q_tree_search_node(tree, search_func, user_data); in q_tree_search()
1115 * @tree: a #QTree
1123 * Returns: the height of @tree
1126 q_tree_height(QTree *tree) in q_tree_height() argument
1131 g_return_val_if_fail(tree != NULL, 0); in q_tree_height()
1133 if (!tree->root) { in q_tree_height()
1138 node = tree->root; in q_tree_height()
1153 * @tree: a #QTree
1157 * Returns: the number of nodes in @tree
1160 q_tree_nnodes(QTree *tree) in q_tree_nnodes() argument
1162 g_return_val_if_fail(tree != NULL, 0); in q_tree_nnodes()
1164 return tree->nnodes; in q_tree_nnodes()
1186 q_tree_find_node(QTree *tree, 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()