← Back to branch summary

~vojtech-horky/helenos/numa

« back to all changes in this revision

Viewing changes to kernel/test/avltree/avltree1.c

  • Committer: Martin Decky
  • Date: 2009-08-04 11:19:19 UTC
  • Revision ID: martin@uranus.dsrg.hide.ms.mff.cuni.cz-20090804111919-evyclddlr3v5lhmp
Initial import

Show diffs side-by-side

added added

removed removed

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