ucx: test/avl_tests.c@b0f4fb043b47

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2015 Olaf Wintermann. All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #include "avl_tests.h"

    31 #include "ucx/utils.h"

    33 static int node_height(UcxAVLNode *node) {

    34     if(!node) {

    35         return 0;

    36     }

    38     int left = 0;

    39     int right = 0;

    40     if(node->left) {

    41         left = node_height(node->left);

    42     }

    43     if(node->right) {

    44         right = node_height(node->right);

    45     }

    47     return left > right ? left+1 : right+1;

    48 }

    50 static int check_tree(UcxAVLNode *node) {

    51     if(!node) {

    52         return 1;

    53     }

    55     int left_height = node_height(node->left);

    56     int right_height = node_height(node->right);

    57     int bf = -left_height + right_height;

    58     if(bf < -1 || bf > 1) {

    59         return 0;

    60     }

    61     int height = left_height > right_height ? left_height : right_height;

    62     height++;

    63     if(height != node->height) {

    64         return 0;

    65     }

    67     if(!check_tree(node->left)) {

    68         return 0;

    69     }

    70     if(!check_tree(node->right)) {

    71         return 0;

    72     }

    74     return 1;

    75 }

    77 UCX_TEST(test_ucx_avl_put) {

    78     UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp);

    79     UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp);

    80     UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp);

    81     UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp);

    82     UcxAVLTree *tree5 = ucx_avl_new(ucx_ptrcmp);

    84     char *data1 = (char*)"data1";

    85     char *data2 = (char*)"data2";

    86     char *data3 = (char*)"data3";

    88     UCX_TEST_BEGIN

    90     ucx_avl_put(tree1, 2, (char*)data2);

    91     ucx_avl_put(tree1, 1, (char*)data1);

    92     ucx_avl_put(tree1, 3, (char*)data3);

    94     UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");

    95     UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)");

    96     UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)");

    97     UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)");

    99     for(int i=0;i<100000;i++) {

   100         ucx_avl_put(tree2, i, data1);

   101     }

   102     UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");

   104     for(int i=100000;i>=0;i--) {

   105         ucx_avl_put(tree3, i, data1);

   106     }

   107     UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)");

   109     for(int i=0;i<100;i++) {

   110         ucx_avl_put(tree4, i, data1);

   111     }

   112     for(int i=400;i<500;i++) {

   113         ucx_avl_put(tree4, i, data2);

   114     }

   115     for(int i=399;i>200;i--) {

   116         ucx_avl_put(tree4, i, data3);

   117     }

   118     for(int i=800;i<1000;i++) {

   119         ucx_avl_put(tree4, i, data1);

   120     }

   121     UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)");

   122     UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0");

   123     UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1");

   124     UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99");

   125     UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400");

   126     UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410");

   127     UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350");

   128     UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900");

   130     int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4};

   131     int len = sizeof(values) / sizeof(int);

   132     for(int i=0;i<len;i++) {

   133         ucx_avl_put(tree5, values[i], NULL);

   134     }

   135     UCX_TEST_ASSERT(check_tree(tree5->root), "check_tree failed (tree5)");

   137     UCX_TEST_END

   139     ucx_avl_free(tree1);

   140     ucx_avl_free(tree2);

   141     ucx_avl_free(tree3);

   142     ucx_avl_free(tree4);

   143     ucx_avl_free(tree5);

   144 }

Mercurial > hg > ucx / file revision