WebSVN – HelenOS – Diff – /branches/rcu/kernel/test/avltree/avltree1.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/avl.h>
#include <debug.h>
 
 
 
 
#define NODE_COUNT 100
 
/*
 * wrapper structure with a pointer to avl tree root
 */
static avltree_t avltree;
 
/*
 * avl tree nodes in array for faster allocating
 */
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);
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) {
            printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->lft);
        }
    }
    if (node->rgt) {
        tmp = test_tree_parents(node->rgt);
        if (tmp != node) {
            printf("Bad parent pointer key: %d, 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)) {
        printf("Bad balance\n");
    }
    return h1 > h2 ? h1 + 1 : h2 + 1;
}
 
/**
 * Prints the structure of 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)
    {
        printf ("[...]");
        return;
    }
 
    if (node == NULL)
        return;
 
    printf ("%d[%d]", node->key,node->balance);
    if (node->lft != NULL || node->rgt != NULL)
    {
        printf("(");
 
        print_tree_structure_flat (node->lft, level + 1);
        if (node->rgt != NULL)
        {
            printf(",");
            print_tree_structure_flat (node->rgt, level + 1);
        }
 
        printf(")");
    }
}
 
 
//****************************************************************
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]);
    }
    /*
     * 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;
   
    avltree_nodes[i].par = NULL;
    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, unsigned int node_count, int quiet)
{
    unsigned int i;
    avltree_node_t *newnode;
 
    /*
     * Initialize tree before using.
     */
    avltree_create(tree);
   
    if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
 
    for (i = 0; i < node_count; i++) {
        newnode = alloc_avltree_node();
        //if (!quiet) printf("[[[%d]]]\n",newnode->key);
       
        avltree_insert(tree, newnode);
        if (!quiet) {
            test_tree_parents(tree->root);
            test_tree_balance(tree->root);
        }
    }
       
    if (!quiet) printf("Inserting was finished\n");
}
 
 
static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet)
{
    avltree_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");
            while(tree->root != NULL) {
                delnode = tree->root;
                avltree_delete(tree,delnode);
                if (!quiet) {
                    test_tree_parents(tree->root);
                    test_tree_balance(tree->root);
                }
            }
           
            break;
        case 1:
            if (!quiet) printf("\nDelete nodes according to their time of origin\n");
            for (i = 0; i < node_count; i++) {
                avltree_delete(tree,&(avltree_nodes[i]));
                if (!quiet) {
                    test_tree_parents(tree->root);
                    test_tree_balance(tree->root);
                }
            }
 
            break; 
    }
   
    if (!quiet) printf("Deletion was finished\n");
}
 
static void timeout_tree(avltree_t *tree, int node_count, bool quiet)
{
    int i = 0;
   
    if (!quiet) printf("\nTimeout tree ...\n");
   
    while(tree->root != NULL) {
        i++;
        avltree_delete_min(tree);
        if (!quiet) {
            test_tree_parents(tree->root);
            test_tree_balance(tree->root);
        }
    }
 
    if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n");
 
    if (!quiet) printf("Timeout tree finished\n");
}
 
char * test_avltree1(bool quiet)
{
    alloc_avltree_node_prepare();
    test_tree_insert(&avltree, NODE_COUNT, quiet);
    test_tree_delete(&avltree, NODE_COUNT, 0, quiet);
 
    alloc_avltree_node_prepare();
    test_tree_insert(&avltree, NODE_COUNT, quiet);
    test_tree_delete(&avltree, NODE_COUNT, 1, quiet);
 
    alloc_avltree_node_prepare();
    test_tree_insert(&avltree, NODE_COUNT, quiet);
    timeout_tree(&avltree, NODE_COUNT, quiet);
 
    return NULL;
}
 

