Mercurial > hg > ucx / changeset

     1.1 --- a/ucx/avl.h	Sun May 17 17:31:32 2015 +0200
     1.2 +++ b/ucx/avl.h	Sun May 17 17:59:07 2015 +0200
     1.3 @@ -42,10 +42,95 @@
     1.4  #ifndef UCX_AVL_H
     1.5  #define	UCX_AVL_H
     1.6  
     1.7 +#include "ucx.h"
     1.8 +
     1.9 +
    1.10  #ifdef	__cplusplus
    1.11  extern "C" {
    1.12  #endif
    1.13  
    1.14 +/**
    1.15 + * UCX AVL Node type.
    1.16 + * 
    1.17 + * @see UcxAVLNode
    1.18 + */
    1.19 +typedef struct UcxAVLNode UcxAVLNode;
    1.20 +
    1.21 +/**
    1.22 + * UCX AVL Node.
    1.23 + */
    1.24 +struct UcxAVLNode {
    1.25 +    /**
    1.26 +     * The key for this node.
    1.27 +     */
    1.28 +    void *key;
    1.29 +    /**
    1.30 +     * Data contained by this node.
    1.31 +     */
    1.32 +    void *value;
    1.33 +    /**
    1.34 +     * The height of this (sub)-tree.
    1.35 +     */
    1.36 +    size_t height;
    1.37 +    /**
    1.38 +     * Parent node.
    1.39 +     */
    1.40 +    UcxAVLNode *parent;
    1.41 +    /**
    1.42 +     * Root node of left subtree.
    1.43 +     */
    1.44 +    UcxAVLNode *left;
    1.45 +    /**
    1.46 +     * Root node of right subtree.
    1.47 +     */
    1.48 +    UcxAVLNode *right;
    1.49 +};
    1.50 +
    1.51 +/**
    1.52 + * UCX AVL Tree.
    1.53 + */
    1.54 +typedef struct {
    1.55 +    /**
    1.56 +     * Root node of the tree.
    1.57 +     */
    1.58 +    UcxAVLNode *root;
    1.59 +    /**
    1.60 +     * Compare function that shall be used to compare the UcxAVLNode keys.
    1.61 +     * @see UcxAVLNode.key
    1.62 +     */
    1.63 +    cmp_func cmpfunc;
    1.64 +    /**
    1.65 +     * Custom user data.
    1.66 +     * This data will also be provided to the cmpfunc.
    1.67 +     */
    1.68 +    void *userdata;
    1.69 +} UcxAVLTree;
    1.70 +
    1.71 +/**
    1.72 + * Gets the value from the tree, that is associated with the specified key.
    1.73 + * @param tree the UcxAVLTree
    1.74 + * @param key the key
    1.75 + * @return the value (or <code>NULL</code>, if the key is not present)
    1.76 + */
    1.77 +void *ucx_avl_get(UcxAVLTree *tree, void *key);
    1.78 +
    1.79 +/**
    1.80 + * Puts a key/value pair into the tree.
    1.81 + * @param tree the UcxAVLTree
    1.82 + * @param key the key
    1.83 + * @param value the new value
    1.84 + * @return the replaced value (or <code>NULL</code>, if the key is new to the
    1.85 + * tree)
    1.86 + */
    1.87 +void* ucx_avl_put(UcxAVLTree *tree, void *key, void *value);
    1.88 +
    1.89 +/**
    1.90 + * Removes an element from the AVL tree.
    1.91 + * @param tree the UcxAVLTree
    1.92 + * @param key the key
    1.93 + * @return the removed value (or <code>NULL</code>, if the key was not present)
    1.94 + */
    1.95 +void* ucx_avl_remove(UcxAVLTree *tree, void *key);
    1.96  
    1.97  
    1.98