WebSVN – HelenOS – Diff – /branches/rcu/kernel/test/extavltree/extavltree1.c


/*
 * 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(void);
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 (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 (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(void)
{
    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("\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();
                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("\nDelete root nodes\n");
            i = node_count - 1;
            while(tree->root != NULL) {
                delnode = tree->root;
                extavltree_delete(tree,delnode);
                if (!quiet) {
                    if (!exttree_test_link(i)) {
                        print_exttree_link();
                        printf("\n");
                    }
                    exttree_test_parents(tree->root);
                    exttree_test_height(tree->root,1);
                }
                i--;
            }
           
            break;
        case 1:
            if (!quiet) printf("\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(node_count-i-1)) {
                        print_exttree_link();
                        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 - 1;
   
    if (!quiet) printf("\nTimeout tree ...\n");
   
    while(tree->head.next != &(tree->head)) {
        extavltree_delete_min(tree);
        if (!quiet) {
            if (!exttree_test_link(i)) {
                print_exttree_link();
                printf("\n");
            }
            exttree_test_parents(tree->root);
            exttree_test_height(tree->root,1);
        }
        i--;
    }
 
    if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
 
    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;
}
 

Rev 2416	Rev 2421
1	/*	1	/*
2	* Copyright (c) 2007 Vojtech Mencl	2	* Copyright (c) 2007 Vojtech Mencl
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	#include <test.h>	29	#include <test.h>
30	#include <print.h>	30	#include <print.h>
31	#include <adt/extavl.h>	31	#include <adt/extavl.h>
32	#include <debug.h>	32	#include <debug.h>
33		33
34	#include <panic.h>	34	#include <panic.h>
35		35
36		36
37	#define NODE_COUNT 100	37	#define NODE_COUNT 100
38		38
39	/*	39	/*
40	* wrapper structure with a pointer to extended avl tree root	40	* wrapper structure with a pointer to extended avl tree root
41	*/	41	*/
42	static extavltree_t exttree;	42	static extavltree_t exttree;
43		43
44	/*	44	/*
45	* extavltree nodes in array for faster allocating	45	* extavltree nodes in array for faster allocating
46	*/	46	*/
47	static extavltree_node_t extavltree_nodes[NODE_COUNT];	47	static extavltree_node_t extavltree_nodes[NODE_COUNT];
48		48
49	/*	49	/*
50	* head of free nodes' list:	50	* head of free nodes' list:
51	*/	51	*/
52	static extavltree_node_t *first_free_node = NULL;	52	static extavltree_node_t *first_free_node = NULL;
53		53
54		54
55		55
56	static int exttree_test_height(extavltree_node_t *node,bool timeout);	56	static int exttree_test_height(extavltree_node_t *node,bool timeout);
57	static extavltree_node_t exttree_test_parents(extavltree_node_t node);	57	static extavltree_node_t exttree_test_parents(extavltree_node_t node);
58	static void print_exttree_structure_flat (extavltree_node_t *node, int level);	58	static void print_exttree_structure_flat (extavltree_node_t *node, int level);
59	static bool exttree_test_link(int node_count);	59	static bool exttree_test_link(int node_count);
60	static void print_exttree_link(int node_count);	60	static void print_exttree_link(void);
61	static extavltree_node_t *alloc_extavltree_node(void);	61	static extavltree_node_t *alloc_extavltree_node(void);
62		62
63		63
64		64
65	//vraci hloubku stromu	65	//vraci hloubku stromu
66	static int exttree_test_height(extavltree_node_t *node,bool timeout)	66	static int exttree_test_height(extavltree_node_t *node,bool timeout)
67	{	67	{
68	int h1, h2;	68	int h1, h2;
69		69
70	if (!node) return -1;	70	if (!node) return -1;
71		71
72	h1 = exttree_test_height(node->lft,timeout) + 1;	72	h1 = exttree_test_height(node->lft,timeout) + 1;
73	if (!timeout && node->lft_height != h1) {	73	if (!timeout && node->lft_height != h1) {
74	printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node);	74	printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node);
75	}	75	}
76	h2 = exttree_test_height(node->rgt,0) + 1;	76	h2 = exttree_test_height(node->rgt,0) + 1;
77	if (node->rgt_height != h2) {	77	if (node->rgt_height != h2) {
78	printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node);	78	printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node);
79	}	79	}
80	if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) {	80	if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) {
81	printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node);	81	printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node);
82	}	82	}
83		83
84	return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height);	84	return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height);
85	}	85	}
86		86
87		87
88	/** Tests par atribute of every tree node	88	/** Tests par atribute of every tree node
89	*	89	*
90	*/	90	*/
91	static extavltree_node_t exttree_test_parents(extavltree_node_t node)	91	static extavltree_node_t exttree_test_parents(extavltree_node_t node)
92	{	92	{
93	extavltree_node_t *tmp;	93	extavltree_node_t *tmp;
94		94
95	if (!node) return NULL;	95	if (!node) return NULL;
96		96
97	if (node->lft) {	97	if (node->lft) {
98	tmp = exttree_test_parents(node->lft);	98	tmp = exttree_test_parents(node->lft);
99	if (tmp != node) {	99	if (tmp != node) {
100	printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft);	100	printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft);
101	}	101	}
102	}	102	}
103	if (node->rgt) {	103	if (node->rgt) {
104	tmp = exttree_test_parents(node->rgt);	104	tmp = exttree_test_parents(node->rgt);
105	if (tmp != node) {	105	if (tmp != node) {
106	printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt);	106	printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt);
107	}	107	}
108	}	108	}
109	return node->par;	109	return node->par;
110	}	110	}
111		111
112	/** Checks list of nodes	112	/** Checks list of nodes
113	*	113	*
114	*/	114	*/
115	static bool exttree_test_link(int node_count)	115	static bool exttree_test_link(int node_count)
116	{	116	{
117	extavltree_node_t *node;	117	extavltree_node_t *node;
118	int i;	118	int i;
119	bool test_link = true;	119	bool test_link = true;
120		120
121	for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) {	121	for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) {
122	if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {	122	if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {
123	printf("\nList is not sorted (forward direction) at key: %d\n",node->key);	123	printf("\nList is not sorted (forward direction) at key: %d\n",node->key);
124	test_link = false;	124	test_link = false;
125	}	125	}
126	}	126	}
127	if (node_count && i != node_count) {	127	if (i != node_count) {
128	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);	128	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
129	test_link = false;	129	test_link = false;
130	}	130	}
131	for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) {	131	for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) {
132	if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {	132	if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {
133	printf("\nList is not sorted (backward direction) at key: %d\n",node->key);	133	printf("\nList is not sorted (backward direction) at key: %d\n",node->key);
134	test_link = false;	134	test_link = false;
135	}	135	}
136	}	136	}
137	if (node_count && i != node_count) {	137	if (i != node_count) {
138	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);	138	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
139	test_link = false;	139	test_link = false;
140	}	140	}
141	return test_link;	141	return test_link;
142	}	142	}
143		143
144	/** Prints the structure of node, which is level levels from the top of the tree.	144	/** Prints the structure of node, which is level levels from the top of the tree.
145	*	145	*
146	*/	146	*/
147	static void print_exttree_structure_flat (extavltree_node_t *node, int level)	147	static void print_exttree_structure_flat (extavltree_node_t *node, int level)
148	{	148	{
149	extavltree_node_t *tmp;	149	extavltree_node_t *tmp;
150	int i;	150	int i;
151		151
152	if (level > 16)	152	if (level > 16)
153	{	153	{
154	printf ("[...]");	154	printf ("[...]");
155	return;	155	return;
156	}	156	}
157		157
158	if (node == NULL)	158	if (node == NULL)
159	return;	159	return;
160		160
161	for (tmp = node,i = 0; tmp->key == node->key; tmp = tmp->next,i++)	161	for (tmp = node,i = 0; tmp->key == node->key; tmp = tmp->next,i++)
162	;	162	;
163		163
164	printf ("%d[%d,%d,(%d)]", node->key,node->lft_height,node->rgt_height,i);	164	printf ("%d[%d,%d,(%d)]", node->key,node->lft_height,node->rgt_height,i);
165	if (node->lft != NULL \|\| node->rgt != NULL)	165	if (node->lft != NULL \|\| node->rgt != NULL)
166	{	166	{
167	printf("(");	167	printf("(");
168		168
169	print_exttree_structure_flat (node->lft, level + 1);	169	print_exttree_structure_flat (node->lft, level + 1);
170	if (node->rgt != NULL)	170	if (node->rgt != NULL)
171	{	171	{
172	printf(",");	172	printf(",");
173	print_exttree_structure_flat (node->rgt, level + 1);	173	print_exttree_structure_flat (node->rgt, level + 1);
174	}	174	}
175		175
176	printf(")");	176	printf(")");
177	}	177	}
178	}	178	}
179		179
180	/** Prints list of nodes	180	/** Prints list of nodes
181	*	181	*
182	*/	182	*/
183	static void print_exttree_link(int node_count)	183	static void print_exttree_link(void)
184	{	184	{
185	extavltree_node_t *node;	185	extavltree_node_t *node;
186	printf("\n");	186	printf("\n");
187	for (node = exttree.head.next; node != &(exttree.head); node = node->next) {	187	for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
188	printf(" %d,",node->key);	188	printf(" %d,",node->key);
189	}	189	}
190	for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {	190	for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {
191	printf(" %d,",node->key);	191	printf(" %d,",node->key);
192	}	192	}
193	}	193	}
194		194
195	//****************************************************************	195	//****************************************************************
196	static void alloc_extavltree_node_prepare(void)	196	static void alloc_extavltree_node_prepare(void)
197	{	197	{
198	int i;	198	int i;
199		199
200	for (i = 0; i < NODE_COUNT - 1; i++) {	200	for (i = 0; i < NODE_COUNT - 1; i++) {
201	extavltree_nodes[i].next = &(extavltree_nodes[i+1]);	201	extavltree_nodes[i].next = &(extavltree_nodes[i+1]);
202	}	202	}
203	/*	203	/*
204	* Node keys which will be used for insertion. Up to NODE_COUNT size of array.	204	* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
205	*/	205	*/
206		206
207	// First tree node and same key	207	// First tree node and same key
208	extavltree_nodes[0].key = 60;	208	extavltree_nodes[0].key = 60;
209	extavltree_nodes[1].key = 60;	209	extavltree_nodes[1].key = 60;
210	extavltree_nodes[2].key = 60;	210	extavltree_nodes[2].key = 60;
211	//LL rotation	211	//LL rotation
212	extavltree_nodes[3].key = 50;	212	extavltree_nodes[3].key = 50;
213	extavltree_nodes[4].key = 40;	213	extavltree_nodes[4].key = 40;
214	extavltree_nodes[5].key = 30;	214	extavltree_nodes[5].key = 30;
215	//LR rotation	215	//LR rotation
216	extavltree_nodes[6].key = 20;	216	extavltree_nodes[6].key = 20;
217	extavltree_nodes[7].key = 20;	217	extavltree_nodes[7].key = 20;
218	extavltree_nodes[8].key = 25;	218	extavltree_nodes[8].key = 25;
219	extavltree_nodes[9].key = 25;	219	extavltree_nodes[9].key = 25;
220	//LL rotation in lower floor	220	//LL rotation in lower floor
221	extavltree_nodes[10].key = 35;	221	extavltree_nodes[10].key = 35;
222	//RR rotation	222	//RR rotation
223	extavltree_nodes[11].key = 70;	223	extavltree_nodes[11].key = 70;
224	extavltree_nodes[12].key = 80;	224	extavltree_nodes[12].key = 80;
225	//RL rotation	225	//RL rotation
226	extavltree_nodes[13].key = 90;	226	extavltree_nodes[13].key = 90;
227	extavltree_nodes[14].key = 85;	227	extavltree_nodes[14].key = 85;
228	extavltree_nodes[15].key = 100;	228	extavltree_nodes[15].key = 100;
229	extavltree_nodes[16].key = 200;	229	extavltree_nodes[16].key = 200;
230	extavltree_nodes[17].key = 300;	230	extavltree_nodes[17].key = 300;
231	extavltree_nodes[18].key = 400;	231	extavltree_nodes[18].key = 400;
232	extavltree_nodes[19].key = 500;	232	extavltree_nodes[19].key = 500;
233	extavltree_nodes[20].key = 600;	233	extavltree_nodes[20].key = 600;
234		234
235	for (i = 21; i < NODE_COUNT; i++)	235	for (i = 21; i < NODE_COUNT; i++)
236	extavltree_nodes[i].key = i * 3;	236	extavltree_nodes[i].key = i * 3;
237		237
238	extavltree_nodes[i].next = NULL;	238	extavltree_nodes[i].next = NULL;
239	first_free_node = &(extavltree_nodes[0]);	239	first_free_node = &(extavltree_nodes[0]);
240	}	240	}
241		241
242	static extavltree_node_t *alloc_extavltree_node(void)	242	static extavltree_node_t *alloc_extavltree_node(void)
243	{	243	{
244	extavltree_node_t *node;	244	extavltree_node_t *node;
245		245
246	node = first_free_node;	246	node = first_free_node;
247	first_free_node = first_free_node->next;	247	first_free_node = first_free_node->next;
248		248
249	return node;	249	return node;
250	}	250	}
251	//****************************************************************	251	//****************************************************************
252		252
253	static void test_exttree_insert(extavltree_t *tree, unsigned int node_count, int quiet)	253	static void test_exttree_insert(extavltree_t *tree, unsigned int node_count, int quiet)
254	{	254	{
255	unsigned int i;	255	unsigned int i;
256	extavltree_node_t *newnode;	256	extavltree_node_t *newnode;
257		257
258	/*	258	/*
259	* Initialize tree before using.	259	* Initialize tree before using.
260	*/	260	*/
261	extavltree_create(tree);	261	extavltree_create(tree);
262		262
263	if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);	263	if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
264		264
265	for (i = 0; i < node_count; i++) {	265	for (i = 0; i < node_count; i++) {
266	newnode = alloc_extavltree_node();	266	newnode = alloc_extavltree_node();
267	//if (!quiet) printf("[[[%d]]]\n",newnode->key);	267	//if (!quiet) printf("[[[%d]]]\n",newnode->key);
268		268
269	extavltree_insert(tree, newnode);	269	extavltree_insert(tree, newnode);
270	if (!quiet) {	270	if (!quiet) {
271	if (!exttree_test_link(i+1)) {	271	if (!exttree_test_link(i+1)) {
272	print_exttree_link(i+1);	272	print_exttree_link();
273	printf("\n");	273	printf("\n");
274	}	274	}
275	exttree_test_parents(tree->root);	275	exttree_test_parents(tree->root);
276	exttree_test_height(tree->root,1);	276	exttree_test_height(tree->root,1);
277	}	277	}
278	}	278	}
279		279
280	if (!quiet) printf("Inserting was finished\n");	280	if (!quiet) printf("Inserting was finished\n");
281	}	281	}
282		282
283	/*	283	/*
284	static extavltree_node_t exttree_random_delete_node(extavltree_t tree, int node_count, int r, bool quiet)	284	static extavltree_node_t exttree_random_delete_node(extavltree_t tree, int node_count, int r, bool quiet)
285	{	285	{
286	extavltree_node_t *delnode;	286	extavltree_node_t *delnode;
287	int i;	287	int i;
288		288
289	for (i = 0,delnode = tree->head.next; i < (r-1); i++)	289	for (i = 0,delnode = tree->head.next; i < (r-1); i++)
290	delnode = delnode->next;	290	delnode = delnode->next;
291		291
292	if (delnode == &tree->head) {	292	if (delnode == &tree->head) {
293	if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);	293	if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);
294	return NULL;	294	return NULL;
295	}	295	}
296		296
297	extavltree_delete(tree, delnode);	297	extavltree_delete(tree, delnode);
298		298
299	return delnode;	299	return delnode;
300	}	300	}
301	*/	301	*/
302		302
303	static void test_exttree_delete(extavltree_t *tree, int node_count, int node_position, bool quiet)	303	static void test_exttree_delete(extavltree_t *tree, int node_count, int node_position, bool quiet)
304	{	304	{
305	extavltree_node_t *delnode;	305	extavltree_node_t *delnode;
306	unsigned int i;	306	unsigned int i;
307		307
308	//aktualni pocet tiku:	308	//aktualni pocet tiku:
309	if (!quiet) printf("Deleting tree...\n");	309	if (!quiet) printf("Deleting tree...\n");
310		310
311	switch(node_position) {	311	switch(node_position) {
312	case 0: //mazani vzdy korene	312	case 0: //mazani vzdy korene
313	if (!quiet) printf("\n\nDelete root nodes\n");	313	if (!quiet) printf("\nDelete root nodes\n");
314	i = node_count;	314	i = node_count - 1;
315	while(tree->root != NULL) {	315	while(tree->root != NULL) {
316	delnode = tree->root;	316	delnode = tree->root;
317	extavltree_delete(tree,delnode);	317	extavltree_delete(tree,delnode);
318	if (!quiet) {	318	if (!quiet) {
319	if (!exttree_test_link(i)) {	319	if (!exttree_test_link(i)) {
320	print_exttree_link(i);	320	print_exttree_link();
321	printf("\n");	321	printf("\n");
322	}	322	}
323	exttree_test_parents(tree->root);	323	exttree_test_parents(tree->root);
324	exttree_test_height(tree->root,1);	324	exttree_test_height(tree->root,1);
325	}	325	}
326	i--;	326	i--;
327	}	327	}
328		328
329	break;	329	break;
330	case 1:	330	case 1:
331	if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");	331	if (!quiet) printf("\nDelete nodes according to their time of origin\n");
332	for (i = 0; i < node_count; i++) {	332	for (i = 0; i < node_count; i++) {
333	extavltree_delete(tree,&(extavltree_nodes[i]));	333	extavltree_delete(tree,&(extavltree_nodes[i]));
334	if (!quiet) {	334	if (!quiet) {
335	if (!exttree_test_link(i+1)) {	335	if (!exttree_test_link(node_count-i-1)) {
336	print_exttree_link(i+1);	336	print_exttree_link();
337	printf("\n");	337	printf("\n");
338	}	338	}
339	exttree_test_parents(tree->root);	339	exttree_test_parents(tree->root);
340	exttree_test_height(tree->root,1);	340	exttree_test_height(tree->root,1);
341	}	341	}
342	}	342	}
343		343
344	break;	344	break;
345	}	345	}
346		346
347	if (!quiet) printf("Deletion was finished\n");	347	if (!quiet) printf("Deletion was finished\n");
348	}	348	}
349		349
350	static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)	350	static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)
351	{	351	{
352	int i = node_count;	352	int i = node_count - 1;
353		353
354	if (!quiet) printf("Timeout tree ...\n");	354	if (!quiet) printf("\nTimeout tree ...\n");
355		355
356	while(tree->head.next != &(tree->head)) {	356	while(tree->head.next != &(tree->head)) {
357	extavltree_delete_min(tree);	357	extavltree_delete_min(tree);
358	if (!quiet) {	358	if (!quiet) {
359	if (!exttree_test_link(i)) {	359	if (!exttree_test_link(i)) {
360	print_exttree_link(i);	360	print_exttree_link();
361	printf("\n");	361	printf("\n");
362	}	362	}
363	exttree_test_parents(tree->root);	363	exttree_test_parents(tree->root);
364	exttree_test_height(tree->root,1);	364	exttree_test_height(tree->root,1);
365	}	365	}
366	i--;	366	i--;
367	}	367	}
368		368
369	if (!quiet && (i != 0)) printf("Bad node count. Some nodes have been lost!");	369	if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
370		370
371	if (!quiet) printf("Timeout tree finished\n");	371	if (!quiet) printf("Timeout tree finished\n");
372	}	372	}
373		373
374	/*	374	/*
375	void timeout_exttree_run(extavltree_t *tree, int operation_count, int verbal)	375	void timeout_exttree_run(extavltree_t *tree, int operation_count, int verbal)
376	{	376	{
377	int i;	377	int i;
378	extavltree_node_t *node;	378	extavltree_node_t *node;
379	int r;	379	int r;
380	int count;	380	int count;
381		381
382	//inicializace stromu:	382	//inicializace stromu:
383	extavltree_create(tree);	383	extavltree_create(tree);
384		384
385	for(i = 0, count = 0; i < operation_count; i++) {	385	for(i = 0, count = 0; i < operation_count; i++) {
386	if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {	386	if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {
387	if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne	387	if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne
388	node = exttree_random_delete_node(tree,(r % tree->count));	388	node = exttree_random_delete_node(tree,(r % tree->count));
389	//printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);	389	//printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
390	node->next = first_free_node;	390	node->next = first_free_node;
391	first_free_node = node;	391	first_free_node = node;
392	} else {	392	} else {
393	node = tree->head.next;	393	node = tree->head.next;
394	extavltree_delete_min(tree);	394	extavltree_delete_min(tree);
395	//printf("TIMEOUT key: %d, address: %p\n",node->key,node);	395	//printf("TIMEOUT key: %d, address: %p\n",node->key,node);
396	node->next = first_free_node;	396	node->next = first_free_node;
397	first_free_node = node;	397	first_free_node = node;
398	}	398	}
399	} else {	399	} else {
400	node = alloc_extavltree_node_random();	400	node = alloc_extavltree_node_random();
401	//printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);	401	//printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
402	extavltree_insert(tree, node);	402	extavltree_insert(tree, node);
403	}	403	}
404	//test_exttree_height(tree->root,1);	404	//test_exttree_height(tree->root,1);
405	//exttree_test_parents(tree->root);	405	//exttree_test_parents(tree->root);
406	//print_exttree_link(tree->count);	406	//print_exttree_link(tree->count);
407	//print_exttree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');	407	//print_exttree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
408	}	408	}
409	}	409	}
410	*/	410	*/
411		411
412	char * test_extavltree1(bool quiet)	412	char * test_extavltree1(bool quiet)
413	{	413	{
414	alloc_extavltree_node_prepare();	414	alloc_extavltree_node_prepare();
415	test_exttree_insert(&exttree, NODE_COUNT, quiet);	415	test_exttree_insert(&exttree, NODE_COUNT, quiet);
416	test_exttree_delete(&exttree, NODE_COUNT, 0, quiet);	416	test_exttree_delete(&exttree, NODE_COUNT, 0, quiet);
417		417
418	alloc_extavltree_node_prepare();	418	alloc_extavltree_node_prepare();
419	test_exttree_insert(&exttree, NODE_COUNT, quiet);	419	test_exttree_insert(&exttree, NODE_COUNT, quiet);
420	test_exttree_delete(&exttree, NODE_COUNT, 1, quiet);	420	test_exttree_delete(&exttree, NODE_COUNT, 1, quiet);
421		421
422	alloc_extavltree_node_prepare();	422	alloc_extavltree_node_prepare();
423	test_exttree_insert(&exttree, NODE_COUNT, quiet);	423	test_exttree_insert(&exttree, NODE_COUNT, quiet);
424	timeout_exttree(&exttree, NODE_COUNT, quiet);	424	timeout_exttree(&exttree, NODE_COUNT, quiet);
425		425
426	return NULL;	426	return NULL;
427	}	427	}
428		428

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/extavltree/extavltree1.c – Rev 2416 → 2421