Subversion Repositories HelenOS

Rev

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

Rev 3022 Rev 4055
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);