# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1431967159 -7200
# Node ID 1b4cdafef2eb2e95ccb2c99af3cb905d63d7c7d0
# Parent  bec61f067ea07e4328c2ac94fc7af9d55448401e
added free() to AVL tree implementation + use UcxAllocator

diff -r bec61f067ea0 -r 1b4cdafef2eb ucx/avl.c
--- a/ucx/avl.c	Mon May 18 12:54:18 2015 +0200
+++ b/ucx/avl.c	Mon May 18 18:39:19 2015 +0200
@@ -107,7 +107,7 @@
 }
 
 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) {
-    UcxAVLTree *tree = malloc(sizeof(UcxAVLTree));
+    UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree));
     if (tree) {
         tree->allocator = allocator;
         tree->cmpfunc = cmpfunc;
@@ -118,6 +118,20 @@
     return tree;
 }
 
+static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) {
+    if (node) {
+        ucx_avl_free_node(al, node->left);
+        ucx_avl_free_node(al, node->right);
+        alfree(al, node);
+    }
+}
+
+void ucx_avl_free(UcxAVLTree *tree) {
+    UcxAllocator *al = tree->allocator;
+    ucx_avl_free_node(al, tree->root);
+    alfree(al, tree);
+}
+
 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
     UcxAVLNode *n = tree->root;
     int cmpresult;
@@ -143,7 +157,7 @@
         }
 
         if (cmpresult) {
-            UcxAVLNode *e = malloc(sizeof(UcxAVLNode));
+            UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode));
             e->key = key; e->value = value; e->height = 1;
             e->parent = e->left = e->right = NULL;
             ucx_avl_connect(tree, n, e, 0);
@@ -155,7 +169,7 @@
             return prevval;
         }
     } else {
-        tree->root = malloc(sizeof(UcxAVLNode));
+        tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode));
         tree->root->key = key; tree->root->value = value;
         tree->root->height = 1;
         tree->root->parent = tree->root->left = tree->root->right = NULL;
@@ -181,14 +195,15 @@
             ucx_avl_connect(tree, s->parent, s->right, s->key);
             n->key = s->key; n->value = s->value;
             p = s->parent;
+            alfree(tree->allocator, s);
         } else {
             if (p) {
                 ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key);
             } else {
                 tree->root = n->right ? n->right : n->left;
             }
+            alfree(tree->allocator, n);
         }
-        // TODO: free the correct memory
 
         if (p) {
             ucx_avl_balance(tree, p);
diff -r bec61f067ea0 -r 1b4cdafef2eb ucx/avl.h
--- a/ucx/avl.h	Mon May 18 12:54:18 2015 +0200
+++ b/ucx/avl.h	Mon May 18 18:39:19 2015 +0200
@@ -134,6 +134,12 @@
 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator);
 
 /**
+ * Destroys an UcxAVLTree.
+ * @param tree the tree to destroy
+ */
+void ucx_avl_free(UcxAVLTree *tree);
+
+/**
  * Macro for initializing a new UcxAVLTree with the default allocator and a
  * ucx_ptrcmp() compare function.
  *