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

Subversion Repositories HelenOS

(root)/branches/dynload/kernel/test/avltree/avltree1.c – Rev 2927 → 3149