Subversion Repositories HelenOS

/*

 * Copyright (c) 2007 Vojtech Mencl

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 *

 * - Redistributions of source code must retain the above copyright

 *   notice, this list of conditions and the following disclaimer.

 * - Redistributions in binary form must reproduce the above copyright

 *   notice, this list of conditions and the following disclaimer in the

 *   documentation and/or other materials provided with the distribution.

 * - The name of the author may not be used to endorse or promote products

 *   derived from this software without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR

 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.

 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,

 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

#include <test.h>

#include <print.h>

#include <adt/avl.h>

#include <adt/extavl.h>

#include <adt/extavlrel.h>

#include <debug.h>

#include <arch/types.h>

#include <arch/cycle.h>

#include <arch/asm.h>

#include <panic.h>

#include <mm/slab.h>

/*

 * Node count must be more then 1000!

 */

#define NODE_COUNT 100000

#define GEN_NUM 275604541

#define OPERATION_COUNT 1000000

#define TEST_COUNT 3

static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT};

/*

 * Wrapper tree data structures.

 */

static avltree_t avltree;

static extavltree_t extavltree;

static extavlreltree_t extavlreltree;

/*

 * Slab cache variables.

 */

static slab_cache_t *avl_slab;

static slab_cache_t *extavl_slab;

static slab_cache_t *extavlrel_slab;

/*

 * Head of free nodes' list:

 */

static avltree_node_t *avl_ffn = NULL;

static extavltree_node_t *extavl_ffn = NULL;

static extavlreltree_node_t *extavlrel_ffn = NULL;

static void keys_prepare(int node_count, int type)

{

    unsigned int i;

    uint16_t s;

    avltree_node_t *a = avl_ffn;

    extavltree_node_t *b = extavl_ffn;

    extavlreltree_node_t *c = extavlrel_ffn;

    switch (type) {

        case 0:

            s = (uint16_t) get_cycle();

            for (i = 0; i < node_count; i++) {

                a->key = s;

                b->key = s;

                c->key = s;

                s += GEN_NUM;

                a = a->par;

                b = b->par;

                c = c->par;

            }

            break;

        case 1:

            for (i = 1; i <= node_count; i++) {

                a->key = i;

                b->key = i;

                c->key = i;

                a = a->par;

                b = b->par;

                c = c->par;

            }

            break;

        case 2:

            for (i = node_count; i > 0; i--) {

                a->key = i;

                b->key = i;

                c->key = i;

                a = a->par;

                b = b->par;

                c = c->par;        

            }

            break;

    }

}

static bool alloc_nodes(int node_count)

{

    int i;

    avltree_node_t *a;

    extavltree_node_t *b;

    extavlreltree_node_t *c;

    avl_ffn = NULL;

    extavl_ffn = NULL;

    extavlrel_ffn = NULL;

    for (i = 0; i < node_count; i++) {

        a = (avltree_node_t *) slab_alloc(avl_slab,0);

        if (!a) {

            printf("Not enough memory to allocate test arrays.");

            return false;

        }

        b = (extavltree_node_t *) slab_alloc(extavl_slab,0);

        if (!b) {

            printf("Not enough memory to allocate test arrays.");

            return false;

        }

        c = (extavlreltree_node_t *) slab_alloc(extavlrel_slab,0);

        if (!c) {

            printf("Not enough memory to allocate test arrays.");

            return false;

        }

        a->par = avl_ffn;

        b->par = extavl_ffn;

        c->par = extavlrel_ffn;

        avl_ffn = a;

        extavl_ffn = b;

        extavlrel_ffn = c;

    }

    return true;

}

static void free_nodes(int node_count)

{

    int i;

    avltree_node_t *a;

    extavltree_node_t *b;

    extavlreltree_node_t *c;

    for (i = 0; i < node_count; i++) {

        a = avl_ffn;

        b = extavl_ffn;

        c = extavlrel_ffn;

        if (!a || !b || !c) {

            printf("Deleted nodes: %d, node count: %d, a: %p, b: %p,c: %p ",i,node_count,a,b,c);

            panic("Some nodes have been lost!");

        }

        avl_ffn = avl_ffn->par;

        extavl_ffn = extavl_ffn->par;

        extavlrel_ffn = extavlrel_ffn->par;

        slab_free(avl_slab,a);

        slab_free(extavl_slab,b);

        slab_free(extavlrel_slab,c);

    }

}

static avltree_node_t *alloc_avltree_node(void)

