Subversion Repositories HelenOS

Rev

Go to most recent revision | Details | 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/extavl.h>
32
#include <debug.h>
33
 
34
#include <panic.h>
35
 
36
 
37
#define NODE_COUNT 100
38
 
39
/*
40
 * wrapper structure with a pointer to extended avl tree root
41
 */
42
static extavltree_t exttree;
43
 
44
/*
45
 * extavltree nodes in array for faster allocating
46
 */
47
static extavltree_node_t extavltree_nodes[NODE_COUNT];
48
 
49
/*
50
 * head of free nodes' list:
51
 */
52
static extavltree_node_t *first_free_node = NULL;
53
 
54
 
55
 
56
static int exttree_test_height(extavltree_node_t *node,bool timeout);
57
static extavltree_node_t *exttree_test_parents(extavltree_node_t *node);
58
static void print_exttree_structure_flat (extavltree_node_t *node, int level);
59
static bool exttree_test_link(int node_count);
60
static void print_exttree_link(int node_count);
61
static extavltree_node_t *alloc_extavltree_node(void);
62
 
63
 
64
 
65
//vraci hloubku stromu
66
static int exttree_test_height(extavltree_node_t *node,bool timeout)
67
{
68
    int h1, h2;
69
 
70
    if (!node) return -1;
71
 
72
    h1 = exttree_test_height(node->lft,timeout) + 1;
73
    if (!timeout && node->lft_height != h1) {
74
        printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node);
75
    }
76
    h2 = exttree_test_height(node->rgt,0) + 1;
77
    if (node->rgt_height != h2) {
78
        printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node);
79
    }
80
    if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) {
81
        printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node);
82
    }
83
 
84
    return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height);
85
}
86
 
87
 
88
/** Tests par atribute of every tree node
89
 *
90
 */
91
static extavltree_node_t *exttree_test_parents(extavltree_node_t *node)
92
{
93
    extavltree_node_t *tmp;
94
 
95
    if (!node) return NULL;
96
 
97
    if (node->lft) {
98
        tmp = exttree_test_parents(node->lft);
99
        if (tmp != node) {
100
            printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft);
101
        }
102
    }
103
    if (node->rgt) {
104
        tmp = exttree_test_parents(node->rgt);
105
        if (tmp != node) {
106
            printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt);
107
        }
108
    }
109
    return node->par;
110
}
111
 
112
/** Checks list of nodes
113
 *
114
 */
115
static bool exttree_test_link(int node_count)
116
{
117
    extavltree_node_t *node;
118
    int i;
119
    bool test_link = true;
120
 
121
    for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) {
122
        if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {
123
            printf("\nList is not sorted (forward direction) at key: %d\n",node->key);
124
            test_link = false;
125
        }
126
    }
127
    if (node_count && i != node_count) {
128
        printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
129
        test_link = false;
130
    }
131
    for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) {
132
        if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {
133
            printf("\nList is not sorted (backward direction) at key: %d\n",node->key);
134
            test_link = false;
135
        }
136
    }
137
    if (node_count && i != node_count) {
138
        printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
139
        test_link = false;
140
    }
141
    return test_link;
142
}
143
 
144
/** Prints the structure of node, which is level levels from the top of the tree.
145
 *
146
 */
147
static void print_exttree_structure_flat (extavltree_node_t *node, int level)
148
{
149
    extavltree_node_t *tmp;
150
    int i;
151
 
152
    if (level > 16)
153
    {
154
        printf ("[...]");
155
        return;
156
    }
157
 
158
    if (node == NULL)
159
        return;
160
 
161
    for (tmp = node,i = 0; tmp->key == node->key; tmp = tmp->next,i++)
162
        ;
163
 
164
    printf ("%d[%d,%d,(%d)]", node->key,node->lft_height,node->rgt_height,i);
165
    if (node->lft != NULL || node->rgt != NULL)
166
    {
167
        printf("(");
168
 
169
        print_exttree_structure_flat (node->lft, level + 1);
170
        if (node->rgt != NULL)
171
        {
172
            printf(",");
173
            print_exttree_structure_flat (node->rgt, level + 1);
174
        }
175
 
176
        printf(")");
177
    }
178
}
179
 
