Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 4376 → Rev 4377

/branches/tracing/kernel/test/avltree/avltree1.c
41,7 → 41,7
*/
static avltree_node_t avltree_nodes[NODE_COUNT];
 
/*
/*
* head of free nodes' list:
*/
static avltree_node_t *first_free_node = NULL;
58,11 → 58,11
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);
}
}
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);
}
80,49 → 80,50
int test_tree_balance(avltree_node_t *node)
{
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.
* 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.
* 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(")");
}
}
 
129,10 → 130,10
static void alloc_avltree_node_prepare(void)
{
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;
/*
139,37 → 140,44
* Node keys which will be used for insertion. Up to NODE_COUNT size of
* 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;
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;
avltree_nodes[19].key = 400;
avltree_nodes[20].key = 300;
 
for (i = 21; i < NODE_COUNT; i++)
avltree_nodes[i].key = i * 3;
179,40 → 187,35
static avltree_node_t *alloc_avltree_node(void)
{
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);
}
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);
}
}
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);
}
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
break;
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);
}
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");
if (i != node_count)
TPRINTF("Bad node count. Some nodes have been lost!\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;
}