Subversion Repositories HelenOS

Rev

Rev 3069 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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
{