Subversion Repositories HelenOS

/*

 * Copyright (c) 2007 Vojtech Mencl

 * All rights reserved.

 *

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

 * modification, are permitted provided that the following conditions

 * are met:

 *

 * - Redistributions of source code must retain the above copyright

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

 * - 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.

 * - The name of the author may not be used to endorse or promote products

 *   derived from this software without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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 <test.h>

#include <print.h>

#include <adt/extavl.h>

#include <debug.h>

#include <panic.h>

#define NODE_COUNT 100

/*

 * wrapper structure with a pointer to extended avl tree root

 */

static extavltree_t exttree;

/*

 * extavltree nodes in array for faster allocating

 */

static extavltree_node_t extavltree_nodes[NODE_COUNT];

/*

 * head of free nodes' list:

 */

static extavltree_node_t *first_free_node = NULL;

static int exttree_test_height(extavltree_node_t *node,bool timeout);

static extavltree_node_t *exttree_test_parents(extavltree_node_t *node);

static void print_exttree_structure_flat (extavltree_node_t *node, int level);

static bool exttree_test_link(int node_count);

static void print_exttree_link(int node_count);

static extavltree_node_t *alloc_extavltree_node(void);

//vraci hloubku stromu

static int exttree_test_height(extavltree_node_t *node,bool timeout)

{

    int h1, h2;

    if (!node) return -1;

    h1 = exttree_test_height(node->lft,timeout) + 1;

    if (!timeout && node->lft_height != h1) {

        printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node);

    }

    h2 = exttree_test_height(node->rgt,0) + 1;

    if (node->rgt_height != h2) {

        printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node);

    }

    if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) {

        printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node);

    }

    return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height);

}

/** Tests par atribute of every tree node

 *

 */

static extavltree_node_t *exttree_test_parents(extavltree_node_t *node)

{

    extavltree_node_t *tmp;

    if (!node) return NULL;

    if (node->lft) {

        tmp = exttree_test_parents(node->lft);

        if (tmp != node) {

            printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft);

        }

    }

    if (node->rgt) {

        tmp = exttree_test_parents(node->rgt);

        if (tmp != node) {

            printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt);

        }

    }

    return node->par;

}

/** Checks list of nodes

 *

 */

static bool exttree_test_link(int node_count)

{

    extavltree_node_t *node;

    int i;

    bool test_link = true;

    for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) {

        if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {

            printf("\nList is not sorted (forward direction) at key: %d\n",node->key);

            test_link = false;

        }

    }

    if (node_count && i != node_count) {

        printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);

        test_link = false;

    }

    for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) {

        if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {

            printf("\nList is not sorted (backward direction) at key: %d\n",node->key);

            test_link = false;

        }

    }

    if (node_count && i != node_count) {

        printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);

        test_link = false;

    }

    return test_link;

}

/** Prints the structure of node, which is level levels from the top of the tree.

 *

 */

static void print_exttree_structure_flat (extavltree_node_t *node, int level)

{

    extavltree_node_t *tmp;

    int i;

    if (level > 16)

    {

        printf ("[...]");

        return;

    }

    if (node == NULL)

        return;

    for (tmp = node,i = 0; tmp->key == node->key; tmp = tmp->next,i++)

        ;

    printf ("%d[%d,%d,(%d)]", node->key,node->lft_height,node->rgt_height,i);

    if (node->lft != NULL || node->rgt != NULL)

    {

        printf("(");

        print_exttree_structure_flat (node->lft, level + 1);

        if (node->rgt != NULL)

        {

            printf(",");

            print_exttree_structure_flat (node->rgt, level + 1);

        }

        printf(")");

    }

}

/** Prints list of nodes

 *

 */

static void print_exttree_link(int node_count)

{

    extavltree_node_t *node;

    printf("\n");

    for (node = exttree.head.next; node != &(exttree.head); node = node->next) {

        printf(" %d,",node->key);

    }

    for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {

        printf(" %d,",node->key);

    }

}

//****************************************************************

static void alloc_extavltree_node_prepare(void)

{

    int i;

    for (i = 0; i < NODE_COUNT - 1; i++) {

        extavltree_nodes[i].next = &(extavltree_nodes[i+1]);

    }

    /*

     * Node keys which will be used for insertion. Up to NODE_COUNT size of array.

     */

    // First tree node and same key

    extavltree_nodes[0].key = 60;

    extavltree_nodes[1].key = 60;

    extavltree_nodes[2].key = 60;

    //LL rotation

    extavltree_nodes[3].key = 50;

    extavltree_nodes[4].key = 40;

    extavltree_nodes[5].key = 30;

    //LR rotation

    extavltree_nodes[6].key = 20;

    extavltree_nodes[7].key = 20;

    extavltree_nodes[8].key = 25;

    extavltree_nodes[9].key = 25;

    //LL rotation in lower floor

    extavltree_nodes[10].key = 35;

    //RR rotation

    extavltree_nodes[11].key = 70;

    extavltree_nodes[12].key = 80;

    //RL rotation

    extavltree_nodes[13].key = 90;

    extavltree_nodes[14].key = 85;

    extavltree_nodes[15].key = 100;

    extavltree_nodes[16].key = 200;

    extavltree_nodes[17].key = 300;

    extavltree_nodes[18].key = 400;

    extavltree_nodes[19].key = 500;

    extavltree_nodes[20].key = 600;

    for (i = 21; i < NODE_COUNT; i++)

        extavltree_nodes[i].key = i * 3;

    extavltree_nodes[i].next = NULL;

    first_free_node = &(extavltree_nodes[0]);

}

