Changeset cb01e1e in mainline for kernel/test/avltree/avltree1.c


Ignore:
Timestamp:
2009-04-04T00:26:27Z (16 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
a85aebd
Parents:
171f9a1
Message:

use global variable and a macro for silencing tests

File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/test/avltree/avltree1.c

    r171f9a1 rcb01e1e  
    4242static avltree_node_t avltree_nodes[NODE_COUNT];
    4343
    44 /* 
     44/*
    4545 * head of free nodes' list:
    4646 */
    … …  
    5959        if (!node)
    6060                return NULL;
    61 
     61       
    6262        if (node->lft) {
    6363                tmp = test_tree_parents(node->lft);
    6464                if (tmp != node) {
    65                         printf("Bad parent pointer key: %" PRIu64
     65                        TPRINTF("Bad parent pointer key: %" PRIu64
    6666                            ", address: %p\n", tmp->key, node->lft);
    6767                }
    … …  
    7070                tmp = test_tree_parents(node->rgt);
    7171                if (tmp != node) {
    72                         printf("Bad parent pointer key: %" PRIu64
     72                        TPRINTF("Bad parent pointer key: %" PRIu64
    7373                            ", address: %p\n",
    7474                            tmp->key,node->rgt);
    … …  
    8181{
    8282        int h1, h2, diff;
    83 
     83       
    8484        if (!node)
    8585                return 0;
     86       
    8687        h1 = test_tree_balance(node->lft);
    8788        h2 = test_tree_balance(node->rgt);
    8889        diff = h2 - h1;
    89         if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) {
    90                 printf("Bad balance\n");
    91         }
    92         return h1 > h2 ? h1 + 1 : h2 + 1;
     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));
    9395}
    9496
    9597/**
    9698 * Prints the structure of the node, which is level levels from the top of the
    97  * tree.
    98  */
    99 static void
    100 print_tree_structure_flat(avltree_node_t *node, int level)
     99 * tree.
     100 */
     101static void print_tree_structure_flat(avltree_node_t *node, int level)
    101102{
    102103        /*
    103104         * 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          * so that a large level indicates a loop, which is a bug.
     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.
    106107         */
    107108        if (level > 16) {
    108                 printf("[...]");
     109                TPRINTF("[...]");
    109110                return;
    110111        }
    111 
     112       
    112113        if (node == NULL)
    113114                return;
    114 
    115         printf("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance);
     115       
     116        TPRINTF("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance);
    116117        if (node->lft != NULL || node->rgt != NULL) {
    117                 printf("(");
    118 
     118                TPRINTF("(");
     119               
    119120                print_tree_structure_flat(node->lft, level + 1);
    120121                if (node->rgt != NULL) {
    121                         printf(",");
     122                        TPRINTF(",");
    122123                        print_tree_structure_flat(node->rgt, level + 1);
    123124                }
    124 
    125                 printf(")");
     125               
     126                TPRINTF(")");
    126127        }
    127128}
    … …  
    130131{
    131132        int i;
    132 
    133         for (i = 0; i < NODE_COUNT - 1; i++) {
     133       
     134        for (i = 0; i < NODE_COUNT - 1; i++)
    134135                avltree_nodes[i].par = &avltree_nodes[i + 1];
    135         }
     136       
    136137        avltree_nodes[i].par = NULL;
    137138       
    … …  
    140141         * array.
    141142         */
    142 
     143       
    143144        /* First tree node and same key */
    144145        avltree_nodes[0].key = 60;
    145146        avltree_nodes[1].key = 60;
    146147        avltree_nodes[2].key = 60;
     148       
    147149        /* LL rotation */
    148150        avltree_nodes[3].key = 50;
    149151        avltree_nodes[4].key = 40;
    150152        avltree_nodes[5].key = 30;
     153       
    151154        /* LR rotation */
    152155        avltree_nodes[6].key = 20;
    … …  
    154157        avltree_nodes[8].key = 25;
    155158        avltree_nodes[9].key = 25;
     159       
    156160        /* LL rotation in lower floor */
    157161        avltree_nodes[10].key = 35;
     162       
    158163        /* RR rotation */
    159164        avltree_nodes[11].key = 70;
    160165        avltree_nodes[12].key = 80;
     166       
    161167        /* RL rotation */
    162168        avltree_nodes[13].key = 90;
    163169        avltree_nodes[14].key = 85;
     170       
    164171        /* Insert 0 key */
    165172        avltree_nodes[15].key = 0;
    166173        avltree_nodes[16].key = 0;
     174       
    167175        /* Insert reverse */
    168176        avltree_nodes[17].key = 600;
    … …  
    170178        avltree_nodes[19].key = 400;
    171179        avltree_nodes[20].key = 300;
    172 
     180       
    173181        for (i = 21; i < NODE_COUNT; i++)
    174182                avltree_nodes[i].key = i * 3;
    … …  
    180188{
    181189        avltree_node_t *node;
    182 
     190       
    183191        node = first_free_node;
    184192        first_free_node = first_free_node->par;
    185 
     193       
    186194        return node;
    187195}
    188196
    189 static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet)
     197static void test_tree_insert(avltree_t *tree, count_t node_count)
    190198{
    191199        unsigned int i;
    192200        avltree_node_t *newnode;
    193 
     201       
    194202        avltree_create(tree);
    195203       
    196         if (!quiet)
    197                 printf("Inserting %" PRIc " nodes...", node_count);
    198 
     204        TPRINTF("Inserting %" PRIc " nodes...", node_count);
     205       
    199206        for (i = 0; i < node_count; i++) {
    200207                newnode = alloc_avltree_node();
    201208               
    202209                avltree_insert(tree, newnode);
    203                 if (!quiet) {
    204                         test_tree_parents(tree->root);
    205                         test_tree_balance(tree->root);
    206                 }
    207         }
    208                
    209         if (!quiet)
    210                 printf("done.\n");
    211 }
    212 
     210                test_tree_parents(tree->root);
     211                test_tree_balance(tree->root);
     212        }
     213       
     214        TPRINTF("done.\n");
     215}
    213216
    214217static void test_tree_delete(avltree_t *tree, count_t node_count,
    215     int node_position, bool quiet)
     218    int node_position)
    216219{
    217220        avltree_node_t *delnode;
    … …  
    220223        switch (node_position) {
    221224        case 0:
    222                 if (!quiet)
    223                         printf("Deleting root nodes...");
     225                TPRINTF("Deleting root nodes...");
     226               
    224227                while (tree->root != NULL) {
    225228                        delnode = tree->root;
    226229                        avltree_delete(tree, delnode);
    227                         if (!quiet) {
    228                                 test_tree_parents(tree->root);
    229                                 test_tree_balance(tree->root);
    230                         }
    231                 }
     230                        test_tree_parents(tree->root);
     231                        test_tree_balance(tree->root);
     232                }
    232233                break;
    233234        case 1:
    234                 if (!quiet)
    235                         printf("Deleting nodes according to creation time...");
     235                TPRINTF("Deleting nodes according to creation time...");
     236               
    236237                for (i = 0; i < node_count; i++) {
    237238                        avltree_delete(tree, &avltree_nodes[i]);
    238                         if (!quiet) {
    239                                 test_tree_parents(tree->root);
    240                                 test_tree_balance(tree->root);
    241                         }
    242                 }
    243                 break; 
    244         }
    245        
    246         if (!quiet)
    247                 printf("done.\n");
    248 }
    249 
    250 static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet)
     239                        test_tree_parents(tree->root);
     240                        test_tree_balance(tree->root);
     241                }
     242                break;
     243        }
     244       
     245        TPRINTF("done.\n");
     246}
     247
     248static void test_tree_delmin(avltree_t *tree, count_t node_count)
    251249{
    252250        unsigned int i = 0;
    253251       
    254         if (!quiet)
    255                 printf("Deleting minimum nodes...");
     252        TPRINTF("Deleting minimum nodes...");
    256253       
    257254        while (tree->root != NULL) {
    258255                i++;
    259256                avltree_delete_min(tree);
    260                 if (!quiet) {
    261                         test_tree_parents(tree->root);
    262                         test_tree_balance(tree->root);
    263                 }
    264         }
    265 
    266         if (!quiet && (i != node_count))
    267                 printf("Bad node count. Some nodes have been lost!\n");
    268 
    269         if (!quiet)
    270                 printf("done.\n");
    271 }
    272 
    273 char *test_avltree1(bool quiet)
     257                test_tree_parents(tree->root);
     258                test_tree_balance(tree->root);
     259        }
     260       
     261        if (i != node_count)
     262                TPRINTF("Bad node count. Some nodes have been lost!\n");
     263       
     264        TPRINTF("done.\n");
     265}
     266
     267char *test_avltree1(void)
    274268{
    275269        alloc_avltree_node_prepare();
    276         test_tree_insert(&avltree, NODE_COUNT, quiet);
    277         test_tree_delete(&avltree, NODE_COUNT, 0, quiet);
    278 
     270        test_tree_insert(&avltree, NODE_COUNT);
     271        test_tree_delete(&avltree, NODE_COUNT, 0);
     272       
    279273        alloc_avltree_node_prepare();
    280         test_tree_insert(&avltree, NODE_COUNT, quiet);
    281         test_tree_delete(&avltree, NODE_COUNT, 1, quiet);
    282 
     274        test_tree_insert(&avltree, NODE_COUNT);
     275        test_tree_delete(&avltree, NODE_COUNT, 1);
     276       
    283277        alloc_avltree_node_prepare();
    284         test_tree_insert(&avltree, NODE_COUNT, quiet);
    285         test_tree_delmin(&avltree, NODE_COUNT, quiet);
    286 
     278        test_tree_insert(&avltree, NODE_COUNT);
     279        test_tree_delmin(&avltree, NODE_COUNT);
     280       
    287281        return NULL;
    288282}
    289 
Note: See TracChangeset for help on using the changeset viewer.