// cedar -- C++ implementation of Efficiently-updatable Double ARray trie
//  $Id: bench.cc 1913 2016-01-19 12:55:27Z ynaga $
// Copyright (c) 2013-2015 Naoki Yoshinaga <ynaga@tkl.iis.u-tokyo.ac.jp>
#ifdef __APPLE__
#include <mach/mach.h>
#endif
#include <unistd.h>
#include <fcntl.h>
#include <sys/time.h>
#include <cstdio>
#include <cstring>
#include <cstddef> // for ternary search tree
#include <vector>
#include <memory>
#include <numeric>
// C++ containers
#include <unordered_map>
// cedar variants
#ifdef USE_PREFIX_TRIE
#include <cedarpp.h>
#else
#include <cedar.h>
#endif
// Google's containers and variants
#include <sparsepp/spp.h>
#include <google/dense_hash_map>
// Cache-concious containers
#include <Judy.h>
#ifdef USE_HAT
#include <htrie_map.h>
#endif
#ifdef USE_AHASH
#include <array_map.h>
#endif
#ifdef USE_HHASH
#include <hopscotch_map.h>
#endif
#include <city.h>

struct str_hash {
  size_t operator () (const char* key) const
  { return CityHash64 (key, std::strlen (key)); }
  size_t operator () (const char* key, size_t key_size) const
  { return CityHash64 (key, key_size); }
};

struct str_equal {
  bool operator () (const char* p, const char* q) const {
    // return std::strcmp (p, q) == 0; // slow
    for (; *p || *q; ++q, ++p)
     if (*p != *q)
       return false; // reject immediately
     return true;
  }
};


// typedef
#if   defined (USE_CEDAR_UNORDERED)
typedef cedar::da <int, -1, -2, false> cedar_t;
#else
typedef cedar::da <int> cedar_t;
#endif
typedef std::unordered_map <const char*, int, str_hash, str_equal>     hash_t;
typedef google::dense_hash_map <const char*, int, str_hash, str_equal> gdhash_t;
typedef spp::sparse_hash_map <const char*, int, str_hash, str_equal>   shash_t;
typedef Pvoid_t judy_t;
#ifdef USE_AHASH
typedef tsl::array_map <char, int, str_hash> ahash_t;
#endif
#ifdef USE_HAT
typedef tsl::htrie_map <char, int, str_hash> hat_t;
#endif
#ifdef USE_HHASH
typedef tsl::hopscotch_map <const char*, int, str_hash, str_equal> hhash_t;
#endif

size_t get_process_size () {
#ifdef __APPLE__
  struct task_basic_info t_info;
  mach_msg_type_number_t t_info_count = TASK_BASIC_INFO_COUNT;
  task_info (current_task (), TASK_BASIC_INFO,
             reinterpret_cast <task_info_t> (&t_info), &t_info_count);
  return t_info.resident_size;
#else
  FILE* fp = std::fopen("/proc/self/statm", "r");
  size_t dummy (0), vm (0);
  std::fscanf (fp, "%ld %ld ", &dummy, &vm); // get resident (see procfs)
  std::fclose (fp);
  return vm * ::getpagesize ();
#endif
}

size_t read_data (const char* file, char*& data) {
  int fd = ::open (file, O_RDONLY);
  if (fd < 0)
    { std::fprintf (stderr, "no such file: %s\n", file); std::exit (1); }
  size_t size = static_cast <size_t> (::lseek (fd, 0L, SEEK_END));
  data = new char[size];
  ::lseek (fd, 0L, SEEK_SET);
  ::read  (fd, data, size);
  ::close (fd);
  return size;
}

#ifdef USE_BINARY_DATA
#define KEY_SEP '\0'
inline char* find_sep (char* p) { while (*p != '\0') ++p; return p; }
#else
#define KEY_SEP '\n'
inline char* find_sep (char* p) { while (*p != '\n') ++p; *p = '\0'; return p; }
#endif

template <typename T>
inline T* create () { return new T (); }

template <>
inline gdhash_t* create () { gdhash_t* p = new gdhash_t; p->set_empty_key (""); return p; }

template <typename T>
inline void destroy (T* t) {
  for (typename T::const_iterator it = t->begin (); it != t->end (); ++it)
    delete [] it->first;
  delete t;
}

template <>
inline void destroy (cedar_t* t) { delete t; }

#ifdef USE_HAT
template <>
inline void destroy (hat_t* t)   { delete t; }
#endif

#ifdef USE_AHASH
template <>
inline void destroy (ahash_t* t) { delete t; }
#endif

template <>
inline void destroy (judy_t* t) { Word_t bytes = 0; JSLFA (bytes, *t); delete t; }

// avoid to new temporary objects regarding std::string
template <typename T> //  hash
inline void insert_key (T* t, const char* key, size_t len, int n) {
  t->insert ({::strdup (key), n});
}
template <typename T>  // hash
inline bool lookup_key (const T& t, const char* key, size_t len)
{ return t.find (key) != t.end (); }

// hat-trie
#ifdef USE_HAT
template <>
inline void insert_key (hat_t* t, const char* key, const size_t len, int n)
{ t->insert_ks (key, len, n); }
template <>
inline bool lookup_key (const hat_t& t, const char* key, const size_t len)
{ return t.find_ks (key, len) != t.end (); }
#endif

