#include <stdio.h>
#include <unistd.h>
#include <getopt.h>
#include <stdlib.h>
#include <libgen.h>
#include <errno.h>
#include <sched.h>
#include <malloc.h>

#include <algorithm>
#include <numeric>
#include <vector>
#include <set>
#include <ext/hash_set>
#include <ext/malloc_allocator.h>
#include <tr1/unordered_set>

#define BOOST_MULTI_INDEX_OPT
#define BOOST_MULTI_INDEX_DISABLE_SERIALIZATION
#define BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE 1
#define BOOST_MULTI_INDEX_LIMIT_TAG_SIZE 1
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>

#include <google/dense_hash_set>
#include <google/sparse_hash_set>

#include <boost/lexical_cast.hpp>

#include "stopwatch.h"

////////////////////////////////////////////////////////////////////////////////////////////////

#define likely(x)	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)

////////////////////////////////////////////////////////////////////////////////////////////////

void error(char const* file, int line, char const* s, int err) __attribute__ ((noreturn));

void error(char const* file, int line, char const* s, int err)
{
    char b[0x400];
    snprintf(b, sizeof b, "%s:%d %s: ", file, line, s);
    if((errno = err))
        perror(b);
    else
        fprintf(stderr, "%s false\n", b);
    exit(1);
}

