WebSVN – HelenOS – Diff – /branches/rcu/kernel/test/extavlreltree/extavlreltree1.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/extavlrel.h>
#include <debug.h>
 
#include <panic.h>
 
 
#define NODE_COUNT 100
 
/*
 * wrapper structure with a pointer to extended avl tree root
 */
static extavlreltree_t extreltree;
 
/*
 * extavltree nodes in array for faster allocating
 */
static extavlreltree_node_t extavlreltree_nodes[NODE_COUNT];
 
/*
 * head of free nodes' list:
 */
static extavlreltree_node_t *first_free_node = NULL;
 
 
 
static int extreltree_test_height(extavlreltree_node_t *node,bool timeout);
static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node);
static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level);
static bool extreltree_test_link(extavlreltree_t *tree, int node_count);
static void print_extreltree_link(extavlreltree_t *tree);
static extavlreltree_node_t *alloc_extavlreltree_node(void);
 
 
 
//vraci hloubku stromu
static int extreltree_test_height(extavlreltree_node_t *node,bool timeout)
{
    int h1, h2;
 
    if (!node) return -1;
 
    h1 = extreltree_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 = extreltree_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 extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node)
{
    extavlreltree_node_t *tmp;
   
    if (!node) return NULL;
 
    if (node->lft) {
        tmp = extreltree_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 = extreltree_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 extreltree_test_link(extavlreltree_t *tree, int node_count)
{
    extavlreltree_node_t *node;
    int i;
    bool test_link = true;
 
    for (i = 0,node = tree->head.next; node != &(tree->head); i++,node = node->next)
        ;
    if (i != node_count) {
        printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
        test_link = false;
    }
    for (i = 0,node = tree->head.prev; node != &(tree->head); i++,node = node->prev)
        ;
    if (i != node_count) {
        printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
        test_link = false;
    }
    return test_link;
}
 
static int _sum_extreltree(extavlreltree_node_t *node)
{
    int sum = 0;
 
    if (node->rgt)
        sum += _sum_extreltree(node->rgt);
    if (node->lft)
        sum += _sum_extreltree(node->lft);
   
    return sum + node->key;
}
 
static int extreltree_test_rgtsum(extavlreltree_node_t *node)
{
    int rs, ls;
   
    if (!node) return 0;
   
    rs = extreltree_test_rgtsum(node->rgt);
    ls = extreltree_test_rgtsum(node->lft);
 
    if (rs != node->rgt_sum) {
        printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_sum,rs,node->key,node);
 
    }
    return rs + ls + node->key;
}
 
/** Prints the structure of node, which is level levels from the top of the tree.
 *
 */
static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level)
{
    extavlreltree_node_t *tmp;
    int i;
 
    if (level > 16)
    {
        printf ("[...]");
        return;
    }
 
    if (node == NULL)
        return;
   
    for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++)
        ;
 
    printf ("%d[%d,%d]", node->key,node->rgt_sum,i);
    if (node->lft != NULL || node->rgt != NULL)
    {
        printf ("(");
 
        print_extreltree_structure_flat (node->lft, level + 1);
        if (node->rgt != NULL)
        {
            printf(",");
            print_extreltree_structure_flat (node->rgt, level + 1);
        }
 
        printf(")");
    }
}
 
/** Prints list of nodes
 *
 */
static void print_extreltree_link(extavlreltree_t *tree)
{
    extavlreltree_node_t *node;
    printf("\n");
    for (node = tree->head.next; node != &(tree->head); node = node->next) {
        printf(" %d,",node->key);
    }
    for (node = tree->head.prev; node != &(tree->head); node = node->prev) {
        printf(" %d,",node->key);
    }
}
 
