WebSVN – HelenOS – Diff – /branches/dd/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>
#include <arch/types.h>
 
#define NODE_COUNT 100
 
static avltree_t avltree;
 
/*
 * avl tree nodes in array for faster allocation
 */
static avltree_node_t avltree_nodes[NODE_COUNT];
 
/*
 * head of free nodes' list:
 */
static avltree_node_t *first_free_node = NULL;
 
static int test_tree_balance(avltree_node_t *node);
static avltree_node_t *test_tree_parents(avltree_node_t *node);
static void print_tree_structure_flat (avltree_node_t *node, int level)
    __attribute__ ((used));
static avltree_node_t *alloc_avltree_node(void);
 
static avltree_node_t *test_tree_parents(avltree_node_t *node)
{
    avltree_node_t *tmp;
   
    if (!node)
        return NULL;
 
    if (node->lft) {
        tmp = test_tree_parents(node->lft);
        if (tmp != node) {
            printf("Bad parent pointer key: %" PRIu64
                ", address: %p\n", tmp->key, node->lft);
        }
    }
    if (node->rgt) {
        tmp = test_tree_parents(node->rgt);
        if (tmp != node) {
            printf("Bad parent pointer key: %" PRIu64
                ", address: %p\n",
                tmp->key,node->rgt);
        }
    }
    return node->par;
}
 
int test_tree_balance(avltree_node_t *node)
{
    int h1, h2, diff;
 
    if (!node)
        return 0;
    h1 = test_tree_balance(node->lft);
    h2 = test_tree_balance(node->rgt);
    diff = h2 - h1;
    if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) {
        printf("Bad balance\n");
    }
    return h1 > h2 ? h1 + 1 : h2 + 1;
}
 
/**
 * Prints the structure of the node, which is level levels from the top of the
 * tree.
 */
static void
print_tree_structure_flat(avltree_node_t *node, int level)
{
    /*
     * You can set the maximum level as high as you like.
         * Most of the time, you'll want to debug code using small trees,
         * so that a large level indicates a loop, which is a bug.
     */
    if (level > 16) {
        printf("[...]");
        return;
    }
 
    if (node == NULL)
        return;
 
    printf("%" PRIu64 "[%" PRIu8 "]", 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];
    }
    avltree_nodes[i].par = NULL;
   
    /*
     * Node keys which will be used for insertion. Up to NODE_COUNT size of
     * array.
     */
 
    /* First tree node and same key */
    avltree_nodes[0].key = 60;
    avltree_nodes[1].key = 60;
    avltree_nodes[2].key = 60;
    /* LL rotation */
    avltree_nodes[3].key = 50;
    avltree_nodes[4].key = 40;
    avltree_nodes[5].key = 30;
    /* LR rotation */
    avltree_nodes[6].key = 20;
    avltree_nodes[7].key = 20;
    avltree_nodes[8].key = 25;
    avltree_nodes[9].key = 25;
    /* LL rotation in lower floor */
    avltree_nodes[10].key = 35;
    /* RR rotation */
    avltree_nodes[11].key = 70;
    avltree_nodes[12].key = 80;
    /* RL rotation */
    avltree_nodes[13].key = 90;
    avltree_nodes[14].key = 85;
    /* Insert 0 key */
    avltree_nodes[15].key = 0;
    avltree_nodes[16].key = 0;
    /* Insert reverse */
    avltree_nodes[17].key = 600;
    avltree_nodes[18].key = 500;
    avltree_nodes[19].key = 400;
    avltree_nodes[20].key = 300;
 
    for (i = 21; i < NODE_COUNT; i++)
        avltree_nodes[i].key = i * 3;
   
 
    first_free_node = &avltree_nodes[0];
}
 
static avltree_node_t *alloc_avltree_node(void)
{
    avltree_node_t *node;
 
    node = first_free_node;
    first_free_node = first_free_node->par;
 
    return node;
}
 
static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet)
{
    unsigned int i;
    avltree_node_t *newnode;
 
    avltree_create(tree);
   
    if (!quiet)
        printf("Inserting %" PRIc " nodes...", node_count);
 
    for (i = 0; i < node_count; i++) {
        newnode = alloc_avltree_node();
       
        avltree_insert(tree, newnode);
        if (!quiet) {
            test_tree_parents(tree->root);
            test_tree_balance(tree->root);
        }
    }
       
    if (!quiet)
        printf("done.\n");
}
 
 
static void test_tree_delete(avltree_t *tree, count_t node_count,
    int node_position, bool quiet)
{
    avltree_node_t *delnode;
    unsigned int i;
   
    switch (node_position) {
    case 0:
        if (!quiet)
            printf("Deleting root nodes...");
        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("Deleting nodes according to creation time...");
        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("done.\n");
}
 
static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet)
{
    unsigned int i = 0;
   
    if (!quiet)
        printf("Deleting minimum nodes...");
   
    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("done.\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);
    test_tree_delmin(&avltree, NODE_COUNT, quiet);
 
    return NULL;
}
 
 

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

Subversion Repositories HelenOS

(root)/branches/dd/kernel/test/avltree/avltree1.c – Rev 3022 → 4055