#define CHK_CALL(exp)                           \
do {                                            \
    if(unlikely(!(exp)))                        \
        error(__FILE__, __LINE__, #exp, errno); \
} while(0)

#define CHK(exp)                                \
do {                                            \
    if(unlikely(!(exp)))                        \
        error(__FILE__, __LINE__, #exp, 0);     \
} while(0)

////////////////////////////////////////////////////////////////////////////////////////////////

size_t malloc_usage;

size_t const malloc_align(8);

void* malloc_hook(size_t s, void const*)
{
    __malloc_hook = 0;

    if(!__realloc_hook)
    {
        size_t* p = (size_t*)malloc(s);
        __malloc_hook = malloc_hook;
        return p;
    }

    size_t* p = (size_t*)malloc(s + malloc_align);
    __malloc_hook = malloc_hook;

    if(likely(p))
    {
        *p = s;
        malloc_usage += s;
        return (char*)p + malloc_align;
    }

    return 0;
}

void free_hook(void* p, void const*)
{
    __free_hook = 0;

    if(!__realloc_hook)
    {
        free(p);
        __free_hook = free_hook;
        return;
    }

    if(likely(p))
    {
        p = (char*)p - malloc_align;
        malloc_usage -= *(size_t*)p;
    }

    free(p);
    __free_hook = free_hook;
}

void* realloc_hook(void* q, size_t t, void const*)
{
    if(q)
    {
        q = (char*)q - malloc_align;
        malloc_usage -= *(size_t*)q;
    }

    size_t s = t;
    if(s)
        s += malloc_align;

    __realloc_hook = 0;
    size_t* p = (size_t*)realloc(q, s);
    __realloc_hook = realloc_hook;

    if(likely(p))
    {
        *p = t;
        malloc_usage += t;
        return (char*)p + malloc_align;
    }

    return 0;
}

void* memalign_hook(size_t, size_t, void const*)
{
    CHK(!"memalign_hook not imlemented");
    return 0;
}

void init_malloc_hook()
{
    __malloc_hook   = malloc_hook;
    __realloc_hook  = realloc_hook;
    __memalign_hook = memalign_hook;
    __free_hook     = free_hook;
}

void(*__malloc_initialize_hook)(void) = init_malloc_hook;

////////////////////////////////////////////////////////////////////////////////////////////////

class malloc_gauge
{
private:
    unsigned long s_;

public:
    malloc_gauge() : s_(malloc_usage) {}
    unsigned long delta() const { return malloc_usage - s_; }
};

////////////////////////////////////////////////////////////////////////////////////////////////

unsigned const def_n(32768);
unsigned const def_x(1);
unsigned X(def_x), N(def_n);
bool quiet(false);

////////////////////////////////////////////////////////////////////////////////////////////////

void high_priority()
{
    sched_param p = {0};
    p.sched_priority = 99;
    if(::sched_setscheduler(0, SCHED_FIFO, &p))
        perror("sched_setscheduler");
}

////////////////////////////////////////////////////////////////////////////////////////////////

enum { 
      test_std_hash
    , test_ext_hash
    , test_std_set
    , test_mi_hash
    , test_mi_set
    , test_gd_hash
    , test_gs_hash
    , test_max 
};

char const* names[] = {
      "std_hash "
    , "ext_hash "
    , "std_set  "
    , "mi_hash  "
    , "mi_set   "
    , "gd_hash  "
    , "gs_hash  "
};

template<class T> struct adapter;

////////////////////////////////////////////////////////////////////////////////////////////////

template<class T, int N> struct std_adapter
{
    static int const index = N;

    T h;

    template<class I> void insert(I begin, I end) { h.insert(begin, end); }
    bool find(unsigned t) { return h.end() != h.find(t); }
    unsigned iterate() { return std::accumulate(h.begin(), h.end(), 0u); }
    bool erase(unsigned t) { return 0 != h.erase(t); }
    unsigned size() { return h.size(); }
};

////////////////////////////////////////////////////////////////////////////////////////////////

typedef std::tr1::unordered_set<
      unsigned
    , std::tr1::hash<unsigned>
    , std::equal_to<unsigned>
    , __gnu_cxx::malloc_allocator<unsigned> 
> std_hash;
template<> struct adapter<std_hash> : std_adapter<std_hash, test_std_hash> {};

////////////////////////////////////////////////////////////////////////////////////////////////

typedef __gnu_cxx::hash_set<
      unsigned
    , __gnu_cxx::hash<unsigned>
    , std::equal_to<unsigned>
    , __gnu_cxx::malloc_allocator<unsigned> 
    > ext_hash;
template<> struct adapter<ext_hash> : std_adapter<ext_hash, test_ext_hash> {};

////////////////////////////////////////////////////////////////////////////////////////////////

typedef std::set<
      unsigned
    , std::less<unsigned>
    , __gnu_cxx::malloc_allocator<unsigned> 
> std_set;
template<> struct adapter<std_set> : std_adapter<std_set, test_std_set> {};

////////////////////////////////////////////////////////////////////////////////////////////////

namespace mi = boost::multi_index;

typedef mi::multi_index_container<
      unsigned
    , mi::indexed_by<mi::hashed_unique<mi::identity<unsigned> > >
    , __gnu_cxx::malloc_allocator<unsigned> 
    > mi_hash;
template<> struct adapter<mi_hash> : std_adapter<mi_hash, test_mi_hash> {};

typedef mi::multi_index_container<
      unsigned
    , mi::indexed_by<mi::ordered_unique<mi::identity<unsigned> > >
    , __gnu_cxx::malloc_allocator<unsigned> 
    > mi_set;
template<> struct adapter<mi_set> : std_adapter<mi_set, test_mi_set> {};

////////////////////////////////////////////////////////////////////////////////////////////////

typedef google::dense_hash_set<unsigned> gd_hash;
template<> struct adapter<gd_hash> : std_adapter<gd_hash, test_gd_hash>
{
    adapter()
    {
        this->h.set_empty_key(0u);
        this->h.set_deleted_key(-1u);
    }
};

typedef google::sparse_hash_set<unsigned> gs_hash;
template<> struct adapter<gs_hash> : std_adapter<gs_hash, test_gs_hash>
{
    adapter()
    {
        this->h.set_deleted_key(-1u);
    }
};

////////////////////////////////////////////////////////////////////////////////////////////////

struct result
{
    unsigned long long insert;
    unsigned long long find_hit;
    unsigned long long find_miss;
    unsigned long long iterate;
    unsigned long long erase;
    unsigned long long total;
    unsigned long long memory;
    unsigned product;
} results[test_max];

enum {
      result_insert
    , result_find_hit
    , result_find_miss
    , result_iterate
    , result_erase
    , result_memory
    , result_max
};

char const* result_names[result_max] = {
      "insert"
    , "find hit"
    , "find miss"
    , "iterate"
    , "erase"
    , "memory"
};

unsigned long long (result::* const result_members[result_max]) = {
      &result::insert
    , &result::find_hit
    , &result::find_miss
    , &result::iterate
    , &result::erase
    , &result::memory
};

unsigned sizes[test_max];

void prt(unsigned index)
{
    result const& r(results[index]);
    printf(
          "%s (%u): "
          "add: %9llu; "
          "hit: %9llu; "
          "miss: %9llu; "
          "iter: %9llu; "
          "del: %9llu; "
          "total: %9llu; "
          "mem: %8llu\n"
        , names[index]
        , sizes[index]
        , r.insert
        , r.find_hit
        , r.find_miss
        , r.iterate
        , r.erase
        , r.insert + r.find_hit + r.find_miss + r.iterate + r.erase
        , r.memory
        );
}

////////////////////////////////////////////////////////////////////////////////////////////////

void csv_prt_hdr(FILE* f)
{
    fprintf(f,
         "elements;"
         "memory;"
         "container;"
         "insert;"
         "find hit;"
         "find miss;"
         "iterate;"
         "erase;"
         "\n"
       );
}

void csv_prt(FILE* f, unsigned index)
{
    result const& r(results[index]);
    fprintf(f,
          "%u;%llu;%s;%llu;%llu;%llu;%llu;%llu;\n"
        , sizes[index]
        , r.memory
        , names[index]
        , r.insert
        , r.find_hit
        , r.find_miss
        , r.iterate
        , r.erase
        );
}

void csv_prt(FILE* f)
{
    csv_prt_hdr(f);
    for(unsigned index = 0; index != test_max; ++index)
        csv_prt(f, index);
}

////////////////////////////////////////////////////////////////////////////////////////////////

struct result_less
{
    unsigned n;
    
    bool operator()(unsigned a, unsigned b) const
    {
        return results[a].*result_members[n] < results[b].*result_members[n];
    }
};

void ascii_prt(FILE* f)
{
    fprintf(f, "%u elements; %u iterations\n", *sizes, X);

    for(unsigned n = 0; n != result_max; ++n)
    {
        unsigned indexes[test_max];
        for(unsigned m = 0; m != test_max; ++m)
            indexes[m] = m;
        result_less less = { n };
        std::sort(indexes, indexes + test_max, less);

        fprintf(f, "%s test (lower is better)\n", result_names[n]);

        for(unsigned m = 0; m != test_max; ++m)
        {
            unsigned i = indexes[m];
            double p = 100.0 * results[i].*result_members[n] / results[indexes[test_max - 1]].*result_members[n];
            fprintf(f, "%s [%6.2f%%] ", names[i], p);
            
            int const max_bar(40);
            for(int c = static_cast<int>(max_bar * p / 100); c > 0; c -= 16)
                fprintf(f, "%.*s", c, "OOOOOOOOOOOOOOOO");

            if(n != result_memory)
                fprintf(f, " %llu usec\n", results[i].*result_members[n]);
            else
                fprintf(f, " %llu bytes\n", results[i].*result_members[n]);
        }
    }
}

////////////////////////////////////////////////////////////////////////////////////////////////

inline unsigned rand_wrap()
{
    return std::rand() & std::numeric_limits<int>::max();
}

// [1; std::numeric_limits<int>::max()]
unsigned generate_hits() 
{
    unsigned t = rand_wrap();
    return t + !t; 
}

// [std::numeric_limits<int>::max(), std::numeric_limits<unsigned>::max() - 1]
unsigned generate_misses()
{
    unsigned t = rand_wrap() + std::numeric_limits<int>::max();
    return t - (-1u == t);
}

std::vector<unsigned> hits, misses;

////////////////////////////////////////////////////////////////////////////////////////////////

template<class T>
void do_test_loop(result* r)
{
    malloc_gauge mem;
    util::stopwatch total;

    {
    typedef adapter<T> adapter;

    adapter hash;

    // insert
    {
        util::stopwatch s;
        hash.insert(hits.begin(), hits.end());
        r->insert += s.elapsed();
    }

    if(unlikely(0 == sizes[adapter::index]))
        sizes[adapter::index] = hash.size();
    
    // make sure memory measurements stay the same
    if(likely(r->memory))
        CHK(mem.delta() == r->memory);
    else
        r->memory = mem.delta();
    
    // find_hit
    {
        util::stopwatch s;
        for(std::vector<unsigned>::const_iterator i(hits.begin()), j(hits.end()); i != j; ++i)
            r->product += hash.find(*i);
        r->find_hit += s.elapsed();
    }

    // find_miss
    {
        util::stopwatch s;
        for(std::vector<unsigned>::const_iterator i(misses.begin()), j(misses.end()); i != j; ++i)
            r->product += hash.find(*i);
        r->find_miss += s.elapsed();
    }

    // iterate
    {
        util::stopwatch s;
        r->product += hash.iterate();
        r->iterate += s.elapsed();
    }

    // erase
    {
        util::stopwatch s;
        for(std::vector<unsigned>::const_iterator i(hits.begin()), j(hits.end()); i != j; ++i)
            r->product += hash.erase(*i);
        r->erase += s.elapsed();
    }
    }

    r->total += total.elapsed();
}

template<class T>
void do_test()
{
    typedef adapter<T> adapter;

    result warm_up = {};
    for(unsigned n = 4; n--;)
        do_test_loop<T>(&warm_up);

    unsigned percent(-1u);
    for(unsigned n = 0; n < X; ++n)
    {
        if(!quiet)
        {
            unsigned p(100 * (1 + n) / X);
            if(p != percent)
            {
                percent = p;
                printf("[%u:%u] %s %u%%\r", 1 + adapter::index, test_max, names[adapter::index], percent);
                fflush(stdout);
            }
        }
        do_test_loop<T>(results + adapter::index);
    }

    // product is never zero after test
    results[adapter::index].product += !results[adapter::index].product;

    if(!quiet)
        prt(adapter::index);
}

void test()
{
    do_test<std_hash>();
    do_test<ext_hash>();
    do_test<std_set>();
    do_test<mi_hash>();
    do_test<mi_set>();
    do_test<gd_hash>();
    do_test<gs_hash>();

    // make sure all tests have produced the same product
    for(unsigned n = 0, t = 0; n < test_max; ++n)
    {
        if(n && sizes[n] != sizes[n - 1])
        {
            for(unsigned index = 0; index != test_max; ++index)
                printf("%s: %u\n", names[index], sizes[index]);
            CHK(!"bad size");
        }

        if(results[n].product)
        {
            if(t)
            {
                if(results[n].product == t)
                    continue;
                for(unsigned index = 0; index != test_max; ++index)
                    printf("%s: %u\n", names[index], results[index].product);
                CHK(!"bad product");
            }
            else
                t = results[n].product;
        }
    }
}

////////////////////////////////////////////////////////////////////////////////////////////////

void usage(char** av)
{
    fprintf(stderr,
          "usage: %s [OPTION...]\n"
          "  -x,--iter   iteration number, default is %u\n"
          "  -n,--num    number of elements, default is %u\n"
          "  -o,--out    csv output file\n"
          "  -a,--ascii  ascii-art output file\n"
          "  -q,--quiet  quiet\n"
        , basename(*av), def_x, def_n
        );
    exit(1);
}

////////////////////////////////////////////////////////////////////////////////////////////////

int main(int ac, char** av)
{
    char const* csvout = 0;
    char const* ascii = "-";
    static char const shopt[] = "n:x:o:a:qh";
    static struct option const lopt[] = {
          { "number", 1, 0, 'n' }
        , { "iter",   1, 0, 'x' }
        , { "out",    1, 0, 'o' }
        , { "ascii",  1, 0, 'a' }
        , { "quiet",  0, 0, 'q' }
        , { "help",   0, 0, 'h' }
    };

    for(int c; -1 != (c = ::getopt_long(ac, av, shopt, lopt, 0));)
    try
    {
        switch(c)
        {
        case 'n': N = boost::lexical_cast<unsigned>(::optarg); break;
        case 'x': X = boost::lexical_cast<unsigned>(::optarg); break;
        case 'o': csvout = ::optarg; break;
        case 'a': ascii = ::optarg; break;
        case 'q': quiet = true; break;
        default: usage(av);
        }
    }
    catch(std::bad_cast&)
    {
        usage(av);
    }    

    hits.resize(N);
    generate(hits.begin(), hits.end(), generate_hits);
    misses.resize(N);
    generate(misses.begin(), misses.end(), generate_misses);

    high_priority();

    if(!quiet)
        printf("**** performing %u iterations with %u random elements\n", X, N);
    util::stopwatch s;
    test();
    if(!quiet)
        printf("**** total: %lluusec\n", s.elapsed());

    if(csvout)
    {
        FILE* f = strcmp(csvout, "-") ? fopen(csvout, "a") : stdout;
        CHK(f);
        csv_prt(f);
    }

    if(ascii)
    {
        FILE* f = strcmp(ascii, "-") ? fopen(ascii, "a") : stdout;
        CHK(f);
        ascii_prt(f);
    }
}

////////////////////////////////////////////////////////////////////////////////////////////////