ucx: test/avl_tests.c@45810f5b7b84 (annotated)

test/avl_tests.c@45810f5b7b84 (annotated)

test/avl_tests.c

Mon, 18 May 2015 20:17:16 +0200

author: Olaf Wintermann <olaf.wintermann@gmail.com>
date: Mon, 18 May 2015 20:17:16 +0200
changeset 201: 45810f5b7b84
parent 200: e3aad99d2d80
child 203: 3d999ea3f780
permissions: -rw-r--r--

extended ucx_avl_remove tests

 /*
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
  *
  * Copyright 2015 Olaf Wintermann. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
  *
  *   1. Redistributions of source code must retain the above copyright
  *      notice, this list of conditions and the following disclaimer.
  *
  *   2. Redistributions in binary form must reproduce the above copyright
  *      notice, this list of conditions and the following disclaimer in the
  *      documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
 #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);
 }
 UCX_TEST(test_ucx_avl_remove) {
     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);
     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);
     void *val = ucx_avl_remove(tree1, 3);
     UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
     UCX_TEST_ASSERT(
             val == data3,
             "wrong return value for key: 1 (tree1)");
     UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == NULL, "value not removed (tree1)");
     UCX_TEST_ASSERT(
             ucx_avl_remove(tree1, 2) == data2,
             "wrong return value for key: 2 (tree1)");
     UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
     UCX_TEST_ASSERT(
             ucx_avl_remove(tree1, 1) == data1,
             "wrong return value for key: 1 (tree1)");
     UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
     UCX_TEST_ASSERT(tree1->root == NULL, "root not NULL (tree1)");
     for(int i=0;i<20;i++) {
         if(i==10) {
             ucx_avl_put(tree2, i, data3);
         } else if(i==15) {
             ucx_avl_put(tree2, i, data2);
         } else {
             ucx_avl_put(tree2, i, data1);
         }
     }
     UCX_TEST_ASSERT(
             ucx_avl_remove(tree2, 10) == data3,
             "wrong return value for key: 10 (tree2)");
     UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
     UCX_TEST_ASSERT(
             ucx_avl_remove(tree2, 15) == data2,
             "wrong return value for key: 15 (tree2)");
     UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
     for(int i=0;i<20;i++) {
         ucx_avl_remove(tree2, i);
         UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
     }
     for(int i=0;i<100000;i++) {
         ucx_avl_put(tree3, i, data1);
     }
     for(int i=100000-1;i>=0;i--) {
         ucx_avl_remove(tree3, i);
     }
     UCX_TEST_ASSERT(tree3->root == NULL, "root not NULL (tree3)");
     UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)");
     ucx_avl_put(tree4, 1, data1);
     ucx_avl_remove(tree4, 1);
     UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)");
     UCX_TEST_ASSERT(tree4->root == NULL, "root not NULL (tree4)");
     UCX_TEST_END
     ucx_avl_free(tree1);
     ucx_avl_free(tree2);
     ucx_avl_free(tree3);
     ucx_avl_free(tree4);
 }

Mercurial > hg > ucx / annotate

test/avl_tests.c@45810f5b7b84 (annotated)

test/avl_tests.c