180
/** Prints list of nodes
181
 *
182
 */
183
static void print_exttree_link(int node_count)
184
{
185
    extavltree_node_t *node;
186
    printf("\n");
187
    for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
188
        printf(" %d,",node->key);
189
    }
190
    for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {
191
        printf(" %d,",node->key);
192
    }
193
}
194
 
195
//****************************************************************
196
static void alloc_extavltree_node_prepare(void)
197
{
198
    int i;
199
 
200
    for (i = 0; i < NODE_COUNT - 1; i++) {
201
        extavltree_nodes[i].next = &(extavltree_nodes[i+1]);
202
    }
203
    /*
204
     * Node keys which will be used for insertion. Up to NODE_COUNT size of array.
205
     */
206
 
207
    // First tree node and same key
208
    extavltree_nodes[0].key = 60;
209
    extavltree_nodes[1].key = 60;
210
    extavltree_nodes[2].key = 60;
211
    //LL rotation
212
    extavltree_nodes[3].key = 50;
213
    extavltree_nodes[4].key = 40;
214
    extavltree_nodes[5].key = 30;
215
    //LR rotation
216
    extavltree_nodes[6].key = 20;
217
    extavltree_nodes[7].key = 20;
218
    extavltree_nodes[8].key = 25;
219
    extavltree_nodes[9].key = 25;
220
    //LL rotation in lower floor
221
    extavltree_nodes[10].key = 35;
222
    //RR rotation
223
    extavltree_nodes[11].key = 70;
224
    extavltree_nodes[12].key = 80;
225
    //RL rotation
226
    extavltree_nodes[13].key = 90;
227
    extavltree_nodes[14].key = 85;
228
    extavltree_nodes[15].key = 100;
229
    extavltree_nodes[16].key = 200;
230
    extavltree_nodes[17].key = 300;
231
    extavltree_nodes[18].key = 400;
232
    extavltree_nodes[19].key = 500;
233
    extavltree_nodes[20].key = 600;
234
 
235
    for (i = 21; i < NODE_COUNT; i++)
236
        extavltree_nodes[i].key = i * 3;
237
 
238
    extavltree_nodes[i].next = NULL;
239
    first_free_node = &(extavltree_nodes[0]);
240
}
241
 
242
static extavltree_node_t *alloc_extavltree_node(void)
243
{
244
    extavltree_node_t *node;
245
 
246
    node = first_free_node;
247
    first_free_node = first_free_node->next;
248
 
249
    return node;
250
}
251
//****************************************************************
252
 
253
static void test_exttree_insert(extavltree_t *tree, unsigned int node_count, int quiet)
254
{
255
    unsigned int i;
256
    extavltree_node_t *newnode;
257
 
258
    /*
259
     * Initialize tree before using.
260
     */
261
    extavltree_create(tree);
262
 
263
    if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
264
 
265
    for (i = 0; i < node_count; i++) {
266
        newnode = alloc_extavltree_node();
267
        //if (!quiet) printf("[[[%d]]]\n",newnode->key);
268
 
269
        extavltree_insert(tree, newnode);
270
        if (!quiet) {
271
            if (!exttree_test_link(i+1)) {
272
                print_exttree_link(i+1);
273
                printf("\n");
274
            }
275
            exttree_test_parents(tree->root);
276
            exttree_test_height(tree->root,1);
277
        }
278
    }
279
 
280
    if (!quiet) printf("Inserting was finished\n");
281
}
282
 
283
/*
284
static extavltree_node_t *exttree_random_delete_node(extavltree_t *tree, int node_count, int r, bool quiet)
285
{
286
    extavltree_node_t *delnode;
287
    int i;
288
 
289
    for (i = 0,delnode = tree->head.next; i < (r-1); i++)
290
        delnode = delnode->next;
291
 
292
    if (delnode == &tree->head) {
293
        if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);
294
        return NULL;
295
    }
296
 
297
    extavltree_delete(tree, delnode);
298
 
299
    return delnode;
300
}
301
*/
302
 
