WebSVN – HelenOS – Diff – /branches/rcu/kernel/test/extavltree/extavltree1.c



 
static int exttree_test_height(extavltree_node_t *node,bool timeout);
static extavltree_node_t *exttree_test_parents(extavltree_node_t *node);
static void print_exttree_structure_flat (extavltree_node_t *node, int level);
static bool exttree_test_link(int node_count);
static void print_exttree_link(void);
static extavltree_node_t *alloc_extavltree_node(void);
 
 
 
//vraci hloubku stromu

        if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {
            printf("\nList is not sorted (forward direction) at key: %d\n",node->key);
            test_link = false;
        }
    }
    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) {
        if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {
            printf("\nList is not sorted (backward direction) at key: %d\n",node->key);
            test_link = false;
        }
    }
    if (i != node_count) {
        printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
        test_link = false;
    }
    return test_link;
}

}
 
/** Prints list of nodes
 *
 */
static void print_exttree_link(void)
{
    extavltree_node_t *node;
    printf("\n");
    for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
        printf(" %d,",node->key);

    /*
     * Initialize tree before using.
     */
    extavltree_create(tree);
   
    if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
 
    for (i = 0; i < node_count; i++) {
        newnode = alloc_extavltree_node();
        //if (!quiet) printf("[[[%d]]]\n",newnode->key);
       
        extavltree_insert(tree, newnode);
        if (!quiet) {
            if (!exttree_test_link(i+1)) {
                print_exttree_link();
                printf("\n");
            }
            exttree_test_parents(tree->root);
            exttree_test_height(tree->root,1);
        }

    //aktualni pocet tiku:
    if (!quiet) printf("Deleting tree...\n");
 
    switch(node_position) {
        case 0: //mazani vzdy korene
            if (!quiet) printf("\nDelete root nodes\n");
            i = node_count - 1;
            while(tree->root != NULL) {
                delnode = tree->root;
                extavltree_delete(tree,delnode);
                if (!quiet) {
                    if (!exttree_test_link(i)) {
                        print_exttree_link();
                        printf("\n");
                    }
                    exttree_test_parents(tree->root);
                    exttree_test_height(tree->root,1);
                }
                i--;
            }
           
            break;
        case 1:
            if (!quiet) printf("\nDelete nodes according to their time of origin\n");
            for (i = 0; i < node_count; i++) {
                extavltree_delete(tree,&(extavltree_nodes[i]));
                if (!quiet) {
                    if (!exttree_test_link(node_count-i-1)) {
                        print_exttree_link();
                        printf("\n");
                    }
                    exttree_test_parents(tree->root);
                    exttree_test_height(tree->root,1);
                }

    if (!quiet) printf("Deletion was finished\n");
}
 
static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)
{
    int i = node_count - 1;
   
    if (!quiet) printf("\nTimeout tree ...\n");
   
    while(tree->head.next != &(tree->head)) {
        extavltree_delete_min(tree);
        if (!quiet) {
            if (!exttree_test_link(i)) {
                print_exttree_link();
                printf("\n");
            }
            exttree_test_parents(tree->root);
            exttree_test_height(tree->root,1);
        }
        i--;
    }
 
    if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
 
    if (!quiet) printf("Timeout tree finished\n");
}
 
/*

Rev 2416	Rev 2421
Line 55...	Line 55...
55		55
56	static int exttree_test_height(extavltree_node_t *node,bool timeout);	56	static int exttree_test_height(extavltree_node_t *node,bool timeout);
57	static extavltree_node_t exttree_test_parents(extavltree_node_t node);	57	static extavltree_node_t exttree_test_parents(extavltree_node_t node);
58	static void print_exttree_structure_flat (extavltree_node_t *node, int level);	58	static void print_exttree_structure_flat (extavltree_node_t *node, int level);
59	static bool exttree_test_link(int node_count);	59	static bool exttree_test_link(int node_count);
60	static void print_exttree_link(int node_count);	60	static void print_exttree_link(void);
61	static extavltree_node_t *alloc_extavltree_node(void);	61	static extavltree_node_t *alloc_extavltree_node(void);
62		62
63		63
64		64
65	//vraci hloubku stromu	65	//vraci hloubku stromu
Line 122...	Line 122...
122	if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {	122	if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {
123	printf("\nList is not sorted (forward direction) at key: %d\n",node->key);	123	printf("\nList is not sorted (forward direction) at key: %d\n",node->key);
124	test_link = false;	124	test_link = false;
125	}	125	}
126	}	126	}
127	if (node_count && i != node_count) {	127	if (i != node_count) {
128	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);	128	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
129	test_link = false;	129	test_link = false;
130	}	130	}
131	for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) {	131	for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) {
132	if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {	132	if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {
133	printf("\nList is not sorted (backward direction) at key: %d\n",node->key);	133	printf("\nList is not sorted (backward direction) at key: %d\n",node->key);
134	test_link = false;	134	test_link = false;
135	}	135	}
136	}	136	}
137	if (node_count && i != node_count) {	137	if (i != node_count) {
138	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);	138	printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
139	test_link = false;	139	test_link = false;
140	}	140	}
141	return test_link;	141	return test_link;
142	}	142	}
Line 178...	Line 178...
178	}	178	}
179		179
180	/** Prints list of nodes	180	/** Prints list of nodes
181	*	181	*
182	*/	182	*/
183	static void print_exttree_link(int node_count)	183	static void print_exttree_link(void)
184	{	184	{
185	extavltree_node_t *node;	185	extavltree_node_t *node;
186	printf("\n");	186	printf("\n");
187	for (node = exttree.head.next; node != &(exttree.head); node = node->next) {	187	for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
188	printf(" %d,",node->key);	188	printf(" %d,",node->key);
Line 258...	Line 258...
258	/*	258	/*
259	* Initialize tree before using.	259	* Initialize tree before using.
260	*/	260	*/
261	extavltree_create(tree);	261	extavltree_create(tree);
262		262
263	if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);	263	if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
264		264
265	for (i = 0; i < node_count; i++) {	265	for (i = 0; i < node_count; i++) {
266	newnode = alloc_extavltree_node();	266	newnode = alloc_extavltree_node();
267	//if (!quiet) printf("[[[%d]]]\n",newnode->key);	267	//if (!quiet) printf("[[[%d]]]\n",newnode->key);
268		268
269	extavltree_insert(tree, newnode);	269	extavltree_insert(tree, newnode);
270	if (!quiet) {	270	if (!quiet) {
271	if (!exttree_test_link(i+1)) {	271	if (!exttree_test_link(i+1)) {
272	print_exttree_link(i+1);	272	print_exttree_link();
273	printf("\n");	273	printf("\n");
274	}	274	}
275	exttree_test_parents(tree->root);	275	exttree_test_parents(tree->root);
276	exttree_test_height(tree->root,1);	276	exttree_test_height(tree->root,1);
277	}	277	}
Line 308...	Line 308...
308	//aktualni pocet tiku:	308	//aktualni pocet tiku:
309	if (!quiet) printf("Deleting tree...\n");	309	if (!quiet) printf("Deleting tree...\n");
310		310
311	switch(node_position) {	311	switch(node_position) {
312	case 0: //mazani vzdy korene	312	case 0: //mazani vzdy korene
313	if (!quiet) printf("\n\nDelete root nodes\n");	313	if (!quiet) printf("\nDelete root nodes\n");
314	i = node_count;	314	i = node_count - 1;
315	while(tree->root != NULL) {	315	while(tree->root != NULL) {
316	delnode = tree->root;	316	delnode = tree->root;
317	extavltree_delete(tree,delnode);	317	extavltree_delete(tree,delnode);
318	if (!quiet) {	318	if (!quiet) {
319	if (!exttree_test_link(i)) {	319	if (!exttree_test_link(i)) {
320	print_exttree_link(i);	320	print_exttree_link();
321	printf("\n");	321	printf("\n");
322	}	322	}
323	exttree_test_parents(tree->root);	323	exttree_test_parents(tree->root);
324	exttree_test_height(tree->root,1);	324	exttree_test_height(tree->root,1);
325	}	325	}
326	i--;	326	i--;
327	}	327	}
328		328
329	break;	329	break;
330	case 1:	330	case 1:
331	if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");	331	if (!quiet) printf("\nDelete nodes according to their time of origin\n");
332	for (i = 0; i < node_count; i++) {	332	for (i = 0; i < node_count; i++) {
333	extavltree_delete(tree,&(extavltree_nodes[i]));	333	extavltree_delete(tree,&(extavltree_nodes[i]));
334	if (!quiet) {	334	if (!quiet) {
335	if (!exttree_test_link(i+1)) {	335	if (!exttree_test_link(node_count-i-1)) {
336	print_exttree_link(i+1);	336	print_exttree_link();
337	printf("\n");	337	printf("\n");
338	}	338	}
339	exttree_test_parents(tree->root);	339	exttree_test_parents(tree->root);
340	exttree_test_height(tree->root,1);	340	exttree_test_height(tree->root,1);
341	}	341	}
Line 347...	Line 347...
347	if (!quiet) printf("Deletion was finished\n");	347	if (!quiet) printf("Deletion was finished\n");
348	}	348	}
349		349
350	static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)	350	static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)
351	{	351	{
352	int i = node_count;	352	int i = node_count - 1;
353		353
354	if (!quiet) printf("Timeout tree ...\n");	354	if (!quiet) printf("\nTimeout tree ...\n");
355		355
356	while(tree->head.next != &(tree->head)) {	356	while(tree->head.next != &(tree->head)) {
357	extavltree_delete_min(tree);	357	extavltree_delete_min(tree);
358	if (!quiet) {	358	if (!quiet) {
359	if (!exttree_test_link(i)) {	359	if (!exttree_test_link(i)) {
360	print_exttree_link(i);	360	print_exttree_link();
361	printf("\n");	361	printf("\n");
362	}	362	}
363	exttree_test_parents(tree->root);	363	exttree_test_parents(tree->root);
364	exttree_test_height(tree->root,1);	364	exttree_test_height(tree->root,1);
365	}	365	}
366	i--;	366	i--;
367	}	367	}
368		368
369	if (!quiet && (i != 0)) printf("Bad node count. Some nodes have been lost!");	369	if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
370		370
371	if (!quiet) printf("Timeout tree finished\n");	371	if (!quiet) printf("Timeout tree finished\n");
372	}	372	}
373		373
374	/*	374	/*

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/extavltree/extavltree1.c – Rev 2416 → 2421