GLib Reference Manual | |||
---|---|---|---|

<<< Previous Page | Home | Up | Next Page >>> |

#include <glib.h> struct GTree; GTree* g_tree_new (GCompareFunc key_compare_func); void g_tree_insert (GTree *tree, gpointer key, gpointer value); gint g_tree_nnodes (GTree *tree); gint g_tree_height (GTree *tree); gpointer g_tree_lookup (GTree *tree, gpointer key); gpointer g_tree_search (GTree *tree, GSearchFunc search_func, gpointer data); gint (*GSearchFunc) (gpointer key, gpointer data); void g_tree_traverse (GTree *tree, GTraverseFunc traverse_func, GTraverseType traverse_type, gpointer data); gint (*GTraverseFunc) (gpointer key, gpointer value, gpointer data); enum GTraverseType; void g_tree_remove (GTree *tree, gpointer key); void g_tree_destroy (GTree *tree); |

The GTree structure and its associated functions provide a sorted collection of key/value pairs optimised for searching and traversing in order.

To create a new GTree use g_tree_new().

To insert a key/value pair into a GTree use g_tree_insert().

To lookup the value corresponding to a given key, use g_tree_lookup().

To find out the number of nodes in a GTree, use g_tree_nnodes(). To get the height of a GTree, use g_tree_height().

To traverse a GTree, calling a function for each node visited in the traversal, use g_tree_traverse().

To remove a key/value pair use g_tree_remove().

To destroy a GTree, use g_tree_destroy().

struct GTree; |

The GTree struct is an opaque data structure representing a Balanced Binary Tree. It should be accessed only by using the following functions.

GTree* g_tree_new (GCompareFunc key_compare_func); |

Creates a new GTree.

:key_compare_func | the function used to order the nodes in the GTree.
It should return values similar to the standard strcmp()
function -
0 if the two arguments are equal, a negative value if the first argument comes
before the second, or a positive value if the first argument comes after the
second. |

Returns : | a new GTree. |

void g_tree_insert (GTree *tree, gpointer key, gpointer value); |

Inserts a key/value pair into a GTree. If the given key already exists in the GTree it is set to the new value. (If you are using dynamically allocated keys and values you should be careful to ensure that the old values are freed.)

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.

:tree | a GTree. |

:key | the key to insert. |

:value | the value corresponding to the key. |

gint g_tree_height (GTree *tree); |

Gets the height of a GTree.

If the GTree contains no nodes, the height is 0. If the GTree contains only one root node the height is 1. If the root node has children the height is 2, etc.

gpointer g_tree_lookup (GTree *tree, gpointer key); |

Gets the value corresponding to the given key. Since a GTree is automatically balanced as key/value pairs are added, key lookup is very fast.

:tree | a GTree. |

:key | the key to look up. |

Returns : | the value corresponding to the key. |

gpointer g_tree_search (GTree *tree, GSearchFunc search_func, gpointer data); |

Searches a GTree using an alternative form of the comparison function.

This function is not as useful as it sounds.
It allows you to use a different function for performing the lookup of
a key. However, since the tree is ordered according to the ` key_compare_func`
function passed to g_tree_new(), the function you pass to g_tree_search() must
return exactly the same value as would be returned by the comparison function,
for each pair of tree nodes, or the search will not work.

To search for a specific value, you can use g_tree_traverse().

gint (*GSearchFunc) (gpointer key, gpointer data); |

Specifies the type of function passed to g_tree_search().

void g_tree_traverse (GTree *tree, GTraverseFunc traverse_func, GTraverseType traverse_type, gpointer data); |

Calls the given function for each node in the GTree.

:tree | a GTree. |

:traverse_func | the function to call for each node visited. If this function returns TRUE, the traversal is stopped. |

:traverse_type | the order in which nodes are visited, one of G_IN_ORDER,
G_PRE_ORDER and G_POST_ORDER. |

:data | user data to pass to the traverse function. |

gint (*GTraverseFunc) (gpointer key, gpointer value, gpointer data); |

Specifies the type of function passed to g_tree_traverse().
It is passed the key and value of each node, together with
the ` user_data` parameter passed to g_tree_traverse().
If the function returns TRUE, the traversal is stopped.

:key | a key of a GTree node. |

:value | the value corresponding to the key. |

:data | user data passed to g_tree_traverse(). |

Returns : | TRUE to stop the traversal. |

typedef enum { G_IN_ORDER, G_PRE_ORDER, G_POST_ORDER, G_LEVEL_ORDER } GTraverseType; |

Specifies the type of traveral performed by g_tree_traverse(), g_node_traverse() and g_node_find().

`G_PRE_ORDER`visits a node, then its children.`G_IN_ORDER`vists a node's left child first, then the node itself, then its right child. This is the one to use if you want the output sorted according to the compare function.`G_POST_ORDER`visits the node's children, then the node itself.`G_LEVEL_ORDER`is not implemented for Balanced Binary Trees. For N-ary Trees it calls the function for each child of the node, then it recursively visits each child.

void g_tree_remove (GTree *tree, gpointer key); |

Removes a key/value pair from a GTree. If the key or value is dynamically allocated you must remember to free them yourself.

:tree | a GTree. |

:key | the key to remove. |