303
static void test_exttree_delete(extavltree_t *tree, int node_count, int node_position, bool quiet)
304
{
305
    extavltree_node_t *delnode;
306
    unsigned int i;
307
 
308
    //aktualni pocet tiku:
309
    if (!quiet) printf("Deleting tree...\n");
310
 
311
    switch(node_position) {
312
        case 0: //mazani vzdy korene
313
            if (!quiet) printf("\n\nDelete root nodes\n");
314
            i = node_count;
315
            while(tree->root != NULL) {
316
                delnode = tree->root;
317
                extavltree_delete(tree,delnode);
318
                if (!quiet) {
319
                    if (!exttree_test_link(i)) {
320
                        print_exttree_link(i);
321
                        printf("\n");
322
                    }
323
                    exttree_test_parents(tree->root);
324
                    exttree_test_height(tree->root,1);
325
                }
326
                i--;
327
            }
328
 
329
            break;
330
        case 1:
331
            if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
332
            for (i = 0; i < node_count; i++) {
333
                extavltree_delete(tree,&(extavltree_nodes[i]));
334
                if (!quiet) {
335
                    if (!exttree_test_link(i+1)) {
336
                        print_exttree_link(i+1);
337
                        printf("\n");
338
                    }
339
                    exttree_test_parents(tree->root);
340
                    exttree_test_height(tree->root,1);
341
                }
342
            }
343
 
344
            break; 
345
    }
346
 
347
    if (!quiet) printf("Deletion was finished\n");
348
}
349
 
350
static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)
351
{
352
    int i = node_count;
353
 
354
    if (!quiet) printf("Timeout tree ...\n");
355
 
356
    while(tree->head.next != &(tree->head)) {
357
        extavltree_delete_min(tree);
358
        if (!quiet) {
359
            if (!exttree_test_link(i)) {
360
                print_exttree_link(i);
361
                printf("\n");
362
            }
363
            exttree_test_parents(tree->root);
364
            exttree_test_height(tree->root,1);
365
        }
366
        i--;
367
    }
368
 
369
    if (!quiet && (i != 0)) printf("Bad node count. Some nodes have been lost!");
370
 
371
    if (!quiet) printf("Timeout tree finished\n");
372
}
373
 
374
/*
375
void timeout_exttree_run(extavltree_t *tree, int operation_count, int verbal)
376
{
377
    int i;
378
    extavltree_node_t *node;
379
    int r;
380
    int count;
381
 
382
    //inicializace stromu:
383
    extavltree_create(tree);
384
 
385
    for(i = 0, count = 0; i < operation_count; i++) {
386
        if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {
387
            if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne
388
                node = exttree_random_delete_node(tree,(r % tree->count));
389
                //printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
390
                node->next = first_free_node;
391
                first_free_node = node;
392
            } else {
393
                node = tree->head.next;
394
                extavltree_delete_min(tree);
395
                //printf("TIMEOUT key: %d, address: %p\n",node->key,node);
396
                node->next = first_free_node;
397
                first_free_node = node;
398
            }
399
            } else {
400
                    node = alloc_extavltree_node_random();
401
            //printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
402
            extavltree_insert(tree, node);
403
            }
404
        //test_exttree_height(tree->root,1);
405
        //exttree_test_parents(tree->root);    
406
        //print_exttree_link(tree->count);
407
        //print_exttree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
408
    }
409
}
410
*/
411
 
412
char * test_extavltree1(bool quiet)
413
{
414
    alloc_extavltree_node_prepare();
415
    test_exttree_insert(&exttree, NODE_COUNT, quiet);
416
    test_exttree_delete(&exttree, NODE_COUNT, 0, quiet);
417
 
418
    alloc_extavltree_node_prepare();
419
    test_exttree_insert(&exttree, NODE_COUNT, quiet);
420
    test_exttree_delete(&exttree, NODE_COUNT, 1, quiet);
421
 
422
    alloc_extavltree_node_prepare();
423
    test_exttree_insert(&exttree, NODE_COUNT, quiet);
424
    timeout_exttree(&exttree, NODE_COUNT, quiet);
425
 
426
    return NULL;
427
}