Rev 2499 | Rev 3165 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2499 | Rev 2745 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (c) 2007 Vojtech Mencl |
2 | * Copyright (c) 2007 Vojtech Mencl |
3 | * All rights reserved. |
3 | * All rights reserved. |
4 | * |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions |
6 | * modification, are permitted provided that the following conditions |
7 | * are met: |
7 | * are met: |
8 | * |
8 | * |
9 | * - Redistributions of source code must retain the above copyright |
9 | * - Redistributions of source code must retain the above copyright |
10 | * notice, this list of conditions and the following disclaimer. |
10 | * notice, this list of conditions and the following disclaimer. |
11 | * - Redistributions in binary form must reproduce the above copyright |
11 | * - Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
13 | * documentation and/or other materials provided with the distribution. |
14 | * - The name of the author may not be used to endorse or promote products |
14 | * - The name of the author may not be used to endorse or promote products |
15 | * derived from this software without specific prior written permission. |
15 | * derived from this software without specific prior written permission. |
16 | * |
16 | * |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
27 | */ |
28 | 28 | ||
29 | #include <test.h> |
29 | #include <test.h> |
30 | #include <print.h> |
30 | #include <print.h> |
31 | #include <adt/avl.h> |
31 | #include <adt/avl.h> |
32 | #include <debug.h> |
32 | #include <debug.h> |
33 | #include <arch/types.h> |
33 | #include <arch/types.h> |
34 | 34 | ||
35 | #define NODE_COUNT 100 |
35 | #define NODE_COUNT 100 |
36 | 36 | ||
37 | static avltree_t avltree; |
37 | static avltree_t avltree; |
38 | 38 | ||
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); |
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 | static avltree_node_t *alloc_avltree_node(void); |
52 | static avltree_node_t *alloc_avltree_node(void); |
53 | 53 | ||
54 | static avltree_node_t *test_tree_parents(avltree_node_t *node) |
54 | static avltree_node_t *test_tree_parents(avltree_node_t *node) |
55 | { |
55 | { |
56 | avltree_node_t *tmp; |
56 | avltree_node_t *tmp; |
57 | 57 | ||
58 | if (!node) |
58 | if (!node) |
59 | return NULL; |
59 | return NULL; |
60 | 60 | ||
61 | if (node->lft) { |
61 | if (node->lft) { |
62 | tmp = test_tree_parents(node->lft); |
62 | tmp = test_tree_parents(node->lft); |
63 | if (tmp != node) { |
63 | if (tmp != node) { |
64 | printf("Bad parent pointer key: %d, address: %p\n", |
64 | printf("Bad parent pointer key: %d, address: %p\n", |
65 | tmp->key, node->lft); |
65 | tmp->key, node->lft); |
66 | } |
66 | } |
67 | } |
67 | } |
68 | if (node->rgt) { |
68 | if (node->rgt) { |
69 | tmp = test_tree_parents(node->rgt); |
69 | tmp = test_tree_parents(node->rgt); |
70 | if (tmp != node) { |
70 | if (tmp != node) { |
71 | printf("Bad parent pointer key: %d, address: %p\n", |
71 | printf("Bad parent pointer key: %d, address: %p\n", |
72 | tmp->key,node->rgt); |
72 | tmp->key,node->rgt); |
73 | } |
73 | } |
74 | } |
74 | } |
75 | return node->par; |
75 | return node->par; |
76 | } |
76 | } |
77 | 77 | ||
78 | int test_tree_balance(avltree_node_t *node) |
78 | int test_tree_balance(avltree_node_t *node) |
79 | { |
79 | { |
80 | int h1, h2, diff; |
80 | int h1, h2, diff; |
81 | 81 | ||
82 | if (!node) |
82 | if (!node) |
83 | return 0; |
83 | return 0; |
84 | h1 = test_tree_balance(node->lft); |
84 | h1 = test_tree_balance(node->lft); |
85 | h2 = test_tree_balance(node->rgt); |
85 | h2 = test_tree_balance(node->rgt); |
86 | diff = h2 - h1; |
86 | diff = h2 - h1; |
87 | if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) { |
87 | if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) { |
88 | printf("Bad balance\n"); |
88 | printf("Bad balance\n"); |
89 | } |
89 | } |
90 | return h1 > h2 ? h1 + 1 : h2 + 1; |
90 | return h1 > h2 ? h1 + 1 : h2 + 1; |
91 | } |
91 | } |
92 | 92 | ||
93 | /** |
93 | /** |
94 | * Prints the structure of the node, which is level levels from the top of the |
94 | * Prints the structure of the node, which is level levels from the top of the |
95 | * tree. |
95 | * tree. |
96 | */ |
96 | */ |
97 | static void print_tree_structure_flat(avltree_node_t *node, int level) |
97 | static void print_tree_structure_flat(avltree_node_t *node, int level) |
98 | { |
98 | { |
99 | /* |
99 | /* |
100 | * You can set the maximum level as high as you like. |
100 | * 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, |
101 | * 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. |
102 | * so that a large level indicates a loop, which is a bug. |
103 | */ |
103 | */ |
104 | if (level > 16) { |
104 | if (level > 16) { |
105 | printf("[...]"); |
105 | printf("[...]"); |
106 | return; |
106 | return; |
107 | } |
107 | } |
108 | 108 | ||
109 | if (node == NULL) |
109 | if (node == NULL) |
110 | return; |
110 | return; |
111 | 111 | ||
112 | printf("%d[%d]", node->key, node->balance); |
112 | printf("%d[%d]", node->key, node->balance); |
113 | if (node->lft != NULL || node->rgt != NULL) { |
113 | if (node->lft != NULL || node->rgt != NULL) { |
114 | printf("("); |
114 | printf("("); |
115 | 115 | ||
116 | print_tree_structure_flat(node->lft, level + 1); |
116 | print_tree_structure_flat(node->lft, level + 1); |
117 | if (node->rgt != NULL) { |
117 | if (node->rgt != NULL) { |
118 | printf(","); |
118 | printf(","); |
119 | print_tree_structure_flat(node->rgt, level + 1); |
119 | print_tree_structure_flat(node->rgt, level + 1); |
120 | } |
120 | } |
121 | 121 | ||
122 | printf(")"); |
122 | printf(")"); |
123 | } |
123 | } |
124 | } |
124 | } |
125 | 125 | ||
126 | static void alloc_avltree_node_prepare(void) |
126 | static void alloc_avltree_node_prepare(void) |
127 | { |
127 | { |
128 | int i; |
128 | int i; |
129 | 129 | ||
130 | for (i = 0; i < NODE_COUNT - 1; i++) { |
130 | for (i = 0; i < NODE_COUNT - 1; i++) { |
131 | avltree_nodes[i].par = &avltree_nodes[i + 1]; |
131 | avltree_nodes[i].par = &avltree_nodes[i + 1]; |
132 | } |
132 | } |
133 | 133 | ||
134 | /* |
134 | /* |
135 | * Node keys which will be used for insertion. Up to NODE_COUNT size of |
135 | * Node keys which will be used for insertion. Up to NODE_COUNT size of |
136 | * array. |
136 | * array. |
137 | */ |
137 | */ |
138 | 138 | ||
139 | /* First tree node and same key */ |
139 | /* First tree node and same key */ |
140 | avltree_nodes[0].key = 60; |
140 | avltree_nodes[0].key = 60; |
141 | avltree_nodes[1].key = 60; |
141 | avltree_nodes[1].key = 60; |
142 | avltree_nodes[2].key = 60; |
142 | avltree_nodes[2].key = 60; |
143 | /* LL rotation */ |
143 | /* LL rotation */ |
144 | avltree_nodes[3].key = 50; |
144 | avltree_nodes[3].key = 50; |
145 | avltree_nodes[4].key = 40; |
145 | avltree_nodes[4].key = 40; |
146 | avltree_nodes[5].key = 30; |
146 | avltree_nodes[5].key = 30; |
147 | /* LR rotation */ |
147 | /* LR rotation */ |
148 | avltree_nodes[6].key = 20; |
148 | avltree_nodes[6].key = 20; |
149 | avltree_nodes[7].key = 20; |
149 | avltree_nodes[7].key = 20; |
150 | avltree_nodes[8].key = 25; |
150 | avltree_nodes[8].key = 25; |
151 | avltree_nodes[9].key = 25; |
151 | avltree_nodes[9].key = 25; |
152 | /* LL rotation in lower floor */ |
152 | /* LL rotation in lower floor */ |
153 | avltree_nodes[10].key = 35; |
153 | avltree_nodes[10].key = 35; |
154 | /* RR rotation */ |
154 | /* RR rotation */ |
155 | avltree_nodes[11].key = 70; |
155 | avltree_nodes[11].key = 70; |
156 | avltree_nodes[12].key = 80; |
156 | avltree_nodes[12].key = 80; |
157 | /* RL rotation */ |
157 | /* RL rotation */ |
158 | avltree_nodes[13].key = 90; |
158 | avltree_nodes[13].key = 90; |
159 | avltree_nodes[14].key = 85; |
159 | avltree_nodes[14].key = 85; |
160 | /* Insert 0 key */ |
160 | /* Insert 0 key */ |
161 | avltree_nodes[15].key = 0; |
161 | avltree_nodes[15].key = 0; |
162 | avltree_nodes[16].key = 0; |
162 | avltree_nodes[16].key = 0; |
163 | /* Insert reverse */ |
163 | /* Insert reverse */ |
164 | avltree_nodes[17].key = 600; |
164 | avltree_nodes[17].key = 600; |
165 | avltree_nodes[18].key = 500; |
165 | avltree_nodes[18].key = 500; |
166 | avltree_nodes[19].key = 400; |
166 | avltree_nodes[19].key = 400; |
167 | avltree_nodes[20].key = 300; |
167 | avltree_nodes[20].key = 300; |
168 | 168 | ||
169 | for (i = 21; i < NODE_COUNT; i++) |
169 | for (i = 21; i < NODE_COUNT; i++) |
170 | avltree_nodes[i].key = i * 3; |
170 | avltree_nodes[i].key = i * 3; |
171 | 171 | ||
172 | avltree_nodes[i].par = NULL; |
172 | avltree_nodes[i].par = NULL; |
173 | first_free_node = &avltree_nodes[0]; |
173 | first_free_node = &avltree_nodes[0]; |
174 | } |
174 | } |
175 | 175 | ||
176 | static avltree_node_t *alloc_avltree_node(void) |
176 | static avltree_node_t *alloc_avltree_node(void) |
177 | { |
177 | { |
178 | avltree_node_t *node; |
178 | avltree_node_t *node; |
179 | 179 | ||
180 | node = first_free_node; |
180 | node = first_free_node; |
181 | first_free_node = first_free_node->par; |
181 | first_free_node = first_free_node->par; |
182 | 182 | ||
183 | return node; |
183 | return node; |
184 | } |
184 | } |
185 | 185 | ||
186 | static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet) |
186 | static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet) |
187 | { |
187 | { |
188 | unsigned int i; |
188 | unsigned int i; |
189 | avltree_node_t *newnode; |
189 | avltree_node_t *newnode; |
190 | 190 | ||
191 | avltree_create(tree); |
191 | avltree_create(tree); |
192 | 192 | ||
193 | if (!quiet) |
193 | if (!quiet) |
194 | printf("Inserting %d nodes...", node_count); |
194 | printf("Inserting %d nodes...", node_count); |
195 | 195 | ||
196 | for (i = 0; i < node_count; i++) { |
196 | for (i = 0; i < node_count; i++) { |
197 | newnode = alloc_avltree_node(); |
197 | newnode = alloc_avltree_node(); |
198 | 198 | ||
199 | avltree_insert(tree, newnode); |
199 | avltree_insert(tree, newnode); |
200 | if (!quiet) { |
200 | if (!quiet) { |
201 | test_tree_parents(tree->root); |
201 | test_tree_parents(tree->root); |
202 | test_tree_balance(tree->root); |
202 | test_tree_balance(tree->root); |
203 | } |
203 | } |
204 | } |
204 | } |
205 | 205 | ||
206 | if (!quiet) |
206 | if (!quiet) |
207 | printf("done.\n"); |
207 | printf("done.\n"); |
208 | } |
208 | } |
209 | 209 | ||
210 | 210 | ||
211 | static void test_tree_delete(avltree_t *tree, count_t node_count, |
211 | static void test_tree_delete(avltree_t *tree, count_t node_count, |
212 | int node_position, bool quiet) |
212 | int node_position, bool quiet) |
213 | { |
213 | { |
214 | avltree_node_t *delnode; |
214 | avltree_node_t *delnode; |
215 | unsigned int i; |
215 | unsigned int i; |
216 | 216 | ||
217 | switch (node_position) { |
217 | switch (node_position) { |
218 | case 0: |
218 | case 0: |
219 | if (!quiet) |
219 | if (!quiet) |
220 | printf("Deleting root nodes..."); |
220 | printf("Deleting root nodes..."); |
221 | while (tree->root != NULL) { |
221 | while (tree->root != NULL) { |
222 | delnode = tree->root; |
222 | delnode = tree->root; |
223 | avltree_delete(tree, delnode); |
223 | avltree_delete(tree, delnode); |
224 | if (!quiet) { |
224 | if (!quiet) { |
225 | test_tree_parents(tree->root); |
225 | test_tree_parents(tree->root); |
226 | test_tree_balance(tree->root); |
226 | test_tree_balance(tree->root); |
227 | } |
227 | } |
228 | } |
228 | } |
229 | break; |
229 | break; |
230 | case 1: |
230 | case 1: |
231 | if (!quiet) |
231 | if (!quiet) |
232 | printf("Deleting nodes according to creation time..."); |
232 | printf("Deleting nodes according to creation time..."); |
233 | for (i = 0; i < node_count; i++) { |
233 | for (i = 0; i < node_count; i++) { |
234 | avltree_delete(tree, &avltree_nodes[i]); |
234 | avltree_delete(tree, &avltree_nodes[i]); |
235 | if (!quiet) { |
235 | if (!quiet) { |
236 | test_tree_parents(tree->root); |
236 | test_tree_parents(tree->root); |
237 | test_tree_balance(tree->root); |
237 | test_tree_balance(tree->root); |
238 | } |
238 | } |
239 | } |
239 | } |
240 | break; |
240 | break; |
241 | } |
241 | } |
242 | 242 | ||
243 | if (!quiet) |
243 | if (!quiet) |
244 | printf("done.\n"); |
244 | printf("done.\n"); |
245 | } |
245 | } |
246 | 246 | ||
247 | static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet) |
247 | static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet) |
248 | { |
248 | { |
249 | int i = 0; |
249 | unsigned int i = 0; |
250 | 250 | ||
251 | if (!quiet) |
251 | if (!quiet) |
252 | printf("Deleting minimum nodes..."); |
252 | printf("Deleting minimum nodes..."); |
253 | 253 | ||
254 | while (tree->root != NULL) { |
254 | while (tree->root != NULL) { |
255 | i++; |
255 | i++; |
256 | avltree_delete_min(tree); |
256 | avltree_delete_min(tree); |
257 | if (!quiet) { |
257 | if (!quiet) { |
258 | test_tree_parents(tree->root); |
258 | test_tree_parents(tree->root); |
259 | test_tree_balance(tree->root); |
259 | test_tree_balance(tree->root); |
260 | } |
260 | } |
261 | } |
261 | } |
262 | 262 | ||
263 | if (!quiet && (i != node_count)) |
263 | if (!quiet && (i != node_count)) |
264 | printf("Bad node count. Some nodes have been lost!\n"); |
264 | printf("Bad node count. Some nodes have been lost!\n"); |
265 | 265 | ||
266 | if (!quiet) |
266 | if (!quiet) |
267 | printf("done.\n"); |
267 | printf("done.\n"); |
268 | } |
268 | } |
269 | 269 | ||
270 | char *test_avltree1(bool quiet) |
270 | char *test_avltree1(bool quiet) |
271 | { |
271 | { |
272 | alloc_avltree_node_prepare(); |
272 | alloc_avltree_node_prepare(); |
273 | test_tree_insert(&avltree, NODE_COUNT, quiet); |
273 | test_tree_insert(&avltree, NODE_COUNT, quiet); |
274 | test_tree_delete(&avltree, NODE_COUNT, 0, quiet); |
274 | test_tree_delete(&avltree, NODE_COUNT, 0, quiet); |
275 | 275 | ||
276 | alloc_avltree_node_prepare(); |
276 | alloc_avltree_node_prepare(); |
277 | test_tree_insert(&avltree, NODE_COUNT, quiet); |
277 | test_tree_insert(&avltree, NODE_COUNT, quiet); |
278 | test_tree_delete(&avltree, NODE_COUNT, 1, quiet); |
278 | test_tree_delete(&avltree, NODE_COUNT, 1, quiet); |
279 | 279 | ||
280 | alloc_avltree_node_prepare(); |
280 | alloc_avltree_node_prepare(); |
281 | test_tree_insert(&avltree, NODE_COUNT, quiet); |
281 | test_tree_insert(&avltree, NODE_COUNT, quiet); |
282 | test_tree_delmin(&avltree, NODE_COUNT, quiet); |
282 | test_tree_delmin(&avltree, NODE_COUNT, quiet); |
283 | 283 | ||
284 | return NULL; |
284 | return NULL; |
285 | } |
285 | } |
286 | 286 | ||
287 | 287 |