Subversion Repositories HelenOS

Rev

Rev 2461 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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