Subversion Repositories HelenOS

Rev

Rev 2927 | Rev 3191 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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