Rev 2421	Rev 2431
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/avl.h>	31	#include <adt/avl.h>
32	#include <debug.h>	32	#include <debug.h>
33		33
34	#include <panic.h>	-
35		-
36		34
37	#define NODE_COUNT 100	35	#define NODE_COUNT 100
38		36
39	/*	37	/*
40	* wrapper structure with a pointer to avl tree root	38	* wrapper structure with a pointer to avl tree root
41	*/	39	*/
42	static avltree_t avltree;	40	static avltree_t avltree;
43		41
44	/*	42	/*
45	* avl tree nodes in array for faster allocating	43	* avl tree nodes in array for faster allocating
46	*/	44	*/
47	static avltree_node_t avltree_nodes[NODE_COUNT];	45	static avltree_node_t avltree_nodes[NODE_COUNT];
48		46
49	/*	47	/*
50	* head of free nodes' list:	48	* head of free nodes' list:
51	*/	49	*/
52	static avltree_node_t *first_free_node = NULL;	50	static avltree_node_t *first_free_node = NULL;
53		51
54		52
55		53
56	static int test_tree_balance(avltree_node_t *node);	54	static int test_tree_balance(avltree_node_t *node);
57	static avltree_node_t test_tree_parents(avltree_node_t node);	55	static avltree_node_t test_tree_parents(avltree_node_t node);
58	static void print_tree_structure_flat (avltree_node_t *node, int level);	56	static void print_tree_structure_flat (avltree_node_t *node, int level);
59	static avltree_node_t *alloc_avltree_node(void);	57	static avltree_node_t *alloc_avltree_node(void);
60		58
61		59
62		60
63	static avltree_node_t test_tree_parents(avltree_node_t node)	61	static avltree_node_t test_tree_parents(avltree_node_t node)
64	{	62	{
65	avltree_node_t *tmp;	63	avltree_node_t *tmp;
66		64
67	if (!node) return NULL;	65	if (!node) return NULL;
68		66
69	if (node->lft) {	67	if (node->lft) {
70	tmp = test_tree_parents(node->lft);	68	tmp = test_tree_parents(node->lft);
71	if (tmp != node) {	69	if (tmp != node) {
72	printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->lft);	70	printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->lft);
73	}	71	}
74	}	72	}
75	if (node->rgt) {	73	if (node->rgt) {
76	tmp = test_tree_parents(node->rgt);	74	tmp = test_tree_parents(node->rgt);
77	if (tmp != node) {	75	if (tmp != node) {
78	printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->rgt);	76	printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->rgt);
79	}	77	}
80	}	78	}
81	return node->par;	79	return node->par;
82	}	80	}
83		81
84	int test_tree_balance(avltree_node_t *node)	82	int test_tree_balance(avltree_node_t *node)
85	{	83	{
86	int h1, h2, diff;	84	int h1, h2, diff;
87		85
88	if (!node) return 0;	86	if (!node) return 0;
89	h1 = test_tree_balance(node->lft);	87	h1 = test_tree_balance(node->lft);
90	h2 = test_tree_balance(node->rgt);	88	h2 = test_tree_balance(node->rgt);
91	diff = h2 - h1;	89	diff = h2 - h1;
92	if (diff != node->balance \|\| (diff != -1 && diff != 0 && diff != 1)) {	90	if (diff != node->balance \|\| (diff != -1 && diff != 0 && diff != 1)) {
93	printf("Bad balance\n");	91	printf("Bad balance\n");
94	}	92	}
95	return h1 > h2 ? h1 + 1 : h2 + 1;	93	return h1 > h2 ? h1 + 1 : h2 + 1;
96	}	94	}
97		95
98	/**	96	/**
99	* Prints the structure of node, which is level levels from the top of the tree.	97	* Prints the structure of node, which is level levels from the top of the tree.
100	*/	98	*/
101	static void print_tree_structure_flat (avltree_node_t *node, int level)	99	static void print_tree_structure_flat (avltree_node_t *node, int level)
102	{	100	{
103	/* You can set the maximum level as high as you like.	101	/* You can set the maximum level as high as you like.
104	Most of the time, you'll want to debug code using small trees,	102	Most of the time, you'll want to debug code using small trees,
105	so that a large level indicates a loop, which is a bug. */	103	so that a large level indicates a loop, which is a bug. */
106	if (level > 16)	104	if (level > 16)
107	{	105	{
108	printf ("[...]");	106	printf ("[...]");
109	return;	107	return;
110	}	108	}
111		109
112	if (node == NULL)	110	if (node == NULL)
113	return;	111	return;
114		112
115	printf ("%d[%d]", node->key,node->balance);	113	printf ("%d[%d]", node->key,node->balance);
116	if (node->lft != NULL \|\| node->rgt != NULL)	114	if (node->lft != NULL \|\| node->rgt != NULL)
117	{	115	{
118	printf("(");	116	printf("(");
119		117
120	print_tree_structure_flat (node->lft, level + 1);	118	print_tree_structure_flat (node->lft, level + 1);
121	if (node->rgt != NULL)	119	if (node->rgt != NULL)
122	{	120	{
123	printf(",");	121	printf(",");
124	print_tree_structure_flat (node->rgt, level + 1);	122	print_tree_structure_flat (node->rgt, level + 1);
125	}	123	}
126		124
127	printf(")");	125	printf(")");
128	}	126	}
129	}	127	}
130		128
131		129
132	//****************************************************************	130	//****************************************************************
133	static void alloc_avltree_node_prepare(void)	131	static void alloc_avltree_node_prepare(void)
134	{	132	{
135	int i;	133	int i;
136		134
137	for (i = 0; i < NODE_COUNT - 1; i++) {	135	for (i = 0; i < NODE_COUNT - 1; i++) {
138	avltree_nodes[i].par = &(avltree_nodes[i+1]);	136	avltree_nodes[i].par = &(avltree_nodes[i+1]);
139	}	137	}
140	/*	138	/*
141	* Node keys which will be used for insertion. Up to NODE_COUNT size of array.	139	* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
142	*/	140	*/
143		141
144	// First tree node and same key	142	// First tree node and same key
145	avltree_nodes[0].key = 60;	143	avltree_nodes[0].key = 60;
146	avltree_nodes[1].key = 60;	144	avltree_nodes[1].key = 60;
147	avltree_nodes[2].key = 60;	145	avltree_nodes[2].key = 60;
148	//LL rotation	146	//LL rotation
149	avltree_nodes[3].key = 50;	147	avltree_nodes[3].key = 50;
150	avltree_nodes[4].key = 40;	148	avltree_nodes[4].key = 40;
151	avltree_nodes[5].key = 30;	149	avltree_nodes[5].key = 30;
152	//LR rotation	150	//LR rotation
153	avltree_nodes[6].key = 20;	151	avltree_nodes[6].key = 20;
154	avltree_nodes[7].key = 20;	152	avltree_nodes[7].key = 20;
155	avltree_nodes[8].key = 25;	153	avltree_nodes[8].key = 25;
156	avltree_nodes[9].key = 25;	154	avltree_nodes[9].key = 25;
157	//LL rotation in lower floor	155	//LL rotation in lower floor
158	avltree_nodes[10].key = 35;	156	avltree_nodes[10].key = 35;
159	//RR rotation	157	//RR rotation
160	avltree_nodes[11].key = 70;	158	avltree_nodes[11].key = 70;
161	avltree_nodes[12].key = 80;	159	avltree_nodes[12].key = 80;
162	//RL rotation	160	//RL rotation
163	avltree_nodes[13].key = 90;	161	avltree_nodes[13].key = 90;
164	avltree_nodes[14].key = 85;	162	avltree_nodes[14].key = 85;
-		163	//Insert 0 key
165	avltree_nodes[15].key = 100;	164	avltree_nodes[15].key = 0;
166	avltree_nodes[16].key = 200;	165	avltree_nodes[16].key = 0;
-		166	//Insert reverse
167	avltree_nodes[17].key = 300;	167	avltree_nodes[17].key = 600;
168	avltree_nodes[18].key = 400;	168	avltree_nodes[18].key = 500;
169	avltree_nodes[19].key = 500;	169	avltree_nodes[19].key = 400;
170	avltree_nodes[20].key = 600;	170	avltree_nodes[20].key = 300;
171		171
172	for (i = 21; i < NODE_COUNT; i++)	172	for (i = 21; i < NODE_COUNT; i++)
173	avltree_nodes[i].key = i * 3;	173	avltree_nodes[i].key = i * 3;
174		174
175	avltree_nodes[i].par = NULL;	175	avltree_nodes[i].par = NULL;
176	first_free_node = &(avltree_nodes[0]);	176	first_free_node = &(avltree_nodes[0]);
177	}	177	}
178		178
179	static avltree_node_t *alloc_avltree_node(void)	179	static avltree_node_t *alloc_avltree_node(void)
180	{	180	{
181	avltree_node_t *node;	181	avltree_node_t *node;
182		182
183	node = first_free_node;	183	node = first_free_node;
184	first_free_node = first_free_node->par;	184	first_free_node = first_free_node->par;
185		185
186	return node;	186	return node;
187	}	187	}
188	//****************************************************************	188	//****************************************************************
189		189
190	static void test_tree_insert(avltree_t *tree, unsigned int node_count, int quiet)	190	static void test_tree_insert(avltree_t *tree, unsigned int node_count, int quiet)
191	{	191	{
192	unsigned int i;	192	unsigned int i;
193	avltree_node_t *newnode;	193	avltree_node_t *newnode;
194		194
195	/*	195	/*
196	* Initialize tree before using.	196	* Initialize tree before using.
197	*/	197	*/
198	avltree_create(tree);	198	avltree_create(tree);
199		199
200	if (!quiet) printf("\nInserting %d nodes ...\n", node_count);	200	if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
201		201
202	for (i = 0; i < node_count; i++) {	202	for (i = 0; i < node_count; i++) {
203	newnode = alloc_avltree_node();	203	newnode = alloc_avltree_node();
204	//if (!quiet) printf("[[[%d]]]\n",newnode->key);	204	//if (!quiet) printf("[[[%d]]]\n",newnode->key);
205		205
206	avltree_insert(tree, newnode);	206	avltree_insert(tree, newnode);
207	if (!quiet) {	207	if (!quiet) {
208	test_tree_parents(tree->root);	208	test_tree_parents(tree->root);
209	test_tree_balance(tree->root);	209	test_tree_balance(tree->root);
210	}	210	}
211	}	211	}
212		212
213	if (!quiet) printf("Inserting was finished\n");	213	if (!quiet) printf("Inserting was finished\n");
214	}	214	}
215		215
216		216
217	static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet)	217	static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet)
218	{	218	{
219	avltree_node_t *delnode;	219	avltree_node_t *delnode;
220	unsigned int i;	220	unsigned int i;
221		221
222	//aktualni pocet tiku:	222	//aktualni pocet tiku:
223	if (!quiet) printf("Deleting tree...\n");	223	if (!quiet) printf("Deleting tree...\n");
224		224
225	switch(node_position) {	225	switch(node_position) {
226	case 0: //mazani vzdy korene	226	case 0: //mazani vzdy korene
227	if (!quiet) printf("\nDelete root nodes\n");	227	if (!quiet) printf("\nDelete root nodes\n");
228	while(tree->root != NULL) {	228	while(tree->root != NULL) {
229	delnode = tree->root;	229	delnode = tree->root;
230	avltree_delete(tree,delnode);	230	avltree_delete(tree,delnode);
231	if (!quiet) {	231	if (!quiet) {
232	test_tree_parents(tree->root);	232	test_tree_parents(tree->root);
233	test_tree_balance(tree->root);	233	test_tree_balance(tree->root);
234	}	234	}
235	}	235	}
236		236
237	break;	237	break;
238	case 1:	238	case 1:
239	if (!quiet) printf("\nDelete nodes according to their time of origin\n");	239	if (!quiet) printf("\nDelete nodes according to their time of origin\n");
240	for (i = 0; i < node_count; i++) {	240	for (i = 0; i < node_count; i++) {
241	avltree_delete(tree,&(avltree_nodes[i]));	241	avltree_delete(tree,&(avltree_nodes[i]));
242	if (!quiet) {	242	if (!quiet) {
243	test_tree_parents(tree->root);	243	test_tree_parents(tree->root);
244	test_tree_balance(tree->root);	244	test_tree_balance(tree->root);
245	}	245	}
246	}	246	}
247		247
248	break;	248	break;
249	}	249	}
250		250
251	if (!quiet) printf("Deletion was finished\n");	251	if (!quiet) printf("Deletion was finished\n");
252	}	252	}
253		253
254	static void timeout_tree(avltree_t *tree, int node_count, bool quiet)	254	static void timeout_tree(avltree_t *tree, int node_count, bool quiet)
255	{	255	{
256	int i = 0;	256	int i = 0;
257		257
258	if (!quiet) printf("\nTimeout tree ...\n");	258	if (!quiet) printf("\nTimeout tree ...\n");
259		259
260	while(tree->root != NULL) {	260	while(tree->root != NULL) {
261	i++;	261	i++;
262	avltree_delete_min(tree);	262	avltree_delete_min(tree);
263	if (!quiet) {	263	if (!quiet) {
264	test_tree_parents(tree->root);	264	test_tree_parents(tree->root);
265	test_tree_balance(tree->root);	265	test_tree_balance(tree->root);
266	}	266	}
267	}	267	}
268		268
269	if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n");	269	if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n");
270		270
271	if (!quiet) printf("Timeout tree finished\n");	271	if (!quiet) printf("Timeout tree finished\n");
272	}	272	}
273		273
274	char * test_avltree1(bool quiet)	274	char * test_avltree1(bool quiet)
275	{	275	{
276	alloc_avltree_node_prepare();	276	alloc_avltree_node_prepare();
277	test_tree_insert(&avltree, NODE_COUNT, quiet);	277	test_tree_insert(&avltree, NODE_COUNT, quiet);
278	test_tree_delete(&avltree, NODE_COUNT, 0, quiet);	278	test_tree_delete(&avltree, NODE_COUNT, 0, quiet);
279		279
280	alloc_avltree_node_prepare();	280	alloc_avltree_node_prepare();
281	test_tree_insert(&avltree, NODE_COUNT, quiet);	281	test_tree_insert(&avltree, NODE_COUNT, quiet);
282	test_tree_delete(&avltree, NODE_COUNT, 1, quiet);	282	test_tree_delete(&avltree, NODE_COUNT, 1, quiet);
283		283
284	alloc_avltree_node_prepare();	284	alloc_avltree_node_prepare();
285	test_tree_insert(&avltree, NODE_COUNT, quiet);	285	test_tree_insert(&avltree, NODE_COUNT, quiet);
286	timeout_tree(&avltree, NODE_COUNT, quiet);	286	timeout_tree(&avltree, NODE_COUNT, quiet);
287		287
288	return NULL;	288	return NULL;
289	}	289	}
290		290

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/avltree/avltree1.c @ 2498 – Rev 2421 → 2431