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