Mercurial > hg > ucx / changeset

--- a/ucx/avl.h	Sun May 17 17:31:32 2015 +0200
+++ b/ucx/avl.h	Sun May 17 17:59:07 2015 +0200
@@ -42,10 +42,95 @@
 #ifndef UCX_AVL_H
 #define	UCX_AVL_H
 
+#include "ucx.h"
+
+
 #ifdef	__cplusplus
 extern "C" {
 #endif
 
+/**
+ * UCX AVL Node type.
+ * 
+ * @see UcxAVLNode
+ */
+typedef struct UcxAVLNode UcxAVLNode;
+
+/**
+ * UCX AVL Node.
+ */
+struct UcxAVLNode {
+    /**
+     * The key for this node.
+     */
+    void *key;
+    /**
+     * Data contained by this node.
+     */
+    void *value;
+    /**
+     * The height of this (sub)-tree.
+     */
+    size_t height;
+    /**
+     * Parent node.
+     */
+    UcxAVLNode *parent;
+    /**
+     * Root node of left subtree.
+     */
+    UcxAVLNode *left;
+    /**
+     * Root node of right subtree.
+     */
+    UcxAVLNode *right;
+};
+
+/**
+ * UCX AVL Tree.
+ */
+typedef struct {
+    /**
+     * Root node of the tree.
+     */
+    UcxAVLNode *root;
+    /**
+     * Compare function that shall be used to compare the UcxAVLNode keys.
+     * @see UcxAVLNode.key
+     */
+    cmp_func cmpfunc;
+    /**
+     * Custom user data.
+     * This data will also be provided to the cmpfunc.
+     */
+    void *userdata;
+} UcxAVLTree;
+
+/**
+ * Gets the value from the tree, that is associated with the specified key.
+ * @param tree the UcxAVLTree
+ * @param key the key
+ * @return the value (or <code>NULL</code>, if the key is not present)
+ */
+void *ucx_avl_get(UcxAVLTree *tree, void *key);
+
+/**
+ * Puts a key/value pair into the tree.
+ * @param tree the UcxAVLTree
+ * @param key the key
+ * @param value the new value
+ * @return the replaced value (or <code>NULL</code>, if the key is new to the
+ * tree)
+ */
+void* ucx_avl_put(UcxAVLTree *tree, void *key, void *value);
+
+/**
+ * Removes an element from the AVL tree.
+ * @param tree the UcxAVLTree
+ * @param key the key
+ * @return the removed value (or <code>NULL</code>, if the key was not present)
+ */
+void* ucx_avl_remove(UcxAVLTree *tree, void *key);