Subversion Repositories HelenOS

Rev

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