Rev 2416 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2416 | Rev 2421 | ||
---|---|---|---|
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/extavl.h> |
31 | #include <adt/extavl.h> |
32 | #include <debug.h> |
32 | #include <debug.h> |
33 | 33 | ||
34 | #include <panic.h> |
34 | #include <panic.h> |
35 | 35 | ||
36 | 36 | ||
37 | #define NODE_COUNT 100 |
37 | #define NODE_COUNT 100 |
38 | 38 | ||
39 | /* |
39 | /* |
40 | * wrapper structure with a pointer to extended avl tree root |
40 | * wrapper structure with a pointer to extended avl tree root |
41 | */ |
41 | */ |
42 | static extavltree_t exttree; |
42 | static extavltree_t exttree; |
43 | 43 | ||
44 | /* |
44 | /* |
45 | * extavltree nodes in array for faster allocating |
45 | * extavltree nodes in array for faster allocating |
46 | */ |
46 | */ |
47 | static extavltree_node_t extavltree_nodes[NODE_COUNT]; |
47 | static extavltree_node_t extavltree_nodes[NODE_COUNT]; |
48 | 48 | ||
49 | /* |
49 | /* |
50 | * head of free nodes' list: |
50 | * head of free nodes' list: |
51 | */ |
51 | */ |
52 | static extavltree_node_t *first_free_node = NULL; |
52 | static extavltree_node_t *first_free_node = NULL; |
53 | 53 | ||
54 | 54 | ||
55 | 55 | ||
56 | static int exttree_test_height(extavltree_node_t *node,bool timeout); |
56 | static int exttree_test_height(extavltree_node_t *node,bool timeout); |
57 | static extavltree_node_t *exttree_test_parents(extavltree_node_t *node); |
57 | static extavltree_node_t *exttree_test_parents(extavltree_node_t *node); |
58 | static void print_exttree_structure_flat (extavltree_node_t *node, int level); |
58 | static void print_exttree_structure_flat (extavltree_node_t *node, int level); |
59 | static bool exttree_test_link(int node_count); |
59 | static bool exttree_test_link(int node_count); |
60 | static void print_exttree_link(int node_count); |
60 | static void print_exttree_link(void); |
61 | static extavltree_node_t *alloc_extavltree_node(void); |
61 | static extavltree_node_t *alloc_extavltree_node(void); |
62 | 62 | ||
63 | 63 | ||
64 | 64 | ||
65 | //vraci hloubku stromu |
65 | //vraci hloubku stromu |
66 | static int exttree_test_height(extavltree_node_t *node,bool timeout) |
66 | static int exttree_test_height(extavltree_node_t *node,bool timeout) |
67 | { |
67 | { |
68 | int h1, h2; |
68 | int h1, h2; |
69 | 69 | ||
70 | if (!node) return -1; |
70 | if (!node) return -1; |
71 | 71 | ||
72 | h1 = exttree_test_height(node->lft,timeout) + 1; |
72 | h1 = exttree_test_height(node->lft,timeout) + 1; |
73 | if (!timeout && node->lft_height != h1) { |
73 | if (!timeout && node->lft_height != h1) { |
74 | printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node); |
74 | printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node); |
75 | } |
75 | } |
76 | h2 = exttree_test_height(node->rgt,0) + 1; |
76 | h2 = exttree_test_height(node->rgt,0) + 1; |
77 | if (node->rgt_height != h2) { |
77 | if (node->rgt_height != h2) { |
78 | printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node); |
78 | printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node); |
79 | } |
79 | } |
80 | if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) { |
80 | if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) { |
81 | printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node); |
81 | printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node); |
82 | } |
82 | } |
83 | 83 | ||
84 | return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height); |
84 | return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height); |
85 | } |
85 | } |
86 | 86 | ||
87 | 87 | ||
88 | /** Tests par atribute of every tree node |
88 | /** Tests par atribute of every tree node |
89 | * |
89 | * |
90 | */ |
90 | */ |
91 | static extavltree_node_t *exttree_test_parents(extavltree_node_t *node) |
91 | static extavltree_node_t *exttree_test_parents(extavltree_node_t *node) |
92 | { |
92 | { |
93 | extavltree_node_t *tmp; |
93 | extavltree_node_t *tmp; |
94 | 94 | ||
95 | if (!node) return NULL; |
95 | if (!node) return NULL; |
96 | 96 | ||
97 | if (node->lft) { |
97 | if (node->lft) { |
98 | tmp = exttree_test_parents(node->lft); |
98 | tmp = exttree_test_parents(node->lft); |
99 | if (tmp != node) { |
99 | if (tmp != node) { |
100 | printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft); |
100 | printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft); |
101 | } |
101 | } |
102 | } |
102 | } |
103 | if (node->rgt) { |
103 | if (node->rgt) { |
104 | tmp = exttree_test_parents(node->rgt); |
104 | tmp = exttree_test_parents(node->rgt); |
105 | if (tmp != node) { |
105 | if (tmp != node) { |
106 | printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt); |
106 | printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt); |
107 | } |
107 | } |
108 | } |
108 | } |
109 | return node->par; |
109 | return node->par; |
110 | } |
110 | } |
111 | 111 | ||
112 | /** Checks list of nodes |
112 | /** Checks list of nodes |
113 | * |
113 | * |
114 | */ |
114 | */ |
115 | static bool exttree_test_link(int node_count) |
115 | static bool exttree_test_link(int node_count) |
116 | { |
116 | { |
117 | extavltree_node_t *node; |
117 | extavltree_node_t *node; |
118 | int i; |
118 | int i; |
119 | bool test_link = true; |
119 | bool test_link = true; |
120 | 120 | ||
121 | for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) { |
121 | for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) { |
122 | if ((node->next != &(exttree.head)) && (node->key > node->next->key)) { |
122 | if ((node->next != &(exttree.head)) && (node->key > node->next->key)) { |
123 | printf("\nList is not sorted (forward direction) at key: %d\n",node->key); |
123 | printf("\nList is not sorted (forward direction) at key: %d\n",node->key); |
124 | test_link = false; |
124 | test_link = false; |
125 | } |
125 | } |
126 | } |
126 | } |
127 | if (node_count && i != node_count) { |
127 | if (i != node_count) { |
128 | printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
128 | printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
129 | test_link = false; |
129 | test_link = false; |
130 | } |
130 | } |
131 | for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) { |
131 | for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) { |
132 | if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) { |
132 | if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) { |
133 | printf("\nList is not sorted (backward direction) at key: %d\n",node->key); |
133 | printf("\nList is not sorted (backward direction) at key: %d\n",node->key); |
134 | test_link = false; |
134 | test_link = false; |
135 | } |
135 | } |
136 | } |
136 | } |
137 | if (node_count && i != node_count) { |
137 | if (i != node_count) { |
138 | printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
138 | printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count); |
139 | test_link = false; |
139 | test_link = false; |
140 | } |
140 | } |
141 | return test_link; |
141 | return test_link; |
142 | } |
142 | } |
143 | 143 | ||
144 | /** Prints the structure of node, which is level levels from the top of the tree. |
144 | /** Prints the structure of node, which is level levels from the top of the tree. |
145 | * |
145 | * |
146 | */ |
146 | */ |
147 | static void print_exttree_structure_flat (extavltree_node_t *node, int level) |
147 | static void print_exttree_structure_flat (extavltree_node_t *node, int level) |
148 | { |
148 | { |
149 | extavltree_node_t *tmp; |
149 | extavltree_node_t *tmp; |
150 | int i; |
150 | int i; |
151 | 151 | ||
152 | if (level > 16) |
152 | if (level > 16) |
153 | { |
153 | { |
154 | printf ("[...]"); |
154 | printf ("[...]"); |
155 | return; |
155 | return; |
156 | } |
156 | } |
157 | 157 | ||
158 | if (node == NULL) |
158 | if (node == NULL) |
159 | return; |
159 | return; |
160 | 160 | ||
161 | for (tmp = node,i = 0; tmp->key == node->key; tmp = tmp->next,i++) |
161 | for (tmp = node,i = 0; tmp->key == node->key; tmp = tmp->next,i++) |
162 | ; |
162 | ; |
163 | 163 | ||
164 | printf ("%d[%d,%d,(%d)]", node->key,node->lft_height,node->rgt_height,i); |
164 | printf ("%d[%d,%d,(%d)]", node->key,node->lft_height,node->rgt_height,i); |
165 | if (node->lft != NULL || node->rgt != NULL) |
165 | if (node->lft != NULL || node->rgt != NULL) |
166 | { |
166 | { |
167 | printf("("); |
167 | printf("("); |
168 | 168 | ||
169 | print_exttree_structure_flat (node->lft, level + 1); |
169 | print_exttree_structure_flat (node->lft, level + 1); |
170 | if (node->rgt != NULL) |
170 | if (node->rgt != NULL) |
171 | { |
171 | { |
172 | printf(","); |
172 | printf(","); |
173 | print_exttree_structure_flat (node->rgt, level + 1); |
173 | print_exttree_structure_flat (node->rgt, level + 1); |
174 | } |
174 | } |
175 | 175 | ||
176 | printf(")"); |
176 | printf(")"); |
177 | } |
177 | } |
178 | } |
178 | } |
179 | 179 | ||
180 | /** Prints list of nodes |
180 | /** Prints list of nodes |
181 | * |
181 | * |
182 | */ |
182 | */ |
183 | static void print_exttree_link(int node_count) |
183 | static void print_exttree_link(void) |
184 | { |
184 | { |
185 | extavltree_node_t *node; |
185 | extavltree_node_t *node; |
186 | printf("\n"); |
186 | printf("\n"); |
187 | for (node = exttree.head.next; node != &(exttree.head); node = node->next) { |
187 | for (node = exttree.head.next; node != &(exttree.head); node = node->next) { |
188 | printf(" %d,",node->key); |
188 | printf(" %d,",node->key); |
189 | } |
189 | } |
190 | for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) { |
190 | for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) { |
191 | printf(" %d,",node->key); |
191 | printf(" %d,",node->key); |
192 | } |
192 | } |
193 | } |
193 | } |
194 | 194 | ||
195 | //**************************************************************** |
195 | //**************************************************************** |
196 | static void alloc_extavltree_node_prepare(void) |
196 | static void alloc_extavltree_node_prepare(void) |
197 | { |
197 | { |
198 | int i; |
198 | int i; |
199 | 199 | ||
200 | for (i = 0; i < NODE_COUNT - 1; i++) { |
200 | for (i = 0; i < NODE_COUNT - 1; i++) { |
201 | extavltree_nodes[i].next = &(extavltree_nodes[i+1]); |
201 | extavltree_nodes[i].next = &(extavltree_nodes[i+1]); |
202 | } |
202 | } |
203 | /* |
203 | /* |
204 | * Node keys which will be used for insertion. Up to NODE_COUNT size of array. |
204 | * Node keys which will be used for insertion. Up to NODE_COUNT size of array. |
205 | */ |
205 | */ |
206 | 206 | ||
207 | // First tree node and same key |
207 | // First tree node and same key |
208 | extavltree_nodes[0].key = 60; |
208 | extavltree_nodes[0].key = 60; |
209 | extavltree_nodes[1].key = 60; |
209 | extavltree_nodes[1].key = 60; |
210 | extavltree_nodes[2].key = 60; |
210 | extavltree_nodes[2].key = 60; |
211 | //LL rotation |
211 | //LL rotation |
212 | extavltree_nodes[3].key = 50; |
212 | extavltree_nodes[3].key = 50; |
213 | extavltree_nodes[4].key = 40; |
213 | extavltree_nodes[4].key = 40; |
214 | extavltree_nodes[5].key = 30; |
214 | extavltree_nodes[5].key = 30; |
215 | //LR rotation |
215 | //LR rotation |
216 | extavltree_nodes[6].key = 20; |
216 | extavltree_nodes[6].key = 20; |
217 | extavltree_nodes[7].key = 20; |
217 | extavltree_nodes[7].key = 20; |
218 | extavltree_nodes[8].key = 25; |
218 | extavltree_nodes[8].key = 25; |
219 | extavltree_nodes[9].key = 25; |
219 | extavltree_nodes[9].key = 25; |
220 | //LL rotation in lower floor |
220 | //LL rotation in lower floor |
221 | extavltree_nodes[10].key = 35; |
221 | extavltree_nodes[10].key = 35; |
222 | //RR rotation |
222 | //RR rotation |
223 | extavltree_nodes[11].key = 70; |
223 | extavltree_nodes[11].key = 70; |
224 | extavltree_nodes[12].key = 80; |
224 | extavltree_nodes[12].key = 80; |
225 | //RL rotation |
225 | //RL rotation |
226 | extavltree_nodes[13].key = 90; |
226 | extavltree_nodes[13].key = 90; |
227 | extavltree_nodes[14].key = 85; |
227 | extavltree_nodes[14].key = 85; |
228 | extavltree_nodes[15].key = 100; |
228 | extavltree_nodes[15].key = 100; |
229 | extavltree_nodes[16].key = 200; |
229 | extavltree_nodes[16].key = 200; |
230 | extavltree_nodes[17].key = 300; |
230 | extavltree_nodes[17].key = 300; |
231 | extavltree_nodes[18].key = 400; |
231 | extavltree_nodes[18].key = 400; |
232 | extavltree_nodes[19].key = 500; |
232 | extavltree_nodes[19].key = 500; |
233 | extavltree_nodes[20].key = 600; |
233 | extavltree_nodes[20].key = 600; |
234 | 234 | ||
235 | for (i = 21; i < NODE_COUNT; i++) |
235 | for (i = 21; i < NODE_COUNT; i++) |
236 | extavltree_nodes[i].key = i * 3; |
236 | extavltree_nodes[i].key = i * 3; |
237 | 237 | ||
238 | extavltree_nodes[i].next = NULL; |
238 | extavltree_nodes[i].next = NULL; |
239 | first_free_node = &(extavltree_nodes[0]); |
239 | first_free_node = &(extavltree_nodes[0]); |
240 | } |
240 | } |
241 | 241 | ||
242 | static extavltree_node_t *alloc_extavltree_node(void) |
242 | static extavltree_node_t *alloc_extavltree_node(void) |
243 | { |
243 | { |
244 | extavltree_node_t *node; |
244 | extavltree_node_t *node; |
245 | 245 | ||
246 | node = first_free_node; |
246 | node = first_free_node; |
247 | first_free_node = first_free_node->next; |
247 | first_free_node = first_free_node->next; |
248 | 248 | ||
249 | return node; |
249 | return node; |
250 | } |
250 | } |
251 | //**************************************************************** |
251 | //**************************************************************** |
252 | 252 | ||
253 | static void test_exttree_insert(extavltree_t *tree, unsigned int node_count, int quiet) |
253 | static void test_exttree_insert(extavltree_t *tree, unsigned int node_count, int quiet) |
254 | { |
254 | { |
255 | unsigned int i; |
255 | unsigned int i; |
256 | extavltree_node_t *newnode; |
256 | extavltree_node_t *newnode; |
257 | 257 | ||
258 | /* |
258 | /* |
259 | * Initialize tree before using. |
259 | * Initialize tree before using. |
260 | */ |
260 | */ |
261 | extavltree_create(tree); |
261 | extavltree_create(tree); |
262 | 262 | ||
263 | if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count); |
263 | if (!quiet) printf("\nInserting %d nodes ...\n", node_count); |
264 | 264 | ||
265 | for (i = 0; i < node_count; i++) { |
265 | for (i = 0; i < node_count; i++) { |
266 | newnode = alloc_extavltree_node(); |
266 | newnode = alloc_extavltree_node(); |
267 | //if (!quiet) printf("[[[%d]]]\n",newnode->key); |
267 | //if (!quiet) printf("[[[%d]]]\n",newnode->key); |
268 | 268 | ||
269 | extavltree_insert(tree, newnode); |
269 | extavltree_insert(tree, newnode); |
270 | if (!quiet) { |
270 | if (!quiet) { |
271 | if (!exttree_test_link(i+1)) { |
271 | if (!exttree_test_link(i+1)) { |
272 | print_exttree_link(i+1); |
272 | print_exttree_link(); |
273 | printf("\n"); |
273 | printf("\n"); |
274 | } |
274 | } |
275 | exttree_test_parents(tree->root); |
275 | exttree_test_parents(tree->root); |
276 | exttree_test_height(tree->root,1); |
276 | exttree_test_height(tree->root,1); |
277 | } |
277 | } |
278 | } |
278 | } |
279 | 279 | ||
280 | if (!quiet) printf("Inserting was finished\n"); |
280 | if (!quiet) printf("Inserting was finished\n"); |
281 | } |
281 | } |
282 | 282 | ||
283 | /* |
283 | /* |
284 | static extavltree_node_t *exttree_random_delete_node(extavltree_t *tree, int node_count, int r, bool quiet) |
284 | static extavltree_node_t *exttree_random_delete_node(extavltree_t *tree, int node_count, int r, bool quiet) |
285 | { |
285 | { |
286 | extavltree_node_t *delnode; |
286 | extavltree_node_t *delnode; |
287 | int i; |
287 | int i; |
288 | 288 | ||
289 | for (i = 0,delnode = tree->head.next; i < (r-1); i++) |
289 | for (i = 0,delnode = tree->head.next; i < (r-1); i++) |
290 | delnode = delnode->next; |
290 | delnode = delnode->next; |
291 | |
291 | |
292 | if (delnode == &tree->head) { |
292 | if (delnode == &tree->head) { |
293 | if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r); |
293 | if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r); |
294 | return NULL; |
294 | return NULL; |
295 | } |
295 | } |
296 | 296 | ||
297 | extavltree_delete(tree, delnode); |
297 | extavltree_delete(tree, delnode); |
298 | 298 | ||
299 | return delnode; |
299 | return delnode; |
300 | } |
300 | } |
301 | */ |
301 | */ |
302 | 302 | ||
303 | static void test_exttree_delete(extavltree_t *tree, int node_count, int node_position, bool quiet) |
303 | static void test_exttree_delete(extavltree_t *tree, int node_count, int node_position, bool quiet) |
304 | { |
304 | { |
305 | extavltree_node_t *delnode; |
305 | extavltree_node_t *delnode; |
306 | unsigned int i; |
306 | unsigned int i; |
307 | 307 | ||
308 | //aktualni pocet tiku: |
308 | //aktualni pocet tiku: |
309 | if (!quiet) printf("Deleting tree...\n"); |
309 | if (!quiet) printf("Deleting tree...\n"); |
310 | 310 | ||
311 | switch(node_position) { |
311 | switch(node_position) { |
312 | case 0: //mazani vzdy korene |
312 | case 0: //mazani vzdy korene |
313 | if (!quiet) printf("\n\nDelete root nodes\n"); |
313 | if (!quiet) printf("\nDelete root nodes\n"); |
314 | i = node_count; |
314 | i = node_count - 1; |
315 | while(tree->root != NULL) { |
315 | while(tree->root != NULL) { |
316 | delnode = tree->root; |
316 | delnode = tree->root; |
317 | extavltree_delete(tree,delnode); |
317 | extavltree_delete(tree,delnode); |
318 | if (!quiet) { |
318 | if (!quiet) { |
319 | if (!exttree_test_link(i)) { |
319 | if (!exttree_test_link(i)) { |
320 | print_exttree_link(i); |
320 | print_exttree_link(); |
321 | printf("\n"); |
321 | printf("\n"); |
322 | } |
322 | } |
323 | exttree_test_parents(tree->root); |
323 | exttree_test_parents(tree->root); |
324 | exttree_test_height(tree->root,1); |
324 | exttree_test_height(tree->root,1); |
325 | } |
325 | } |
326 | i--; |
326 | i--; |
327 | } |
327 | } |
328 | 328 | ||
329 | break; |
329 | break; |
330 | case 1: |
330 | case 1: |
331 | if (!quiet) printf("\n\nDelete nodes according to their time of origin\n"); |
331 | if (!quiet) printf("\nDelete nodes according to their time of origin\n"); |
332 | for (i = 0; i < node_count; i++) { |
332 | for (i = 0; i < node_count; i++) { |
333 | extavltree_delete(tree,&(extavltree_nodes[i])); |
333 | extavltree_delete(tree,&(extavltree_nodes[i])); |
334 | if (!quiet) { |
334 | if (!quiet) { |
335 | if (!exttree_test_link(i+1)) { |
335 | if (!exttree_test_link(node_count-i-1)) { |
336 | print_exttree_link(i+1); |
336 | print_exttree_link(); |
337 | printf("\n"); |
337 | printf("\n"); |
338 | } |
338 | } |
339 | exttree_test_parents(tree->root); |
339 | exttree_test_parents(tree->root); |
340 | exttree_test_height(tree->root,1); |
340 | exttree_test_height(tree->root,1); |
341 | } |
341 | } |
342 | } |
342 | } |
343 | 343 | ||
344 | break; |
344 | break; |
345 | } |
345 | } |
346 | 346 | ||
347 | if (!quiet) printf("Deletion was finished\n"); |
347 | if (!quiet) printf("Deletion was finished\n"); |
348 | } |
348 | } |
349 | 349 | ||
350 | static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet) |
350 | static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet) |
351 | { |
351 | { |
352 | int i = node_count; |
352 | int i = node_count - 1; |
353 | 353 | ||
354 | if (!quiet) printf("Timeout tree ...\n"); |
354 | if (!quiet) printf("\nTimeout tree ...\n"); |
355 | 355 | ||
356 | while(tree->head.next != &(tree->head)) { |
356 | while(tree->head.next != &(tree->head)) { |
357 | extavltree_delete_min(tree); |
357 | extavltree_delete_min(tree); |
358 | if (!quiet) { |
358 | if (!quiet) { |
359 | if (!exttree_test_link(i)) { |
359 | if (!exttree_test_link(i)) { |
360 | print_exttree_link(i); |
360 | print_exttree_link(); |
361 | printf("\n"); |
361 | printf("\n"); |
362 | } |
362 | } |
363 | exttree_test_parents(tree->root); |
363 | exttree_test_parents(tree->root); |
364 | exttree_test_height(tree->root,1); |
364 | exttree_test_height(tree->root,1); |
365 | } |
365 | } |
366 | i--; |
366 | i--; |
367 | } |
367 | } |
368 | 368 | ||
369 | if (!quiet && (i != 0)) printf("Bad node count. Some nodes have been lost!"); |
369 | if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n"); |
370 | 370 | ||
371 | if (!quiet) printf("Timeout tree finished\n"); |
371 | if (!quiet) printf("Timeout tree finished\n"); |
372 | } |
372 | } |
373 | 373 | ||
374 | /* |
374 | /* |
375 | void timeout_exttree_run(extavltree_t *tree, int operation_count, int verbal) |
375 | void timeout_exttree_run(extavltree_t *tree, int operation_count, int verbal) |
376 | { |
376 | { |
377 | int i; |
377 | int i; |
378 | extavltree_node_t *node; |
378 | extavltree_node_t *node; |
379 | int r; |
379 | int r; |
380 | int count; |
380 | int count; |
381 | |
381 | |
382 | //inicializace stromu: |
382 | //inicializace stromu: |
383 | extavltree_create(tree); |
383 | extavltree_create(tree); |
384 | |
384 | |
385 | for(i = 0, count = 0; i < operation_count; i++) { |
385 | for(i = 0, count = 0; i < operation_count; i++) { |
386 | if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) { |
386 | if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) { |
387 | if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne |
387 | if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne |
388 | node = exttree_random_delete_node(tree,(r % tree->count)); |
388 | node = exttree_random_delete_node(tree,(r % tree->count)); |
389 | //printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node); |
389 | //printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node); |
390 | node->next = first_free_node; |
390 | node->next = first_free_node; |
391 | first_free_node = node; |
391 | first_free_node = node; |
392 | } else { |
392 | } else { |
393 | node = tree->head.next; |
393 | node = tree->head.next; |
394 | extavltree_delete_min(tree); |
394 | extavltree_delete_min(tree); |
395 | //printf("TIMEOUT key: %d, address: %p\n",node->key,node); |
395 | //printf("TIMEOUT key: %d, address: %p\n",node->key,node); |
396 | node->next = first_free_node; |
396 | node->next = first_free_node; |
397 | first_free_node = node; |
397 | first_free_node = node; |
398 | } |
398 | } |
399 | } else { |
399 | } else { |
400 | node = alloc_extavltree_node_random(); |
400 | node = alloc_extavltree_node_random(); |
401 | //printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node); |
401 | //printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node); |
402 | extavltree_insert(tree, node); |
402 | extavltree_insert(tree, node); |
403 | } |
403 | } |
404 | //test_exttree_height(tree->root,1); |
404 | //test_exttree_height(tree->root,1); |
405 | //exttree_test_parents(tree->root); |
405 | //exttree_test_parents(tree->root); |
406 | //print_exttree_link(tree->count); |
406 | //print_exttree_link(tree->count); |
407 | //print_exttree_structure_flat(tree->root,0); putchar('\n'); putchar('\n'); |
407 | //print_exttree_structure_flat(tree->root,0); putchar('\n'); putchar('\n'); |
408 | } |
408 | } |
409 | } |
409 | } |
410 | */ |
410 | */ |
411 | 411 | ||
412 | char * test_extavltree1(bool quiet) |
412 | char * test_extavltree1(bool quiet) |
413 | { |
413 | { |
414 | alloc_extavltree_node_prepare(); |
414 | alloc_extavltree_node_prepare(); |
415 | test_exttree_insert(&exttree, NODE_COUNT, quiet); |
415 | test_exttree_insert(&exttree, NODE_COUNT, quiet); |
416 | test_exttree_delete(&exttree, NODE_COUNT, 0, quiet); |
416 | test_exttree_delete(&exttree, NODE_COUNT, 0, quiet); |
417 | 417 | ||
418 | alloc_extavltree_node_prepare(); |
418 | alloc_extavltree_node_prepare(); |
419 | test_exttree_insert(&exttree, NODE_COUNT, quiet); |
419 | test_exttree_insert(&exttree, NODE_COUNT, quiet); |
420 | test_exttree_delete(&exttree, NODE_COUNT, 1, quiet); |
420 | test_exttree_delete(&exttree, NODE_COUNT, 1, quiet); |
421 | 421 | ||
422 | alloc_extavltree_node_prepare(); |
422 | alloc_extavltree_node_prepare(); |
423 | test_exttree_insert(&exttree, NODE_COUNT, quiet); |
423 | test_exttree_insert(&exttree, NODE_COUNT, quiet); |
424 | timeout_exttree(&exttree, NODE_COUNT, quiet); |
424 | timeout_exttree(&exttree, NODE_COUNT, quiet); |
425 | 425 | ||
426 | return NULL; |
426 | return NULL; |
427 | } |
427 | } |
428 | 428 |