// array-hash
#ifdef USE_AHASH
template <>
inline void insert_key (ahash_t* t, const char* key, const size_t len, int n)
{ t->insert_ks (key, len, n); }
template <>
inline bool lookup_key (const ahash_t& t, const char* key, const size_t len)
{ return t.find_ks (key, len) != t.end (); }
#endif

// cedar
template <>
inline void insert_key (cedar_t* t, const char* key, const size_t len, int n)
{ t->update (key, len) = n; }
template <>
inline bool lookup_key (const cedar_t& t, const char* key, const size_t len)
{ return t.exactMatchSearch <int> (key, len) >= 0; }

// judy array
template <>
inline void insert_key (judy_t* t, const char* key, const size_t len, int n)
{ Word_t* PValue = 0; JSLI (PValue, *t, key); *PValue = n; }
template <>
inline bool lookup_key (const judy_t& t, const char* key, size_t len)
{ PWord_t PValue = 0; JSLG (PValue, t, key); return PValue; }

template <typename T>
void insert (T* t, char* data, size_t size, int& n) {
  for (char* start (data), *end (data), *tail (data + size);
       end != tail; start = ++end) {
    end = find_sep (end);
    insert_key (t, start, end - start, ++n);
  }
}

// lookup
template <typename T>
void lookup (const T& t, char* data, size_t size, int& n_, int& n) {
  for (char* start (data), *end (data), *tail (data + size);
       end != tail; start = ++end) {
    end = find_sep (end);
    if (lookup_key (t, start, end - start))
      ++n_;
    ++n;
  }
}

template <typename T>
void bench (const char* keys, const char* queries, const char* label) {
  std::fprintf (stderr, "---- %-25s --------------------------\n", label);
  //
  T* t = create <T> ();
  struct timeval st, et;
  {
    // build trie
    char* data = 0;
    const size_t size = read_data (keys, data);
    size_t rss = get_process_size ();
    std::fprintf (stderr, "%-20s %.2f MiB (%ld bytes)\n",
                  "Init RSS:", rss / 1048576.0, rss);
    int n = 0;
    ::gettimeofday (&st, NULL);
    insert (t, data, size, n);
    ::gettimeofday (&et, NULL);
    double elapsed = (et.tv_sec - st.tv_sec) + (et.tv_usec - st.tv_usec) * 1e-6;
    std::fprintf (stderr, "%-20s %.2f sec (%.2f nsec per key)\n",
                  "Time to insert:", elapsed, elapsed * 1e9 / n);
    std::fprintf (stderr, "%-20s %d\n", "Words:", n);
    delete [] data;
  }
  if (std::strcmp (queries, "-") != 0) {
    // load data
    char* data = 0;
    const size_t size = read_data (queries, data);
    // search
    int n (0), n_ (0);
    ::gettimeofday (&st, NULL);
    lookup (*t, data, size, n_, n);
    ::gettimeofday (&et, NULL);
    double elapsed = (et.tv_sec - st.tv_sec) + (et.tv_usec - st.tv_usec) * 1e-6;
    std::fprintf (stderr, "%-20s %.2f sec (%.2f nsec per key)\n",
                  "Time to search:", elapsed, elapsed * 1e9 / n);
    std::fprintf (stderr, "%-20s %d\n", "Words:", n);
    std::fprintf (stderr, "%-20s %d\n", "Found:", n_);
    delete [] data;
  }
  destroy (t);
}

int main (int argc, char** argv) {
  if (argc < 3)
    { std::fprintf (stderr, "Usage: %s keys queries\n", argv[0]); std::exit (1); }
  //
#ifdef USE_CEDAR
#if   defined (USE_PREFIX_TRIE)
  bench <cedar_t>   (argv[1], argv[2], "cedar (prefix)");
#elif defined (USE_REDUCED_TRIE)
  bench <cedar_t>   (argv[1], argv[2], "cedar (reduced)");
#else
  bench <cedar_t>   (argv[1], argv[2], "cedar");
#endif
#endif
#ifdef USE_CEDAR_UNORDERED
#if   defined (USE_PREFIX_TRIE)
  bench <cedar_t>   (argv[1], argv[2], "cedar unordered (prefix)");
#elif defined (USE_REDUCED_TRIE)
  bench <cedar_t>   (argv[1], argv[2], "cedar unordered (reduced)");
#else
  bench <cedar_t>   (argv[1], argv[2], "cedar unordered");
#endif
#endif
#ifdef USE_HASH
  bench <hash_t>    (argv[1], argv[2], "hash");
#endif
#ifdef USE_GOOGLE_DHASH
  bench <gdhash_t>  (argv[1], argv[2], "gdhash");
#endif
#ifdef USE_SHASH
  bench <shash_t>   (argv[1], argv[2],  "shash");
#endif
#ifdef USE_SPLAY
  bench <splay_t>   (argv[1], argv[2], "splay");
#endif
#ifdef USE_JUDY
  bench <judy_t>    (argv[1], argv[2], "judy");
#endif
#ifdef USE_HAT
  bench <hat_t>     (argv[1], argv[2], "hat");
#endif
#ifdef USE_AHASH
  bench <ahash_t>   (argv[1], argv[2], "ahash");
#endif
#ifdef USE_HHASH
  bench <hhash_t>   (argv[1], argv[2], "hhash");
#endif
}