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
87     gpointer   key;         /* key for this node */  member
97 static QTreeNode *q_tree_node_new(gpointer       key,
100                                          gpointer key,
104                                          gconstpointer  key,
108                                    gconstpointer  key);
119 q_tree_node_new(gpointer key,  in q_tree_node_new()  argument
129     node->key = key;  in q_tree_node_new()
180  * @key_destroy_func: a function to free the memory allocated for the key
188  * to free the memory allocated for the key and value that get called when
327             tree->key_destroy_func(node->key);  in q_tree_remove_all()
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
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
451     node = q_tree_insert_internal(tree, key, value, FALSE);  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
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
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
508     node = q_tree_insert_internal(tree, key, value, TRUE);  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
531     q_tree_replace_node(tree, key, value);  in q_tree_replace()
537                        gpointer  key,  in q_tree_insert_internal()  argument
548         tree->root = q_tree_node_new(key, value);  in q_tree_insert_internal()
558         int cmp = tree->key_compare(key, node->key, tree->key_compare_data);  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()
576                     tree->key_destroy_func(key);  in q_tree_insert_internal()
586                 QTreeNode *child = q_tree_node_new(key, value);  in q_tree_insert_internal()
604                 QTreeNode *child = q_tree_node_new(key, value);  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()
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()
726                        gconstpointer  key,  in q_tree_remove_internal()  argument
745         int cmp = tree->key_compare(key, node->key, tree->key_compare_data);  in q_tree_remove_internal()
907             tree->key_destroy_func(node->key);  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()
970  * @lookup_key: the key to look up
971  * @orig_key: (out) (optional) (nullable): returns the original key
973  *         the key
975  * Looks up a key in the #QTree, returning the original key and the
977  * allocated for the original key, for example before calling
980  * Returns: %TRUE if the key was found in the #QTree
996             *orig_key = node->key;  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
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
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
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
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
1187                  gconstpointer key)  in q_tree_find_node()  argument
1198         cmp = tree->key_compare(key, node->key, tree->key_compare_data);  in q_tree_find_node()
1229         dir = (*search_func)(node->key, data);  in q_tree_node_search()