Subversion Repositories PlanixRsrch.SVN

#include <stdarg.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <time.h>

#include <mutests.h>

#include "mavl.h"

/* Compare function to compare integers */
static int
cmp(const void *v1, const void *v2)
{
        return *((int *)v1) - *((int *)v2);
}

static float 
calc_depth(int numvals)
{
        int i;
        unsigned int r=1;
        for (i=0; i<64; i++){
                if (r>(unsigned int)numvals)
                        return (float)((double)i*1.44);
                r=r<<1;
        }
        return (float)0.0;
}

static int 
test_mavl(const char * name,int numvals,int type)
{
        int i;
        int insval;
        int exists,existed;
        struct mavl *t;
        int rc;
        float depth, maxdepth;

        (void) printf ("Running insert %s: numvals=%d, type=%d\n"
                        ,name, numvals,type);


        /* Create a MAVL object which store object of size of int. */
        t = mavl_create(cmp, NULL, sizeof(int));
        mu_assert (t!=NULL, "mavl_create(%s): %s", name,strerror(errno));

        srand((unsigned int)time(NULL));
        existed=0;
        for (i = 0; i < numvals; i++) {
                switch (type) {
                case 0:
                        insval = rand();
                        break;
                case -1:
                        insval = numvals-i;
                        break;
                default:                        
                        insval = i;
                        break;

                };
                (void)mavl_insert(t, &insval, &exists);
                if (exists)
                        existed++;
        }
        rc = mavl_verify(t);
        mu_assert(rc,"Verify (%s)",name);

        mu_assert(t->count+existed == numvals,
                        "%s %d != %d",name,t->count+existed, numvals);

        depth = (float)mavl_get_depth(t);
        maxdepth = calc_depth(numvals);
        mu_assert(depth < maxdepth,
                        "%s Depth %f >= %f",name,depth,maxdepth);

        mavl_destroy(t);
        return 1;
}

static int 
test_mavl_del(const char * name,int numvals,int type)
{
        int i;
        int insval,delval;
        int exists,existed;
        struct mavl *t;
        int rc;
        float depth, maxdepth;
        int * vals;

        (void) printf ("Running insert and del %s: numvals=%d, type=%d\n"
                        ,name, numvals,type);

        vals = malloc(sizeof(int)*(size_t)numvals);
        mu_assert(vals != NULL,"%s - allocate vals",
                        name);

        /* Create a MAVL object which store object of size of int. */
        t = mavl_create(cmp, NULL, sizeof(int));
        mu_assert (t!=NULL, "mavl_create(%s): %s", name,strerror(errno));

        srand((unsigned int)time(NULL));
        existed=0;
        for (i = 0; i < numvals; i++) {
                switch (type) {
                case 0:
                        insval = rand();
                        break;
                case -1:
                        insval = numvals-i;
                        break;
                default:                        
                        insval = i;
                        break;

                };
                vals[i]=insval;
                (void)mavl_insert(t, &insval, &exists);
                if (exists)
                        existed++;

        }
        rc = mavl_verify(t);
        mu_assert(rc,"Verify (%s)",name);

        mu_assert(t->count+existed == numvals,
                        "%s %d != %d",name,t->count+existed, numvals);

        depth = (float)mavl_get_depth(t);
        maxdepth = calc_depth(numvals);
        mu_assert(depth < maxdepth,
                        "%s Depth %f >= %f",name,depth,maxdepth);

/*      {                       FILE * outfile;
                        int i1;
                        outfile = fopen("error.dat","wt");
                        for (i1=0; i1<numvals; i1++){
                                fprintf(outfile, "%d ",vals[i1]);
                        }
                        fclose(outfile);
        }
*/      for (i=0; i<numvals; i++){
                int before_count;
                
                delval = vals[i];
                before_count = t->count;
                (void)mavl_del(t,&delval);

                mu_assert(before_count != t->count-1,"%s count %d != %d",
                                name, before_count,t->count-1);
                
                depth = (float)mavl_get_depth(t);
                maxdepth = calc_depth(t->count);
                
                if (!(depth<=maxdepth)){
                }

                mu_assert(depth <= maxdepth,
                        "%s Del Depth %f >= %f (N: %d)",name,depth,maxdepth,t->count);

        }
        mavl_destroy(t);
        free(vals);
        return 1;
}





static int test0(void)
{
        const char * name = "test0";
        int type = 0;
        int i;
        
        for (i=0; i<1000; i++){
                (void)test_mavl(name,i+1,type);
        }

        (void)test_mavl(name,1024,type);
        (void)test_mavl(name,31871,type);
        (void)test_mavl(name,123456,type);
        (void)test_mavl(name,1000000,type);
        return 1;
}

static int test1(void)
{
        const char * name = "test1";
        int type = -1;
        (void)test_mavl(name,1,type);
        (void)test_mavl(name,2,type);
        (void)test_mavl(name,3,type);
        (void)test_mavl(name,10,type);
        (void)test_mavl(name,1024,type);
        (void)test_mavl(name,31871,type);
        (void)test_mavl(name,123456,type);
        (void)test_mavl(name,1000000,type);
        return 1;
}

static int test2(void)
{
        const char * name = "test2";
        int type = 1;
        (void)test_mavl(name,1,type);
        (void)test_mavl(name,2,type);
        (void)test_mavl(name,3,type);
        (void)test_mavl(name,10,type);
        (void)test_mavl(name,1024,type);
        (void)test_mavl(name,31871,type);
        (void)test_mavl(name,123456,type);
        (void)test_mavl(name,1000000,type);
        return 1;
}

static int test0_del(void)
{
        int i;
        const char * name = "test0_del";
        int type = 0;
        for(i=0; i<1500; i++)
                (void)test_mavl_del(name,i+1,type);

        for (i=0; i<2; i++)
                (void)test_mavl_del(name,16300,type);
        return 1;
}


int 
main(void)
{
        mutests tf = {
                test0_del,
                test0,
                test1,
                test2,
                NULL
        };
        return mutests_run(tf);
}