#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <sys/types.h>
#include <stdint.h>
#include <unistd.h>

#include "khash.hh"
#include <ext/hash_set>
#include <tr1/unordered_set>

#ifdef HAVE_GOOGLEHASH
#include <google/sparse_hash_set>
#include <google/dense_hash_set>
#endif

static int data_size = 5000000;
static unsigned *int_data;
static char **str_data;

typedef struct {
    size_t rss, vsize;
    double utime, stime;
} RunProcDyn;

RunProcDyn g_init_rpd;

int run_get_dynamic_proc_info(pid_t pid, RunProcDyn *rpd);

struct eqint {
    inline bool operator()(unsigned s1, unsigned s2) const {
        return s1 == s2;
    }
};

struct eqstr {
    inline bool operator()(const char *s1, const char *s2) const {
        return strcmp(s1, s2) == 0;
    }
};

void ht_reset_rpd(int is)
{
    RunProcDyn rpd;
    run_get_dynamic_proc_info(getpid(), &rpd);
    printf("--- current rss: %lu (reset: %c)\n", rpd.rss, is? 'Y' : 'N');
    if (is) g_init_rpd = rpd;
}
void ht_init_data()
{
    int i;
    char buf[256];
    printf("--- generating data... ");
    srand48(11);
    int_data = (unsigned*)calloc(data_size, sizeof(unsigned));
    str_data = (char**)calloc(data_size, sizeof(char*));
    for (i = 0; i < data_size; ++i) {
        int_data[i] = (unsigned)(data_size * drand48() / 4) * 271828183u;
        sprintf(buf, "%x", int_data[i]);
        str_data[i] = strdup(buf);
    }
    printf("done!\n");
}
void ht_destroy_data()
{
    int i;
    for (i = 0; i < data_size; ++i) free(str_data[i]);
    free(str_data); free(int_data);
}

// for khash, STL and TR1
template<class hash_t, class keytype_t>
void ht_cpp(hash_t *h, keytype_t *data)
{
    RunProcDyn rpd_init, rpd;
    pid_t pid = getpid();
    int i, step = data_size / 10;
    size_t max_rss = 0;

    run_get_dynamic_proc_info(pid, &rpd_init);
    rpd = rpd_init;
    for (i = 0; i < data_size; ++i) {
        if ((i + 1) % step == 0) {
            run_get_dynamic_proc_info(pid, &rpd);
            if (rpd.rss > max_rss) max_rss = rpd.rss;
        }
        if (h->insert(data[i]).second == false) h->erase(data[i]);
//      if (h->find(data[i]) != h->end()) h->erase(data[i]);
//      else h->insert(data[i]);
    }
    run_get_dynamic_proc_info(pid, &rpd);
    if (rpd.rss > max_rss) max_rss = rpd.rss;
    printf("(user, sys, peak_rss, size, capacity): (%.3lf, %.3lf, %lu, %lu, %lu)\n", rpd.utime - rpd_init.utime,
           rpd.stime - rpd_init.stime, max_rss - g_init_rpd.rss, h->size(), h->bucket_count());
}

// for glib
#ifdef HAVE_GLIB

#include <glib.h>

void ht_glib_int()
{
    RunProcDyn rpd_init, rpd;
    pid_t pid = getpid();
    int i, step = data_size / 10;
    size_t max_rss = 0;
    unsigned *data = int_data;
    GHashTable *h;
    int val = 11;

    h = g_hash_table_new(g_int_hash, g_int_equal);
    run_get_dynamic_proc_info(pid, &rpd_init);
    rpd = rpd_init;
    for (i = 0; i < data_size; ++i) {
        if ((i + 1) % step == 0) {
            run_get_dynamic_proc_info(pid, &rpd);
            if (rpd.rss > max_rss) max_rss = rpd.rss;
        }
        if (g_hash_table_lookup(h, &data[i])) g_hash_table_steal(h, &data[i]);
        else g_hash_table_insert(h, &data[i], &val);
    }
    run_get_dynamic_proc_info(pid, &rpd);
    if (rpd.rss > max_rss) max_rss = rpd.rss;
    printf("(user, sys, peak_rss, size): (%.3lf, %.3lf, %lu, %u)\n", rpd.utime - rpd_init.utime,
           rpd.stime - rpd_init.stime, max_rss - g_init_rpd.rss, g_hash_table_size(h));
    g_hash_table_destroy(h);
}
void ht_glib_str()
{
    RunProcDyn rpd_init, rpd;
    pid_t pid = getpid();
    int i, step = data_size / 10;
    size_t max_rss = 0;
    char **data = str_data;
    GHashTable *h;
    int val = 11;

    h = g_hash_table_new(g_str_hash, g_str_equal);
    run_get_dynamic_proc_info(pid, &rpd_init);
    rpd = rpd_init;
    for (i = 0; i < data_size; ++i) {
        if ((i + 1) % step == 0) {
            run_get_dynamic_proc_info(pid, &rpd);
            if (rpd.rss > max_rss) max_rss = rpd.rss;
        }
        if (g_hash_table_lookup(h, data[i])) g_hash_table_steal(h, data[i]);
        else g_hash_table_insert(h, data[i], &val);
    }
    run_get_dynamic_proc_info(pid, &rpd);
    if (rpd.rss > max_rss) max_rss = rpd.rss;
    printf("(user, sys, peak_rss, size): (%.3lf, %.3lf, %lu, %u)\n", rpd.utime - rpd_init.utime,
           rpd.stime - rpd_init.stime, max_rss - g_init_rpd.rss, g_hash_table_size(h));
    g_hash_table_destroy(h);
}
#endif // HAVE_GLIB

