Mercurial > hg > ucx / file diff

--- a/test/avl_tests.c	Mon May 18 18:42:45 2015 +0200
+++ b/test/avl_tests.c	Mon May 18 19:12:32 2015 +0200
@@ -28,3 +28,117 @@
 
 #include "avl_tests.h"
 
+#include "ucx/utils.h"
+
+static int node_height(UcxAVLNode *node) {
+    if(!node) {
+        return 0;
+    }
+    
+    int left = 0;
+    int right = 0;
+    if(node->left) {
+        left = node_height(node->left);
+    }
+    if(node->right) {
+        right = node_height(node->right);
+    }
+    
+    return left > right ? left+1 : right+1;
+}
+
+static int check_tree(UcxAVLNode *node) {
+    if(!node) {
+        return 1;
+    }
+    
+    int left_height = node_height(node->left);
+    int right_height = node_height(node->right);
+    int bf = -left_height + right_height;
+    if(bf < -1 || bf > 1) {
+        return 0;
+    }
+    int height = left_height > right_height ? left_height : right_height;
+    height++;
+    if(height != node->height) {
+        return 0;
+    }
+    
+    if(!check_tree(node->left)) {
+        return 0;
+    }
+    if(!check_tree(node->right)) {
+        return 0;
+    }
+    
+    return 1;
+}
+
+UCX_TEST(test_ucx_avl_put) {
+    UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp);
+    UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp);
+    UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp);
+    UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp);
+    UcxAVLTree *tree5 = ucx_avl_new(ucx_ptrcmp);
+    
+    char *data1 = (char*)"data1";
+    char *data2 = (char*)"data2";
+    char *data3 = (char*)"data3";
+    
+    UCX_TEST_BEGIN
+    
+    ucx_avl_put(tree1, 2, (char*)data2);
+    ucx_avl_put(tree1, 1, (char*)data1);
+    ucx_avl_put(tree1, 3, (char*)data3);
+    
+    UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
+    UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)");
+    UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)");
+    UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)");
+    
+    for(int i=0;i<100000;i++) {
+        ucx_avl_put(tree2, i, data1);
+    }
+    UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
+    
+    for(int i=100000;i>=0;i--) {
+        ucx_avl_put(tree3, i, data1);
+    }
+    UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)");
+    
+    for(int i=0;i<100;i++) {
+        ucx_avl_put(tree4, i, data1);
+    }
+    for(int i=400;i<500;i++) {
+        ucx_avl_put(tree4, i, data2);
+    }
+    for(int i=399;i>200;i--) {
+        ucx_avl_put(tree4, i, data3);
+    }
+    for(int i=800;i<1000;i++) {
+        ucx_avl_put(tree4, i, data1);
+    }
+    UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)");
+    UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0");
+    UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1");
+    UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99");
+    UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400");
+    UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410");
+    UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350");
+    UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900");
+    
+    int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4};
+    int len = sizeof(values) / sizeof(int);
+    for(int i=0;i<len;i++) {
+        ucx_avl_put(tree5, values[i], NULL);
+    }
+    UCX_TEST_ASSERT(check_tree(tree5->root), "check_tree failed (tree5)");
+            
+    UCX_TEST_END
+    
+    ucx_avl_free(tree1);
+    ucx_avl_free(tree2);
+    ucx_avl_free(tree3);
+    ucx_avl_free(tree4);
+    ucx_avl_free(tree5);
+}