Mercurial > hg > ucx / changeset

     1.1 --- a/test/avl_tests.c	Mon May 18 18:42:45 2015 +0200
     1.2 +++ b/test/avl_tests.c	Mon May 18 19:12:32 2015 +0200
     1.3 @@ -28,3 +28,117 @@
     1.4  
     1.5  #include "avl_tests.h"
     1.6  
     1.7 +#include "ucx/utils.h"
     1.8 +
     1.9 +static int node_height(UcxAVLNode *node) {
    1.10 +    if(!node) {
    1.11 +        return 0;
    1.12 +    }
    1.13 +    
    1.14 +    int left = 0;
    1.15 +    int right = 0;
    1.16 +    if(node->left) {
    1.17 +        left = node_height(node->left);
    1.18 +    }
    1.19 +    if(node->right) {
    1.20 +        right = node_height(node->right);
    1.21 +    }
    1.22 +    
    1.23 +    return left > right ? left+1 : right+1;
    1.24 +}
    1.25 +
    1.26 +static int check_tree(UcxAVLNode *node) {
    1.27 +    if(!node) {
    1.28 +        return 1;
    1.29 +    }
    1.30 +    
    1.31 +    int left_height = node_height(node->left);
    1.32 +    int right_height = node_height(node->right);
    1.33 +    int bf = -left_height + right_height;
    1.34 +    if(bf < -1 || bf > 1) {
    1.35 +        return 0;
    1.36 +    }
    1.37 +    int height = left_height > right_height ? left_height : right_height;
    1.38 +    height++;
    1.39 +    if(height != node->height) {
    1.40 +        return 0;
    1.41 +    }
    1.42 +    
    1.43 +    if(!check_tree(node->left)) {
    1.44 +        return 0;
    1.45 +    }
    1.46 +    if(!check_tree(node->right)) {
    1.47 +        return 0;
    1.48 +    }
    1.49 +    
    1.50 +    return 1;
    1.51 +}
    1.52 +
    1.53 +UCX_TEST(test_ucx_avl_put) {
    1.54 +    UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp);
    1.55 +    UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp);
    1.56 +    UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp);
    1.57 +    UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp);
    1.58 +    UcxAVLTree *tree5 = ucx_avl_new(ucx_ptrcmp);
    1.59 +    
    1.60 +    char *data1 = (char*)"data1";
    1.61 +    char *data2 = (char*)"data2";
    1.62 +    char *data3 = (char*)"data3";
    1.63 +    
    1.64 +    UCX_TEST_BEGIN
    1.65 +    
    1.66 +    ucx_avl_put(tree1, 2, (char*)data2);
    1.67 +    ucx_avl_put(tree1, 1, (char*)data1);
    1.68 +    ucx_avl_put(tree1, 3, (char*)data3);
    1.69 +    
    1.70 +    UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
    1.71 +    UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)");
    1.72 +    UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)");
    1.73 +    UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)");
    1.74 +    
    1.75 +    for(int i=0;i<100000;i++) {
    1.76 +        ucx_avl_put(tree2, i, data1);
    1.77 +    }
    1.78 +    UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
    1.79 +    
    1.80 +    for(int i=100000;i>=0;i--) {
    1.81 +        ucx_avl_put(tree3, i, data1);
    1.82 +    }
    1.83 +    UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)");
    1.84 +    
    1.85 +    for(int i=0;i<100;i++) {
    1.86 +        ucx_avl_put(tree4, i, data1);
    1.87 +    }
    1.88 +    for(int i=400;i<500;i++) {
    1.89 +        ucx_avl_put(tree4, i, data2);
    1.90 +    }
    1.91 +    for(int i=399;i>200;i--) {
    1.92 +        ucx_avl_put(tree4, i, data3);
    1.93 +    }
    1.94 +    for(int i=800;i<1000;i++) {
    1.95 +        ucx_avl_put(tree4, i, data1);
    1.96 +    }
    1.97 +    UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)");
    1.98 +    UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0");
    1.99 +    UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1");
   1.100 +    UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99");
   1.101 +    UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400");
   1.102 +    UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410");
   1.103 +    UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350");
   1.104 +    UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900");
   1.105 +    
   1.106 +    int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4};
   1.107 +    int len = sizeof(values) / sizeof(int);
   1.108 +    for(int i=0;i<len;i++) {
   1.109 +        ucx_avl_put(tree5, values[i], NULL);
   1.110 +    }
   1.111 +    UCX_TEST_ASSERT(check_tree(tree5->root), "check_tree failed (tree5)");
   1.112 +            
   1.113 +    UCX_TEST_END
   1.114 +    
   1.115 +    ucx_avl_free(tree1);
   1.116 +    ucx_avl_free(tree2);
   1.117 +    ucx_avl_free(tree3);
   1.118 +    ucx_avl_free(tree4);
   1.119 +    ucx_avl_free(tree5);
   1.120 +}

     2.1 --- a/test/avl_tests.h	Mon May 18 18:42:45 2015 +0200
     2.2 +++ b/test/avl_tests.h	Mon May 18 19:12:32 2015 +0200
     2.3 @@ -36,7 +36,7 @@
     2.4  extern "C" {
     2.5  #endif
     2.6  
     2.7 -
     2.8 +UCX_TEST(test_ucx_avl_put);
     2.9  
    2.10  #ifdef	__cplusplus
    2.11  }

     3.1 --- a/test/main.c	Mon May 18 18:42:45 2015 +0200
     3.2 +++ b/test/main.c	Mon May 18 19:12:32 2015 +0200
     3.3 @@ -43,6 +43,7 @@
     3.4  #include "prop_tests.h"
     3.5  #include "buffer_tests.h"
     3.6  #include "utils_tests.h"
     3.7 +#include "avl_tests.h"
     3.8  
     3.9  UCX_EXTERN UCX_TEST(testTestSuitePositive) {
    3.10      UCX_TEST_BEGIN
    3.11 @@ -217,6 +218,9 @@
    3.12          ucx_test_register(suite, test_ucx_fprintf);
    3.13          ucx_test_register(suite, test_ucx_asprintf);
    3.14          ucx_test_register(suite, test_ucx_stream_copy);
    3.15 +        
    3.16 +        /* AVL Tests */
    3.17 +        ucx_test_register(suite, test_ucx_avl_put);
    3.18  
    3.19          ucx_test_run(suite, stdout);
    3.20          fflush(stdout);

     4.1 --- a/test/string_tests.c	Mon May 18 18:42:45 2015 +0200
     4.2 +++ b/test/string_tests.c	Mon May 18 19:12:32 2015 +0200
     4.3 @@ -31,7 +31,7 @@
     4.4  UCX_TEST(test_sstr) {
     4.5      sstr_t s1 = sstr((char*)"1234");
     4.6      sstr_t s2 = sstrn((char*)"ab", 2);
     4.7 -    
     4.8 +     
     4.9      UCX_TEST_BEGIN
    4.10      
    4.11      UCX_TEST_ASSERT(s1.length == 4, "s1 length must be 4");