#ifdef HAVE_GHTHASH
#include <ght_hash_table.h>
void ht_ghthash_int()
{
    RunProcDyn rpd_init, rpd;
    pid_t pid = getpid();
    int i, step = data_size / 10;
    size_t max_rss = 0;
    unsigned *data = int_data;
    ght_hash_table_t *h;

    h = ght_create(data_size/5);
//  ght_set_rehash(h, 1);
    run_get_dynamic_proc_info(pid, &rpd_init);
    rpd = rpd_init;
    for (i = 0; i < data_size; ++i) {
        if ((i + 1) % step == 0) {
            run_get_dynamic_proc_info(pid, &rpd);
            if (rpd.rss > max_rss) max_rss = rpd.rss;
        }
        if (ght_insert(h, 0, 4, &data[i]) == -1) ght_remove(h, 4, &data[i]);
    }
    run_get_dynamic_proc_info(pid, &rpd);
    if (rpd.rss > max_rss) max_rss = rpd.rss;
    printf("(user, sys, peak_rss, size, capacity): (%.3lf, %.3lf, %lu, %d, %u)\n", rpd.utime - rpd_init.utime,
           rpd.stime - rpd_init.stime, max_rss - g_init_rpd.rss, ght_size(h), ght_table_size(h));
    ght_finalize(h);
}
void ht_ghthash_str()
{
    RunProcDyn rpd_init, rpd;
    pid_t pid = getpid();
    int i, step = data_size / 10;
    size_t max_rss = 0;
    char **data = str_data;
    ght_hash_table_t *h;

    h = ght_create(data_size/5);
//  ght_set_rehash(h, 1);
    run_get_dynamic_proc_info(pid, &rpd_init);
    rpd = rpd_init;
    for (i = 0; i < data_size; ++i) {
        int l = strlen(data[i]);
        if ((i + 1) % step == 0) {
            run_get_dynamic_proc_info(pid, &rpd);
            if (rpd.rss > max_rss) max_rss = rpd.rss;
        }
        if (ght_insert(h, 0, l, data[i]) == -1) ght_remove(h, l, data[i]);
    }
    run_get_dynamic_proc_info(pid, &rpd);
    if (rpd.rss > max_rss) max_rss = rpd.rss;
    printf("(user, sys, peak_rss, size, capacity): (%.3lf, %.3lf, %lu, %d, %u)\n", rpd.utime - rpd_init.utime,
           rpd.stime - rpd_init.stime, max_rss - g_init_rpd.rss, ght_size(h), ght_table_size(h));
    ght_finalize(h);
}
#endif

static int usage()
{
    fprintf(stderr, "Usage:   hash_test [th] [-n %d]\n", data_size);
    fprintf(stderr, "Options: -n INT  size of data [%d]\n", data_size);
    fprintf(stderr, "         -c HEX  bitwise codes for evaluation [%x]\n", 0x6f);
    fprintf(stderr, "         -S      disable string test\n");
    fprintf(stderr, "         -h      help\n");
    return 1;
}

