Subversion Repositories HelenOS

Rev

Rev 2431 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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