static extavltree_node_t *alloc_extavltree_node(void)

{

    extavltree_node_t *node;

    node = first_free_node;

    first_free_node = first_free_node->next;

    return node;

}

//****************************************************************

static void test_exttree_insert(extavltree_t *tree, unsigned int node_count, int quiet)

{

    unsigned int i;

    extavltree_node_t *newnode;

    /*

     * Initialize tree before using.

     */

    extavltree_create(tree);

    if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);

    for (i = 0; i < node_count; i++) {

        newnode = alloc_extavltree_node();

        //if (!quiet) printf("[[[%d]]]\n",newnode->key);

        extavltree_insert(tree, newnode);

        if (!quiet) {

            if (!exttree_test_link(i+1)) {

                print_exttree_link(i+1);

                printf("\n");

            }

            exttree_test_parents(tree->root);

            exttree_test_height(tree->root,1);

        }

    }

    if (!quiet) printf("Inserting was finished\n");

}

/*

static extavltree_node_t *exttree_random_delete_node(extavltree_t *tree, int node_count, int r, bool quiet)

{

    extavltree_node_t *delnode;

    int i;

    for (i = 0,delnode = tree->head.next; i < (r-1); i++)

        delnode = delnode->next;

    if (delnode == &tree->head) {

        if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);

        return NULL;

    }

    extavltree_delete(tree, delnode);

    return delnode;

}

*/

static void test_exttree_delete(extavltree_t *tree, int node_count, int node_position, bool quiet)

{

    extavltree_node_t *delnode;

    unsigned int i;

    //aktualni pocet tiku:

    if (!quiet) printf("Deleting tree...\n");

    switch(node_position) {

        case 0: //mazani vzdy korene

            if (!quiet) printf("\n\nDelete root nodes\n");

            i = node_count;

            while(tree->root != NULL) {

                delnode = tree->root;

                extavltree_delete(tree,delnode);

                if (!quiet) {

                    if (!exttree_test_link(i)) {

                        print_exttree_link(i);

                        printf("\n");

                    }

                    exttree_test_parents(tree->root);

                    exttree_test_height(tree->root,1);

                }

                i--;

            }

            break;

        case 1:

            if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");

            for (i = 0; i < node_count; i++) {

                extavltree_delete(tree,&(extavltree_nodes[i]));

                if (!quiet) {

                    if (!exttree_test_link(i+1)) {

                        print_exttree_link(i+1);

                        printf("\n");

                    }

                    exttree_test_parents(tree->root);

                    exttree_test_height(tree->root,1);

                }

            }

            break; 

    }

    if (!quiet) printf("Deletion was finished\n");

}

static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)

{

    int i = node_count;

    if (!quiet) printf("Timeout tree ...\n");

    while(tree->head.next != &(tree->head)) {

        extavltree_delete_min(tree);

        if (!quiet) {

            if (!exttree_test_link(i)) {

                print_exttree_link(i);

                printf("\n");

            }

            exttree_test_parents(tree->root);

            exttree_test_height(tree->root,1);

        }

        i--;

    }

    if (!quiet && (i != 0)) printf("Bad node count. Some nodes have been lost!");

    if (!quiet) printf("Timeout tree finished\n");

}

/*

void timeout_exttree_run(extavltree_t *tree, int operation_count, int verbal)

{

    int i;

    extavltree_node_t *node;

    int r;

    int count;

    //inicializace stromu:

    extavltree_create(tree);

    for(i = 0, count = 0; i < operation_count; i++) {

        if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {

            if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne

                node = exttree_random_delete_node(tree,(r % tree->count));

                //printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);

                node->next = first_free_node;

                first_free_node = node;

            } else {

                node = tree->head.next;

                extavltree_delete_min(tree);

                //printf("TIMEOUT key: %d, address: %p\n",node->key,node);

                node->next = first_free_node;

                first_free_node = node;

            }

            } else {

                    node = alloc_extavltree_node_random();

            //printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);

            extavltree_insert(tree, node);

            }

        //test_exttree_height(tree->root,1);

        //exttree_test_parents(tree->root);    

        //print_exttree_link(tree->count);

        //print_exttree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');

    }

}

*/

char * test_extavltree1(bool quiet)

{

    alloc_extavltree_node_prepare();

    test_exttree_insert(&exttree, NODE_COUNT, quiet);

    test_exttree_delete(&exttree, NODE_COUNT, 0, quiet);

    alloc_extavltree_node_prepare();

    test_exttree_insert(&exttree, NODE_COUNT, quiet);

    test_exttree_delete(&exttree, NODE_COUNT, 1, quiet);

    alloc_extavltree_node_prepare();

    test_exttree_insert(&exttree, NODE_COUNT, quiet);

    timeout_exttree(&exttree, NODE_COUNT, quiet);

    return NULL;

}