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