Subversion Repositories HelenOS

Rev

Rev 2745 | Rev 3149 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

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