{

    avltree_node_t *node;

    node = avl_ffn;

    avl_ffn = avl_ffn->par;

    return node;

}

static extavltree_node_t *alloc_extavltree_node(void)

{

    extavltree_node_t *node;

    node = extavl_ffn;

    extavl_ffn = extavl_ffn->par;

    return node;

}

static extavlreltree_node_t *alloc_extavlreltree_node(void)

{

    extavlreltree_node_t *node;

    node = extavlrel_ffn;

    extavlrel_ffn = extavlrel_ffn->par;

    return node;

}

static void free_avltree_node(avltree_node_t *node)

{

    node->par = avl_ffn;

    avl_ffn = node;

}

static void free_extavltree_node(extavltree_node_t *node)

{

    node->par = extavl_ffn;

    extavl_ffn = node;

}

static void free_extavlreltree_node(extavlreltree_node_t *node)

{

    node->par = extavlrel_ffn;

    extavlrel_ffn = node;

}

/** Insert keys of ascending sequence and delete tree deleting root nodes.

 */

static void test1(void)

{

    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];

    uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];

    unsigned int i,ii;

    avltree_node_t *a;

    extavltree_node_t *b;

    extavlreltree_node_t *c;

    printf("INSERT nodes with keys of ascending sequence.\n");

    printf("Nodes:\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++) {

        printf("%20u",node_count[ii]);

        keys_prepare(node_count[ii],1);

        /*

         * AVL INSERT

         */

        s[0][ii] = get_cycle();

        avltree_create(&avltree);

        for (i = 0; i < node_count[ii]; i++) {

            avltree_insert(&avltree,alloc_avltree_node());

        }

        f[0][ii] = get_cycle();

        /*

         * AVL DELETE

         */

        ds[0][ii] = get_cycle();

        while ((a = avltree.root) != NULL) {

            avltree_delete(&avltree,a);

            free_avltree_node(a);

        }

        df[0][ii] = get_cycle();

        /*

         * ExtAVL INSERT

         */

        s[1][ii] = get_cycle();

        extavltree_create(&extavltree);

        for (i = 0; i < node_count[ii]; i++) {

            extavltree_insert(&extavltree,alloc_extavltree_node());

        }

        f[1][ii] = get_cycle();

        /*

         * ExtAVL DELETE

         */

        ds[1][ii] = get_cycle();

        while ((b = extavltree.root) != NULL) {

            extavltree_delete(&extavltree,b);

            free_extavltree_node(b);

        }

        df[1][ii] = get_cycle();

        /*

         * ExtAVLrel INSERT

         */

        s[2][ii] = get_cycle();

        extavlreltree_create(&extavlreltree);

        for (i = 0; i < node_count[ii]; i++) {

            extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());

        }

        f[2][ii] = get_cycle();

        /*

         * ExtAVLrel DELETE

         */

        ds[2][ii] = get_cycle();

        while ((c = extavlreltree.root) != NULL) {

            extavlreltree_delete(&extavlreltree,c);

            free_extavlreltree_node(c);

        }

        df[2][ii] = get_cycle();

    }

    printf("\n----------------------------------------------------------------------------");  

    printf("\nAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[0][ii]-s[0][ii]);

    printf("\nExtAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[1][ii]-s[1][ii]);

    printf("\nExtAVLrel\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[2][ii]-s[2][ii]);

    printf("\n\n");

    printf("DELETE tree deleting root nodes\n");

    printf("Nodes:\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20u",node_count[ii]);

    printf("\n----------------------------------------------------------------------------");  

    printf("\nAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",df[0][ii]-ds[0][ii]);

    printf("\nExtAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",df[1][ii]-ds[1][ii]);

    printf("\nExtAVLrel\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",df[2][ii]-ds[2][ii]);

    printf("\n\n");

}

/** Insert keys of ascending sequence and delete tree with delete_min functions.

 */

static void test2(void)

{

    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];

    uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];

    unsigned int i,ii;

    avltree_node_t *a;

    extavltree_node_t *b;

    extavlreltree_node_t *c;

    printf("INSERT nodes with keys of descending sequence.\n");

    printf("Nodes:\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++) {

        printf("%20u",node_count[ii]);

        keys_prepare(node_count[ii],2);

        /*

         * AVL INSERT

         */

        s[0][ii] = get_cycle();

        avltree_create(&avltree);

        for (i = 0; i < node_count[ii]; i++) {

            avltree_insert(&avltree,alloc_avltree_node());

        }

        f[0][ii] = get_cycle();

        /*

         * AVL DELETE

         */

        ds[0][ii] = get_cycle();

        while (avltree.root != NULL) {

            a = avltree_find_min(&avltree);

            avltree_delete_min(&avltree);

            free_avltree_node(a);

        }

        df[0][ii] = get_cycle();

        /*

         * ExtAVL INSERT

         */

        s[1][ii] = get_cycle();

        extavltree_create(&extavltree);

        for (i = 0; i < node_count[ii]; i++) {

            extavltree_insert(&extavltree,alloc_extavltree_node());

        }

        f[1][ii] = get_cycle();

        /*

         * ExtAVL DELETE

         */

        ds[1][ii] = get_cycle();

        while (extavltree.root != NULL) {

            b = extavltree.head.next;

            extavltree_delete_min(&extavltree);

            free_extavltree_node(b);

        }

        df[1][ii] = get_cycle();

        /*

         * ExtAVLrel INSERT

         */

        s[2][ii] = get_cycle();

        extavlreltree_create(&extavlreltree);

        for (i = 0; i < node_count[ii]; i++) {

            extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());

        }

        f[2][ii] = get_cycle();

        /*

         * ExtAVLrel DELETE

         */

        ds[2][ii] = get_cycle();

        while (extavlreltree.root != NULL) {

            c = extavlreltree.head.next;

            extavlreltree_delete_min(&extavlreltree);

            free_extavlreltree_node(c);

        }

        df[2][ii] = get_cycle();

    }

    printf("\n----------------------------------------------------------------------------");  

    printf("\nAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[0][ii]-s[0][ii]);

    printf("\nExtAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[1][ii]-s[1][ii]);

    printf("\nExtAVLrel\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[2][ii]-s[2][ii]);

    printf("\n\n");

    printf("DELETE tree deleting nodes with minimal key\n");

    printf("Nodes:\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20u",node_count[ii]);

    printf("\n----------------------------------------------------------------------------");  

    printf("\nAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",df[0][ii]-ds[0][ii]);

    printf("\nExtAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",df[1][ii]-ds[1][ii]);

    printf("\nExtAVLrel\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",df[2][ii]-ds[2][ii]);

    printf("\n\n");

}

/** Insert keys of random sequence and delete tree with delete_min functions.

 */

static void test3(void)

{

    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];

    uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];

    unsigned int i,ii;

    avltree_node_t *a;

    extavltree_node_t *b;

    extavlreltree_node_t *c;

    printf("INSERT nodes with keys of random sequence 1-65536.\n");

    printf("Nodes:\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++) {

        printf("%20u",node_count[ii]);

        keys_prepare(node_count[ii],0);

        /*

         * AVL INSERT

         */

        s[0][ii] = get_cycle();

        avltree_create(&avltree);

        for (i = 0; i < node_count[ii]; i++) {

            avltree_insert(&avltree,alloc_avltree_node());

        }

        f[0][ii] = get_cycle();

        /*

         * AVL DELETE

         */

        ds[0][ii] = get_cycle();

        while (avltree.root != NULL) {

            a = avltree_find_min(&avltree);

            avltree_delete_min(&avltree);

            free_avltree_node(a);

        }

        df[0][ii] = get_cycle();

        /*

         * ExtAVL INSERT

         */

        s[1][ii] = get_cycle();

        extavltree_create(&extavltree);

        for (i = 0; i < node_count[ii]; i++) {

            extavltree_insert(&extavltree,alloc_extavltree_node());

        }

        f[1][ii] = get_cycle();

        /*

         * ExtAVL DELETE

         */

        ds[1][ii] = get_cycle();

        while (extavltree.root != NULL) {

            b = extavltree.head.next;

            extavltree_delete_min(&extavltree);

            free_extavltree_node(b);

        }

        df[1][ii] = get_cycle();

        /*

         * ExtAVLrel INSERT

         */

        s[2][ii] = get_cycle();

        extavlreltree_create(&extavlreltree);

        for (i = 0; i < node_count[ii]; i++) {

            extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());

        }

        f[2][ii] = get_cycle();

        /*

         * ExtAVLrel DELETE

         */

        ds[2][ii] = get_cycle();

        while (extavlreltree.root != NULL) {

            c = extavlreltree.head.next;

            extavlreltree_delete_min(&extavlreltree);

            free_extavlreltree_node(c);

        }

        df[2][ii] = get_cycle();

    }

    printf("\n----------------------------------------------------------------------------");  

    printf("\nAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[0][ii]-s[0][ii]);

    printf("\nExtAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[1][ii]-s[1][ii]);

    printf("\nExtAVLrel\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[2][ii]-s[2][ii]);

    printf("\n\n");

    printf("DELETE tree deleting nodes with minimal key\n");

    printf("Nodes:\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20u",node_count[ii]);

    printf("\n----------------------------------------------------------------------------");  

    printf("\nAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",df[0][ii]-ds[0][ii]);

    printf("\nExtAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",df[1][ii]-ds[1][ii]);

    printf("\nExtAVLrel\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",df[2][ii]-ds[2][ii]);

    printf("\n\n");

}

/** Simulating timeout mechanismus with insert and delete_min operations.

 */

static void test4(void)

{

    uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];

    unsigned int i,ii;

    avltree_node_t *a;

    extavltree_node_t *b;

    extavlreltree_node_t *c;

    uint64_t r;

    uint16_t rr;

    unsigned int mn,nc;

    printf("Simulating timeout mechanismus with %d insert or delete_min operations\n",OPERATION_COUNT);

    printf("Maximum nodes:\t");

    for (ii = 0; ii < TEST_COUNT; ii++) {

        printf("%20u",node_count[ii]);

        r = (uint64_t) get_cycle();

        mn = node_count[ii];

        /*

         * AVL

         */

        rr = r;

        nc = 0;

        s[0][ii] = get_cycle();

        avltree_create(&avltree);

        for (i = 0; i < OPERATION_COUNT; i++) {

            if (((rr % mn) <= nc) && nc) {

                /*

                 * Delete min.

                 */

                a = avltree_find_min(&avltree);

                avltree_delete_min(&avltree);

                free_avltree_node(a);

                nc--;

            } else {

                /*

                 * Insert.

                 */

                a = alloc_avltree_node();

                a->key = rr;

                avltree_insert(&avltree,a);

                nc++;

            }

            rr += GEN_NUM;

        }

        /*

         * Delete rest tree.

         */

        while (avltree.root != NULL) {

            a = avltree_find_min(&avltree);

            avltree_delete_min(&avltree);

            free_avltree_node(a);

        }  

        f[0][ii] = get_cycle();

        /*

         * ExtAVL

         */

        rr = r;

        nc = 0;

        s[1][ii] = get_cycle();

        extavltree_create(&extavltree);

        for (i = 0; i < OPERATION_COUNT; i++) {

            if (((rr % mn) <= nc) && nc) {

                /*

                 * Delete min.

                 */

                b = extavltree.head.next;

                extavltree_delete_min(&extavltree);

                free_extavltree_node(b);

                nc--;

            } else {

                /*

                 * Insert.

                 */

                b = alloc_extavltree_node();

                b->key = rr;

                extavltree_insert(&extavltree,b);

                nc++;

            }

            rr += GEN_NUM;

        }

        /*

         * Delete rest tree.

         */

        while (extavltree.root != NULL) {

            b = extavltree.head.next;

            extavltree_delete_min(&extavltree);

            free_extavltree_node(b);

        }

        f[1][ii] = get_cycle();

        /*

         * ExtAVLrel

         */

        rr = r;

        nc = 0;

        s[2][ii] = get_cycle();

        extavlreltree_create(&extavlreltree);

        for (i = 0; i < OPERATION_COUNT; i++) {

            if (((rr % mn) <= nc) && nc) {

                /*

                 * Delete min.

                 */

                c = extavlreltree.head.next;

                //if (ii == 2 && !(i % 100)) printf("DEL key %llu, nc: %u, op: %u\n",c->key,nc,i);

                extavlreltree_delete_min(&extavlreltree);

                free_extavlreltree_node(c);

                nc--;

            } else {

                /*

                 * Insert.

                 */

                c = alloc_extavlreltree_node();

                c->key = rr;

                //if (ii == 2 && !(i % 100)) printf("INS key %llu, nc: %u, op: %u\n",c->key,nc,i);

                extavlreltree_insert(&extavlreltree,c);

                nc++;

            }

            rr += GEN_NUM;

        }

        /*

         * Delete rest tree.

         */

        while (extavlreltree.root != NULL) {

            c = extavlreltree.head.next;

            extavlreltree_delete_min(&extavlreltree);

            free_extavlreltree_node(c);

        }

        f[2][ii] = get_cycle();

    }

    printf("\n----------------------------------------------------------------------------");  

    printf("\nAVL\t\t");

    for (ii = 0; ii < TEST_COUNT; ii++)

        printf("%20llu",f[0][ii]-s[0][ii]);