int main(int argc, char *argv[])
{
    int c, code = 0x6f, is_str = 1;
    while ((c = getopt(argc, argv, "c:n:hS")) >= 0) {
        switch (c) {
        case 'c': sscanf(optarg, "%x", &code); break;
        case 'h': return usage();
        case 'n': data_size = atoi(optarg); break;
        case 'S': is_str = 0; break;
        }
    }

    ht_init_data();
    ht_reset_rpd(1);

    if (code & 0x1) {
        printf("--- khash ---\n");
        ht_reset_rpd(1);
        khset_t<unsigned> *h_int = new khset_t<unsigned>;
        ht_cpp(h_int, int_data);
        delete h_int;
        if (is_str) {
            ht_reset_rpd(0);
            khset_t<const char*> *h_str = new khset_t<const char*>;
            ht_cpp(h_str, str_data);
            delete h_str;
        }
    }
#ifdef HAVE_GLIB
    if (code & 0x2) {
        printf("--- GLIB ---\n");
        ht_reset_rpd(1);
        ht_glib_int();
        ht_reset_rpd(0);
        if (is_str) ht_glib_str();
    }
#endif
    if (code &0x4) {
        printf("--- TR1 ---\n");
        ht_reset_rpd(1);
        using namespace __gnu_cxx;
        using namespace std::tr1;
        unordered_set<unsigned> *h_int = new unordered_set<unsigned>;
        ht_cpp(h_int, int_data);
        delete h_int;
        if (is_str) {
            ht_reset_rpd(0);
            unordered_set<const char*, __gnu_cxx::hash<const char*>, eqstr> *h_str
                = new unordered_set<const char*, __gnu_cxx::hash<const char*>, eqstr>;
            ht_cpp(h_str, str_data);
            delete h_str;
        }
    }
    if (code & 0x8){
        printf("--- SGI STL ---\n");
        ht_reset_rpd(0);
        using namespace __gnu_cxx;
        using namespace std;
        hash_set<unsigned, hash<unsigned>, eqint> *h_int = new hash_set<unsigned, hash<unsigned>, eqint>;
        ht_cpp(h_int, int_data);
        delete h_int;
        if (is_str) {
            ht_reset_rpd(0);
            hash_set<const char*, hash<const char*>, eqstr> *h_str = new hash_set<const char*, hash<const char*>, eqstr>;
            ht_cpp(h_str, str_data);
            delete h_str;
        }
    }
#ifdef HAVE_GHTHASH
    if (code & 0x10) {
        printf("--- GHTHASH ---\n");
        ht_reset_rpd(1);
        ht_ghthash_int();
        ht_reset_rpd(0);
        if (is_str) ht_ghthash_str();
    }
#endif
#ifdef HAVE_GOOGLEHASH
    if (code & 0x20) {
        printf("--- Google sparse hash ---\n");
        using google::sparse_hash_set;
        ht_reset_rpd(0);
        sparse_hash_set<unsigned, __gnu_cxx::hash<unsigned>, eqint> *h_int = new sparse_hash_set<unsigned, __gnu_cxx::hash<unsigned>, eqint>;
        h_int->set_deleted_key(0xffffffffu);
        ht_cpp(h_int, int_data);
        delete h_int;
        if (is_str) {
            ht_reset_rpd(0);
            sparse_hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr> *h_str = new sparse_hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr>;
            h_str->set_deleted_key("");
            ht_cpp(h_str, str_data);
            delete h_str;
        }
    }
    if (code & 0x40) {
        printf("--- Google dense hash ---\n");
        using google::dense_hash_set;
        ht_reset_rpd(0);
        dense_hash_set<unsigned, __gnu_cxx::hash<unsigned>, eqint> *h_int = new dense_hash_set<unsigned, __gnu_cxx::hash<unsigned>, eqint>;
        h_int->set_empty_key(0xffffffffu);
        h_int->set_deleted_key(0xfffffffeu);
        ht_cpp(h_int, int_data);
        delete h_int;
        if (is_str) {
            ht_reset_rpd(0);
            dense_hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr> *h_str = new dense_hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr>;
            h_str->set_empty_key("*");
            h_str->set_deleted_key("");
            ht_cpp(h_str, str_data);
            delete h_str;
        }
    }
#endif


    ht_reset_rpd(0);
    ht_destroy_data();
    ht_reset_rpd(0);

    return 0;
}

// attractivechaos: statistic routine, copied from my runlib

#define RUN_ERR_WRONG_OS        1
#define RUN_ERR_MISSING_INFO    2
#define RUN_ERR_PROC_FINISHED   3

