Subversion Repositories HelenOS

Rev

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

Rev 2787 Rev 3424
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: %d, 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: %d, 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 107... Line 110...
107
    }
110
    }
108
 
111
 
109
    if (node == NULL)
112
    if (node == NULL)
110
        return;
113
        return;
111
 
114
 
112
    printf("%d[%d]", node->key, node->balance);
115
    printf("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance);
113
    if (node->lft != NULL || node->rgt != NULL) {
116
    if (node->lft != NULL || node->rgt != NULL) {
114
        printf("(");
117
        printf("(");
115
 
118
 
116
        print_tree_structure_flat(node->lft, level + 1);
119
        print_tree_structure_flat(node->lft, level + 1);
117
        if (node->rgt != NULL) {
120
        if (node->rgt != NULL) {
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
{
Line 189... Line 192...
189
    avltree_node_t *newnode;
192
    avltree_node_t *newnode;
190
 
193
 
191
    avltree_create(tree);
194
    avltree_create(tree);
192
   
195
   
193
    if (!quiet)
196
    if (!quiet)
194
        printf("Inserting %d nodes...", node_count);
197
        printf("Inserting %" PRIc " nodes...", node_count);
195
 
198
 
196
    for (i = 0; i < node_count; i++) {
199
    for (i = 0; i < node_count; i++) {
197
        newnode = alloc_avltree_node();
200
        newnode = alloc_avltree_node();
198
       
201
       
199
        avltree_insert(tree, newnode);
202
        avltree_insert(tree, newnode);