#include <assert.h>
#include <db_185.h>
#include <dlfcn.h>

#include <fcntl.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <sys/types.h>

#include <Judy.h>

typedef uint32_t ITEMTYPE;
#define SETSIZE 300000

#define NRUNS   2000000


static void
bdb_test(ITEMTYPE *set, DBTYPE dbtype, void *dbinfo)
{
    size_t i;
    DB *db;
    DBT key, data;
    ITEMTYPE sample;

    struct timeval begin, end;

    db = dbopen(NULL, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR, dbtype, dbinfo);

    data.data = NULL;
    data.size = 0;
    key.size = sizeof(ITEMTYPE);
    for (i=0; i<SETSIZE; i++) {
        key.data = &set[i];
        db->put(db, &key, &data, 0);
    }

    gettimeofday(&begin, NULL);
    key.data = &sample;
    for (i=0; i<NRUNS; i++) {
        sample = rand();
        db->get(db, &key, &data, 0);
    }
    gettimeofday(&end, NULL);
    printf("%f secs\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0);
    db->close(db);
}

static int
cmp_func(const void *p1, const void *p2)
{
    ITEMTYPE *a = (ITEMTYPE *)p1;
    ITEMTYPE *b = (ITEMTYPE *)p2;
    return *a - *b;
}

static void
bsearch_test(ITEMTYPE *setsample)
{
    size_t i;
    ITEMTYPE *set;
    struct timeval begin, end;

    set = malloc(SETSIZE * sizeof(ITEMTYPE));
    assert(set != NULL);
    memcpy(set, setsample, SETSIZE * sizeof(ITEMTYPE));

    qsort(set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);

    printf("bsearch: ");

    gettimeofday(&begin, NULL);
    for (i=0; i<NRUNS; i++) {
        ITEMTYPE sample, *res;

        sample = rand();
        res = bsearch(&sample, set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);
    }
    gettimeofday(&end, NULL);
    printf("%f secs\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0);
    free(set);
}


static int
bsearch_opt_search(const ITEMTYPE *arr, ITEMTYPE n, ITEMTYPE key, int niters)
{
    int min = 0, max = n, middle;
    size_t i, iters;

    iters = niters;

    for (i=0; i<iters; i++) {
        middle = (min + max) >> 1;
        if (key > arr [middle]) min = middle + 1;
        else max = middle;
    }

    if (key != arr[min]) return -1;
    return min;
}

static int
interpolation_search(const ITEMTYPE *set, ITEMTYPE n, ITEMTYPE key)
{
    int low = 0;
    int high = n - 1;
    int mid;

    int l = set[low];
    int h = set[high];

    while (l <= key && h >= key) {
        int m;
        mid = low + (int64_t)((int64_t)(high - low)*(int64_t)(key - l))/((int64_t)(h-l));
/*      mid = low + ((float)(high - low)*(float)(key - l))/(1+(float)(h-l));*/

        m = set[mid];

        if (m < key) {
            l = set[low = mid + 1];
        } else if (m > key) {
            h = set[high = mid - 1];
        } else {
            return mid;
        }
    }

    if (set[low] == key)
        return low;
    else
        return -1;
}

static void
interpolation_test(ITEMTYPE *setsample)
{
    size_t i;
    ITEMTYPE *set;
    struct timeval begin, end;
    int acc = 0;

    set = malloc(SETSIZE * sizeof(ITEMTYPE));
    assert(set != NULL);
    memcpy(set, setsample, SETSIZE * sizeof(ITEMTYPE));

    qsort(set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);

    printf("interpolation: ");

    gettimeofday(&begin, NULL);
    for (i=0; i<NRUNS; i++) {
        ITEMTYPE sample, *sres;
        int ridx;

        sample = rand();

        ridx = interpolation_search(set, SETSIZE, sample);
        if (ridx > 0) acc += ridx;

#if 0
        sres = bsearch(&sample, set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);
        if (!sres) {
            continue;
        }

        if (*sres != set[ridx]) {
            fprintf(stderr, "incorrect i-search, step %u: %u != %u (sample: %u)\n", i, *sres, set[ridx], sample);
            exit(1);
        }
#endif
    }
    gettimeofday(&end, NULL);
    printf("%f secs, acc %d\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0, acc);
    free(set);
}

static void
bsearch_opt_test(ITEMTYPE *setsample)
{
    size_t i;
    ITEMTYPE *set;
    struct timeval begin, end;
    int acc = 0, niters;

    set = malloc(SETSIZE * sizeof(ITEMTYPE));
    assert(set != NULL);
    memcpy(set, setsample, SETSIZE * sizeof(ITEMTYPE));

    qsort(set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);
    niters = (sizeof(size_t) * CHAR_BIT) - __builtin_clz((size_t)SETSIZE);

    printf("hbsearch: ");

    gettimeofday(&begin, NULL);
    for (i=0; i<NRUNS; i++) {
        ITEMTYPE sample, *sres;
        int ridx;

        sample = rand();

        ridx = bsearch_opt_search(set, SETSIZE, sample, niters);
        if (ridx > 0) acc += ridx;

    }
    gettimeofday(&end, NULL);
    printf("%f secs, acc %d\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0, acc);
    free(set);
}

static void
judy_test(ITEMTYPE *setsample)
{
    size_t i;
    Pvoid_t PJ1Array = (Pvoid_t)NULL;
    int jw;
    ITEMTYPE *set;
    struct timeval begin, end;

    set = malloc(SETSIZE * sizeof(ITEMTYPE));
    assert(set != NULL);
    memcpy(set, setsample, SETSIZE * sizeof(ITEMTYPE));

    qsort(set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);

    for (i=0; i<SETSIZE; i++) {
        int pbit;
        J1S(pbit, PJ1Array, set[i]);
    }

    printf("judy: ");

    gettimeofday(&begin, NULL);
    for (i=0; i<NRUNS; i++) {
        ITEMTYPE sample, *sres;
        int r;

        sample = rand();
        J1T(r, PJ1Array, sample);

#if 0
        sres = bsearch(&sample, set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);

        if (((sres == NULL) && (r > 0)) || ((sres != NULL) && (r == 0))) {
            fprintf(stderr, "incorrect judy test, step %u, sample %u, r %d, sres %p\n", i, sample, r, (void *)sres);
            exit(1);
        }
#endif
    }
    gettimeofday(&end, NULL);
    printf("%f secs\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0);
    J1FA(jw, PJ1Array);
    free(set);
}

static void
bitmap_test(ITEMTYPE *setsample)
{
    size_t i;
    ITEMTYPE *set;
    struct timeval begin, end;
    uint32_t *bitmap;
    int acc = 0;

    set = malloc(SETSIZE * sizeof(ITEMTYPE));
    assert(set != NULL);
    memcpy(set, setsample, SETSIZE * sizeof(ITEMTYPE));

    qsort(set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);

    bitmap = calloc(512*1024*1024, 1);

    for (i=0; i<SETSIZE; i++) {
        bitmap[set[i] / 32] |= 1 << (set[i] % 32);
    }

    printf("bitmap: ");

    gettimeofday(&begin, NULL);
    for (i=0; i<NRUNS; i++) {
        ITEMTYPE sample, *sres;
        int r;

        sample = rand();
        r = bitmap[sample / 32] & (1 << (sample % 32));
        acc += r;

#if 0
        sres = bsearch(&sample, set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);

        if (((sres == NULL) && (r != 0)) || ((sres != NULL) && (r == 0))) {
            fprintf(stderr, "incorrect judy test, step %u, sample %u, r %d, sres %p\n", i, sample, r, (void *)sres);
            exit(1);
        }
#endif
    }
    gettimeofday(&end, NULL);
    printf("%f secs, acc %d\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0, acc);
    free(bitmap);
    free(set);
}




#define HTSIZE (1 << 16)

struct hbucket
{
    size_t nent;
    ITEMTYPE *entries;
};

static void
hhash_test(ITEMTYPE *set)
{
    size_t i;
    struct timeval begin, end;
    struct hbucket hash_table[HTSIZE];
    int acc = 0;

    memset(hash_table, 0, HTSIZE * sizeof(struct hbucket));

    for (i=0; i<SETSIZE; i++) {
        uint16_t idx;

        /*idx = set[i] >> 16;*/
        idx = set[i] & 0x0000ffff;
        hash_table[idx].entries = realloc(hash_table[idx].entries, (hash_table[idx].nent + 1) * sizeof(ITEMTYPE *));
        hash_table[idx].entries[hash_table[idx].nent] = set[i];
        hash_table[idx].nent++;
    }

    printf("hash: ");

    gettimeofday(&begin, NULL);
    for (i=0; i<NRUNS; i++) {
        ITEMTYPE sample;
        uint16_t idx;
        size_t j;

        sample = rand();
        /*idx = sample >> 16;*/
        idx = sample & 0x0000ffff;

        for (j=0; j<hash_table[idx].nent; j++) {
            if (hash_table[idx].entries[j] == sample) {
                acc += sample;
                break;
            }
        }
    }
    gettimeofday(&end, NULL);
    printf("%f secs\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0);

    for (i=0; i<HTSIZE; i++) {
        if (hash_table[i].nent > 0) free(hash_table[i].entries);
    }
}

int
main()
{
    ITEMTYPE *set;
    size_t i;

    BTREEINFO btree_info;
    HASHINFO  hash_info;

    set = malloc(SETSIZE * sizeof(ITEMTYPE));
    assert(set != NULL);

    for (i=0; i<SETSIZE; i++) {
        set[i] = rand();
    }

    judy_test(set);
    bitmap_test(set);
    hhash_test(set);
    interpolation_test(set);
    bsearch_opt_test(set);
    bsearch_test(set);

    printf("BDB btree: ");
    memset(&btree_info, 0, sizeof(BTREEINFO));
    btree_info.cachesize = 100 * 1024 * 1024;
    bdb_test(set, DB_BTREE, &btree_info);

    printf("BDB hash: ");
    memset(&hash_info, 0, sizeof(HASHINFO));
    hash_info.cachesize = 100 * 1024 * 1024;
    bdb_test(set, DB_HASH, &hash_info);

    free(set);
    return EXIT_SUCCESS;
}