//****************************************************************
static void alloc_extavlreltree_node_prepare(void)
{
    int i;
 
    for (i = 0; i < NODE_COUNT - 1; i++) {
        extavlreltree_nodes[i].next = &(extavlreltree_nodes[i+1]);
    }
    /*
     * Node keys which will be used for insertion. Up to NODE_COUNT size of array.
     */
 
    // First tree node and same key
    extavlreltree_nodes[0].key = 60;
    extavlreltree_nodes[1].key = 60;
    extavlreltree_nodes[2].key = 60;
    //LL rotation
    extavlreltree_nodes[3].key = 50;
    extavlreltree_nodes[4].key = 40;
    extavlreltree_nodes[5].key = 30;
    //LR rotation
    extavlreltree_nodes[6].key = 20;
    extavlreltree_nodes[7].key = 20;
    extavlreltree_nodes[8].key = 25;
    extavlreltree_nodes[9].key = 25;
    //LL rotation in lower floor
    extavlreltree_nodes[10].key = 35;
    //RR rotation
    extavlreltree_nodes[11].key = 70;
    extavlreltree_nodes[12].key = 80;
    //RL rotation
    extavlreltree_nodes[13].key = 90;
    extavlreltree_nodes[14].key = 85;
    extavlreltree_nodes[15].key = 100;
    extavlreltree_nodes[16].key = 200;
    extavlreltree_nodes[17].key = 300;
    extavlreltree_nodes[18].key = 400;
    extavlreltree_nodes[19].key = 500;
    extavlreltree_nodes[20].key = 600;
 
    for (i = 21; i < NODE_COUNT; i++)
        extavlreltree_nodes[i].key = i * 3;
   
    extavlreltree_nodes[i].next = NULL;
    first_free_node = &(extavlreltree_nodes[0]);
}
 
static extavlreltree_node_t *alloc_extavlreltree_node(void)
{
    extavlreltree_node_t *node;
 
    node = first_free_node;
    first_free_node = first_free_node->next;
 
    return node;
}
//****************************************************************
 
static void test_extreltree_insert(extavlreltree_t *tree, unsigned int node_count, int quiet)
{
    unsigned int i;
    extavlreltree_node_t *newnode;
 
    /*
     * Initialize tree before using.
     */
    extavlreltree_create(tree);
   
    if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
 
    for (i = 0; i < node_count; i++) {
        newnode = alloc_extavlreltree_node();
        //if (!quiet) printf("[[[%d]]]\n",newnode->key);
       
        extavlreltree_insert(tree, newnode);
        if (!quiet) {
            if (!extreltree_test_link(tree,i+1)) {
                print_extreltree_link(tree);
                printf("\n");
            }
            extreltree_test_parents(tree->root);
            extreltree_test_height(tree->root,1);
            extreltree_test_rgtsum(tree->root);
        }
    }
       
    if (!quiet) printf("Inserting was finished\n");
}
 
static void test_extreltree_delete(extavlreltree_t *tree, int node_count, int node_position, bool quiet)
{
    extavlreltree_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;
                extavlreltree_delete(tree,delnode);
                if (!quiet) {
                    if (!extreltree_test_link(tree,i)) {
                        print_extreltree_link(tree);
                        printf("\n");
                    }
                    extreltree_test_parents(tree->root);
                    extreltree_test_height(tree->root,1);
                    extreltree_test_rgtsum(tree->root);
                }
                i--;
            }
           
            break;
        case 1:
            if (!quiet) printf("\nDelete nodes according to their time of origin\n");
            for (i = 0; i < node_count; i++) {
                extavlreltree_delete(tree,&(extavlreltree_nodes[i]));
                if (!quiet) {
                    if (!extreltree_test_link(tree,node_count-i-1)) {
                        print_extreltree_link(tree);
                        printf("\n");
                    }
                    extreltree_test_parents(tree->root);
                    extreltree_test_height(tree->root,1);
                    extreltree_test_rgtsum(tree->root);
                }
            }
 
            break; 
    }
   
    if (!quiet) printf("Deletion was finished\n");
}
 
