Subversion Repositories HelenOS

Rev

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