Rev 2461 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2461 | Rev 2466 | ||
---|---|---|---|
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 <adt/favl.h> |
32 | #include <adt/favl.h> |
33 | #include <adt/extavl.h> |
33 | #include <adt/extavl.h> |
34 | #include <adt/extavlrel.h> |
34 | #include <adt/extavlrel.h> |
35 | #include <debug.h> |
35 | #include <debug.h> |
36 | #include <arch/types.h> |
36 | #include <arch/types.h> |
37 | #include <arch/cycle.h> |
37 | #include <arch/cycle.h> |
38 | #include <arch/asm.h> |
38 | #include <arch/asm.h> |
39 | #include <panic.h> |
39 | #include <panic.h> |
40 | #include <mm/slab.h> |
40 | #include <mm/slab.h> |
41 | 41 | ||
42 | /* |
42 | /* |
43 | * Node count must be more then 1000! |
43 | * Node count must be more then 1000! |
44 | */ |
44 | */ |
45 | #define NODE_COUNT 100000 |
45 | #define NODE_COUNT 100000 |
- | 46 | /* |
|
- | 47 | * Seed constant. |
|
- | 48 | */ |
|
46 | #define GEN_NUM 275604541 |
49 | #define GEN_NUM 275604541 |
47 | #define OPERATION_COUNT 1000000 |
50 | #define OPERATION_COUNT 1000000 |
48 | #define TEST_COUNT 3 |
51 | #define TEST_COUNT 3 |
49 | 52 | ||
50 | static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT}; |
53 | static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT}; |
51 | 54 | ||
52 | /* |
55 | /* |
53 | * Wrapper tree data structures. |
56 | * Wrapper tree data structures. |
54 | */ |
57 | */ |
55 | static avltree_t avltree; |
58 | static avltree_t avltree; |
56 | static favltree_t favltree; |
59 | static favltree_t favltree; |
57 | static extavltree_t extavltree; |
60 | static extavltree_t extavltree; |
58 | static extavlreltree_t extavlreltree; |
61 | static extavlreltree_t extavlreltree; |
59 | 62 | ||
60 | /* |
63 | /* |
61 | * Slab cache variables. |
64 | * Slab cache variables. |
62 | */ |
65 | */ |
63 | static slab_cache_t *avl_slab; |
66 | static slab_cache_t *avl_slab; |
64 | static slab_cache_t *favl_slab; |
67 | static slab_cache_t *favl_slab; |
65 | static slab_cache_t *extavl_slab; |
68 | static slab_cache_t *extavl_slab; |
66 | static slab_cache_t *extavlrel_slab; |
69 | static slab_cache_t *extavlrel_slab; |
67 | 70 | ||
68 | /* |
71 | /* |
69 | * Head of free nodes' list: |
72 | * Head of free nodes' list: |
70 | */ |
73 | */ |
71 | static avltree_node_t *avl_ffn = NULL; |
74 | static avltree_node_t *avl_ffn = NULL; |
72 | static favltree_node_t *favl_ffn = NULL; |
75 | static favltree_node_t *favl_ffn = NULL; |
73 | static extavltree_node_t *extavl_ffn = NULL; |
76 | static extavltree_node_t *extavl_ffn = NULL; |
74 | static extavlreltree_node_t *extavlrel_ffn = NULL; |
77 | static extavlreltree_node_t *extavlrel_ffn = NULL; |
75 | 78 | ||
76 | 79 | ||
77 | static void keys_prepare(int node_count, int type) |
80 | static void keys_prepare(int node_count, int type) |
78 | { |
81 | { |
79 | unsigned int i; |
82 | unsigned int i; |
80 | uint16_t s; |
83 | uint16_t s; |
81 | avltree_node_t *a = avl_ffn; |
84 | avltree_node_t *a = avl_ffn; |
82 | favltree_node_t *b = favl_ffn; |
85 | favltree_node_t *b = favl_ffn; |
83 | extavltree_node_t *c = extavl_ffn; |
86 | extavltree_node_t *c = extavl_ffn; |
84 | extavlreltree_node_t *d = extavlrel_ffn; |
87 | extavlreltree_node_t *d = extavlrel_ffn; |
85 | 88 | ||
86 | switch (type) { |
89 | switch (type) { |
87 | case 0: |
90 | case 0: |
88 | s = (uint16_t) get_cycle(); |
91 | s = (uint16_t) get_cycle(); |
89 | for (i = 0; i < node_count; i++) { |
92 | for (i = 0; i < node_count; i++) { |
90 | a->key = s; |
93 | a->key = s; |
91 | b->key = s; |
94 | b->key = s; |
92 | c->key = s; |
95 | c->key = s; |
93 | d->key = s; |
96 | d->key = s; |
94 | s += GEN_NUM; |
97 | s += GEN_NUM; |
95 | a = a->par; |
98 | a = a->par; |
96 | b = b->par; |
99 | b = b->par; |
97 | c = c->par; |
100 | c = c->par; |
98 | d = d->par; |
101 | d = d->par; |
99 | } |
102 | } |
100 | break; |
103 | break; |
101 | case 1: |
104 | case 1: |
102 | for (i = 1; i <= node_count; i++) { |
105 | for (i = 1; i <= node_count; i++) { |
103 | a->key = i; |
106 | a->key = i; |
104 | b->key = i; |
107 | b->key = i; |
105 | c->key = i; |
108 | c->key = i; |
106 | d->key = i; |
109 | d->key = i; |
107 | a = a->par; |
110 | a = a->par; |
108 | b = b->par; |
111 | b = b->par; |
109 | c = c->par; |
112 | c = c->par; |
110 | d = d->par; |
113 | d = d->par; |
111 | } |
114 | } |
112 | break; |
115 | break; |
113 | case 2: |
116 | case 2: |
114 | for (i = node_count; i > 0; i--) { |
117 | for (i = node_count; i > 0; i--) { |
115 | a->key = i; |
118 | a->key = i; |
116 | b->key = i; |
119 | b->key = i; |
117 | c->key = i; |
120 | c->key = i; |
118 | d->key = i; |
121 | d->key = i; |
119 | a = a->par; |
122 | a = a->par; |
120 | b = b->par; |
123 | b = b->par; |
121 | c = c->par; |
124 | c = c->par; |
122 | d = d->par; |
125 | d = d->par; |
123 | } |
126 | } |
124 | break; |
127 | break; |
125 | } |
128 | } |
126 | } |
129 | } |
127 | 130 | ||
128 | 131 | ||
129 | static bool alloc_nodes(int node_count) |
132 | static bool alloc_nodes(int node_count) |
130 | { |
133 | { |
131 | int i; |
134 | int i; |
132 | avltree_node_t *a; |
135 | avltree_node_t *a; |
133 | extavltree_node_t *b; |
136 | extavltree_node_t *b; |
134 | extavlreltree_node_t *c; |
137 | extavlreltree_node_t *c; |
135 | favltree_node_t *d; |
138 | favltree_node_t *d; |
136 | 139 | ||
137 | avl_ffn = NULL; |
140 | avl_ffn = NULL; |
138 | favl_ffn = NULL; |
141 | favl_ffn = NULL; |
139 | extavl_ffn = NULL; |
142 | extavl_ffn = NULL; |
140 | extavlrel_ffn = NULL; |
143 | extavlrel_ffn = NULL; |
141 | 144 | ||
142 | for (i = 0; i < node_count; i++) { |
145 | for (i = 0; i < node_count; i++) { |
143 | a = (avltree_node_t *) slab_alloc(avl_slab,0); |
146 | a = (avltree_node_t *) slab_alloc(avl_slab,0); |
144 | if (!a) { |
147 | if (!a) { |
145 | printf("Not enough memory to allocate test arrays."); |
148 | printf("Not enough memory to allocate test arrays."); |
146 | return false; |
149 | return false; |
147 | } |
150 | } |
148 | b = (extavltree_node_t *) slab_alloc(extavl_slab,0); |
151 | b = (extavltree_node_t *) slab_alloc(extavl_slab,0); |
149 | if (!b) { |
152 | if (!b) { |
150 | printf("Not enough memory to allocate test arrays."); |
153 | printf("Not enough memory to allocate test arrays."); |
151 | return false; |
154 | return false; |
152 | } |
155 | } |
153 | c = (extavlreltree_node_t *) slab_alloc(extavlrel_slab,0); |
156 | c = (extavlreltree_node_t *) slab_alloc(extavlrel_slab,0); |
154 | if (!c) { |
157 | if (!c) { |
155 | printf("Not enough memory to allocate test arrays."); |
158 | printf("Not enough memory to allocate test arrays."); |
156 | return false; |
159 | return false; |
157 | } |
160 | } |
158 | d = (favltree_node_t *) slab_alloc(favl_slab,0); |
161 | d = (favltree_node_t *) slab_alloc(favl_slab,0); |
159 | if (!d) { |
162 | if (!d) { |
160 | printf("Not enough memory to allocate test arrays."); |
163 | printf("Not enough memory to allocate test arrays."); |
161 | return false; |
164 | return false; |
162 | } |
165 | } |
163 | a->par = avl_ffn; |
166 | a->par = avl_ffn; |
164 | b->par = extavl_ffn; |
167 | b->par = extavl_ffn; |
165 | c->par = extavlrel_ffn; |
168 | c->par = extavlrel_ffn; |
166 | d->par = favl_ffn; |
169 | d->par = favl_ffn; |
167 | avl_ffn = a; |
170 | avl_ffn = a; |
168 | extavl_ffn = b; |
171 | extavl_ffn = b; |
169 | extavlrel_ffn = c; |
172 | extavlrel_ffn = c; |
170 | favl_ffn = d; |
173 | favl_ffn = d; |
171 | } |
174 | } |
172 | return true; |
175 | return true; |
173 | } |
176 | } |
174 | 177 | ||
175 | static void free_nodes(int node_count) |
178 | static void free_nodes(int node_count) |
176 | { |
179 | { |
177 | int i; |
180 | int i; |
178 | avltree_node_t *a; |
181 | avltree_node_t *a; |
179 | extavltree_node_t *b; |
182 | extavltree_node_t *b; |
180 | extavlreltree_node_t *c; |
183 | extavlreltree_node_t *c; |
181 | favltree_node_t *d; |
184 | favltree_node_t *d; |
182 | 185 | ||
183 | for (i = 0; i < node_count; i++) { |
186 | for (i = 0; i < node_count; i++) { |
184 | a = avl_ffn; |
187 | a = avl_ffn; |
185 | b = extavl_ffn; |
188 | b = extavl_ffn; |
186 | c = extavlrel_ffn; |
189 | c = extavlrel_ffn; |
187 | d = favl_ffn; |
190 | d = favl_ffn; |
188 | if (!a || !b || !c || !d) { |
191 | if (!a || !b || !c || !d) { |
189 | printf("Deleted nodes: %d, node count: %d, a: %p, b: %p, c: %p, d: %p\n", |
192 | printf("Deleted nodes: %d, node count: %d, a: %p, b: %p, c: %p, d: %p\n", |
190 | i,node_count,a,b,c,d); |
193 | i,node_count,a,b,c,d); |
191 | panic("Some nodes have been lost!"); |
194 | panic("Some nodes have been lost!"); |
192 | } |
195 | } |
193 | avl_ffn = avl_ffn->par; |
196 | avl_ffn = avl_ffn->par; |
194 | extavl_ffn = extavl_ffn->par; |
197 | extavl_ffn = extavl_ffn->par; |
195 | extavlrel_ffn = extavlrel_ffn->par; |
198 | extavlrel_ffn = extavlrel_ffn->par; |
196 | favl_ffn = favl_ffn->par; |
199 | favl_ffn = favl_ffn->par; |
197 | slab_free(avl_slab,a); |
200 | slab_free(avl_slab,a); |
198 | slab_free(extavl_slab,b); |
201 | slab_free(extavl_slab,b); |
199 | slab_free(extavlrel_slab,c); |
202 | slab_free(extavlrel_slab,c); |
200 | slab_free(favl_slab,d); |
203 | slab_free(favl_slab,d); |
201 | } |
204 | } |
202 | } |
205 | } |
203 | 206 | ||
204 | static avltree_node_t *alloc_avltree_node(void) |
207 | static avltree_node_t *alloc_avltree_node(void) |
205 | { |
208 | { |
206 | avltree_node_t *node; |
209 | avltree_node_t *node; |
207 | 210 | ||
208 | node = avl_ffn; |
211 | node = avl_ffn; |
209 | avl_ffn = avl_ffn->par; |
212 | avl_ffn = avl_ffn->par; |
210 | 213 | ||
211 | return node; |
214 | return node; |
212 | } |
215 | } |
213 | 216 | ||
214 | static favltree_node_t *alloc_favltree_node(void) |
217 | static favltree_node_t *alloc_favltree_node(void) |
215 | { |
218 | { |
216 | favltree_node_t *node; |
219 | favltree_node_t *node; |
217 | 220 | ||
218 | node = favl_ffn; |
221 | node = favl_ffn; |
219 | favl_ffn = favl_ffn->par; |
222 | favl_ffn = favl_ffn->par; |
220 | 223 | ||
221 | return node; |
224 | return node; |
222 | } |
225 | } |
223 | 226 | ||
224 | static extavltree_node_t *alloc_extavltree_node(void) |
227 | static extavltree_node_t *alloc_extavltree_node(void) |
225 | { |
228 | { |
226 | extavltree_node_t *node; |
229 | extavltree_node_t *node; |
227 | 230 | ||
228 | node = extavl_ffn; |
231 | node = extavl_ffn; |
229 | 232 | ||
230 | extavl_ffn = extavl_ffn->par; |
233 | extavl_ffn = extavl_ffn->par; |
231 | 234 | ||
232 | return node; |
235 | return node; |
233 | } |
236 | } |
234 | 237 | ||
235 | static extavlreltree_node_t *alloc_extavlreltree_node(void) |
238 | static extavlreltree_node_t *alloc_extavlreltree_node(void) |
236 | { |
239 | { |
237 | extavlreltree_node_t *node; |
240 | extavlreltree_node_t *node; |
238 | 241 | ||
239 | node = extavlrel_ffn; |
242 | node = extavlrel_ffn; |
240 | extavlrel_ffn = extavlrel_ffn->par; |
243 | extavlrel_ffn = extavlrel_ffn->par; |
241 | 244 | ||
242 | return node; |
245 | return node; |
243 | } |
246 | } |
244 | 247 | ||
245 | static void free_avltree_node(avltree_node_t *node) |
248 | static void free_avltree_node(avltree_node_t *node) |
246 | { |
249 | { |
247 | node->par = avl_ffn; |
250 | node->par = avl_ffn; |
248 | avl_ffn = node; |
251 | avl_ffn = node; |
249 | } |
252 | } |
250 | 253 | ||
251 | static void free_favltree_node(favltree_node_t *node) |
254 | static void free_favltree_node(favltree_node_t *node) |
252 | { |
255 | { |
253 | node->par = favl_ffn; |
256 | node->par = favl_ffn; |
254 | favl_ffn = node; |
257 | favl_ffn = node; |
255 | } |
258 | } |
256 | 259 | ||
257 | static void free_extavltree_node(extavltree_node_t *node) |
260 | static void free_extavltree_node(extavltree_node_t *node) |
258 | { |
261 | { |
259 | node->par = extavl_ffn; |
262 | node->par = extavl_ffn; |
260 | extavl_ffn = node; |
263 | extavl_ffn = node; |
261 | } |
264 | } |
262 | 265 | ||
263 | static void free_extavlreltree_node(extavlreltree_node_t *node) |
266 | static void free_extavlreltree_node(extavlreltree_node_t *node) |
264 | { |
267 | { |
265 | node->par = extavlrel_ffn; |
268 | node->par = extavlrel_ffn; |
266 | extavlrel_ffn = node; |
269 | extavlrel_ffn = node; |
267 | } |
270 | } |
268 | 271 | ||
269 | /** Insert keys of ascending sequence and delete tree deleting root nodes. |
272 | /** Insert keys of ascending sequence and delete tree deleting root nodes. |
270 | */ |
273 | */ |
271 | static void test1(void) |
274 | static void test1(void) |
272 | { |
275 | { |
273 | uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
276 | uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
274 | uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT]; |
277 | uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT]; |
275 | unsigned int i,ii; |
278 | unsigned int i,ii; |
276 | avltree_node_t *a; |
279 | avltree_node_t *a; |
277 | extavltree_node_t *b; |
280 | extavltree_node_t *b; |
278 | extavlreltree_node_t *c; |
281 | extavlreltree_node_t *c; |
279 | favltree_node_t *d; |
282 | favltree_node_t *d; |
280 | 283 | ||
281 | 284 | ||
282 | printf("INSERT nodes with keys of ascending sequence.\n"); |
285 | printf("INSERT nodes with keys of ascending sequence.\n"); |
283 | printf("Nodes:\t\t"); |
286 | printf("Nodes:\t\t"); |
284 | for (ii = 0; ii < TEST_COUNT; ii++) { |
287 | for (ii = 0; ii < TEST_COUNT; ii++) { |
285 | printf("%20u",node_count[ii]); |
288 | printf("%20u",node_count[ii]); |
286 | keys_prepare(node_count[ii],1); |
289 | keys_prepare(node_count[ii],1); |
287 | 290 | ||
288 | /* |
291 | /* |
289 | * AVL INSERT |
292 | * AVL INSERT |
290 | */ |
293 | */ |
291 | s[0][ii] = get_cycle(); |
294 | s[0][ii] = get_cycle(); |
292 | 295 | ||
293 | avltree_create(&avltree); |
296 | avltree_create(&avltree); |
294 | for (i = 0; i < node_count[ii]; i++) { |
297 | for (i = 0; i < node_count[ii]; i++) { |
295 | avltree_insert(&avltree,alloc_avltree_node()); |
298 | avltree_insert(&avltree,alloc_avltree_node()); |
296 | } |
299 | } |
297 | 300 | ||
298 | f[0][ii] = get_cycle(); |
301 | f[0][ii] = get_cycle(); |
299 | /* |
302 | /* |
300 | * AVL DELETE |
303 | * AVL DELETE |
301 | */ |
304 | */ |
302 | ds[0][ii] = get_cycle(); |
305 | ds[0][ii] = get_cycle(); |
303 | 306 | ||
304 | while ((a = avltree.root) != NULL) { |
307 | while ((a = avltree.root) != NULL) { |
305 | avltree_delete(&avltree,a); |
308 | avltree_delete(&avltree,a); |
306 | free_avltree_node(a); |
309 | free_avltree_node(a); |
307 | } |
310 | } |
308 | 311 | ||
309 | df[0][ii] = get_cycle(); |
312 | df[0][ii] = get_cycle(); |
310 | 313 | ||
311 | /* |
314 | /* |
312 | * ExtAVL INSERT |
315 | * ExtAVL INSERT |
313 | */ |
316 | */ |
314 | s[1][ii] = get_cycle(); |
317 | s[1][ii] = get_cycle(); |
315 | 318 | ||
316 | extavltree_create(&extavltree); |
319 | extavltree_create(&extavltree); |
317 | for (i = 0; i < node_count[ii]; i++) { |
320 | for (i = 0; i < node_count[ii]; i++) { |
318 | extavltree_insert(&extavltree,alloc_extavltree_node()); |
321 | extavltree_insert(&extavltree,alloc_extavltree_node()); |
319 | } |
322 | } |
320 | 323 | ||
321 | f[1][ii] = get_cycle(); |
324 | f[1][ii] = get_cycle(); |
322 | /* |
325 | /* |
323 | * ExtAVL DELETE |
326 | * ExtAVL DELETE |
324 | */ |
327 | */ |
325 | ds[1][ii] = get_cycle(); |
328 | ds[1][ii] = get_cycle(); |
326 | 329 | ||
327 | while ((b = extavltree.root) != NULL) { |
330 | while ((b = extavltree.root) != NULL) { |
328 | extavltree_delete(&extavltree,b); |
331 | extavltree_delete(&extavltree,b); |
329 | free_extavltree_node(b); |
332 | free_extavltree_node(b); |
330 | } |
333 | } |
331 | 334 | ||
332 | df[1][ii] = get_cycle(); |
335 | df[1][ii] = get_cycle(); |
333 | 336 | ||
334 | /* |
337 | /* |
335 | * ExtAVLrel INSERT |
338 | * ExtAVLrel INSERT |
336 | */ |
339 | */ |
337 | s[2][ii] = get_cycle(); |
340 | s[2][ii] = get_cycle(); |
338 | 341 | ||
339 | extavlreltree_create(&extavlreltree); |
342 | extavlreltree_create(&extavlreltree); |
340 | for (i = 0; i < node_count[ii]; i++) { |
343 | for (i = 0; i < node_count[ii]; i++) { |
341 | extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node()); |
344 | extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node()); |
342 | } |
345 | } |
343 | 346 | ||
344 | f[2][ii] = get_cycle(); |
347 | f[2][ii] = get_cycle(); |
345 | /* |
348 | /* |
346 | * ExtAVLrel DELETE |
349 | * ExtAVLrel DELETE |
347 | */ |
350 | */ |
348 | ds[2][ii] = get_cycle(); |
351 | ds[2][ii] = get_cycle(); |
349 | 352 | ||
350 | while ((c = extavlreltree.root) != NULL) { |
353 | while ((c = extavlreltree.root) != NULL) { |
351 | extavlreltree_delete(&extavlreltree,c); |
354 | extavlreltree_delete(&extavlreltree,c); |
352 | free_extavlreltree_node(c); |
355 | free_extavlreltree_node(c); |
353 | } |
356 | } |
354 | 357 | ||
355 | df[2][ii] = get_cycle(); |
358 | df[2][ii] = get_cycle(); |
356 | 359 | ||
357 | /* |
360 | /* |
358 | * FAVL INSERT |
361 | * FAVL INSERT |
359 | */ |
362 | */ |
360 | s[3][ii] = get_cycle(); |
363 | s[3][ii] = get_cycle(); |
361 | 364 | ||
362 | favltree_create(&favltree); |
365 | favltree_create(&favltree); |
363 | for (i = 0; i < node_count[ii]; i++) { |
366 | for (i = 0; i < node_count[ii]; i++) { |
364 | favltree_insert(&favltree,alloc_favltree_node()); |
367 | favltree_insert(&favltree,alloc_favltree_node()); |
365 | } |
368 | } |
366 | 369 | ||
367 | f[3][ii] = get_cycle(); |
370 | f[3][ii] = get_cycle(); |
368 | /* |
371 | /* |
369 | * FAVL DELETE |
372 | * FAVL DELETE |
370 | */ |
373 | */ |
371 | ds[3][ii] = get_cycle(); |
374 | ds[3][ii] = get_cycle(); |
372 | 375 | ||
373 | while ((d = favltree.root) != NULL) { |
376 | while ((d = favltree.root) != NULL) { |
374 | favltree_delete(&favltree,d); |
377 | favltree_delete(&favltree,d); |
375 | free_favltree_node(d); |
378 | free_favltree_node(d); |
376 | } |
379 | } |
377 | 380 | ||
378 | df[3][ii] = get_cycle(); |
381 | df[3][ii] = get_cycle(); |
379 | } |
382 | } |
380 | printf("\n----------------------------------------------------------------------------"); |
383 | printf("\n----------------------------------------------------------------------------"); |
381 | printf("\nAVL\t\t"); |
384 | printf("\nAVL\t\t"); |
382 | for (ii = 0; ii < TEST_COUNT; ii++) |
385 | for (ii = 0; ii < TEST_COUNT; ii++) |
383 | printf("%20llu",f[0][ii]-s[0][ii]); |
386 | printf("%20llu",f[0][ii]-s[0][ii]); |
384 | printf("\nFAVL\t\t"); |
387 | printf("\nFAVL\t\t"); |
385 | for (ii = 0; ii < TEST_COUNT; ii++) |
388 | for (ii = 0; ii < TEST_COUNT; ii++) |
386 | printf("%20llu",f[3][ii]-s[3][ii]); |
389 | printf("%20llu",f[3][ii]-s[3][ii]); |
387 | printf("\nExtAVL\t\t"); |
390 | printf("\nExtAVL\t\t"); |
388 | for (ii = 0; ii < TEST_COUNT; ii++) |
391 | for (ii = 0; ii < TEST_COUNT; ii++) |
389 | printf("%20llu",f[1][ii]-s[1][ii]); |
392 | printf("%20llu",f[1][ii]-s[1][ii]); |
390 | printf("\nExtAVLrel\t"); |
393 | printf("\nExtAVLrel\t"); |
391 | for (ii = 0; ii < TEST_COUNT; ii++) |
394 | for (ii = 0; ii < TEST_COUNT; ii++) |
392 | printf("%20llu",f[2][ii]-s[2][ii]); |
395 | printf("%20llu",f[2][ii]-s[2][ii]); |
393 | printf("\n\n"); |
396 | printf("\n\n"); |
394 | 397 | ||
395 | printf("DELETE tree deleting root nodes\n"); |
398 | printf("DELETE tree deleting root nodes\n"); |
396 | printf("Nodes:\t\t"); |
399 | printf("Nodes:\t\t"); |
397 | for (ii = 0; ii < TEST_COUNT; ii++) |
400 | for (ii = 0; ii < TEST_COUNT; ii++) |
398 | printf("%20u",node_count[ii]); |
401 | printf("%20u",node_count[ii]); |
399 | printf("\n----------------------------------------------------------------------------"); |
402 | printf("\n----------------------------------------------------------------------------"); |
400 | printf("\nAVL\t\t"); |
403 | printf("\nAVL\t\t"); |
401 | for (ii = 0; ii < TEST_COUNT; ii++) |
404 | for (ii = 0; ii < TEST_COUNT; ii++) |
402 | printf("%20llu",df[0][ii]-ds[0][ii]); |
405 | printf("%20llu",df[0][ii]-ds[0][ii]); |
403 | printf("\nAVL\t\t"); |
406 | printf("\nAVL\t\t"); |
404 | for (ii = 0; ii < TEST_COUNT; ii++) |
407 | for (ii = 0; ii < TEST_COUNT; ii++) |
405 | printf("%20llu",df[3][ii]-ds[3][ii]); |
408 | printf("%20llu",df[3][ii]-ds[3][ii]); |
406 | printf("\nExtAVL\t\t"); |
409 | printf("\nExtAVL\t\t"); |
407 | for (ii = 0; ii < TEST_COUNT; ii++) |
410 | for (ii = 0; ii < TEST_COUNT; ii++) |
408 | printf("%20llu",df[1][ii]-ds[1][ii]); |
411 | printf("%20llu",df[1][ii]-ds[1][ii]); |
409 | printf("\nExtAVLrel\t"); |
412 | printf("\nExtAVLrel\t"); |
410 | for (ii = 0; ii < TEST_COUNT; ii++) |
413 | for (ii = 0; ii < TEST_COUNT; ii++) |
411 | printf("%20llu",df[2][ii]-ds[2][ii]); |
414 | printf("%20llu",df[2][ii]-ds[2][ii]); |
412 | printf("\n\n"); |
415 | printf("\n\n"); |
413 | } |
416 | } |
414 | 417 | ||
415 | 418 | ||
416 | /** Insert keys of ascending sequence and delete tree with delete_min functions. |
419 | /** Insert keys of ascending sequence and delete tree with delete_min functions. |
417 | */ |
420 | */ |
418 | static void test2(void) |
421 | static void test2(void) |
419 | { |
422 | { |
420 | uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
423 | uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
421 | uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT]; |
424 | uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT]; |
422 | unsigned int i,ii; |
425 | unsigned int i,ii; |
423 | avltree_node_t *a; |
426 | avltree_node_t *a; |
424 | extavltree_node_t *b; |
427 | extavltree_node_t *b; |
425 | extavlreltree_node_t *c; |
428 | extavlreltree_node_t *c; |
426 | favltree_node_t *d; |
429 | favltree_node_t *d; |
427 | 430 | ||
428 | 431 | ||
429 | printf("INSERT nodes with keys of descending sequence.\n"); |
432 | printf("INSERT nodes with keys of descending sequence.\n"); |
430 | printf("Nodes:\t\t"); |
433 | printf("Nodes:\t\t"); |
431 | for (ii = 0; ii < TEST_COUNT; ii++) { |
434 | for (ii = 0; ii < TEST_COUNT; ii++) { |
432 | printf("%20u",node_count[ii]); |
435 | printf("%20u",node_count[ii]); |
433 | keys_prepare(node_count[ii],2); |
436 | keys_prepare(node_count[ii],2); |
434 | 437 | ||
435 | /* |
438 | /* |
436 | * AVL INSERT |
439 | * AVL INSERT |
437 | */ |
440 | */ |
438 | s[0][ii] = get_cycle(); |
441 | s[0][ii] = get_cycle(); |
439 | 442 | ||
440 | avltree_create(&avltree); |
443 | avltree_create(&avltree); |
441 | for (i = 0; i < node_count[ii]; i++) { |
444 | for (i = 0; i < node_count[ii]; i++) { |
442 | avltree_insert(&avltree,alloc_avltree_node()); |
445 | avltree_insert(&avltree,alloc_avltree_node()); |
443 | } |
446 | } |
444 | 447 | ||
445 | f[0][ii] = get_cycle(); |
448 | f[0][ii] = get_cycle(); |
446 | /* |
449 | /* |
447 | * AVL DELETE |
450 | * AVL DELETE |
448 | */ |
451 | */ |
449 | ds[0][ii] = get_cycle(); |
452 | ds[0][ii] = get_cycle(); |
450 | 453 | ||
451 | while (avltree.root != NULL) { |
454 | while (avltree.root != NULL) { |
452 | a = avltree_find_min(&avltree); |
455 | a = avltree_find_min(&avltree); |
453 | avltree_delete_min(&avltree); |
456 | avltree_delete_min(&avltree); |
454 | free_avltree_node(a); |
457 | free_avltree_node(a); |
455 | } |
458 | } |
456 | 459 | ||
457 | df[0][ii] = get_cycle(); |
460 | df[0][ii] = get_cycle(); |
458 | 461 | ||
459 | /* |
462 | /* |
460 | * ExtAVL INSERT |
463 | * ExtAVL INSERT |
461 | */ |
464 | */ |
462 | s[1][ii] = get_cycle(); |
465 | s[1][ii] = get_cycle(); |
463 | 466 | ||
464 | extavltree_create(&extavltree); |
467 | extavltree_create(&extavltree); |
465 | for (i = 0; i < node_count[ii]; i++) { |
468 | for (i = 0; i < node_count[ii]; i++) { |
466 | extavltree_insert(&extavltree,alloc_extavltree_node()); |
469 | extavltree_insert(&extavltree,alloc_extavltree_node()); |
467 | } |
470 | } |
468 | 471 | ||
469 | f[1][ii] = get_cycle(); |
472 | f[1][ii] = get_cycle(); |
470 | /* |
473 | /* |
471 | * ExtAVL DELETE |
474 | * ExtAVL DELETE |
472 | */ |
475 | */ |
473 | ds[1][ii] = get_cycle(); |
476 | ds[1][ii] = get_cycle(); |
474 | 477 | ||
475 | while (extavltree.root != NULL) { |
478 | while (extavltree.root != NULL) { |
476 | b = extavltree.head.next; |
479 | b = extavltree.head.next; |
477 | extavltree_delete_min(&extavltree); |
480 | extavltree_delete_min(&extavltree); |
478 | free_extavltree_node(b); |
481 | free_extavltree_node(b); |
479 | } |
482 | } |
480 | 483 | ||
481 | df[1][ii] = get_cycle(); |
484 | df[1][ii] = get_cycle(); |
482 | /* |
485 | /* |
483 | * ExtAVLrel INSERT |
486 | * ExtAVLrel INSERT |
484 | */ |
487 | */ |
485 | s[2][ii] = get_cycle(); |
488 | s[2][ii] = get_cycle(); |
486 | 489 | ||
487 | extavlreltree_create(&extavlreltree); |
490 | extavlreltree_create(&extavlreltree); |
488 | for (i = 0; i < node_count[ii]; i++) { |
491 | for (i = 0; i < node_count[ii]; i++) { |
489 | extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node()); |
492 | extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node()); |
490 | } |
493 | } |
491 | 494 | ||
492 | f[2][ii] = get_cycle(); |
495 | f[2][ii] = get_cycle(); |
493 | /* |
496 | /* |
494 | * ExtAVLrel DELETE |
497 | * ExtAVLrel DELETE |
495 | */ |
498 | */ |
496 | ds[2][ii] = get_cycle(); |
499 | ds[2][ii] = get_cycle(); |
497 | 500 | ||
498 | while (extavlreltree.root != NULL) { |
501 | while (extavlreltree.root != NULL) { |
499 | c = extavlreltree.head.next; |
502 | c = extavlreltree.head.next; |
500 | extavlreltree_delete_min(&extavlreltree); |
503 | extavlreltree_delete_min(&extavlreltree); |
501 | free_extavlreltree_node(c); |
504 | free_extavlreltree_node(c); |
502 | } |
505 | } |
503 | 506 | ||
504 | df[2][ii] = get_cycle(); |
507 | df[2][ii] = get_cycle(); |
505 | 508 | ||
506 | /* |
509 | /* |
507 | * FAVL INSERT |
510 | * FAVL INSERT |
508 | */ |
511 | */ |
509 | s[3][ii] = get_cycle(); |
512 | s[3][ii] = get_cycle(); |
510 | 513 | ||
511 | favltree_create(&favltree); |
514 | favltree_create(&favltree); |
512 | for (i = 0; i < node_count[ii]; i++) { |
515 | for (i = 0; i < node_count[ii]; i++) { |
513 | favltree_insert(&favltree,alloc_favltree_node()); |
516 | favltree_insert(&favltree,alloc_favltree_node()); |
514 | } |
517 | } |
515 | 518 | ||
516 | f[3][ii] = get_cycle(); |
519 | f[3][ii] = get_cycle(); |
517 | /* |
520 | /* |
518 | * AVL DELETE |
521 | * AVL DELETE |
519 | */ |
522 | */ |
520 | ds[3][ii] = get_cycle(); |
523 | ds[3][ii] = get_cycle(); |
521 | 524 | ||
522 | while (favltree.root != NULL) { |
525 | while (favltree.root != NULL) { |
523 | d = favltree_find_min(&favltree); |
526 | d = favltree_find_min(&favltree); |
524 | favltree_delete_min(&favltree); |
527 | favltree_delete_min(&favltree); |
525 | free_favltree_node(d); |
528 | free_favltree_node(d); |
526 | } |
529 | } |
527 | 530 | ||
528 | df[3][ii] = get_cycle(); |
531 | df[3][ii] = get_cycle(); |
529 | 532 | ||
530 | } |
533 | } |
531 | printf("\n----------------------------------------------------------------------------"); |
534 | printf("\n----------------------------------------------------------------------------"); |
532 | printf("\nAVL\t\t"); |
535 | printf("\nAVL\t\t"); |
533 | for (ii = 0; ii < TEST_COUNT; ii++) |
536 | for (ii = 0; ii < TEST_COUNT; ii++) |
534 | printf("%20llu",f[0][ii]-s[0][ii]); |
537 | printf("%20llu",f[0][ii]-s[0][ii]); |
535 | printf("\nFAVL\t\t"); |
538 | printf("\nFAVL\t\t"); |
536 | for (ii = 0; ii < TEST_COUNT; ii++) |
539 | for (ii = 0; ii < TEST_COUNT; ii++) |
537 | printf("%20llu",f[3][ii]-s[3][ii]); |
540 | printf("%20llu",f[3][ii]-s[3][ii]); |
538 | printf("\nExtAVL\t\t"); |
541 | printf("\nExtAVL\t\t"); |
539 | for (ii = 0; ii < TEST_COUNT; ii++) |
542 | for (ii = 0; ii < TEST_COUNT; ii++) |
540 | printf("%20llu",f[1][ii]-s[1][ii]); |
543 | printf("%20llu",f[1][ii]-s[1][ii]); |
541 | printf("\nExtAVLrel\t"); |
544 | printf("\nExtAVLrel\t"); |
542 | for (ii = 0; ii < TEST_COUNT; ii++) |
545 | for (ii = 0; ii < TEST_COUNT; ii++) |
543 | printf("%20llu",f[2][ii]-s[2][ii]); |
546 | printf("%20llu",f[2][ii]-s[2][ii]); |
544 | printf("\n\n"); |
547 | printf("\n\n"); |
545 | 548 | ||
546 | printf("DELETE tree deleting nodes with minimal key\n"); |
549 | printf("DELETE tree deleting nodes with minimal key\n"); |
547 | printf("Nodes:\t\t"); |
550 | printf("Nodes:\t\t"); |
548 | for (ii = 0; ii < TEST_COUNT; ii++) |
551 | for (ii = 0; ii < TEST_COUNT; ii++) |
549 | printf("%20u",node_count[ii]); |
552 | printf("%20u",node_count[ii]); |
550 | printf("\n----------------------------------------------------------------------------"); |
553 | printf("\n----------------------------------------------------------------------------"); |
551 | printf("\nAVL\t\t"); |
554 | printf("\nAVL\t\t"); |
552 | for (ii = 0; ii < TEST_COUNT; ii++) |
555 | for (ii = 0; ii < TEST_COUNT; ii++) |
553 | printf("%20llu",df[0][ii]-ds[0][ii]); |
556 | printf("%20llu",df[0][ii]-ds[0][ii]); |
554 | printf("\nFAVL\t\t"); |
557 | printf("\nFAVL\t\t"); |
555 | for (ii = 0; ii < TEST_COUNT; ii++) |
558 | for (ii = 0; ii < TEST_COUNT; ii++) |
556 | printf("%20llu",df[3][ii]-ds[3][ii]); |
559 | printf("%20llu",df[3][ii]-ds[3][ii]); |
557 | printf("\nExtAVL\t\t"); |
560 | printf("\nExtAVL\t\t"); |
558 | for (ii = 0; ii < TEST_COUNT; ii++) |
561 | for (ii = 0; ii < TEST_COUNT; ii++) |
559 | printf("%20llu",df[1][ii]-ds[1][ii]); |
562 | printf("%20llu",df[1][ii]-ds[1][ii]); |
560 | printf("\nExtAVLrel\t"); |
563 | printf("\nExtAVLrel\t"); |
561 | for (ii = 0; ii < TEST_COUNT; ii++) |
564 | for (ii = 0; ii < TEST_COUNT; ii++) |
562 | printf("%20llu",df[2][ii]-ds[2][ii]); |
565 | printf("%20llu",df[2][ii]-ds[2][ii]); |
563 | printf("\n\n"); |
566 | printf("\n\n"); |
564 | } |
567 | } |
565 | 568 | ||
566 | 569 | ||
567 | /** Insert keys of random sequence and delete tree with delete_min functions. |
570 | /** Insert keys of random sequence and delete tree with delete_min functions. |
568 | */ |
571 | */ |
569 | static void test3(void) |
572 | static void test3(void) |
570 | { |
573 | { |
571 | uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
574 | uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
572 | uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT]; |
575 | uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT]; |
573 | unsigned int i,ii; |
576 | unsigned int i,ii; |
574 | avltree_node_t *a; |
577 | avltree_node_t *a; |
575 | extavltree_node_t *b; |
578 | extavltree_node_t *b; |
576 | extavlreltree_node_t *c; |
579 | extavlreltree_node_t *c; |
577 | favltree_node_t *d; |
580 | favltree_node_t *d; |
578 | 581 | ||
579 | 582 | ||
580 | printf("INSERT nodes with keys of random sequence 1-65536.\n"); |
583 | printf("INSERT nodes with keys of random sequence 1-65536.\n"); |
581 | printf("Nodes:\t\t"); |
584 | printf("Nodes:\t\t"); |
582 | for (ii = 0; ii < TEST_COUNT; ii++) { |
585 | for (ii = 0; ii < TEST_COUNT; ii++) { |
583 | printf("%20u",node_count[ii]); |
586 | printf("%20u",node_count[ii]); |
584 | keys_prepare(node_count[ii],0); |
587 | keys_prepare(node_count[ii],0); |
585 | 588 | ||
586 | /* |
589 | /* |
587 | * AVL INSERT |
590 | * AVL INSERT |
588 | */ |
591 | */ |
589 | s[0][ii] = get_cycle(); |
592 | s[0][ii] = get_cycle(); |
590 | 593 | ||
591 | avltree_create(&avltree); |
594 | avltree_create(&avltree); |
592 | for (i = 0; i < node_count[ii]; i++) { |
595 | for (i = 0; i < node_count[ii]; i++) { |
593 | avltree_insert(&avltree,alloc_avltree_node()); |
596 | avltree_insert(&avltree,alloc_avltree_node()); |
594 | } |
597 | } |
595 | 598 | ||
596 | f[0][ii] = get_cycle(); |
599 | f[0][ii] = get_cycle(); |
597 | /* |
600 | /* |
598 | * AVL DELETE |
601 | * AVL DELETE |
599 | */ |
602 | */ |
600 | ds[0][ii] = get_cycle(); |
603 | ds[0][ii] = get_cycle(); |
601 | 604 | ||
602 | while (avltree.root != NULL) { |
605 | while (avltree.root != NULL) { |
603 | a = avltree_find_min(&avltree); |
606 | a = avltree_find_min(&avltree); |
604 | avltree_delete_min(&avltree); |
607 | avltree_delete_min(&avltree); |
605 | free_avltree_node(a); |
608 | free_avltree_node(a); |
606 | } |
609 | } |
607 | 610 | ||
608 | df[0][ii] = get_cycle(); |
611 | df[0][ii] = get_cycle(); |
609 | 612 | ||
610 | /* |
613 | /* |
611 | * ExtAVL INSERT |
614 | * ExtAVL INSERT |
612 | */ |
615 | */ |
613 | s[1][ii] = get_cycle(); |
616 | s[1][ii] = get_cycle(); |
614 | 617 | ||
615 | extavltree_create(&extavltree); |
618 | extavltree_create(&extavltree); |
616 | for (i = 0; i < node_count[ii]; i++) { |
619 | for (i = 0; i < node_count[ii]; i++) { |
617 | extavltree_insert(&extavltree,alloc_extavltree_node()); |
620 | extavltree_insert(&extavltree,alloc_extavltree_node()); |
618 | } |
621 | } |
619 | 622 | ||
620 | f[1][ii] = get_cycle(); |
623 | f[1][ii] = get_cycle(); |
621 | /* |
624 | /* |
622 | * ExtAVL DELETE |
625 | * ExtAVL DELETE |
623 | */ |
626 | */ |
624 | ds[1][ii] = get_cycle(); |
627 | ds[1][ii] = get_cycle(); |
625 | 628 | ||
626 | while (extavltree.root != NULL) { |
629 | while (extavltree.root != NULL) { |
627 | b = extavltree.head.next; |
630 | b = extavltree.head.next; |
628 | extavltree_delete_min(&extavltree); |
631 | extavltree_delete_min(&extavltree); |
629 | free_extavltree_node(b); |
632 | free_extavltree_node(b); |
630 | } |
633 | } |
631 | 634 | ||
632 | df[1][ii] = get_cycle(); |
635 | df[1][ii] = get_cycle(); |
633 | /* |
636 | /* |
634 | * ExtAVLrel INSERT |
637 | * ExtAVLrel INSERT |
635 | */ |
638 | */ |
636 | s[2][ii] = get_cycle(); |
639 | s[2][ii] = get_cycle(); |
637 | 640 | ||
638 | extavlreltree_create(&extavlreltree); |
641 | extavlreltree_create(&extavlreltree); |
639 | for (i = 0; i < node_count[ii]; i++) { |
642 | for (i = 0; i < node_count[ii]; i++) { |
640 | extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node()); |
643 | extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node()); |
641 | } |
644 | } |
642 | 645 | ||
643 | f[2][ii] = get_cycle(); |
646 | f[2][ii] = get_cycle(); |
644 | /* |
647 | /* |
645 | * ExtAVLrel DELETE |
648 | * ExtAVLrel DELETE |
646 | */ |
649 | */ |
647 | ds[2][ii] = get_cycle(); |
650 | ds[2][ii] = get_cycle(); |
648 | 651 | ||
649 | while (extavlreltree.root != NULL) { |
652 | while (extavlreltree.root != NULL) { |
650 | c = extavlreltree.head.next; |
653 | c = extavlreltree.head.next; |
651 | extavlreltree_delete_min(&extavlreltree); |
654 | extavlreltree_delete_min(&extavlreltree); |
652 | free_extavlreltree_node(c); |
655 | free_extavlreltree_node(c); |
653 | } |
656 | } |
654 | 657 | ||
655 | df[2][ii] = get_cycle(); |
658 | df[2][ii] = get_cycle(); |
656 | 659 | ||
657 | /* |
660 | /* |
658 | * FAVL INSERT |
661 | * FAVL INSERT |
659 | */ |
662 | */ |
660 | s[3][ii] = get_cycle(); |
663 | s[3][ii] = get_cycle(); |
661 | 664 | ||
662 | favltree_create(&favltree); |
665 | favltree_create(&favltree); |
663 | for (i = 0; i < node_count[ii]; i++) { |
666 | for (i = 0; i < node_count[ii]; i++) { |
664 | favltree_insert(&favltree,alloc_favltree_node()); |
667 | favltree_insert(&favltree,alloc_favltree_node()); |
665 | } |
668 | } |
666 | 669 | ||
667 | f[3][ii] = get_cycle(); |
670 | f[3][ii] = get_cycle(); |
668 | /* |
671 | /* |
669 | * AVL DELETE |
672 | * AVL DELETE |
670 | */ |
673 | */ |
671 | ds[3][ii] = get_cycle(); |
674 | ds[3][ii] = get_cycle(); |
672 | 675 | ||
673 | while (favltree.root != NULL) { |
676 | while (favltree.root != NULL) { |
674 | d = favltree_find_min(&favltree); |
677 | d = favltree_find_min(&favltree); |
675 | favltree_delete_min(&favltree); |
678 | favltree_delete_min(&favltree); |
676 | free_favltree_node(d); |
679 | free_favltree_node(d); |
677 | } |
680 | } |
678 | 681 | ||
679 | df[3][ii] = get_cycle(); |
682 | df[3][ii] = get_cycle(); |
680 | } |
683 | } |
681 | printf("\n----------------------------------------------------------------------------"); |
684 | printf("\n----------------------------------------------------------------------------"); |
682 | printf("\nAVL\t\t"); |
685 | printf("\nAVL\t\t"); |
683 | for (ii = 0; ii < TEST_COUNT; ii++) |
686 | for (ii = 0; ii < TEST_COUNT; ii++) |
684 | printf("%20llu",f[0][ii]-s[0][ii]); |
687 | printf("%20llu",f[0][ii]-s[0][ii]); |
685 | printf("\nFAVL\t\t"); |
688 | printf("\nFAVL\t\t"); |
686 | for (ii = 0; ii < TEST_COUNT; ii++) |
689 | for (ii = 0; ii < TEST_COUNT; ii++) |
687 | printf("%20llu",f[3][ii]-s[3][ii]); |
690 | printf("%20llu",f[3][ii]-s[3][ii]); |
688 | printf("\nExtAVL\t\t"); |
691 | printf("\nExtAVL\t\t"); |
689 | for (ii = 0; ii < TEST_COUNT; ii++) |
692 | for (ii = 0; ii < TEST_COUNT; ii++) |
690 | printf("%20llu",f[1][ii]-s[1][ii]); |
693 | printf("%20llu",f[1][ii]-s[1][ii]); |
691 | printf("\nExtAVLrel\t"); |
694 | printf("\nExtAVLrel\t"); |
692 | for (ii = 0; ii < TEST_COUNT; ii++) |
695 | for (ii = 0; ii < TEST_COUNT; ii++) |
693 | printf("%20llu",f[2][ii]-s[2][ii]); |
696 | printf("%20llu",f[2][ii]-s[2][ii]); |
694 | printf("\n\n"); |
697 | printf("\n\n"); |
695 | 698 | ||
696 | printf("DELETE tree deleting nodes with minimal key\n"); |
699 | printf("DELETE tree deleting nodes with minimal key\n"); |
697 | printf("Nodes:\t\t"); |
700 | printf("Nodes:\t\t"); |
698 | for (ii = 0; ii < TEST_COUNT; ii++) |
701 | for (ii = 0; ii < TEST_COUNT; ii++) |
699 | printf("%20u",node_count[ii]); |
702 | printf("%20u",node_count[ii]); |
700 | printf("\n----------------------------------------------------------------------------"); |
703 | printf("\n----------------------------------------------------------------------------"); |
701 | printf("\nAVL\t\t"); |
704 | printf("\nAVL\t\t"); |
702 | for (ii = 0; ii < TEST_COUNT; ii++) |
705 | for (ii = 0; ii < TEST_COUNT; ii++) |
703 | printf("%20llu",df[0][ii]-ds[0][ii]); |
706 | printf("%20llu",df[0][ii]-ds[0][ii]); |
704 | printf("\nFAVL\t\t"); |
707 | printf("\nFAVL\t\t"); |
705 | for (ii = 0; ii < TEST_COUNT; ii++) |
708 | for (ii = 0; ii < TEST_COUNT; ii++) |
706 | printf("%20llu",df[3][ii]-ds[3][ii]); |
709 | printf("%20llu",df[3][ii]-ds[3][ii]); |
707 | printf("\nExtAVL\t\t"); |
710 | printf("\nExtAVL\t\t"); |
708 | for (ii = 0; ii < TEST_COUNT; ii++) |
711 | for (ii = 0; ii < TEST_COUNT; ii++) |
709 | printf("%20llu",df[1][ii]-ds[1][ii]); |
712 | printf("%20llu",df[1][ii]-ds[1][ii]); |
710 | printf("\nExtAVLrel\t"); |
713 | printf("\nExtAVLrel\t"); |
711 | for (ii = 0; ii < TEST_COUNT; ii++) |
714 | for (ii = 0; ii < TEST_COUNT; ii++) |
712 | printf("%20llu",df[2][ii]-ds[2][ii]); |
715 | printf("%20llu",df[2][ii]-ds[2][ii]); |
713 | printf("\n\n"); |
716 | printf("\n\n"); |
714 | } |
717 | } |
715 | 718 | ||
716 | 719 | ||
717 | /** Simulating timeout mechanismus with insert and delete_min operations. |
720 | /** Simulating timeout mechanismus with insert and delete_min operations. |
718 | */ |
721 | */ |
719 | static void test4(void) |
722 | static void test4(void) |
720 | { |
723 | { |
721 | uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
724 | uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
722 | unsigned int i,ii; |
725 | unsigned int i,ii; |
723 | avltree_node_t *a; |
726 | avltree_node_t *a; |
724 | extavltree_node_t *b; |
727 | extavltree_node_t *b; |
725 | extavlreltree_node_t *c; |
728 | extavlreltree_node_t *c; |
726 | favltree_node_t *d; |
729 | favltree_node_t *d; |
727 | uint64_t r; |
730 | uint64_t r; |
728 | uint16_t rr; |
731 | uint16_t rr; |
729 | unsigned int mn,nc; |
732 | unsigned int mn,nc; |
730 | 733 | ||
731 | 734 | ||
732 | printf("Simulating timeout mechanismus with %d insert or delete_min operations\n",OPERATION_COUNT); |
735 | printf("Simulating timeout mechanismus with %d insert or delete_min operations\n",OPERATION_COUNT); |
733 | printf("Maximum nodes:\t"); |
736 | printf("Maximum nodes:\t"); |
734 | for (ii = 0; ii < TEST_COUNT; ii++) { |
737 | for (ii = 0; ii < TEST_COUNT; ii++) { |
735 | printf("%20u",node_count[ii]); |
738 | printf("%20u",node_count[ii]); |
736 | 739 | ||
737 | r = (uint64_t) get_cycle(); |
740 | r = (uint64_t) get_cycle(); |
738 | mn = node_count[ii]; |
741 | mn = node_count[ii]; |
739 | 742 | ||
740 | /* |
743 | /* |
741 | * AVL |
744 | * AVL |
742 | */ |
745 | */ |
743 | rr = r; |
746 | rr = r; |
744 | nc = 0; |
747 | nc = 0; |
745 | s[0][ii] = get_cycle(); |
748 | s[0][ii] = get_cycle(); |
746 | 749 | ||
747 | avltree_create(&avltree); |
750 | avltree_create(&avltree); |
748 | for (i = 0; i < OPERATION_COUNT; i++) { |
751 | for (i = 0; i < OPERATION_COUNT; i++) { |
749 | if (((rr % mn) <= nc) && nc) { |
752 | if (((rr % mn) <= nc) && nc) { |
750 | /* |
753 | /* |
751 | * Delete min. |
754 | * Delete min. |
752 | */ |
755 | */ |
753 | a = avltree_find_min(&avltree); |
756 | a = avltree_find_min(&avltree); |
754 | avltree_delete_min(&avltree); |
757 | avltree_delete_min(&avltree); |
755 | free_avltree_node(a); |
758 | free_avltree_node(a); |
756 | nc--; |
759 | nc--; |
757 | } else { |
760 | } else { |
758 | /* |
761 | /* |
759 | * Insert. |
762 | * Insert. |
760 | */ |
763 | */ |
761 | a = alloc_avltree_node(); |
764 | a = alloc_avltree_node(); |
762 | a->key = rr; |
765 | a->key = rr; |
763 | avltree_insert(&avltree,a); |
766 | avltree_insert(&avltree,a); |
764 | nc++; |
767 | nc++; |
765 | } |
768 | } |
766 | rr += GEN_NUM; |
769 | rr += GEN_NUM; |
767 | } |
770 | } |
768 | /* |
771 | /* |
769 | * Delete rest tree. |
772 | * Delete rest tree. |
770 | */ |
773 | */ |
771 | while (avltree.root != NULL) { |
774 | while (avltree.root != NULL) { |
772 | a = avltree_find_min(&avltree); |
775 | a = avltree_find_min(&avltree); |
773 | avltree_delete_min(&avltree); |
776 | avltree_delete_min(&avltree); |
774 | free_avltree_node(a); |
777 | free_avltree_node(a); |
775 | } |
778 | } |
776 | 779 | ||
777 | f[0][ii] = get_cycle(); |
780 | f[0][ii] = get_cycle(); |
778 | 781 | ||
779 | /* |
782 | /* |
780 | * FAVL |
783 | * FAVL |
781 | */ |
784 | */ |
782 | rr = r; |
785 | rr = r; |
783 | nc = 0; |
786 | nc = 0; |
784 | s[3][ii] = get_cycle(); |
787 | s[3][ii] = get_cycle(); |
785 | 788 | ||
786 | avltree_create(&avltree); |
789 | avltree_create(&avltree); |
787 | for (i = 0; i < OPERATION_COUNT; i++) { |
790 | for (i = 0; i < OPERATION_COUNT; i++) { |
788 | if (((rr % mn) <= nc) && nc) { |
791 | if (((rr % mn) <= nc) && nc) { |
789 | /* |
792 | /* |
790 | * Delete min. |
793 | * Delete min. |
791 | */ |
794 | */ |
792 | d = favltree_find_min(&favltree); |
795 | d = favltree_find_min(&favltree); |
793 | favltree_delete_min(&favltree); |
796 | favltree_delete_min(&favltree); |
794 | free_favltree_node(d); |
797 | free_favltree_node(d); |
795 | nc--; |
798 | nc--; |
796 | } else { |
799 | } else { |
797 | /* |
800 | /* |
798 | * Insert. |
801 | * Insert. |
799 | */ |
802 | */ |
800 | d = alloc_favltree_node(); |
803 | d = alloc_favltree_node(); |
801 | d->key = rr; |
804 | d->key = rr; |
802 | favltree_insert(&favltree,d); |
805 | favltree_insert(&favltree,d); |
803 | nc++; |
806 | nc++; |
804 | } |
807 | } |
805 | rr += GEN_NUM; |
808 | rr += GEN_NUM; |
806 | } |
809 | } |
807 | /* |
810 | /* |
808 | * Delete rest tree. |
811 | * Delete rest tree. |
809 | */ |
812 | */ |
810 | while (favltree.root != NULL) { |
813 | while (favltree.root != NULL) { |
811 | d = favltree_find_min(&favltree); |
814 | d = favltree_find_min(&favltree); |
812 | favltree_delete_min(&favltree); |
815 | favltree_delete_min(&favltree); |
813 | free_favltree_node(d); |
816 | free_favltree_node(d); |
814 | } |
817 | } |
815 | 818 | ||
816 | f[3][ii] = get_cycle(); |
819 | f[3][ii] = get_cycle(); |
817 | 820 | ||
818 | /* |
821 | /* |
819 | * ExtAVL |
822 | * ExtAVL |
820 | */ |
823 | */ |
821 | rr = r; |
824 | rr = r; |
822 | nc = 0; |
825 | nc = 0; |
823 | s[1][ii] = get_cycle(); |
826 | s[1][ii] = get_cycle(); |
824 | 827 | ||
825 | extavltree_create(&extavltree); |
828 | extavltree_create(&extavltree); |
826 | for (i = 0; i < OPERATION_COUNT; i++) { |
829 | for (i = 0; i < OPERATION_COUNT; i++) { |
827 | if (((rr % mn) <= nc) && nc) { |
830 | if (((rr % mn) <= nc) && nc) { |
828 | /* |
831 | /* |
829 | * Delete min. |
832 | * Delete min. |
830 | */ |
833 | */ |
831 | b = extavltree.head.next; |
834 | b = extavltree.head.next; |
832 | extavltree_delete_min(&extavltree); |
835 | extavltree_delete_min(&extavltree); |
833 | free_extavltree_node(b); |
836 | free_extavltree_node(b); |
834 | nc--; |
837 | nc--; |
835 | } else { |
838 | } else { |
836 | /* |
839 | /* |
837 | * Insert. |
840 | * Insert. |
838 | */ |
841 | */ |
839 | b = alloc_extavltree_node(); |
842 | b = alloc_extavltree_node(); |
840 | b->key = rr; |
843 | b->key = rr; |
841 | extavltree_insert(&extavltree,b); |
844 | extavltree_insert(&extavltree,b); |
842 | nc++; |
845 | nc++; |
843 | } |
846 | } |
844 | rr += GEN_NUM; |
847 | rr += GEN_NUM; |
845 | } |
848 | } |
846 | /* |
849 | /* |
847 | * Delete rest tree. |
850 | * Delete rest tree. |
848 | */ |
851 | */ |
849 | while (extavltree.root != NULL) { |
852 | while (extavltree.root != NULL) { |
850 | b = extavltree.head.next; |
853 | b = extavltree.head.next; |
851 | extavltree_delete_min(&extavltree); |
854 | extavltree_delete_min(&extavltree); |
852 | free_extavltree_node(b); |
855 | free_extavltree_node(b); |
853 | } |
856 | } |
854 | 857 | ||
855 | f[1][ii] = get_cycle(); |
858 | f[1][ii] = get_cycle(); |
856 | 859 | ||
857 | /* |
860 | /* |
858 | * ExtAVLrel |
861 | * ExtAVLrel |
859 | */ |
862 | */ |
860 | rr = r; |
863 | rr = r; |
861 | nc = 0; |
864 | nc = 0; |
862 | s[2][ii] = get_cycle(); |
865 | s[2][ii] = get_cycle(); |
863 | 866 | ||
864 | extavlreltree_create(&extavlreltree); |
867 | extavlreltree_create(&extavlreltree); |
865 | for (i = 0; i < OPERATION_COUNT; i++) { |
868 | for (i = 0; i < OPERATION_COUNT; i++) { |
866 | if (((rr % mn) <= nc) && nc) { |
869 | if (((rr % mn) <= nc) && nc) { |
867 | /* |
870 | /* |
868 | * Delete min. |
871 | * Delete min. |
869 | */ |
872 | */ |
870 | c = extavlreltree.head.next; |
873 | c = extavlreltree.head.next; |
871 | //if (ii == 2 && !(i % 100)) printf("DEL key %llu, nc: %u, op: %u\n",c->key,nc,i); |
874 | //if (ii == 2 && !(i % 100)) printf("DEL key %llu, nc: %u, op: %u\n",c->key,nc,i); |
872 | extavlreltree_delete_min(&extavlreltree); |
875 | extavlreltree_delete_min(&extavlreltree); |
873 | free_extavlreltree_node(c); |
876 | free_extavlreltree_node(c); |
874 | nc--; |
877 | nc--; |
875 | } else { |
878 | } else { |
876 | /* |
879 | /* |
877 | * Insert. |
880 | * Insert. |
878 | */ |
881 | */ |
879 | c = alloc_extavlreltree_node(); |
882 | c = alloc_extavlreltree_node(); |
880 | c->key = rr; |
883 | c->key = rr; |
881 | //if (ii == 2 && !(i % 100)) printf("INS key %llu, nc: %u, op: %u\n",c->key,nc,i); |
884 | //if (ii == 2 && !(i % 100)) printf("INS key %llu, nc: %u, op: %u\n",c->key,nc,i); |
882 | extavlreltree_insert(&extavlreltree,c); |
885 | extavlreltree_insert(&extavlreltree,c); |
883 | nc++; |
886 | nc++; |
884 | } |
887 | } |
885 | rr += GEN_NUM; |
888 | rr += GEN_NUM; |
886 | } |
889 | } |
887 | /* |
890 | /* |
888 | * Delete rest tree. |
891 | * Delete rest tree. |
889 | */ |
892 | */ |
890 | while (extavlreltree.root != NULL) { |
893 | while (extavlreltree.root != NULL) { |
891 | c = extavlreltree.head.next; |
894 | c = extavlreltree.head.next; |
892 | extavlreltree_delete_min(&extavlreltree); |
895 | extavlreltree_delete_min(&extavlreltree); |
893 | free_extavlreltree_node(c); |
896 | free_extavlreltree_node(c); |
894 | } |
897 | } |
895 | 898 | ||
896 | f[2][ii] = get_cycle(); |
899 | f[2][ii] = get_cycle(); |
897 | } |
900 | } |
898 | printf("\n----------------------------------------------------------------------------"); |
901 | printf("\n----------------------------------------------------------------------------"); |
899 | printf("\nAVL\t\t"); |
902 | printf("\nAVL\t\t"); |
900 | for (ii = 0; ii < TEST_COUNT; ii++) |
903 | for (ii = 0; ii < TEST_COUNT; ii++) |
901 | printf("%20llu",f[0][ii]-s[0][ii]); |
904 | printf("%20llu",f[0][ii]-s[0][ii]); |
902 | printf("\nFAVL\t\t"); |
905 | printf("\nFAVL\t\t"); |
903 | for (ii = 0; ii < TEST_COUNT; ii++) |
906 | for (ii = 0; ii < TEST_COUNT; ii++) |
904 | printf("%20llu",f[3][ii]-s[3][ii]); |
907 | printf("%20llu",f[3][ii]-s[3][ii]); |
905 | printf("\nExtAVL\t\t"); |
908 | printf("\nExtAVL\t\t"); |
906 | for (ii = 0; ii < TEST_COUNT; ii++) |
909 | for (ii = 0; ii < TEST_COUNT; ii++) |
907 | printf("%20llu",f[1][ii]-s[1][ii]); |
910 | printf("%20llu",f[1][ii]-s[1][ii]); |
908 | printf("\nExtAVLrel\t"); |
911 | printf("\nExtAVLrel\t"); |
909 | for (ii = 0; ii < TEST_COUNT; ii++) |
912 | for (ii = 0; ii < TEST_COUNT; ii++) |
910 | printf("%20llu",f[2][ii]-s[2][ii]); |
913 | printf("%20llu",f[2][ii]-s[2][ii]); |
911 | printf("\n\n"); |
914 | printf("\n\n"); |
912 | } |
915 | } |
913 | 916 | ||
914 | 917 | ||
915 | char * test_timeoutbench1(bool quiet) |
918 | char * test_timeoutbench1(bool quiet) |
916 | { |
919 | { |
917 | printf("\n\tBenchmark test of timeout data structures: AVL, ExtAVL and ExtAVLrel.\n" |
920 | printf("\n\tBenchmark test of timeout data structures: AVL, ExtAVL and ExtAVLrel.\n" |
918 | "Run test more than once for eliminating possible distortion due to caching!\n\n"); |
921 | "Run test more than once for eliminating possible distortion due to caching!\n\n"); |
919 | 922 | ||
920 | 923 | ||
921 | avl_slab = slab_cache_create("avl_slab",sizeof(avltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
924 | avl_slab = slab_cache_create("avl_slab",sizeof(avltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
922 | favl_slab = slab_cache_create("favl_slab",sizeof(favltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
925 | favl_slab = slab_cache_create("favl_slab",sizeof(favltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
923 | extavl_slab = slab_cache_create("extavl_slab",sizeof(extavltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
926 | extavl_slab = slab_cache_create("extavl_slab",sizeof(extavltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
924 | extavlrel_slab = slab_cache_create("extavlrel_slab",sizeof(extavlreltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
927 | extavlrel_slab = slab_cache_create("extavlrel_slab",sizeof(extavlreltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
925 | 928 | ||
926 | if (!alloc_nodes(NODE_COUNT)) |
929 | if (!alloc_nodes(NODE_COUNT)) |
927 | return NULL; |
930 | return NULL; |
928 | 931 | ||
929 | /* |
932 | /* |
930 | * store initial cycle count, |
933 | * store initial cycle count, |
931 | * do test, |
934 | * do test, |
932 | * store finish cycle count, |
935 | * store finish cycle count, |
933 | * show results |
936 | * show results |
934 | */ |
937 | */ |
935 | 938 | ||
936 | test1(); |
939 | test1(); |
937 | test2(); |
940 | test2(); |
938 | test3(); |
941 | test3(); |
939 | test4(); |
942 | test4(); |
940 | 943 | ||
941 | /* |
944 | /* |
942 | * Deallocate arrays. |
945 | * Deallocate arrays. |
943 | */ |
946 | */ |
944 | free_nodes(NODE_COUNT); |
947 | free_nodes(NODE_COUNT); |
945 | 948 | ||
946 | return NULL; |
949 | return NULL; |
947 | } |
950 | } |
948 | 951 |