WebSVN – HelenOS – Diff – /trunk/kernel/test/avltree/avltree1.c



 */
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)
    __attribute__ ((used));
static avltree_node_t *alloc_avltree_node(void);
 
static avltree_node_t *test_tree_parents(avltree_node_t *node)
{
    avltree_node_t *tmp;

        return NULL;
 
    if (node->lft) {
        tmp = test_tree_parents(node->lft);
        if (tmp != node) {
            printf("Bad parent pointer key: %" PRIu64
                ", address: %p\n", tmp->key, node->lft);
        }
    }
    if (node->rgt) {
        tmp = test_tree_parents(node->rgt);
        if (tmp != node) {
            printf("Bad parent pointer key: %" PRIu64
                ", address: %p\n",
                tmp->key,node->rgt);
        }
    }
    return node->par;
}

 
/**
 * 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)
{
    /*
     * 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.

    int i;
 
    for (i = 0; i < NODE_COUNT - 1; i++) {
        avltree_nodes[i].par = &avltree_nodes[i + 1];
    }
    avltree_nodes[i].par = NULL;
   
    /*
     * Node keys which will be used for insertion. Up to NODE_COUNT size of
     * array.
     */

    avltree_nodes[20].key = 300;
 
    for (i = 21; i < NODE_COUNT; i++)
        avltree_nodes[i].key = i * 3;
   
 
    first_free_node = &avltree_nodes[0];
}
 
static avltree_node_t *alloc_avltree_node(void)
{

Rev 3069	Rev 3165
Line 46...	Line 46...
46	*/	46	*/
47	static avltree_node_t *first_free_node = NULL;	47	static avltree_node_t *first_free_node = NULL;
48		48
49	static int test_tree_balance(avltree_node_t *node);	49	static int test_tree_balance(avltree_node_t *node);
50	static avltree_node_t test_tree_parents(avltree_node_t node);	50	static avltree_node_t test_tree_parents(avltree_node_t node);
51	static void print_tree_structure_flat (avltree_node_t *node, int level);	51	static void print_tree_structure_flat (avltree_node_t *node, int level)
-		52	__attribute__ ((used));
52	static avltree_node_t *alloc_avltree_node(void);	53	static avltree_node_t *alloc_avltree_node(void);
53		54
54	static avltree_node_t test_tree_parents(avltree_node_t node)	55	static avltree_node_t test_tree_parents(avltree_node_t node)
55	{	56	{
56	avltree_node_t *tmp;	57	avltree_node_t *tmp;
Line 59...	Line 60...
59	return NULL;	60	return NULL;
60		61
61	if (node->lft) {	62	if (node->lft) {
62	tmp = test_tree_parents(node->lft);	63	tmp = test_tree_parents(node->lft);
63	if (tmp != node) {	64	if (tmp != node) {
64	printf("Bad parent pointer key: %" PRIu64 ", address: %p\n",	65	printf("Bad parent pointer key: %" PRIu64
65	tmp->key, node->lft);	66	", address: %p\n", tmp->key, node->lft);
66	}	67	}
67	}	68	}
68	if (node->rgt) {	69	if (node->rgt) {
69	tmp = test_tree_parents(node->rgt);	70	tmp = test_tree_parents(node->rgt);
70	if (tmp != node) {	71	if (tmp != node) {
71	printf("Bad parent pointer key: %" PRIu64 ", address: %p\n",	72	printf("Bad parent pointer key: %" PRIu64
-		73	", address: %p\n",
72	tmp->key,node->rgt);	74	tmp->key,node->rgt);
73	}	75	}
74	}	76	}
75	return node->par;	77	return node->par;
76	}	78	}
Line 92...	Line 94...
92		94
93	/**	95	/**
94	* Prints the structure of the node, which is level levels from the top of the	96	* Prints the structure of the node, which is level levels from the top of the
95	* tree.	97	* tree.
96	*/	98	*/
-		99	static void
97	static void print_tree_structure_flat(avltree_node_t *node, int level)	100	print_tree_structure_flat(avltree_node_t *node, int level)
98	{	101	{
99	/*	102	/*
100	* You can set the maximum level as high as you like.	103	* You can set the maximum level as high as you like.
101	* Most of the time, you'll want to debug code using small trees,	104	* Most of the time, you'll want to debug code using small trees,
102	* so that a large level indicates a loop, which is a bug.	105	* so that a large level indicates a loop, which is a bug.
Line 128...	Line 131...
128	int i;	131	int i;
129		132
130	for (i = 0; i < NODE_COUNT - 1; i++) {	133	for (i = 0; i < NODE_COUNT - 1; i++) {
131	avltree_nodes[i].par = &avltree_nodes[i + 1];	134	avltree_nodes[i].par = &avltree_nodes[i + 1];
132	}	135	}
-		136	avltree_nodes[i].par = NULL;
133		137
134	/*	138	/*
135	* Node keys which will be used for insertion. Up to NODE_COUNT size of	139	* Node keys which will be used for insertion. Up to NODE_COUNT size of
136	* array.	140	* array.
137	*/	141	*/
Line 167...	Line 171...
167	avltree_nodes[20].key = 300;	171	avltree_nodes[20].key = 300;
168		172
169	for (i = 21; i < NODE_COUNT; i++)	173	for (i = 21; i < NODE_COUNT; i++)
170	avltree_nodes[i].key = i * 3;	174	avltree_nodes[i].key = i * 3;
171		175
172	avltree_nodes[i].par = NULL;	-
173	first_free_node = &avltree_nodes[0];	176	first_free_node = &avltree_nodes[0];
174	}	177	}
175		178
176	static avltree_node_t *alloc_avltree_node(void)	179	static avltree_node_t *alloc_avltree_node(void)
177	{	180	{

Subversion Repositories HelenOS

(root)/trunk/kernel/test/avltree/avltree1.c – Rev 3069 → 3165