Subversion Repositories HelenOS

Compare Revisions

Regard whitespace Rev 4376 → Rev 4377

/branches/tracing/kernel/test/avltree/avltree1.c
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;
}