static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet)
{
    int i = node_count - 1;
   
    if (!quiet) printf("\nTimeout tree ...\n");
   
    while(tree->head.next != &(tree->head)) {
        extavlreltree_delete_min(tree);
        if (!quiet) {
            if (!extreltree_test_link(tree,i)) {
                print_extreltree_link(tree);
                printf("\n");
            }
            extreltree_test_parents(tree->root);
            extreltree_test_height(tree->root,1);
            extreltree_test_rgtsum(tree->root);
        }
        i--;
    }
 
    if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
 
    if (!quiet) printf("Timeout tree finished\n");
}
 
char * test_extavlreltree1(bool quiet)
{
    alloc_extavlreltree_node_prepare();
    test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
    test_extreltree_delete(&extreltree, NODE_COUNT, 0, quiet);
 
    alloc_extavlreltree_node_prepare();
    test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
    test_extreltree_delete(&extreltree, NODE_COUNT, 1, quiet);
 
    alloc_extavlreltree_node_prepare();
    test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
    timeout_extreltree(&extreltree, 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/extavlreltree.h>	31	#include <adt/extavlrel.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 extavlreltree_t extreltree;	42	static extavlreltree_t extreltree;
43		43
44	/*	44	/*
45	* extavltree nodes in array for faster allocating	45	* extavltree nodes in array for faster allocating
46	*/	46	*/
47	static extavlreltree_node_t extavlreltree_nodes[NODE_COUNT];	47	static extavlreltree_node_t extavlreltree_nodes[NODE_COUNT];
48		48
49	/*	49	/*
50	* head of free nodes' list:	50	* head of free nodes' list:
51	*/	51	*/
52	static extavlreltree_node_t *first_free_node = NULL;	52	static extavlreltree_node_t *first_free_node = NULL;
53		53
54		54
55		55
56	static int extreltree_test_height(extrelavltree_node_t *node,bool timeout);	56	static int extreltree_test_height(extavlreltree_node_t *node,bool timeout);
57	static extavlreltree_node_t extreltree_test_parents(extavlireltree_node_t node);	57	static extavlreltree_node_t extreltree_test_parents(extavlreltree_node_t node);
58	static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level);	58	static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level);
59	static bool extreltree_test_link(int node_count);	59	static bool extreltree_test_link(extavlreltree_t *tree, int node_count);
60	static void print_extreltree_link(int node_count);	60	static void print_extreltree_link(extavlreltree_t *tree);
61	static extavlreltree_node_t *alloc_extavlreltree_node(void);	61	static extavlreltree_node_t *alloc_extavlreltree_node(void);
62		62
63		63
64		64
65	//vraci hloubku stromu	65	//vraci hloubku stromu
66	static int extreltree_test_height(extavltree_node_t *node,bool timeout)	66	static int extreltree_test_height(extavlreltree_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 = extreltree_test_height(node->lft,timeout) + 1;	72	h1 = extreltree_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 = extreltree_test_height(node->rgt,0) + 1;	76	h2 = extreltree_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 extavlreltree_node_t extreltree_test_parents(extavlreltree_node_t node)	91	static extavlreltree_node_t extreltree_test_parents(extavlreltree_node_t node)
92	{	92	{
93	extavltree_node_t *tmp;	93	extavlreltree_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 = extreltree_test_parents(node->lft);	98	tmp = extreltree_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 = extreltree_test_parents(node->rgt);	104	tmp = extreltree_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 extreltree_test_link(int node_count)	115	static bool extreltree_test_link(extavlreltree_t *tree, int node_count)
116	{	116	{
117	extavltree_node_t *node;	117	extavlreltree_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 = tree->head.next; node != &(tree->head); i++,node = node->next)
122	;	122	;
123	if (node_count && i != node_count) {	123	if (i != node_count) {
124	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);	124	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
125	test_link = false;	125	test_link = false;
126	}	126	}
127	for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev)	127	for (i = 0,node = tree->head.prev; node != &(tree->head); i++,node = node->prev)
128	;	128	;
129	if (node_count && i != node_count) {	129	if (i != node_count) {
130	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);	130	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
131	test_link = false;	131	test_link = false;
132	}	132	}
133	return test_link;	133	return test_link;
134	}	134	}
135		135
136	static int _sum_extreltree(extavlreltree_node_t *node)	136	static int _sum_extreltree(extavlreltree_node_t *node)
137	{	137	{
138	int sum = 0;	138	int sum = 0;
139		139
140	if (node->rgt)	140	if (node->rgt)
141	sum += _sum_extreltree(node->rgt);	141	sum += _sum_extreltree(node->rgt);
142	if (node->lft)	142	if (node->lft)
143	sum += _sum_extreltree(node->lft);	143	sum += _sum_extreltree(node->lft);
144		144
145	return sum + node->key;	145	return sum + node->key;
146	}	146	}
147		147
148	static int extreltree_test_maxsum(extavlreltree_node_t *node)	148	static int extreltree_test_rgtsum(extavlreltree_node_t *node)
149	{	149	{
150	int rs, ls;	150	int rs, ls;
151		151
152	if (!node) return 0;	152	if (!node) return 0;
153		153
154	rs = extreltree_test_maxsum(node->rgt);	154	rs = extreltree_test_rgtsum(node->rgt);
155	ls = extreltree_test_maxsum(node->lft);	155	ls = extreltree_test_rgtsum(node->lft);
156		156
157	if (rs != node->rgt_max_key) {	157	if (rs != node->rgt_sum) {
158	printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_max_key,rs,node->key,node);	158	printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_sum,rs,node->key,node);
159	getchar();	-
160	}	159	}
161	return rs + ls + node->key;	160	return rs + ls + node->key;
162	}	161	}
163		162
164	/** Prints the structure of node, which is level levels from the top of the tree.	163	/** Prints the structure of node, which is level levels from the top of the tree.
165	*	164	*
166	*/	165	*/
167	static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level)	166	static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level)
168	{	167	{
169	extavlreltree_node_t *tmp;	168	extavlreltree_node_t *tmp;
170	int i;	169	int i;
171		170
172	if (level > 16)	171	if (level > 16)
173	{	172	{
174	printf ("[...]");	173	printf ("[...]");
175	return;	174	return;
176	}	175	}
177		176
178	if (node == NULL)	177	if (node == NULL)
179	return;	178	return;
180		179
181	for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++)	180	for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++)
182	;	181	;
183		182
184	printf ("%d[%d,%d]", node->key,node->rgt_max_key,i);	183	printf ("%d[%d,%d]", node->key,node->rgt_sum,i);
185	if (node->lft != NULL \|\| node->rgt != NULL)	184	if (node->lft != NULL \|\| node->rgt != NULL)
186	{	185	{
187	putchar ('(');	186	printf ("(");
188		187
189	print_extreltree_structure_flat (node->lft, level + 1);	188	print_extreltree_structure_flat (node->lft, level + 1);
190	if (node->rgt != NULL)	189	if (node->rgt != NULL)
191	{	190	{
192	putchar (',');	191	printf(",");
193	print_extreltree_structure_flat (node->rgt, level + 1);	192	print_extreltree_structure_flat (node->rgt, level + 1);
194	}	193	}
195		194
196	putchar (')');	195	printf(")");
197	}	196	}
198	}	197	}
199		198
200	/** Prints list of nodes	199	/** Prints list of nodes
201	*	200	*
202	*/	201	*/
203	static void print_extreltree_link(int node_count)	202	static void print_extreltree_link(extavlreltree_t *tree)
204	{	203	{
205	extavltree_node_t *node;	204	extavlreltree_node_t *node;
206	printf("\n");	205	printf("\n");
207	for (node = exttree.head.next; node != &(exttree.head); node = node->next) {	206	for (node = tree->head.next; node != &(tree->head); node = node->next) {
208	printf(" %d,",node->key);	207	printf(" %d,",node->key);
209	}	208	}
210	for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {	209	for (node = tree->head.prev; node != &(tree->head); node = node->prev) {
211	printf(" %d,",node->key);	210	printf(" %d,",node->key);
212	}	211	}
213	}	212	}
214		213
215	//****************************************************************	214	//****************************************************************
216	static void alloc_extavltree_node_prepare(void)	215	static void alloc_extavlreltree_node_prepare(void)
217	{	216	{
218	int i;	217	int i;
219		218
220	for (i = 0; i < NODE_COUNT - 1; i++) {	219	for (i = 0; i < NODE_COUNT - 1; i++) {
221	extavlreltree_nodes[i].next = &(extavlreltree_nodes[i+1]);	220	extavlreltree_nodes[i].next = &(extavlreltree_nodes[i+1]);
222	}	221	}
223	/*	222	/*
224	* Node keys which will be used for insertion. Up to NODE_COUNT size of array.	223	* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
225	*/	224	*/
226		225
227	// First tree node and same key	226	// First tree node and same key
228	extavlreltree_nodes[0].key = 60;	227	extavlreltree_nodes[0].key = 60;
229	extavlreltree_nodes[1].key = 60;	228	extavlreltree_nodes[1].key = 60;
230	extavlreltree_nodes[2].key = 60;	229	extavlreltree_nodes[2].key = 60;
231	//LL rotation	230	//LL rotation
232	extavlreltree_nodes[3].key = 50;	231	extavlreltree_nodes[3].key = 50;
233	extavlreltree_nodes[4].key = 40;	232	extavlreltree_nodes[4].key = 40;
234	extavlreltree_nodes[5].key = 30;	233	extavlreltree_nodes[5].key = 30;
235	//LR rotation	234	//LR rotation
236	extavlreltree_nodes[6].key = 20;	235	extavlreltree_nodes[6].key = 20;
237	extavlreltree_nodes[7].key = 20;	236	extavlreltree_nodes[7].key = 20;
238	extavlreltree_nodes[8].key = 25;	237	extavlreltree_nodes[8].key = 25;
239	extavlreltree_nodes[9].key = 25;	238	extavlreltree_nodes[9].key = 25;
240	//LL rotation in lower floor	239	//LL rotation in lower floor
241	extavlreltree_nodes[10].key = 35;	240	extavlreltree_nodes[10].key = 35;
242	//RR rotation	241	//RR rotation
243	extavlreltree_nodes[11].key = 70;	242	extavlreltree_nodes[11].key = 70;
244	extavlreltree_nodes[12].key = 80;	243	extavlreltree_nodes[12].key = 80;
245	//RL rotation	244	//RL rotation
246	extavlreltree_nodes[13].key = 90;	245	extavlreltree_nodes[13].key = 90;
247	extavlreltree_nodes[14].key = 85;	246	extavlreltree_nodes[14].key = 85;
248	extavlreltree_nodes[15].key = 100;	247	extavlreltree_nodes[15].key = 100;
249	extavlreltree_nodes[16].key = 200;	248	extavlreltree_nodes[16].key = 200;
250	extavlreltree_nodes[17].key = 300;	249	extavlreltree_nodes[17].key = 300;
251	extavlreltree_nodes[18].key = 400;	250	extavlreltree_nodes[18].key = 400;
252	extavlreltree_nodes[19].key = 500;	251	extavlreltree_nodes[19].key = 500;
253	extavlreltree_nodes[20].key = 600;	252	extavlreltree_nodes[20].key = 600;
254		253
255	for (i = 21; i < NODE_COUNT; i++)	254	for (i = 21; i < NODE_COUNT; i++)
256	extavlreltree_nodes[i].key = i * 3;	255	extavlreltree_nodes[i].key = i * 3;
257		256
258	extavlreltree_nodes[i].next = NULL;	257	extavlreltree_nodes[i].next = NULL;
259	first_free_node = &(extavlreltree_nodes[0]);	258	first_free_node = &(extavlreltree_nodes[0]);
260	}	259	}
261		260
262	static extavlreltree_node_t *alloc_extavlreltree_node(void)	261	static extavlreltree_node_t *alloc_extavlreltree_node(void)
263	{	262	{
264	extavlreltree_node_t *node;	263	extavlreltree_node_t *node;
265		264
266	node = first_free_node;	265	node = first_free_node;
267	first_free_node = first_free_node->next;	266	first_free_node = first_free_node->next;
268		267
269	return node;	268	return node;
270	}	269	}
271	//****************************************************************	270	//****************************************************************
272		271
273	static void test_extreltree_insert(extavlreltree_t *tree, unsigned int node_count, int quiet)	272	static void test_extreltree_insert(extavlreltree_t *tree, unsigned int node_count, int quiet)
274	{	273	{
275	unsigned int i;	274	unsigned int i;
276	extavlreltree_node_t *newnode;	275	extavlreltree_node_t *newnode;
277		276
278	/*	277	/*
279	* Initialize tree before using.	278	* Initialize tree before using.
280	*/	279	*/
281	extavlreltree_create(tree);	280	extavlreltree_create(tree);
282		281
283	if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);	282	if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
284		283
285	for (i = 0; i < node_count; i++) {	284	for (i = 0; i < node_count; i++) {
286	newnode = alloc_extavlreltree_node();	285	newnode = alloc_extavlreltree_node();
287	//if (!quiet) printf("[[[%d]]]\n",newnode->key);	286	//if (!quiet) printf("[[[%d]]]\n",newnode->key);
288		287
289	extavlreltree_insert(tree, newnode);	288	extavlreltree_insert(tree, newnode);
290	if (!quiet) {	289	if (!quiet) {
291	if (!extreltree_test_link(i+1)) {	290	if (!extreltree_test_link(tree,i+1)) {
292	print_extreltree_link(i+1);	291	print_extreltree_link(tree);
293	printf("\n");	292	printf("\n");
294	}	293	}
295	extreltree_test_parents(tree->root);	294	extreltree_test_parents(tree->root);
296	extreltree_test_height(tree->root,1);	295	extreltree_test_height(tree->root,1);
297	extreltree_test_rgtsum(tree->root);	296	extreltree_test_rgtsum(tree->root);
298	}	297	}
299	}	298	}
300		299
301	if (!quiet) printf("Inserting was finished\n");	300	if (!quiet) printf("Inserting was finished\n");
302	}	301	}
303		302
304	static void test_extreltree_delete(extavlreltree_t *tree, int node_count, int node_position, bool quiet)	303	static void test_extreltree_delete(extavlreltree_t *tree, int node_count, int node_position, bool quiet)
305	{	304	{
306	extavlreltree_node_t *delnode;	305	extavlreltree_node_t *delnode;
307	unsigned int i;	306	unsigned int i;
308		307
309	//aktualni pocet tiku:	308	//aktualni pocet tiku:
310	if (!quiet) printf("Deleting tree...\n");	309	if (!quiet) printf("Deleting tree...\n");
311		310
312	switch(node_position) {	311	switch(node_position) {
313	case 0: //mazani vzdy korene	312	case 0: //mazani vzdy korene
314	if (!quiet) printf("\n\nDelete root nodes\n");	313	if (!quiet) printf("\nDelete root nodes\n");
315	i = node_count;	314	i = node_count - 1;
316	while(tree->root != NULL) {	315	while(tree->root != NULL) {
317	delnode = tree->root;	316	delnode = tree->root;
318	extavlreltree_delete(tree,delnode);	317	extavlreltree_delete(tree,delnode);
319	if (!quiet) {	318	if (!quiet) {
320	if (!extreltree_test_link(i)) {	319	if (!extreltree_test_link(tree,i)) {
321	print_extreltree_link(i);	320	print_extreltree_link(tree);
322	printf("\n");	321	printf("\n");
323	}	322	}
324	extreltree_test_parents(tree->root);	323	extreltree_test_parents(tree->root);
325	extreltree_test_height(tree->root,1);	324	extreltree_test_height(tree->root,1);
326	extreltree_test_rgtsum(tree->root);	325	extreltree_test_rgtsum(tree->root);
327	}	326	}
328	i--;	327	i--;
329	}	328	}
330		329
331	break;	330	break;
332	case 1:	331	case 1:
333	if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");	332	if (!quiet) printf("\nDelete nodes according to their time of origin\n");
334	for (i = 0; i < node_count; i++) {	333	for (i = 0; i < node_count; i++) {
335	extavlreltree_delete(tree,&(extavlreltree_nodes[i]));	334	extavlreltree_delete(tree,&(extavlreltree_nodes[i]));
336	if (!quiet) {	335	if (!quiet) {
337	if (!extreltree_test_link(i+1)) {	336	if (!extreltree_test_link(tree,node_count-i-1)) {
338	print_extreltree_link(i+1);	337	print_extreltree_link(tree);
339	printf("\n");	338	printf("\n");
340	}	339	}
341	extreltree_test_parents(tree->root);	340	extreltree_test_parents(tree->root);
342	extreltree_test_height(tree->root,1);	341	extreltree_test_height(tree->root,1);
343	extreltree_test_rgtsum(tree->root);	342	extreltree_test_rgtsum(tree->root);
344	}	343	}
345	}	344	}
346		345
347	break;	346	break;
348	}	347	}
349		348
350	if (!quiet) printf("Deletion was finished\n");	349	if (!quiet) printf("Deletion was finished\n");
351	}	350	}
352		351
353	static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet)	352	static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet)
354	{	353	{
355	int i = node_count;	354	int i = node_count - 1;
356		355
357	if (!quiet) printf("Timeout tree ...\n");	356	if (!quiet) printf("\nTimeout tree ...\n");
358		357
359	while(tree->head.next != &(tree->head)) {	358	while(tree->head.next != &(tree->head)) {
360	extavlreltree_delete_min(tree);	359	extavlreltree_delete_min(tree);
361	if (!quiet) {	360	if (!quiet) {
362	if (!extreltree_test_link(i)) {	361	if (!extreltree_test_link(tree,i)) {
363	print_extreltree_link(i);	362	print_extreltree_link(tree);
364	printf("\n");	363	printf("\n");
365	}	364	}
366	extreltree_test_parents(tree->root);	365	extreltree_test_parents(tree->root);
367	extreltree_test_height(tree->root,1);	366	extreltree_test_height(tree->root,1);
368	extreltree_test_rgtsum(tree->root);	367	extreltree_test_rgtsum(tree->root);
369	}	368	}
370	i--;	369	i--;
371	}	370	}
372		371
373	if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!");	372	if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
374		373
375	if (!quiet) printf("Timeout tree finished\n");	374	if (!quiet) printf("Timeout tree finished\n");
376	}	375	}
377		376
378	char * test_extavlreltree1(bool quiet)	377	char * test_extavlreltree1(bool quiet)
379	{	378	{
380	alloc_extavlreltree_node_prepare();	379	alloc_extavlreltree_node_prepare();
381	test_extreltree_insert(&extreltree, NODE_COUNT, quiet);	380	test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
382	test_extreltree_delete(&extreltree, NODE_COUNT, 0, quiet);	381	test_extreltree_delete(&extreltree, NODE_COUNT, 0, quiet);
383		382
384	alloc_extavlreltree_node_prepare();	383	alloc_extavlreltree_node_prepare();
385	test_extreltree_insert(&extreltree, NODE_COUNT, quiet);	384	test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
386	test_extreltree_delete(&extreltree, NODE_COUNT, 1, quiet);	385	test_extreltree_delete(&extreltree, NODE_COUNT, 1, quiet);
387		386
388	alloc_extavlreltree_node_prepare();	387	alloc_extavlreltree_node_prepare();
389	test_extreltree_insert(&extreltree, NODE_COUNT, quiet);	388	test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
390	timeout_extreltree(&extreltree, NODE_COUNT, quiet);	389	timeout_extreltree(&extreltree, NODE_COUNT, quiet);
391		390
392	return NULL;	391	return NULL;
393	}	392	}
394		393

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/extavlreltree/extavlreltree1.c – Rev 2416 → 2421