Subversion Repositories HelenOS

Rev

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

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