source: mainline/kernel/test/avltree/avltree1.c@ 990c70e

/*
 * 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/avl.h>
#include <debug.h>
#include <arch/types.h>

#define NODE_COUNT 100

static avltree_t avltree;

/*
 * avl tree nodes in array for faster allocation
 */
static avltree_node_t avltree_nodes[NODE_COUNT];

/*
 * head of free nodes' list:
 */
static avltree_node_t *first_free_node = NULL;

static int test_tree_balance(avltree_node_t *node);
static avltree_node_t *test_tree_parents(avltree_node_t *node);
static void print_tree_structure_flat (avltree_node_t *node, int level)
    __attribute__ ((used));
static avltree_node_t *alloc_avltree_node(void);

static avltree_node_t *test_tree_parents(avltree_node_t *node)
{
        avltree_node_t *tmp;
        
        if (!node)
                return NULL;
        
        if (node->lft) {
                tmp = test_tree_parents(node->lft);
                if (tmp != node) {
                        TPRINTF("Bad parent pointer key: %" PRIu64
                            ", address: %p\n", tmp->key, node->lft);
                }
        }
        if (node->rgt) {
                tmp = test_tree_parents(node->rgt);
                if (tmp != node) {
                        TPRINTF("Bad parent pointer key: %" PRIu64
                            ", address: %p\n",
                            tmp->key,node->rgt);
                }
        }
        return node->par;
}

int test_tree_balance(avltree_node_t *node)
{
        int h1, h2, diff;
        
        if (!node)
                return 0;
        
        h1 = test_tree_balance(node->lft);
        h2 = test_tree_balance(node->rgt);
        diff = h2 - h1;
        
        if ((diff != node->balance) || ((diff != -1) && (diff != 0) && (diff != 1)))
                TPRINTF("Bad balance\n");
        
        return ((h1 > h2) ? (h1 + 1) : (h2 + 1));
}

/**
 * Prints the structure of the node, which is level levels from the top of the
 * tree.
 */
static void print_tree_structure_flat(avltree_node_t *node, int level)
{
        /*
         * You can set the maximum level as high as you like.
         * Most of the time, you'll want to debug code using small trees,
         * so that a large level indicates a loop, which is a bug.
         */
        if (level > 16) {
                TPRINTF("[...]");
                return;
        }
        
        if (node == NULL)
                return;
        
        TPRINTF("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance);
        if (node->lft != NULL || node->rgt != NULL) {
                TPRINTF("(");
                
                print_tree_structure_flat(node->lft, level + 1);
                if (node->rgt != NULL) {
                        TPRINTF(",");
                        print_tree_structure_flat(node->rgt, level + 1);
                }
                
                TPRINTF(")");
        }
}

static void alloc_avltree_node_prepare(void)
{
        int i;
        
        for (i = 0; i < NODE_COUNT - 1; i++)
                avltree_nodes[i].par = &avltree_nodes[i + 1];
        
        avltree_nodes[i].par = NULL;
        
        /*
         * Node keys which will be used for insertion. Up to NODE_COUNT size of
         * array.
         */
        
        /* First tree node and same key */
        avltree_nodes[0].key = 60;
        avltree_nodes[1].key = 60;
        avltree_nodes[2].key = 60;
        
        /* LL rotation */
        avltree_nodes[3].key = 50;
        avltree_nodes[4].key = 40;
        avltree_nodes[5].key = 30;
        
        /* LR rotation */
        avltree_nodes[6].key = 20;
        avltree_nodes[7].key = 20;
        avltree_nodes[8].key = 25;
        avltree_nodes[9].key = 25;
        
        /* LL rotation in lower floor */
        avltree_nodes[10].key = 35;
        
        /* RR rotation */
        avltree_nodes[11].key = 70;
        avltree_nodes[12].key = 80;
        
        /* RL rotation */
        avltree_nodes[13].key = 90;
        avltree_nodes[14].key = 85;
        
        /* Insert 0 key */
        avltree_nodes[15].key = 0;
        avltree_nodes[16].key = 0;
        
        /* Insert reverse */
        avltree_nodes[17].key = 600;
        avltree_nodes[18].key = 500;
        avltree_nodes[19].key = 400;
        avltree_nodes[20].key = 300;
        
        for (i = 21; i < NODE_COUNT; i++)
                avltree_nodes[i].key = i * 3;
        
        first_free_node = &avltree_nodes[0];
}

static avltree_node_t *alloc_avltree_node(void)
{
        avltree_node_t *node;
        
        node = first_free_node;
        first_free_node = first_free_node->par;
        
        return node;
}

static void test_tree_insert(avltree_t *tree, size_t node_count)
{
        unsigned int i;
        avltree_node_t *newnode;
        
        avltree_create(tree);
        
        TPRINTF("Inserting %" PRIs " nodes...", node_count);
        
        for (i = 0; i < node_count; i++) {
                newnode = alloc_avltree_node();
                
                avltree_insert(tree, newnode);
                test_tree_parents(tree->root);
                test_tree_balance(tree->root);
        }
        
        TPRINTF("done.\n");
}

static void test_tree_delete(avltree_t *tree, size_t node_count,
    int node_position)
{
        avltree_node_t *delnode;
        unsigned int i;
        
        switch (node_position) {
        case 0:
                TPRINTF("Deleting root nodes...");
                
                while (tree->root != NULL) {
                        delnode = tree->root;
                        avltree_delete(tree, delnode);
                        test_tree_parents(tree->root);
                        test_tree_balance(tree->root);
                }
                break;
        case 1:
                TPRINTF("Deleting nodes according to creation time...");
                
                for (i = 0; i < node_count; i++) {
                        avltree_delete(tree, &avltree_nodes[i]);
                        test_tree_parents(tree->root);
                        test_tree_balance(tree->root);
                }
                break;
        }
        
        TPRINTF("done.\n");
}

static void test_tree_delmin(avltree_t *tree, size_t node_count)
{
        unsigned int i = 0;
        
        TPRINTF("Deleting minimum nodes...");
        
        while (tree->root != NULL) {
                i++;
                avltree_delete_min(tree);
                test_tree_parents(tree->root);
                test_tree_balance(tree->root);
        }
        
        if (i != node_count)
                TPRINTF("Bad node count. Some nodes have been lost!\n");
        
        TPRINTF("done.\n");
}

char *test_avltree1(void)
{
        alloc_avltree_node_prepare();
        test_tree_insert(&avltree, NODE_COUNT);
        test_tree_delete(&avltree, NODE_COUNT, 0);
        
        alloc_avltree_node_prepare();
        test_tree_insert(&avltree, NODE_COUNT);
        test_tree_delete(&avltree, NODE_COUNT, 1);
        
        alloc_avltree_node_prepare();
        test_tree_insert(&avltree, NODE_COUNT);
        test_tree_delmin(&avltree, NODE_COUNT);
        
        return NULL;
}