## gsktree

gsktree — A robustly iterateable tree.

## Synopsis

                        GskTreeNode;
                        GskTree;
    GskTree *           gsk_tree_new                        (GCompareFunc compare);
    GskTree *           gsk_tree_ref                        (GskTree *tree);
    void                gsk_tree_unref                      (GskTree *tree);
    GskTree *           gsk_tree_new_full                   (GCompareDataFunc compare,
                                                             gpointer compare_data,
                                                             GDestroyNotify key_destroy_func,
                                                             GDestroyNotify value_destroy_func);
    void                gsk_tree_insert                     (GskTree *tree,
                                                             gpointer key,
                                                             gpointer value);
    void                gsk_tree_replace                    (GskTree *tree,
                                                             gpointer key,
                                                             gpointer value);
    gpointer            gsk_tree_lookup                     (GskTree *tree,
                                                             gpointer key);
    void                gsk_tree_remove                     (GskTree *tree,
                                                             gpointer key);
    guint               gsk_tree_n_nodes                    (GskTree *tree);
    GskTreeNode *       gsk_tree_node_first                 (GskTree *tree);
    GskTreeNode *       gsk_tree_node_last                  (GskTree *tree);
    GskTreeNode *       gsk_tree_node_find                  (GskTree *tree,
                                                             gpointer search_key);
    GskTreeNode *       gsk_tree_node_next                  (GskTree *tree,
                                                             GskTreeNode *node);
    GskTreeNode *       gsk_tree_node_prev                  (GskTree *tree,
                                                             GskTreeNode *node);
    gpointer            gsk_tree_node_peek_key              (GskTreeNode *node);
    gpointer            gsk_tree_node_peek_value            (GskTreeNode *node);
    gboolean            gsk_tree_node_is_removed            (GskTreeNode *node);
    void                gsk_tree_node_visit                 (GskTree *tree,
                                                             GskTreeNode *node);
    void                gsk_tree_node_unvisit               (GskTree *tree,
                                                             GskTreeNode *node);
    gboolean            gsk_tree_validate                   (GskTree *tree);

## Description

This tree provides an efficient map from any type of data which can be totally ordered to any type of data.

The primary interesting feature is that one can iterate the trees in a robust manner using the GskTreeNode, which takes the place of an iterator. In particular, when walking around the tree, any nodes which are being visited cannot be destroyed until their are no more visitors. Even though the nodes are destroyed, they will not be returned by `gsk_tree_lookup()` or `gsk_tree_node_find()`. But the node is in the tree, in the sense that `gsk_tree_node_next()` and `gsk_tree_node_prev()` still work correctly.

XXX: if walking a removed node, and a new node with the same key is added, should `gsk_tree_node_next()` or `gsk_tree_node_prev()` or both or neither return the new node???

## Details

### GskTreeNode

    typedef struct _GskTreeNode GskTreeNode;

An opaque type representing a node of the tree. You should not hold on to a GskTreeNode unless you "own" a visit count on the node.

### GskTree

    typedef struct _GskTree GskTree;

A map from keys to values implemented as a Red-Black tree.

### gsk_tree_new ()

    GskTree *           gsk_tree_new                        (GCompareFunc compare);

Create a new tree.

`compare` : | function to compare two keys and return -1, 0, or +1 to indicate their relative order. Every distinct key must compare to a nonzero value (ie. the ordering is total).
Returns : | the new tree.

### gsk_tree_ref ()

    GskTree *           gsk_tree_ref                        (GskTree *tree);

Increase the reference count on the tree.

`tree` : | tree to add a reference to.
Returns : | the `tree`, as a convenience; it leads to nice looking code.

### gsk_tree_unref ()

    void                gsk_tree_unref                      (GskTree *tree);

Decrease the reference count on the tree. Once its ref-count reached 0, it and all its nodes will be destroyed. So it may be a good idea to hold a reference to a tree you are visiting!

`tree` : | tree to release your reference to.

### gsk_tree_new_full ()

    GskTree *           gsk_tree_new_full                   (GCompareDataFunc compare,
                                                             gpointer compare_data,
                                                             GDestroyNotify key_destroy_func,
                                                             GDestroyNotify value_destroy_func);

Create a new tree.

`compare` : | function to compare two keys and return -1, 0, or +1 to indicate their relative order. Every distinct key must compare to a nonzero value (ie. the ordering is total).
`compare_data` : | data to pass as the third argument to `compare`.
`key_destroy_func` : | function to destroy a key when it is removed.
`value_destroy_func` : | function to destroy a value when it is removed.
Returns : | the new tree.

### gsk_tree_insert ()

    void                gsk_tree_insert                     (GskTree *tree,
                                                             gpointer key,
                                                             gpointer value);

Insert a new key/value pair into the tree.

If the key is currently in the tree, the new key is destroyed, and the old value is destroyed, and the old value is replaced with the new value in the tree. (This is for compatibility with g_hash_table_insert and g_tree_insert.)

See also `gsk_tree_replace()`.

`tree` : | tree to insert a new element into.
`key` : | key of the new element.
`value` : | value of the new element.

### gsk_tree_replace ()

    void                gsk_tree_replace                    (GskTree *tree,
                                                             gpointer key,
                                                             gpointer value);

