62,7 → 62,7 |
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); |
} |
} |
69,7 → 69,7 |
if (node->rgt) { |
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); |
} |
83,21 → 83,22 |
|
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"); |
|
if ((diff != node->balance) || ((diff != -1) && (diff != 0) && (diff != 1))) |
TPRINTF("Bad balance\n"); |
|
return ((h1 > h2) ? (h1 + 1) : (h2 + 1)); |
} |
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) |
static void print_tree_structure_flat(avltree_node_t *node, int level) |
{ |
/* |
* You can set the maximum level as high as you like. |
105,7 → 106,7 |
* so that a large level indicates a loop, which is a bug. |
*/ |
if (level > 16) { |
printf("[...]"); |
TPRINTF("[...]"); |
return; |
} |
|
112,17 → 113,17 |
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,9 → 131,9 |
{ |
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; |
|
/* |
144,26 → 145,33 |
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; |
avltree_nodes[7].key = 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; |
avltree_nodes[18].key = 500; |
186,7 → 194,7 |
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; |
193,26 → 201,21 |
|
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"); |
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; |
unsigned int i; |
219,71 → 222,61 |
|
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); |
} |
} |
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"); |
TPRINTF("done.\n"); |
} |
|
static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet) |
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 (i != node_count) |
TPRINTF("Bad node count. Some nodes have been lost!\n"); |
|
if (!quiet) |
printf("done.\n"); |
TPRINTF("done.\n"); |
} |
|
char *test_avltree1(bool quiet) |
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; |
} |
|