Index: kernel/test/avltree/avltree1.c =================================================================== --- kernel/test/avltree/avltree1.c (revision 8a72a9ab5a133d8b33aa20a89b8d996a84ba6d60) +++ kernel/test/avltree/avltree1.c (revision cb01e1ee9f069d7d14148e3efc3cb37d1011b8de) @@ -42,5 +42,5 @@ static avltree_node_t avltree_nodes[NODE_COUNT]; -/* +/* * head of free nodes' list: */ @@ -59,9 +59,9 @@ if (!node) return NULL; - + if (node->lft) { tmp = test_tree_parents(node->lft); if (tmp != node) { - printf("Bad parent pointer key: %" PRIu64 + TPRINTF("Bad parent pointer key: %" PRIu64 ", address: %p\n", tmp->key, node->lft); } @@ -70,5 +70,5 @@ tmp = test_tree_parents(node->rgt); if (tmp != node) { - printf("Bad parent pointer key: %" PRIu64 + TPRINTF("Bad parent pointer key: %" PRIu64 ", address: %p\n", tmp->key,node->rgt); @@ -81,47 +81,48 @@ { int h1, h2, diff; - + if (!node) return 0; + h1 = test_tree_balance(node->lft); h2 = test_tree_balance(node->rgt); diff = h2 - h1; - if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) { - printf("Bad balance\n"); - } - return h1 > h2 ? h1 + 1 : h2 + 1; + + if ((diff != node->balance) || ((diff != -1) && (diff != 0) && (diff != 1))) + TPRINTF("Bad balance\n"); + + return ((h1 > h2) ? (h1 + 1) : (h2 + 1)); } /** * Prints the structure of the node, which is level levels from the top of the - * tree. - */ -static void -print_tree_structure_flat(avltree_node_t *node, int level) + * tree. + */ +static void print_tree_structure_flat(avltree_node_t *node, int level) { /* * You can set the maximum level as high as you like. - * Most of the time, you'll want to debug code using small trees, - * so that a large level indicates a loop, which is a bug. + * Most of the time, you'll want to debug code using small trees, + * so that a large level indicates a loop, which is a bug. */ if (level > 16) { - printf("[...]"); + TPRINTF("[...]"); return; } - + if (node == NULL) return; - - printf("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance); + + TPRINTF("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance); if (node->lft != NULL || node->rgt != NULL) { - printf("("); - + TPRINTF("("); + print_tree_structure_flat(node->lft, level + 1); if (node->rgt != NULL) { - printf(","); + TPRINTF(","); print_tree_structure_flat(node->rgt, level + 1); } - - printf(")"); + + TPRINTF(")"); } } @@ -130,8 +131,8 @@ { int i; - - for (i = 0; i < NODE_COUNT - 1; i++) { + + for (i = 0; i < NODE_COUNT - 1; i++) avltree_nodes[i].par = &avltree_nodes[i + 1]; - } + avltree_nodes[i].par = NULL; @@ -140,13 +141,15 @@ * array. */ - + /* First tree node and same key */ avltree_nodes[0].key = 60; avltree_nodes[1].key = 60; avltree_nodes[2].key = 60; + /* LL rotation */ avltree_nodes[3].key = 50; avltree_nodes[4].key = 40; avltree_nodes[5].key = 30; + /* LR rotation */ avltree_nodes[6].key = 20; @@ -154,15 +157,20 @@ avltree_nodes[8].key = 25; avltree_nodes[9].key = 25; + /* LL rotation in lower floor */ avltree_nodes[10].key = 35; + /* RR rotation */ avltree_nodes[11].key = 70; avltree_nodes[12].key = 80; + /* RL rotation */ avltree_nodes[13].key = 90; avltree_nodes[14].key = 85; + /* Insert 0 key */ avltree_nodes[15].key = 0; avltree_nodes[16].key = 0; + /* Insert reverse */ avltree_nodes[17].key = 600; @@ -170,5 +178,5 @@ avltree_nodes[19].key = 400; avltree_nodes[20].key = 300; - + for (i = 21; i < NODE_COUNT; i++) avltree_nodes[i].key = i * 3; @@ -180,38 +188,33 @@ { avltree_node_t *node; - + node = first_free_node; first_free_node = first_free_node->par; - + return node; } -static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet) +static void test_tree_insert(avltree_t *tree, count_t node_count) { unsigned int i; avltree_node_t *newnode; - + avltree_create(tree); - if (!quiet) - printf("Inserting %" PRIc " nodes...", node_count); - + TPRINTF("Inserting %" PRIc " nodes...", node_count); + for (i = 0; i < node_count; i++) { newnode = alloc_avltree_node(); avltree_insert(tree, newnode); - if (!quiet) { - test_tree_parents(tree->root); - test_tree_balance(tree->root); - } - } - - if (!quiet) - printf("done.\n"); -} - + test_tree_parents(tree->root); + test_tree_balance(tree->root); + } + + TPRINTF("done.\n"); +} static void test_tree_delete(avltree_t *tree, count_t node_count, - int node_position, bool quiet) + int node_position) { avltree_node_t *delnode; @@ -220,70 +223,60 @@ switch (node_position) { case 0: - if (!quiet) - printf("Deleting root nodes..."); + TPRINTF("Deleting root nodes..."); + while (tree->root != NULL) { delnode = tree->root; avltree_delete(tree, delnode); - if (!quiet) { - test_tree_parents(tree->root); - test_tree_balance(tree->root); - } - } + test_tree_parents(tree->root); + test_tree_balance(tree->root); + } break; case 1: - if (!quiet) - printf("Deleting nodes according to creation time..."); + TPRINTF("Deleting nodes according to creation time..."); + for (i = 0; i < node_count; i++) { avltree_delete(tree, &avltree_nodes[i]); - if (!quiet) { - test_tree_parents(tree->root); - test_tree_balance(tree->root); - } - } - break; - } - - if (!quiet) - printf("done.\n"); -} - -static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet) + test_tree_parents(tree->root); + test_tree_balance(tree->root); + } + break; + } + + TPRINTF("done.\n"); +} + +static void test_tree_delmin(avltree_t *tree, count_t node_count) { unsigned int i = 0; - if (!quiet) - printf("Deleting minimum nodes..."); + TPRINTF("Deleting minimum nodes..."); while (tree->root != NULL) { i++; avltree_delete_min(tree); - if (!quiet) { - test_tree_parents(tree->root); - test_tree_balance(tree->root); - } - } - - if (!quiet && (i != node_count)) - printf("Bad node count. Some nodes have been lost!\n"); - - if (!quiet) - printf("done.\n"); -} - -char *test_avltree1(bool quiet) + test_tree_parents(tree->root); + test_tree_balance(tree->root); + } + + if (i != node_count) + TPRINTF("Bad node count. Some nodes have been lost!\n"); + + TPRINTF("done.\n"); +} + +char *test_avltree1(void) { alloc_avltree_node_prepare(); - test_tree_insert(&avltree, NODE_COUNT, quiet); - test_tree_delete(&avltree, NODE_COUNT, 0, quiet); - + test_tree_insert(&avltree, NODE_COUNT); + test_tree_delete(&avltree, NODE_COUNT, 0); + alloc_avltree_node_prepare(); - test_tree_insert(&avltree, NODE_COUNT, quiet); - test_tree_delete(&avltree, NODE_COUNT, 1, quiet); - + test_tree_insert(&avltree, NODE_COUNT); + test_tree_delete(&avltree, NODE_COUNT, 1); + alloc_avltree_node_prepare(); - test_tree_insert(&avltree, NODE_COUNT, quiet); - test_tree_delmin(&avltree, NODE_COUNT, quiet); - + test_tree_insert(&avltree, NODE_COUNT); + test_tree_delmin(&avltree, NODE_COUNT); + return NULL; } -