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

Subversion Repositories HelenOS

(root)/tags/0.4.0/kernel/test/avltree/avltree1.c – Rev 3165 → 3888