Tree package:gi-glib
The GTree struct is an opaque data structure representing a [balanced
binary tree][glib-Balanced-Binary-Trees]. It should be accessed only
by using the following functions.
Memory-managed wrapper type.
An opaque type which identifies a specific node in a
Tree.
Since: 2.68
Memory-managed wrapper type.
Removes all keys and values from the
Tree and decreases its
reference count by one. If keys and/or values are dynamically
allocated, you should either free them first or create the
Tree
using
treeNewFull. In the latter case the destroy functions you
supplied will be called on all keys and values before destroying the
Tree.
Calls the given function for each of the key/value pairs in the
Tree. The function is passed the key and value of each pair,
and the given
data parameter. The tree is traversed in
sorted order.
The tree may not be modified while iterating over it (you can't
add/remove items). To remove all items matching a predicate, you need
to add each item to a list in your
TraverseFunc as you walk
over the tree, then walk the list and remove each item.
Calls the given function for each of the nodes in the
Tree. The
function is passed the pointer to the particular node, and the given
data parameter. The tree traversal happens in-order.
The tree may not be modified while iterating over it (you can't
add/remove items). To remove all items matching a predicate, you need
to add each item to a list in your
TraverseFunc as you walk
over the tree, then walk the list and remove each item.
Since: 2.68
Gets the height of a
Tree.
If the
Tree contains no nodes, the height is 0. If the
Tree contains only one root node the height is 1. If the root
node has children the height is 2, etc.
Inserts a key/value pair into a
Tree.
Inserts a new key and value into a
Tree as
treeInsertNode does, only this function does not return the
inserted or set node.
Inserts a key/value pair into a
Tree.
If the given key already exists in the
Tree its corresponding
value is set to the new value. If you supplied a
valueDestroyFunc when creating the
Tree, the
old value is freed using that function. If you supplied a
keyDestroyFunc when creating the
Tree, the
passed key is freed using that function.
The tree is automatically 'balanced' as new key/value pairs are added,
so that the distance from the root to every leaf is as small as
possible. The cost of maintaining a balanced tree while inserting new
key/value result in a O(n log(n)) operation where most of the other
operations are O(log(n)).
Since: 2.68
Gets the value corresponding to the given key. Since a
Tree is
automatically balanced as key/value pairs are added, key lookup is
O(log n) (where n is the number of key/value pairs in the tree).
Looks up a key in the
Tree, returning the original key and the
associated value. This is useful if you need to free the memory
allocated for the original key, for example before calling
treeRemove.
Gets the tree node corresponding to the given key. Since a
Tree
is automatically balanced as key/value pairs are added, key lookup is
O(log n) (where n is the number of key/value pairs in the tree).
Since: 2.68
Gets the lower bound node corresponding to the given key, or
Nothing if the tree is empty or all the nodes in the tree have
keys that are strictly lower than the searched key.
The lower bound is the first node that has its key greater than or
equal to the searched key.
Since: 2.68
Creates a new
Tree like
g_tree_new() and allows
to specify functions to free the memory allocated for the key and
value that get called when removing the entry from the
Tree.
Gets the number of nodes in a
Tree.
Returns the first in-order node of the tree, or
Nothing for an
empty tree.
Since: 2.68
Returns the last in-order node of the tree, or
Nothing for an
empty tree.
Since: 2.68
Increments the reference count of tree by one.
It is safe to call this function from any thread.
Since: 2.22
Removes a key/value pair from a
Tree.
If the
Tree was created using
treeNewFull, the key and
value are freed using the supplied destroy functions, otherwise you
have to make sure that any dynamically allocated values are freed
yourself. If the key does not exist in the
Tree, the function
does nothing.
The cost of maintaining a balanced tree while removing a key/value
result in a O(n log(n)) operation where most of the other operations
are O(log(n)).
Removes all nodes from a
Tree and destroys their keys and
values, then resets the
Tree’s root to
Nothing.
Since: 2.70
Inserts a new key and value into a
Tree as
treeReplaceNode does, only this function does not return the
inserted or set node.
Inserts a new key and value into a
Tree similar to
treeInsertNode. The difference is that if the key already
exists in the
Tree, it gets replaced by the new key. If you
supplied a
valueDestroyFunc when creating the
Tree, the old value is freed using that function. If you
supplied a
keyDestroyFunc when creating the
Tree, the old key is freed using that function.
The tree is automatically 'balanced' as new key/value pairs are added,
so that the distance from the root to every leaf is as small as
possible.
Since: 2.68