Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2420 → Rev 2421

/branches/rcu/kernel/test/extavlreltree/extavlreltree1.c
28,7 → 28,7
 
#include <test.h>
#include <print.h>
#include <adt/extavlreltree.h>
#include <adt/extavlrel.h>
#include <debug.h>
 
#include <panic.h>
53,17 → 53,17
 
 
 
static int extreltree_test_height(extrelavltree_node_t *node,bool timeout);
static extavlreltree_node_t *extreltree_test_parents(extavlireltree_node_t *node);
static int extreltree_test_height(extavlreltree_node_t *node,bool timeout);
static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node);
static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level);
static bool extreltree_test_link(int node_count);
static void print_extreltree_link(int node_count);
static bool extreltree_test_link(extavlreltree_t *tree, int node_count);
static void print_extreltree_link(extavlreltree_t *tree);
static extavlreltree_node_t *alloc_extavlreltree_node(void);
 
 
 
//vraci hloubku stromu
static int extreltree_test_height(extavltree_node_t *node,bool timeout)
static int extreltree_test_height(extavlreltree_node_t *node,bool timeout)
{
int h1, h2;
 
90,7 → 90,7
*/
static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node)
{
extavltree_node_t *tmp;
extavlreltree_node_t *tmp;
if (!node) return NULL;
 
112,21 → 112,21
/** Checks list of nodes
*
*/
static bool extreltree_test_link(int node_count)
static bool extreltree_test_link(extavlreltree_t *tree, int node_count)
{
extavltree_node_t *node;
extavlreltree_node_t *node;
int i;
bool test_link = true;
 
for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next)
for (i = 0,node = tree->head.next; node != &(tree->head); i++,node = node->next)
;
if (node_count && i != node_count) {
if (i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev)
for (i = 0,node = tree->head.prev; node != &(tree->head); i++,node = node->prev)
;
if (node_count && i != node_count) {
if (i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
145,18 → 145,17
return sum + node->key;
}
 
static int extreltree_test_maxsum(extavlreltree_node_t *node)
static int extreltree_test_rgtsum(extavlreltree_node_t *node)
{
int rs, ls;
if (!node) return 0;
rs = extreltree_test_maxsum(node->rgt);
ls = extreltree_test_maxsum(node->lft);
rs = extreltree_test_rgtsum(node->rgt);
ls = extreltree_test_rgtsum(node->lft);
 
if (rs != node->rgt_max_key) {
printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_max_key,rs,node->key,node);
getchar();
if (rs != node->rgt_sum) {
printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_sum,rs,node->key,node);
}
return rs + ls + node->key;
}
181,19 → 180,19
for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++)
;
 
printf ("%d[%d,%d]", node->key,node->rgt_max_key,i);
printf ("%d[%d,%d]", node->key,node->rgt_sum,i);
if (node->lft != NULL || node->rgt != NULL)
{
putchar ('(');
printf ("(");
 
print_extreltree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
putchar (',');
printf(",");
print_extreltree_structure_flat (node->rgt, level + 1);
}
 
putchar (')');
printf(")");
}
}
 
200,20 → 199,20
/** Prints list of nodes
*
*/
static void print_extreltree_link(int node_count)
static void print_extreltree_link(extavlreltree_t *tree)
{
extavltree_node_t *node;
extavlreltree_node_t *node;
printf("\n");
for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
for (node = tree->head.next; node != &(tree->head); node = node->next) {
printf(" %d,",node->key);
}
for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {
for (node = tree->head.prev; node != &(tree->head); node = node->prev) {
printf(" %d,",node->key);
}
}
 
//****************************************************************
static void alloc_extavltree_node_prepare(void)
static void alloc_extavlreltree_node_prepare(void)
{
int i;
 
280,7 → 279,7
*/
extavlreltree_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_extavlreltree_node();
288,8 → 287,8
extavlreltree_insert(tree, newnode);
if (!quiet) {
if (!extreltree_test_link(i+1)) {
print_extreltree_link(i+1);
if (!extreltree_test_link(tree,i+1)) {
print_extreltree_link(tree);
printf("\n");
}
extreltree_test_parents(tree->root);
311,14 → 310,14
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\n\nDelete root nodes\n");
i = node_count;
if (!quiet) printf("\nDelete root nodes\n");
i = node_count - 1;
while(tree->root != NULL) {
delnode = tree->root;
extavlreltree_delete(tree,delnode);
if (!quiet) {
if (!extreltree_test_link(i)) {
print_extreltree_link(i);
if (!extreltree_test_link(tree,i)) {
print_extreltree_link(tree);
printf("\n");
}
extreltree_test_parents(tree->root);
330,12 → 329,12
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++) {
extavlreltree_delete(tree,&(extavlreltree_nodes[i]));
if (!quiet) {
if (!extreltree_test_link(i+1)) {
print_extreltree_link(i+1);
if (!extreltree_test_link(tree,node_count-i-1)) {
print_extreltree_link(tree);
printf("\n");
}
extreltree_test_parents(tree->root);
352,15 → 351,15
 
static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet)
{
int i = node_count;
int i = node_count - 1;
if (!quiet) printf("Timeout tree ...\n");
if (!quiet) printf("\nTimeout tree ...\n");
while(tree->head.next != &(tree->head)) {
extavlreltree_delete_min(tree);
if (!quiet) {
if (!extreltree_test_link(i)) {
print_extreltree_link(i);
if (!extreltree_test_link(tree,i)) {
print_extreltree_link(tree);
printf("\n");
}
extreltree_test_parents(tree->root);
370,7 → 369,7
i--;
}
 
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!");
if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
 
if (!quiet) printf("Timeout tree finished\n");
}