source: mainline/kernel/test/avltree/avltree1.c@ 4a23cb6

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 4a23cb6 was 4a23cb6, checked in by Jakub Jermar <jakub@…>, 17 years ago

Fix an off-by-one bug in avltree1 test and also declare an unused static
function as used. These two bugs were breaking building by gcc 4.3.1.
  • Property mode set to 100644
File size: 6.9 KB
Line 
1/*
2 * Copyright (c) 2007 Vojtech Mencl
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
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
15 * derived from this software without specific prior written permission.
16 *
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
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
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
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
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#include <test.h>
30#include <print.h>
31#include <adt/avl.h>
32#include <debug.h>
33#include <arch/types.h>
34
35#define NODE_COUNT 100
36
37static avltree_t avltree;
38
39/*
40 * avl tree nodes in array for faster allocation
41 */
42static avltree_node_t avltree_nodes[NODE_COUNT];
43
44/*
45 * head of free nodes' list:
46 */
47static avltree_node_t *first_free_node = NULL;
48
49static int test_tree_balance(avltree_node_t *node);
50static avltree_node_t *test_tree_parents(avltree_node_t *node);
51static void print_tree_structure_flat (avltree_node_t *node, int level)
52 __attribute__ ((used));
53static avltree_node_t *alloc_avltree_node(void);
54
55static avltree_node_t *test_tree_parents(avltree_node_t *node)
56{
57 avltree_node_t *tmp;
58
59 if (!node)
60 return NULL;
61
62 if (node->lft) {
63 tmp = test_tree_parents(node->lft);
64 if (tmp != node) {
65 printf("Bad parent pointer key: %" PRIu64
66 ", address: %p\n", tmp->key, node->lft);
67 }
68 }
69 if (node->rgt) {
70 tmp = test_tree_parents(node->rgt);
71 if (tmp != node) {
72 printf("Bad parent pointer key: %" PRIu64
73 ", address: %p\n",
74 tmp->key,node->rgt);
75 }
76 }
77 return node->par;
78}
79
80int test_tree_balance(avltree_node_t *node)
81{
82 int h1, h2, diff;
83
84 if (!node)
85 return 0;
86 h1 = test_tree_balance(node->lft);
87 h2 = test_tree_balance(node->rgt);
88 diff = h2 - h1;
89 if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) {
90 printf("Bad balance\n");
91 }
92 return h1 > h2 ? h1 + 1 : h2 + 1;
93}
94
95/**
96 * Prints the structure of the node, which is level levels from the top of the
97 * tree.
98 */
99static void
100print_tree_structure_flat(avltree_node_t *node, int level)
101{
102 /*
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,
105 * so that a large level indicates a loop, which is a bug.
106 */
107 if (level > 16) {
108 printf("[...]");
109 return;
110 }
111
112 if (node == NULL)
113 return;
114
115 printf("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance);
116 if (node->lft != NULL || node->rgt != NULL) {
117 printf("(");
118
119 print_tree_structure_flat(node->lft, level + 1);
120 if (node->rgt != NULL) {
121 printf(",");
122 print_tree_structure_flat(node->rgt, level + 1);
123 }
124
125 printf(")");
126 }
127}
128
129static void alloc_avltree_node_prepare(void)
130{
131 int i;
132
133 for (i = 0; i < NODE_COUNT - 1; i++) {
134 avltree_nodes[i].par = &avltree_nodes[i + 1];
135 }
136 avltree_nodes[i].par = NULL;
137
138 /*
139 * Node keys which will be used for insertion. Up to NODE_COUNT size of
140 * array.
141 */
142
143 /* First tree node and same key */
144 avltree_nodes[0].key = 60;
145 avltree_nodes[1].key = 60;
146 avltree_nodes[2].key = 60;
147 /* LL rotation */
148 avltree_nodes[3].key = 50;
149 avltree_nodes[4].key = 40;
150 avltree_nodes[5].key = 30;
151 /* LR rotation */
152 avltree_nodes[6].key = 20;
153 avltree_nodes[7].key = 20;
154 avltree_nodes[8].key = 25;
155 avltree_nodes[9].key = 25;
156 /* LL rotation in lower floor */
157 avltree_nodes[10].key = 35;
158 /* RR rotation */
159 avltree_nodes[11].key = 70;
160 avltree_nodes[12].key = 80;
161 /* RL rotation */
162 avltree_nodes[13].key = 90;
163 avltree_nodes[14].key = 85;
164 /* Insert 0 key */
165 avltree_nodes[15].key = 0;
166 avltree_nodes[16].key = 0;
167 /* Insert reverse */
168 avltree_nodes[17].key = 600;
169 avltree_nodes[18].key = 500;
170 avltree_nodes[19].key = 400;
171 avltree_nodes[20].key = 300;
172
173 for (i = 21; i < NODE_COUNT; i++)
174 avltree_nodes[i].key = i * 3;
175
176 first_free_node = &avltree_nodes[0];
177}
178
179static avltree_node_t *alloc_avltree_node(void)
180{
181 avltree_node_t *node;
182
183 node = first_free_node;
184 first_free_node = first_free_node->par;
185
186 return node;
187}
188
189static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet)
190{
191 unsigned int i;
192 avltree_node_t *newnode;
193
194 avltree_create(tree);
195
196 if (!quiet)
197 printf("Inserting %" PRIc " nodes...", node_count);
198
199 for (i = 0; i < node_count; i++) {
200 newnode = alloc_avltree_node();
201
202 avltree_insert(tree, newnode);
203 if (!quiet) {
204 test_tree_parents(tree->root);
205 test_tree_balance(tree->root);
206 }
207 }
208
209 if (!quiet)
210 printf("done.\n");
211}
212
213
214static void test_tree_delete(avltree_t *tree, count_t node_count,
215 int node_position, bool quiet)
216{
217 avltree_node_t *delnode;
218 unsigned int i;
219
220 switch (node_position) {
221 case 0:
222 if (!quiet)
223 printf("Deleting root nodes...");
224 while (tree->root != NULL) {
225 delnode = tree->root;
226 avltree_delete(tree, delnode);
227 if (!quiet) {
228 test_tree_parents(tree->root);
229 test_tree_balance(tree->root);
230 }
231 }
232 break;
233 case 1:
234 if (!quiet)
235 printf("Deleting nodes according to creation time...");
236 for (i = 0; i < node_count; i++) {
237 avltree_delete(tree, &avltree_nodes[i]);
238 if (!quiet) {
239 test_tree_parents(tree->root);
240 test_tree_balance(tree->root);
241 }
242 }
243 break;
244 }
245
246 if (!quiet)
247 printf("done.\n");
248}
249
250static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet)
251{
252 unsigned int i = 0;
253
254 if (!quiet)
255 printf("Deleting minimum nodes...");
256
257 while (tree->root != NULL) {
258 i++;
259 avltree_delete_min(tree);
260 if (!quiet) {
261 test_tree_parents(tree->root);
262 test_tree_balance(tree->root);
263 }
264 }
265
266 if (!quiet && (i != node_count))
267 printf("Bad node count. Some nodes have been lost!\n");
268
269 if (!quiet)
270 printf("done.\n");
271}
272
273char *test_avltree1(bool quiet)
274{
275 alloc_avltree_node_prepare();
276 test_tree_insert(&avltree, NODE_COUNT, quiet);
277 test_tree_delete(&avltree, NODE_COUNT, 0, quiet);
278
279 alloc_avltree_node_prepare();
280 test_tree_insert(&avltree, NODE_COUNT, quiet);
281 test_tree_delete(&avltree, NODE_COUNT, 1, quiet);
282
283 alloc_avltree_node_prepare();
284 test_tree_insert(&avltree, NODE_COUNT, quiet);
285 test_tree_delmin(&avltree, NODE_COUNT, quiet);
286
287 return NULL;
288}
289
Note: See TracBrowser for help on using the repository browser.