Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2420 → Rev 2421

/branches/rcu/kernel/test/avltree/avltree1.c
54,7 → 54,7
 
 
static int test_tree_balance(avltree_node_t *node);
static avltree_node_t *tree_test_parents(avltree_node_t *node);
static avltree_node_t *test_tree_parents(avltree_node_t *node);
static void print_tree_structure_flat (avltree_node_t *node, int level);
static avltree_node_t *alloc_avltree_node(void);
 
98,7 → 98,7
/**
* Prints the structure of node, which is level levels from the top of the tree.
*/
static void print_tree_structure_flat (const 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,
115,16 → 115,16
printf ("%d[%d]", node->key,node->balance);
if (node->lft != NULL || node->rgt != NULL)
{
putchar ('(');
printf("(");
 
print_tree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
putchar (',');
printf(",");
print_tree_structure_flat (node->rgt, level + 1);
}
 
putchar (')');
printf(")");
}
}
 
135,7 → 135,7
int i;
 
for (i = 0; i < NODE_COUNT - 1; i++) {
avltree_nodes[i].n = &(avltree_nodes[i+1]);
avltree_nodes[i].par = &(avltree_nodes[i+1]);
}
/*
* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
172,7 → 172,7
for (i = 21; i < NODE_COUNT; i++)
avltree_nodes[i].key = i * 3;
avltree_nodes[i].n = NULL;
avltree_nodes[i].par = NULL;
first_free_node = &(avltree_nodes[0]);
}
 
181,7 → 181,7
avltree_node_t *node;
 
node = first_free_node;
first_free_node = first_free_node->n;
first_free_node = first_free_node->par;
 
return node;
}
197,7 → 197,7
*/
avltree_create(tree);
if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_avltree_node();
213,26 → 213,7
if (!quiet) printf("Inserting was finished\n");
}
 
/*
static avltree_node_t *tree_random_delete_node(avltree_t *tree, int node_count, int r, bool quiet)
{
avltree_node_t *delnode;
int i;
 
for (i = 0,delnode = tree->head.n; i < (r-1); i++)
delnode = delnode->n;
if (delnode == &tree->head) {
if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);
return NULL;
}
 
avltree_delete(tree, delnode);
 
return delnode;
}
*/
 
static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet)
{
avltree_node_t *delnode;
243,7 → 224,7
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\n\nDelete root nodes\n");
if (!quiet) printf("\nDelete root nodes\n");
while(tree->root != NULL) {
delnode = tree->root;
avltree_delete(tree,delnode);
255,7 → 236,7
break;
case 1:
if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
if (!quiet) printf("\nDelete nodes according to their time of origin\n");
for (i = 0; i < node_count; i++) {
avltree_delete(tree,&(avltree_nodes[i]));
if (!quiet) {
274,9 → 255,9
{
int i = 0;
if (!quiet) printf("Timeout tree ...\n");
if (!quiet) printf("\nTimeout tree ...\n");
while(tree->head.n != &(tree->head)) {
while(tree->root != NULL) {
i++;
avltree_delete_min(tree);
if (!quiet) {
285,62 → 266,24
}
}
 
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!");
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n");
 
if (!quiet) printf("Timeout tree finished\n");
}
 
/*
void timeout_tree_run(avltree_t *tree, int operation_count, int verbal)
{
int i;
avltree_node_t *node;
int r;
int count;
//inicializace stromu:
avltree_create(tree);
for(i = 0, count = 0; i < operation_count; i++) {
if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {
if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne
node = tree_random_delete_node(tree,(r % tree->count));
//printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
node->n = first_free_node;
first_free_node = node;
} else {
node = tree->head.n;
avltree_delete_min(tree);
//printf("TIMEOUT key: %d, address: %p\n",node->key,node);
node->n = first_free_node;
first_free_node = node;
}
} else {
node = alloc_avltree_node_random();
//printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
avltree_insert(tree, node);
}
//test_tree_height(tree->root,1);
//tree_test_parents(tree->root);
//print_tree_link(tree->count);
//print_tree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
}
}
*/
 
char * test_avltree1(bool quiet)
{
alloc_avltree_node_prepare();
test_tree_insert(&tree, NODE_COUNT, quiet);
test_tree_delete(&tree, NODE_COUNT, 0, quiet);
test_tree_insert(&avltree, NODE_COUNT, quiet);
test_tree_delete(&avltree, NODE_COUNT, 0, quiet);
 
alloc_avltree_node_prepare();
test_tree_insert(&tree, NODE_COUNT, quiet);
test_tree_delete(&tree, NODE_COUNT, 1, quiet);
test_tree_insert(&avltree, NODE_COUNT, quiet);
test_tree_delete(&avltree, NODE_COUNT, 1, quiet);
 
alloc_avltree_node_prepare();
test_tree_insert(&tree, NODE_COUNT, quiet);
timeout_tree(&tree, NODE_COUNT, quiet);
test_tree_insert(&avltree, NODE_COUNT, quiet);
timeout_tree(&avltree, NODE_COUNT, quiet);
 
return NULL;
}