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