Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2497 → Rev 2498

/branches/rcu/kernel/test/avltree/avltree1.c
30,17 → 30,14
#include <print.h>
#include <adt/avl.h>
#include <debug.h>
#include <arch/types.h>
 
 
#define NODE_COUNT 100
 
/*
* wrapper structure with a pointer to avl tree root
*/
static avltree_t avltree;
 
/*
* avl tree nodes in array for faster allocating
* avl tree nodes in array for faster allocation
*/
static avltree_node_t avltree_nodes[NODE_COUNT];
 
49,31 → 46,30
*/
static avltree_node_t *first_free_node = NULL;
 
 
 
static int test_tree_balance(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);
 
 
 
static avltree_node_t *test_tree_parents(avltree_node_t *node)
{
avltree_node_t *tmp;
if (!node) return NULL;
if (!node)
return NULL;
 
if (node->lft) {
tmp = test_tree_parents(node->lft);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->lft);
printf("Bad parent pointer key: %d, address: %p\n",
tmp->key, node->lft);
}
}
if (node->rgt) {
tmp = test_tree_parents(node->rgt);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->rgt);
printf("Bad parent pointer key: %d, address: %p\n",
tmp->key,node->rgt);
}
}
return node->par;
83,7 → 79,8
{
int h1, h2, diff;
 
if (!node) return 0;
if (!node)
return 0;
h1 = test_tree_balance(node->lft);
h2 = test_tree_balance(node->rgt);
diff = h2 - h1;
94,16 → 91,18
}
 
/**
* Prints the structure of node, which is level levels from the top of the tree.
* 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.
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 ("[...]");
/*
* 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.
*/
if (level > 16) {
printf("[...]");
return;
}
 
110,16 → 109,14
if (node == NULL)
return;
 
printf ("%d[%d]", node->key,node->balance);
if (node->lft != NULL || node->rgt != NULL)
{
printf("%d[%d]", node->key, node->balance);
if (node->lft != NULL || node->rgt != NULL) {
printf("(");
 
print_tree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
print_tree_structure_flat(node->lft, level + 1);
if (node->rgt != NULL) {
printf(",");
print_tree_structure_flat (node->rgt, level + 1);
print_tree_structure_flat(node->rgt, level + 1);
}
 
printf(")");
126,44 → 123,44
}
}
 
 
//****************************************************************
static void alloc_avltree_node_prepare(void)
{
int i;
 
for (i = 0; i < NODE_COUNT - 1; i++) {
avltree_nodes[i].par = &(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.
* Node keys which will be used for insertion. Up to NODE_COUNT size of
* array.
*/
 
// First tree node and same key
/* First tree node and same key */
avltree_nodes[0].key = 60;
avltree_nodes[1].key = 60;
avltree_nodes[2].key = 60;
//LL rotation
/* LL rotation */
avltree_nodes[3].key = 50;
avltree_nodes[4].key = 40;
avltree_nodes[5].key = 30;
//LR rotation
/* 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
/* LL rotation in lower floor */
avltree_nodes[10].key = 35;
//RR rotation
/* RR rotation */
avltree_nodes[11].key = 70;
avltree_nodes[12].key = 80;
//RL rotation
/* RL rotation */
avltree_nodes[13].key = 90;
avltree_nodes[14].key = 85;
//Insert 0 key
/* Insert 0 key */
avltree_nodes[15].key = 0;
avltree_nodes[16].key = 0;
//Insert reverse
/* Insert reverse */
avltree_nodes[17].key = 600;
avltree_nodes[18].key = 500;
avltree_nodes[19].key = 400;
173,7 → 170,7
avltree_nodes[i].key = i * 3;
avltree_nodes[i].par = NULL;
first_free_node = &(avltree_nodes[0]);
first_free_node = &avltree_nodes[0];
}
 
static avltree_node_t *alloc_avltree_node(void)
185,23 → 182,19
 
return node;
}
//****************************************************************
 
static void test_tree_insert(avltree_t *tree, unsigned int node_count, int quiet)
static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet)
{
unsigned int i;
avltree_node_t *newnode;
 
/*
* Initialize tree before using.
*/
avltree_create(tree);
if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
if (!quiet)
printf("Inserting %d nodes...", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_avltree_node();
//if (!quiet) printf("[[[%d]]]\n",newnode->key);
avltree_insert(tree, newnode);
if (!quiet) {
210,54 → 203,55
}
}
if (!quiet) printf("Inserting was finished\n");
if (!quiet)
printf("done.\n");
}
 
 
static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet)
static void test_tree_delete(avltree_t *tree, count_t node_count,
int node_position, bool quiet)
{
avltree_node_t *delnode;
unsigned int i;
//aktualni pocet tiku:
if (!quiet) printf("Deleting tree...\n");
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\nDelete root nodes\n");
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("\nDelete nodes according to their time of origin\n");
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);
}
switch (node_position) {
case 0:
if (!quiet)
printf("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;
}
break;
case 1:
if (!quiet)
printf("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("Deletion was finished\n");
if (!quiet)
printf("done.\n");
}
 
static void timeout_tree(avltree_t *tree, int node_count, bool quiet)
static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet)
{
int i = 0;
if (!quiet) printf("\nTimeout tree ...\n");
if (!quiet)
printf("Deleting minimum nodes...");
while(tree->root != NULL) {
while (tree->root != NULL) {
i++;
avltree_delete_min(tree);
if (!quiet) {
266,12 → 260,14
}
}
 
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n");
if (!quiet && (i != node_count))
printf("Bad node count. Some nodes have been lost!\n");
 
if (!quiet) printf("Timeout tree finished\n");
if (!quiet)
printf("done.\n");
}
 
char * test_avltree1(bool quiet)
char *test_avltree1(bool quiet)
{
alloc_avltree_node_prepare();
test_tree_insert(&avltree, NODE_COUNT, quiet);
283,7 → 279,8
 
alloc_avltree_node_prepare();
test_tree_insert(&avltree, NODE_COUNT, quiet);
timeout_tree(&avltree, NODE_COUNT, quiet);
test_tree_delmin(&avltree, NODE_COUNT, quiet);
 
return NULL;
}