Rev 3386 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 3386 | Rev 4263 | ||
|---|---|---|---|
| Line 39... | Line 39... | ||
| 39 | /* |
39 | /* |
| 40 | * avl tree nodes in array for faster allocation |
40 | * avl tree nodes in array for faster allocation |
| 41 | */ |
41 | */ |
| 42 | static avltree_node_t avltree_nodes[NODE_COUNT]; |
42 | static avltree_node_t avltree_nodes[NODE_COUNT]; |
| 43 | 43 | ||
| 44 | /* |
44 | /* |
| 45 | * head of free nodes' list: |
45 | * head of free nodes' list: |
| 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); |
| Line 56... | Line 56... | ||
| 56 | { |
56 | { |
| 57 | avltree_node_t *tmp; |
57 | avltree_node_t *tmp; |
| 58 | 58 | ||
| 59 | if (!node) |
59 | if (!node) |
| 60 | return NULL; |
60 | return NULL; |
| 61 | 61 | ||
| 62 | if (node->lft) { |
62 | if (node->lft) { |
| 63 | tmp = test_tree_parents(node->lft); |
63 | tmp = test_tree_parents(node->lft); |
| 64 | if (tmp != node) { |
64 | if (tmp != node) { |
| 65 | printf("Bad parent pointer key: %" PRIu64 |
65 | TPRINTF("Bad parent pointer key: %" PRIu64 |
| 66 | ", address: %p\n", tmp->key, node->lft); |
66 | ", address: %p\n", tmp->key, node->lft); |
| 67 | } |
67 | } |
| 68 | } |
68 | } |
| 69 | if (node->rgt) { |
69 | if (node->rgt) { |
| 70 | tmp = test_tree_parents(node->rgt); |
70 | tmp = test_tree_parents(node->rgt); |
| 71 | if (tmp != node) { |
71 | if (tmp != node) { |
| 72 | printf("Bad parent pointer key: %" PRIu64 |
72 | TPRINTF("Bad parent pointer key: %" PRIu64 |
| 73 | ", address: %p\n", |
73 | ", address: %p\n", |
| 74 | tmp->key,node->rgt); |
74 | tmp->key,node->rgt); |
| 75 | } |
75 | } |
| 76 | } |
76 | } |
| 77 | return node->par; |
77 | return node->par; |
| 78 | } |
78 | } |
| 79 | 79 | ||
| 80 | int test_tree_balance(avltree_node_t *node) |
80 | int test_tree_balance(avltree_node_t *node) |
| 81 | { |
81 | { |
| 82 | int h1, h2, diff; |
82 | int h1, h2, diff; |
| 83 | 83 | ||
| 84 | if (!node) |
84 | if (!node) |
| 85 | return 0; |
85 | return 0; |
| - | 86 | ||
| 86 | h1 = test_tree_balance(node->lft); |
87 | h1 = test_tree_balance(node->lft); |
| 87 | h2 = test_tree_balance(node->rgt); |
88 | h2 = test_tree_balance(node->rgt); |
| 88 | diff = h2 - h1; |
89 | diff = h2 - h1; |
| - | 90 | ||
| 89 | if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) { |
91 | if ((diff != node->balance) || ((diff != -1) && (diff != 0) && (diff != 1))) |
| 90 | printf("Bad balance\n"); |
92 | TPRINTF("Bad balance\n"); |
| 91 | } |
93 | |
| 92 | return h1 > h2 ? h1 + 1 : h2 + 1; |
94 | return ((h1 > h2) ? (h1 + 1) : (h2 + 1)); |
| 93 | } |
95 | } |
| 94 | 96 | ||
| 95 | /** |
97 | /** |
| 96 | * Prints the structure of the node, which is level levels from the top of the |
98 | * Prints the structure of the node, which is level levels from the top of the |
| 97 | * tree. |
99 | * tree. |
| 98 | */ |
100 | */ |
| 99 | static void |
- | |
| 100 | print_tree_structure_flat(avltree_node_t *node, int level) |
101 | static void print_tree_structure_flat(avltree_node_t *node, int level) |
| 101 | { |
102 | { |
| 102 | /* |
103 | /* |
| 103 | * You can set the maximum level as high as you like. |
104 | * You can set the maximum level as high as you like. |
| 104 | * Most of the time, you'll want to debug code using small trees, |
105 | * Most of the time, you'll want to debug code using small trees, |
| 105 | * so that a large level indicates a loop, which is a bug. |
106 | * so that a large level indicates a loop, which is a bug. |
| 106 | */ |
107 | */ |
| 107 | if (level > 16) { |
108 | if (level > 16) { |
| 108 | printf("[...]"); |
109 | TPRINTF("[...]"); |
| 109 | return; |
110 | return; |
| 110 | } |
111 | } |
| 111 | 112 | ||
| 112 | if (node == NULL) |
113 | if (node == NULL) |
| 113 | return; |
114 | return; |
| 114 | 115 | ||
| 115 | printf("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance); |
116 | TPRINTF("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance); |
| 116 | if (node->lft != NULL || node->rgt != NULL) { |
117 | if (node->lft != NULL || node->rgt != NULL) { |
| 117 | printf("("); |
118 | TPRINTF("("); |
| 118 | 119 | ||
| 119 | print_tree_structure_flat(node->lft, level + 1); |
120 | print_tree_structure_flat(node->lft, level + 1); |
| 120 | if (node->rgt != NULL) { |
121 | if (node->rgt != NULL) { |
| 121 | printf(","); |
122 | TPRINTF(","); |
| 122 | print_tree_structure_flat(node->rgt, level + 1); |
123 | print_tree_structure_flat(node->rgt, level + 1); |
| 123 | } |
124 | } |
| 124 | 125 | ||
| 125 | printf(")"); |
126 | TPRINTF(")"); |
| 126 | } |
127 | } |
| 127 | } |
128 | } |
| 128 | 129 | ||
| 129 | static void alloc_avltree_node_prepare(void) |
130 | static void alloc_avltree_node_prepare(void) |
| 130 | { |
131 | { |
| 131 | int i; |
132 | int i; |
| 132 | 133 | ||
| 133 | for (i = 0; i < NODE_COUNT - 1; i++) { |
134 | for (i = 0; i < NODE_COUNT - 1; i++) |
| 134 | avltree_nodes[i].par = &avltree_nodes[i + 1]; |
135 | avltree_nodes[i].par = &avltree_nodes[i + 1]; |
| 135 | } |
136 | |
| 136 | avltree_nodes[i].par = NULL; |
137 | avltree_nodes[i].par = NULL; |
| 137 | 138 | ||
| 138 | /* |
139 | /* |
| 139 | * Node keys which will be used for insertion. Up to NODE_COUNT size of |
140 | * Node keys which will be used for insertion. Up to NODE_COUNT size of |
| 140 | * array. |
141 | * array. |
| 141 | */ |
142 | */ |
| 142 | 143 | ||
| 143 | /* First tree node and same key */ |
144 | /* First tree node and same key */ |
| 144 | avltree_nodes[0].key = 60; |
145 | avltree_nodes[0].key = 60; |
| 145 | avltree_nodes[1].key = 60; |
146 | avltree_nodes[1].key = 60; |
| 146 | avltree_nodes[2].key = 60; |
147 | avltree_nodes[2].key = 60; |
| - | 148 | ||
| 147 | /* LL rotation */ |
149 | /* LL rotation */ |
| 148 | avltree_nodes[3].key = 50; |
150 | avltree_nodes[3].key = 50; |
| 149 | avltree_nodes[4].key = 40; |
151 | avltree_nodes[4].key = 40; |
| 150 | avltree_nodes[5].key = 30; |
152 | avltree_nodes[5].key = 30; |
| - | 153 | ||
| 151 | /* LR rotation */ |
154 | /* LR rotation */ |
| 152 | avltree_nodes[6].key = 20; |
155 | avltree_nodes[6].key = 20; |
| 153 | avltree_nodes[7].key = 20; |
156 | avltree_nodes[7].key = 20; |
| 154 | avltree_nodes[8].key = 25; |
157 | avltree_nodes[8].key = 25; |
| 155 | avltree_nodes[9].key = 25; |
158 | avltree_nodes[9].key = 25; |
| - | 159 | ||
| 156 | /* LL rotation in lower floor */ |
160 | /* LL rotation in lower floor */ |
| 157 | avltree_nodes[10].key = 35; |
161 | avltree_nodes[10].key = 35; |
| - | 162 | ||
| 158 | /* RR rotation */ |
163 | /* RR rotation */ |
| 159 | avltree_nodes[11].key = 70; |
164 | avltree_nodes[11].key = 70; |
| 160 | avltree_nodes[12].key = 80; |
165 | avltree_nodes[12].key = 80; |
| - | 166 | ||
| 161 | /* RL rotation */ |
167 | /* RL rotation */ |
| 162 | avltree_nodes[13].key = 90; |
168 | avltree_nodes[13].key = 90; |
| 163 | avltree_nodes[14].key = 85; |
169 | avltree_nodes[14].key = 85; |
| - | 170 | ||
| 164 | /* Insert 0 key */ |
171 | /* Insert 0 key */ |
| 165 | avltree_nodes[15].key = 0; |
172 | avltree_nodes[15].key = 0; |
| 166 | avltree_nodes[16].key = 0; |
173 | avltree_nodes[16].key = 0; |
| - | 174 | ||
| 167 | /* Insert reverse */ |
175 | /* Insert reverse */ |
| 168 | avltree_nodes[17].key = 600; |
176 | avltree_nodes[17].key = 600; |
| 169 | avltree_nodes[18].key = 500; |
177 | avltree_nodes[18].key = 500; |
| 170 | avltree_nodes[19].key = 400; |
178 | avltree_nodes[19].key = 400; |
| 171 | avltree_nodes[20].key = 300; |
179 | avltree_nodes[20].key = 300; |
| 172 | 180 | ||
| 173 | for (i = 21; i < NODE_COUNT; i++) |
181 | for (i = 21; i < NODE_COUNT; i++) |
| 174 | avltree_nodes[i].key = i * 3; |
182 | avltree_nodes[i].key = i * 3; |
| 175 | 183 | ||
| 176 | first_free_node = &avltree_nodes[0]; |
184 | first_free_node = &avltree_nodes[0]; |
| 177 | } |
185 | } |
| 178 | 186 | ||
| 179 | static avltree_node_t *alloc_avltree_node(void) |
187 | static avltree_node_t *alloc_avltree_node(void) |
| 180 | { |
188 | { |
| 181 | avltree_node_t *node; |
189 | avltree_node_t *node; |
| 182 | 190 | ||
| 183 | node = first_free_node; |
191 | node = first_free_node; |
| 184 | first_free_node = first_free_node->par; |
192 | first_free_node = first_free_node->par; |
| 185 | 193 | ||
| 186 | return node; |
194 | return node; |
| 187 | } |
195 | } |
| 188 | 196 | ||
| 189 | static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet) |
197 | static void test_tree_insert(avltree_t *tree, count_t node_count) |
| 190 | { |
198 | { |
| 191 | unsigned int i; |
199 | unsigned int i; |
| 192 | avltree_node_t *newnode; |
200 | avltree_node_t *newnode; |
| 193 | 201 | ||
| 194 | avltree_create(tree); |
202 | avltree_create(tree); |
| 195 | 203 | ||
| 196 | if (!quiet) |
- | |
| 197 | printf("Inserting %" PRIc " nodes...", node_count); |
204 | TPRINTF("Inserting %" PRIc " nodes...", node_count); |
| 198 | 205 | ||
| 199 | for (i = 0; i < node_count; i++) { |
206 | for (i = 0; i < node_count; i++) { |
| 200 | newnode = alloc_avltree_node(); |
207 | newnode = alloc_avltree_node(); |
| 201 | 208 | ||
| 202 | avltree_insert(tree, newnode); |
209 | avltree_insert(tree, newnode); |
| 203 | if (!quiet) { |
- | |
| 204 | test_tree_parents(tree->root); |
210 | test_tree_parents(tree->root); |
| 205 | test_tree_balance(tree->root); |
211 | test_tree_balance(tree->root); |
| 206 | } |
- | |
| 207 | } |
212 | } |
| 208 | 213 | ||
| 209 | if (!quiet) |
- | |
| 210 | printf("done.\n"); |
214 | TPRINTF("done.\n"); |
| 211 | } |
215 | } |
| 212 | 216 | ||
| 213 | - | ||
| 214 | static void test_tree_delete(avltree_t *tree, count_t node_count, |
217 | static void test_tree_delete(avltree_t *tree, count_t node_count, |
| 215 | int node_position, bool quiet) |
218 | int node_position) |
| 216 | { |
219 | { |
| 217 | avltree_node_t *delnode; |
220 | avltree_node_t *delnode; |
| 218 | unsigned int i; |
221 | unsigned int i; |
| 219 | 222 | ||
| 220 | switch (node_position) { |
223 | switch (node_position) { |
| 221 | case 0: |
224 | case 0: |
| 222 | if (!quiet) |
- | |
| 223 | printf("Deleting root nodes..."); |
225 | TPRINTF("Deleting root nodes..."); |
| - | 226 | ||
| 224 | while (tree->root != NULL) { |
227 | while (tree->root != NULL) { |
| 225 | delnode = tree->root; |
228 | delnode = tree->root; |
| 226 | avltree_delete(tree, delnode); |
229 | avltree_delete(tree, delnode); |
| 227 | if (!quiet) { |
- | |
| 228 | test_tree_parents(tree->root); |
230 | test_tree_parents(tree->root); |
| 229 | test_tree_balance(tree->root); |
231 | test_tree_balance(tree->root); |
| 230 | } |
- | |
| 231 | } |
232 | } |
| 232 | break; |
233 | break; |
| 233 | case 1: |
234 | case 1: |
| 234 | if (!quiet) |
- | |
| 235 | printf("Deleting nodes according to creation time..."); |
235 | TPRINTF("Deleting nodes according to creation time..."); |
| - | 236 | ||
| 236 | for (i = 0; i < node_count; i++) { |
237 | for (i = 0; i < node_count; i++) { |
| 237 | avltree_delete(tree, &avltree_nodes[i]); |
238 | avltree_delete(tree, &avltree_nodes[i]); |
| 238 | if (!quiet) { |
- | |
| 239 | test_tree_parents(tree->root); |
239 | test_tree_parents(tree->root); |
| 240 | test_tree_balance(tree->root); |
240 | test_tree_balance(tree->root); |
| 241 | } |
- | |
| 242 | } |
241 | } |
| 243 | break; |
242 | break; |
| 244 | } |
243 | } |
| 245 | 244 | ||
| 246 | if (!quiet) |
- | |
| 247 | printf("done.\n"); |
245 | TPRINTF("done.\n"); |
| 248 | } |
246 | } |
| 249 | 247 | ||
| 250 | static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet) |
248 | static void test_tree_delmin(avltree_t *tree, count_t node_count) |
| 251 | { |
249 | { |
| 252 | unsigned int i = 0; |
250 | unsigned int i = 0; |
| 253 | 251 | ||
| 254 | if (!quiet) |
- | |
| 255 | printf("Deleting minimum nodes..."); |
252 | TPRINTF("Deleting minimum nodes..."); |
| 256 | 253 | ||
| 257 | while (tree->root != NULL) { |
254 | while (tree->root != NULL) { |
| 258 | i++; |
255 | i++; |
| 259 | avltree_delete_min(tree); |
256 | avltree_delete_min(tree); |
| 260 | if (!quiet) { |
- | |
| 261 | test_tree_parents(tree->root); |
257 | test_tree_parents(tree->root); |
| 262 | test_tree_balance(tree->root); |
258 | test_tree_balance(tree->root); |
| 263 | } |
- | |
| 264 | } |
259 | } |
| 265 | 260 | ||
| 266 | if (!quiet && (i != node_count)) |
261 | if (i != node_count) |
| 267 | printf("Bad node count. Some nodes have been lost!\n"); |
262 | TPRINTF("Bad node count. Some nodes have been lost!\n"); |
| 268 | 263 | ||
| 269 | if (!quiet) |
- | |
| 270 | printf("done.\n"); |
264 | TPRINTF("done.\n"); |
| 271 | } |
265 | } |
| 272 | 266 | ||
| 273 | char *test_avltree1(bool quiet) |
267 | char *test_avltree1(void) |
| 274 | { |
268 | { |
| 275 | alloc_avltree_node_prepare(); |
269 | alloc_avltree_node_prepare(); |
| 276 | test_tree_insert(&avltree, NODE_COUNT, quiet); |
270 | test_tree_insert(&avltree, NODE_COUNT); |
| 277 | test_tree_delete(&avltree, NODE_COUNT, 0, quiet); |
271 | test_tree_delete(&avltree, NODE_COUNT, 0); |
| 278 | 272 | ||
| 279 | alloc_avltree_node_prepare(); |
273 | alloc_avltree_node_prepare(); |
| 280 | test_tree_insert(&avltree, NODE_COUNT, quiet); |
274 | test_tree_insert(&avltree, NODE_COUNT); |
| 281 | test_tree_delete(&avltree, NODE_COUNT, 1, quiet); |
275 | test_tree_delete(&avltree, NODE_COUNT, 1); |
| 282 | 276 | ||
| 283 | alloc_avltree_node_prepare(); |
277 | alloc_avltree_node_prepare(); |
| 284 | test_tree_insert(&avltree, NODE_COUNT, quiet); |
278 | test_tree_insert(&avltree, NODE_COUNT); |
| 285 | test_tree_delmin(&avltree, NODE_COUNT, quiet); |
279 | test_tree_delmin(&avltree, NODE_COUNT); |
| 286 | 280 | ||
| 287 | return NULL; |
281 | return NULL; |
| 288 | } |
282 | } |
| 289 | - | ||