Rev 2787 | Rev 4377 | Go to most recent revision | Show entire file | Regard 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); |