Insert a new key/value pair into the tree.

If the key is currently in the tree, the old key and value are destroyed and replaced with this key.

`tree` : | tree to insert a new element into.
`key` : | key of the new element.
`value` : | value of the new element.

### gsk_tree_lookup ()

    gpointer            gsk_tree_lookup                     (GskTree *tree,
                                                             gpointer key);

Find the value of a node in the tree, given a key. Or NULL if the node cannot be found.

`tree` : | the tree to query.
`key` : | the key to look up.
Returns : | the value of a matching node, or NULL.

### gsk_tree_remove ()

    void                gsk_tree_remove                     (GskTree *tree,
                                                             gpointer key);

The element with the given key will be removed from the tree.

Note that if another iterator is visiting the node which is being deleted, then the key/value pair will not be destroyed until the last iterator has left the node. An iterator may determine whether the node it is visiting has been removed by calling `gsk_tree_node_is_removed()`.

`tree` : | the tree to remove an element from.
`key` : | the key of the element to remove.

### gsk_tree_n_nodes ()

    guint               gsk_tree_n_nodes                    (GskTree *tree);

Get the size of the tree, not including removed nodes, even if they are currently being visited.

`tree` : | the tree to query.
Returns : | the number of nodes in the tree.

### gsk_tree_node_first ()

    GskTreeNode *       gsk_tree_node_first                 (GskTree *tree);

Return the first node in the tree, and increment its visit count.

`tree` : | the tree to begin iterating.
Returns : | the first node in the tree, or NULL if the tree is empty.

### gsk_tree_node_last ()

    GskTreeNode *       gsk_tree_node_last                  (GskTree *tree);

Return the last node in the tree, and increment its visit count.

`tree` : | the tree to begin iterating.
Returns : | the last node in the tree, or NULL if the tree is empty.

### gsk_tree_node_find ()

    GskTreeNode *       gsk_tree_node_find                  (GskTree *tree,
                                                             gpointer search_key);

Start iterating at the given key, or return NULL if the node cannot be found.

`tree` : | the tree to query.
`search_key` : | the key to look up.
Returns : | the matching node, whose visit count has been incremented, or NULL.

### gsk_tree_node_next ()

    GskTreeNode *       gsk_tree_node_next                  (GskTree *tree,
                                                             GskTreeNode *node);

Return the next node in the tree after `node`, and increment its visit count, while decrementing the visit count of the current node.

Usually this is used to advance an iterator: node = gsk_tree_node_next(tree,node);

`tree` : | the tree to iterate through.
`node` : | the current node.
Returns : | the next node in the tree, or NULL if `node` is the last node.

### gsk_tree_node_prev ()

    GskTreeNode *       gsk_tree_node_prev                  (GskTree *tree,
                                                             GskTreeNode *node);

Return the previous node in the tree after `node`, and increment its visit count, while decrementing the visit count of the current node.

Usually this is used to advance an iterator backward: node = gsk_tree_node_prev(tree,node);

`tree` : | the tree to iterate through.
`node` : | the current node.
Returns : | the previous node in the tree, or NULL if `node` is the last node.

### gsk_tree_node_peek_key ()

    gpointer            gsk_tree_node_peek_key              (GskTreeNode *node);

Get the key of a node you are visiting. It may have been removed by `gsk_tree_remove()`, but it will not have been destroyed until the visit count has been reduced to 0.

`node` : | visited node to query.
Returns : | key of the current tree node.

### gsk_tree_node_peek_value ()

    gpointer            gsk_tree_node_peek_value            (GskTreeNode *node);

Get the value of a node you are visiting. It may have been removed by `gsk_tree_remove()`, but it will not have been destroyed until the visit count has been reduced to 0.

`node` : | visited node to query.
Returns : | value of the current tree node.

### gsk_tree_node_is_removed ()

    gboolean            gsk_tree_node_is_removed            (GskTreeNode *node);

Check to see if a node which is being visited has been removed from the tree.

(Note that if you are not visiting the node, then it should already have been freed, so it is only valid to call this on a node you are visiting.)

`node` : | a node to check.
Returns : | whether the node has been removed.

### gsk_tree_node_visit ()

    void                gsk_tree_node_visit                 (GskTree *tree,
                                                             GskTreeNode *node);

Increment the visit count for a node. A non-zero visit count prevents the node's key and value from being deleted, even after the node is "removed" from the tree.

The removed node may still be used to advance to "next" and "prev", however, you may iterate freely from a "removed" node, and you cannot get back to it.

`tree` : | the tree that `node` is iterating.
`node` : | the node in the tree that is being visited.

### gsk_tree_node_unvisit ()

    void                gsk_tree_node_unvisit               (GskTree *tree,
                                                             GskTreeNode *node);

Decrease the visit count on the node, indicating that you are done visiting it.

If the node has been removed and you are the last visitor, its key and value will be deleted at this point.

`tree` : | the tree that `node` is iterating.
`node` : | the node in the tree which you want to stop visiting.

### gsk_tree_validate ()

    gboolean            gsk_tree_validate                   (GskTree *tree);

Check the tree for integrity. This is only used for debugging.

`tree` : | the tree to check.
Returns : | whether the tree was valid. If it returns FALSE, then there is either a bug in the tree code, or the comparison function isn't transitive.