#ifdef __linux__
int run_get_dynamic_proc_info(pid_t pid, RunProcDyn *rpd)
{
    int c, n_spc;
    char str[64];
    FILE *fp;
    unsigned long tmp, tmp2;
    size_t page_size;

    page_size = sysconf(_SC_PAGESIZE);
    sprintf(str, "/proc/%u/stat", pid);
    fp = fopen(str, "r");
    if (fp == 0) return RUN_ERR_PROC_FINISHED;
    n_spc = 0;
    while ((c = fgetc(fp)) != EOF) {
        if (c == ' ') ++n_spc;
        if (n_spc == 13) break;
    }
    fscanf(fp, "%lu%lu", &tmp, &tmp2);
    rpd->utime = tmp / 100.0;
    rpd->stime = tmp2 / 100.0;
    ++n_spc;
    while ((c = fgetc(fp)) != EOF) {
        if (c == ' ') ++n_spc;
        if (n_spc == 22) break;
    }
    fscanf(fp, "%lu%lu", &tmp, &tmp2);
    fclose(fp);
    rpd->vsize = tmp / 1024;
    rpd->rss = tmp2 * (page_size / 1024);
    rpd->rss *= 1024;
    rpd->vsize *= 1024;
    return 0;
}
#endif /* __linux */

/* MAC OS X */

#ifdef __APPLE__

#include <sys/types.h>
#include <sys/sysctl.h>
#include <sys/vmmeter.h>
#include <mach/mach_init.h>
#include <mach/mach_host.h>
#include <mach/mach_port.h>
#include <mach/mach_traps.h>
#include <mach/task_info.h>
#include <mach/thread_info.h>
#include <mach/thread_act.h>
#include <mach/vm_region.h>
#include <mach/vm_map.h>
#include <mach/task.h>
#include <mach/shared_memory_server.h>

typedef struct vmtotal vmtotal_t;

/* On Mac OS X, the only way to get enough information is to become root. Pretty frustrating! */
int run_get_dynamic_proc_info(pid_t pid, RunProcDyn *rpd)
{
    task_t task;
    kern_return_t error;
    mach_msg_type_number_t count;
    thread_array_t thread_table;
    thread_basic_info_t thi;
    thread_basic_info_data_t thi_data;
    unsigned table_size;
    struct task_basic_info ti;

    error = task_for_pid(mach_task_self(), pid, &task);
    if (error != KERN_SUCCESS) {
        /* fprintf(stderr, "++ Probably you have to set suid or become root.\n"); */
        rpd->rss = rpd->vsize = 0;
        rpd->utime = rpd->stime = 0;
        return 0;
    }
    count = TASK_BASIC_INFO_COUNT;
    error = task_info(task, TASK_BASIC_INFO, (task_info_t)&ti, &count);
    assert(error == KERN_SUCCESS);
    { /* adapted from ps/tasks.c */
        vm_region_basic_info_data_64_t b_info;
        vm_address_t address = GLOBAL_SHARED_TEXT_SEGMENT;
        vm_size_t size;
        mach_port_t object_name;
        count = VM_REGION_BASIC_INFO_COUNT_64;
        error = vm_region_64(task, &address, &size, VM_REGION_BASIC_INFO,
                             (vm_region_info_t)&b_info, &count, &object_name);
        if (error == KERN_SUCCESS) {
            if (b_info.reserved && size == (SHARED_TEXT_REGION_SIZE) &&
                ti.virtual_size > (SHARED_TEXT_REGION_SIZE + SHARED_DATA_REGION_SIZE))
            {
                ti.virtual_size -= (SHARED_TEXT_REGION_SIZE + SHARED_DATA_REGION_SIZE);
            }
        }
        rpd->rss = ti.resident_size;
        rpd->vsize = ti.virtual_size;
    }
    { /* calculate CPU times, adapted from top/libtop.c */
        unsigned i;
        rpd->utime = ti.user_time.seconds + ti.user_time.microseconds * 1e-6;
        rpd->stime = ti.system_time.seconds + ti.system_time.microseconds * 1e-6;
        error = task_threads(task, &thread_table, &table_size);
        assert(error == KERN_SUCCESS);
        thi = &thi_data;
        for (i = 0; i != table_size; ++i) {
            count = THREAD_BASIC_INFO_COUNT;
            error = thread_info(thread_table[i], THREAD_BASIC_INFO, (thread_info_t)thi, &count);
            assert(error == KERN_SUCCESS);
            if ((thi->flags & TH_FLAGS_IDLE) == 0) {
                rpd->utime += thi->user_time.seconds + thi->user_time.microseconds * 1e-6;
                rpd->stime += thi->system_time.seconds + thi->system_time.microseconds * 1e-6;
            }
            if (task != mach_task_self()) {
                error = mach_port_deallocate(mach_task_self(), thread_table[i]);
                assert(error == KERN_SUCCESS);
            }
        }
        error = vm_deallocate(mach_task_self(), (vm_offset_t)thread_table, table_size * sizeof(thread_array_t));
        assert(error == KERN_SUCCESS);
    }
    mach_port_deallocate(mach_task_self(), task);
    return 0;
}

#endif /* __APPLE__ */