/*
 * Speed test for AVL tree and other search methods.
 * Uses integer key for comparison.
 *
 * 2022-09-07 <Udo.Kreblelder@gmx.at>
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * Search methods to compile.
 */

//#define USE_HASH_MAP        // Robin Hood hash map from Udo
//#define USE_AVL_TREE        // AVL tree from Udo
//#define USE_STD_SET       // red-black tree; store only keys
#define USE_STD_MAP         // red-black tree; store key-value pairs
#define USE_BINARY_SEARCH
#define USE_BINARY_SEARCH_INLINE
//#define USE_BINARY_SEARCH_BRANCHLESS
#define USE_LOWER_BOUND
#define USE_STD_FIND
//#define USE_DIRECT_HASH     // Robin Hood hash with perfect hash function
#define USE_DPA_HASH        // Daniel Abrecht hash map
//#define USE_LINEAR_SEARCH_NB  // Linear Search No Branching
#define USE_STD_UMAP        // std::unordered_map

/*
 * Windows typedefs
 */
typedef int INT;
typedef unsigned UINT;
typedef void VOID;
typedef void* PVOID;
typedef const void* PCVOID;
typedef char* PSTR;
typedef const char* PCSTR;
typedef unsigned short WCHAR;
typedef const WCHAR* PCWSTR;
typedef unsigned char BYTE;
typedef BYTE* PBYTE;
typedef long long INT64;
typedef unsigned long long UINT64;
typedef unsigned long long UINT_PTR;
typedef unsigned long long SIZE_T;

#ifdef _MSC_VER
  #define FORCEINLINE inline
#else
  #define FORCEINLINE __forceinline
#endif

extern "C"
{
    UINT64  PerfCountStamp(VOID);
    UINT64  PerfCountToPS(UINT64 stamp);
    /* Command line processing */
    INT     CmdSwitchA(PSTR argv[], PCSTR switchv[]);
    PSTR    CmdParamA(VOID);
    INT     CmdIntParamA(INT*, INT min, INT max);
    INT     CmdUIntParamA(UINT*);
    INT     CmdUInt64ParamA(UINT64*);
    /* Random number generator */
    VOID    RandSeed(UINT64 seed);
    UINT64  RandRange(UINT64 min, UINT64 max);
}

/* Define to 1 to use strings instead of integer keys */
#define STRING_KEYS 0   /* Does not work. */

/* Size of the search element (the LINE struct) */
#define DATA_SIZE 32

#define BIT(N) (1U << (N))
#define ROUND_UP_POWER2(x, pow2) (((x) + ((pow2)-1)) & ~((pow2)-1))
#define TO_STRING_HELPER(s) #s
#define TO_STRING(s) TO_STRING_HELPER(s)

#if defined(_MSC_VER) && _MSC_VER < 1900
  #undef USE_STD_UMAP
#endif

#ifdef USE_STD_SET
  #include <set>
#endif

#ifdef USE_STD_MAP 
  #include <map>
#endif

#ifdef USE_STD_UMAP
  #include <unordered_map>
#endif

#ifdef USE_BINARY_SEARCH
  #include <algorithm>
#endif

#ifdef USE_STD_FIND
  #include <algorithm>
#endif

#ifdef USE_DPA_HASH
extern "C" {
  #include "dpa/set-and-map.h"
}
#endif

#ifndef __GNUC__
  #pragma warning(disable:4474)   /* printf: too many arguments for format */
#endif

#define FFLUSH() fflush(stdout)
//#define FFLUSH()

#ifndef STATIC_ASSERT
  #define STATIC_ASSERT(exp)
#endif

#ifndef ASSERT
  #define ASSERT(exp)
#endif

#ifndef MIN
  #define MIN(a,b) (a < b ? a : b)
#endif

/*
 * Typical size of L1 cache:
 * Intel i7 8850H 32kB 8-way set-associative, 64 byte line size
 */
#define L1_CACHE 32768
#define L1_SET   8


/*
 * Command line flags
 */
#define FLAG_RANDOM  0x01
#define FLAG_VERBOSE 0x02
#define FLAG_TABLE   0x04
#define FLAG_NOSTAT  0x08
#define FLAG_NOSLOW  0x10
#define FLAG_HASHCOL 0x20


#ifndef USE_AVL_TREE
  // 16 Byte AVL Tree Node
  typedef struct {
      PVOID data[2];
  } AVLNODE;
#endif


/*
 * Search data structure
 */

typedef INT key_t;
#define FILL_DATA (DATA_SIZE - 24)    // ( DATA_SIZE - (sizeof(AVLNODE) + sizeof(key_t)) )


/*
 * User data structure of size DATA_SIZE
 */
typedef struct line
{
    AVLNODE     node;                   /* 16 Bytes */
#if STRING_KEYS
    char        id[DATA_SIZE-16];       /* string key */
#else
    key_t       id;                     /* integer key */
#endif
#if FILL_DATA > 0
    BYTE        fill_data[FILL_DATA];
#endif
} LINE;

STATIC_ASSERT(sizeof(LINE) == DATA_SIZE);

/* Search function pointer type */
typedef const LINE* (*SEARCH_FUNC)(const LINE *tbl, UINT tbl_size,
                                   key_t id, PVOID data, UINT index);


FORCEINLINE INT CompareLine(const LINE *s1, const LINE *s2)
{
    return s1->id - s2->id;
}

FORCEINLINE INT CompareKeyLine(const PVOID key, const LINE *s2)
{
    return (key_t)(UINT_PTR)key - s2->id;
}

/*
 * Direct access without searching; this is the baseline
 */
FORCEINLINE const LINE* DirectSearch(const LINE *tbl, UINT tbl_size, key_t id, PVOID data, UINT index)
{
    return tbl + index;
}


/*
 * Linear search.
 * Note that the key is always in the table.
 */
#if _MSC_VER <= 1500
FORCEINLINE const LINE* LinearSearch(const LINE *tbl, UINT tbl_size, key_t id, PVOID data, UINT index)
{
    const LINE *cp = tbl, *ep = tbl + tbl_size;

    while (cp != ep)
    {
        if (cp->id == id) break;
        cp++;
    }
    return cp;
}
#else
// Better code with newer MS cl?
FORCEINLINE const LINE* LinearSearch(const LINE *tbl, UINT tbl_size, key_t id, PVOID data, UINT index)
{
    UINT n = 0;

    for (; n < tbl_size; n++)
    {
        if (tbl[n].id == id) break;
    }

    return tbl + n;
}
#endif


/*
 * Linear search, no-branch.
 */
FORCEINLINE const LINE* LinearSearch_NB(const LINE *tbl, UINT tbl_size, key_t id, PVOID data, UINT index)
{
    SIZE_T n, k = 0;

    for (n = 0; n < tbl_size; n++)
    {
        k += (tbl[n].id < id) ? 1 : 0;
    }
    return tbl + k;
}


/*
 * AVL tree search with separate nodes.
 */

#if USE_AVL_TREE

#if USE_AVLPTRNODE
/*
 * Use a separate table of AVLNODES with data pointers to the LINE structure.
 */

typedef struct {
    AVLNODE      node;
    const LINE  *data;
} AVLPTRNODE;

FORCEINLINE INT CompareLinePtr(CONST AVLPTRNODE *s1, CONST AVLPTRNODE *s2)
{
    return CompareLine(s1->data, s2->data);
}

FORCEINLINE INT CompareLinePtrKey(CONST PVOID key, CONST AVLPTRNODE *s2)
{
    return CompareKeyLine(key, s2->data);
}

FORCEINLINE const LINE* AVLTreeSearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    AVLPTRNODE *p = (AVLPTRNODE*)avlsninline(
                        (AVLTREE*)data,
                        (avlcf)CompareLinePtrKey,
                        (PVOID)(INT_PTR)key
                        );
    return p->data;
}

#else // USE_AVLPTRNODE

/*
 * Use the AVLNODE embedded in the LINE structure
 */
FORCEINLINE const LINE* AVLTreeSearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    return (const LINE*)avlsninline((AVLTREE*)data, (avlcf)CompareKeyLine, (PVOID)(INT_PTR)key);
}

#endif // USE_AVLRNODE

#endif // USE_AVL_TREE


/*
 * Hash table search.
 */


/*
 * Different hash functions.
 */

#if 0
// https://stackoverflow.com/questions/53110781/whats-the-fastest-portable-way-to-hash-pointers-we-know-are-pointer-aligned-to?noredirect=1&lq=1
#define LARGEST_PRIME8 251u
#define LARGEST_PRIME15 32749u
#define LARGEST_PRIME16 65521u
#define LARGEST_PRIME31 2147483647u
#define LARGEST_PRIME32 4294967291u
#define LARGEST_PRIME63 9223372036854775783u
#define LARGEST_PRIME64 18446744073709551557u

//uint32_t hash = (uint32_t) ((uintptr_t)(void *)p) % LARGEST_PRIME32);

FORCEINLINE UINT HT_Handle2_Hash(HANDLE *key)
{
    UINT64 n = *(UINT64*)key;

    n %= LARGEST_PRIME32;
    return (UINT)n;
}
#endif

#if 0
// http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
FORCEINLINE UINT HT_Handle2_Hash(HANDLE *key0)
{
    UINT64 key = *(UINT64*)key0;

    key ^= (key >> 33);
    key *= 0xff51afd7ed558ccd;
    key ^= (key >> 33);
    key *= 0xc4ceb9fe1a85ec53;
    key ^= (key >> 33);
    return (UINT)key;
}
#endif

#if 0
// http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
FORCEINLINE UINT HT_Handle2_Hash(HANDLE *key0)
{
    UINT64 key = *(UINT64*)key0;
    return Hash_Murmur2_Inline(&key, 8);
}
#endif

#if 0
// http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
FORCEINLINE UINT HT_Handle2_Hash(HANDLE *key0)
{
    UINT64 key = *(UINT64*)key0;

    UINT h = (UINT)(key ^ (key >> 32));

    h ^= h >> 13;
    h *= 0x5bd1e995;
    h ^= h >> 15;

    return h;
}
#endif

#if 0
// https://nullprogram.com/blog/2018/07/31/
FORCEINLINE UINT HT_Handle2_Hash(HANDLE *key)
{
    UINT64 x = *(UINT64*)key;

    x ^= x >> 30;
    x *= 0xbf58476d1ce4e5b9U;
    x ^= x >> 27;
    x *= 0x94d049bb133111ebU;
    x ^= x >> 31;
    return (UINT)x;
}
#endif

#if 0
FORCEINLINE UINT HT_Handle2_Hash(HANDLE *key)
{
    UINT64 x = *(UINT64*)key;

    x ^= x >> 32;
    x *= 0xd6e8feb86659fd93U;
    x ^= x >> 32;
    x *= 0xd6e8feb86659fd93U;
    x ^= x >> 32;
    return (UINT)x;
}
#endif


#if 0
// https://mostlymangling.blogspot.com/2019/12/
FORCEINLINE UINT HT_Handle2_Hash(HANDLE *key)
{
    UINT64 x = *(UINT64*)key;

    x ^= x >> 27;
    x *= 0x3C79AC492BA7B653UL;
    x ^= x >> 33;
    x *= 0x1C69B3F74AC4AE35UL;
    x ^= x >> 27;
    return (UINT)x;
}
#endif

#if 0
// http://mostlymangling.blogspot.com/2018/07/on-mixing-functions-in-fast-splittable.html
FORCEINLINE UINT HT_Handle2_Hash(HANDLE *key)
{
    UINT64 v = *(UINT64*)key;

    v ^= _rotr64(v, 49) ^ _rotr64(v, 24);
    v *= 0x9FB21C651E98DF25L;
    v ^= v >> 28;
    v *= 0x9FB21C651E98DF25L;
    v ^= v >> 28;
    return (UINT)v;
}
#endif


/*
 * Hash table search with integer hash key.
 */

#ifdef USE_HASH_MAP
PVOID HT_Int_Insert(HASH_TABLE *ht, PVOID user_data)
{
    return HT_Handle_InsertNoResize_Inline(ht, user_data)
}

FORCEINLINE const LINE* HashSearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    return (const LINE*)HT_Handle_Search_Inline((HASH_TABLE*)data, (HANDLE)(INT64)key);
}
#endif


#ifdef USE_DIRECT_HASH
/*
 * Hash table search with ideal hash function key == id.
 */

/* Ideal hash function, id = hash */
FORCEINLINE UINT HT_Direct_Hash(UINT *key)
{
    return *key;
}

FORCEINLINE INT HT_Direct_Compare(UINT *hp1, UINT *hp2)
{
    return *hp1 != *hp2;
}

FORCEINLINE PVOID HT_Direct_Search_Inline(HASH_TABLE *ht, UINT search_key)
{
    return HT_Search_Inline(ht, &search_key, (HT_HASH)&HT_Direct_Hash, (HT_CMP)&HT_Direct_Compare);
}

PVOID HT_Direct_Insert(HASH_TABLE *ht, PVOID user_data)
{
    return HT_InsertNoResize_Inline(ht, user_data, (HT_HASH)&HT_Direct_Hash, (HT_CMP)&HT_Direct_Compare);
}

FORCEINLINE const LINE* HashSearchDirect(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    return (const LINE*)HT_Direct_Search_Inline((HASH_TABLE*)data, index);
}
#endif // USE_DIRECT_HASH


#ifdef USE_STD_SET

struct SetCompare
{
    bool operator() (CONST LINE *s1, CONST LINE *s2) CONST
    {
        return s1->id < s2->id ? 1 : 0;
    }
};

#ifndef WINHEAP_H
  typedef std::set<const LINE*, SetCompare> STD_SET;
#else
  typedef std::set<const LINE*, SetCompare, AllocNoThrow<const LINE*>> STD_SET;
#endif

typedef STD_SET::iterator STD_SET_ITER;

/*
 * std::set search.
 */
FORCEINLINE const LINE* StdSetSearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    STD_SET &s = *(STD_SET*)data;
    STD_SET_ITER it;

    // Note that before C14 it was not possible to search for key directly
    // https://stackoverflow.com/questions/48176182/find-elements-of-stdset-by-custom-comparison-with-value-of-different-type
   
    LINE k;
    k.id = key;
    it = s.find(&k);
    return it != s.end() ? (*it) : NULL;
}
#endif // USE_STD_SET


typedef std::pair<const key_t, const LINE*> KEY_VALUE_PAIR;

#ifdef USE_STD_MAP

#ifndef WINHEAP_H
  typedef std::map<key_t, const LINE*> STD_MAP;
#else
  typedef std::map<key_t, const LINE*, std::less<key_t>, AllocNoThrow<KEY_VALUE_PAIR>> STD_MAP;
#endif

typedef STD_MAP::iterator STD_MAP_ITER;

/* std::map search. */
FORCEINLINE const LINE* StdMapSearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    STD_MAP &m = *(STD_MAP*)data;
    STD_MAP_ITER it = m.find(key);
    return it != m.end() ? it->second : NULL;
}
#endif // USE_STD_MAP


#ifdef USE_STD_UMAP
// unordered map needs floating point ceilf...
//inline float ceilf(float a) { return ssceil(a); }

#ifndef WINHEAP_H
  typedef std::unordered_map<key_t, const LINE*> STD_UMAP;
#else
  typedef std::unordered_map< key_t,
                        const LINE*,
                        std::hash<key_t>,
                        std::equal_to<key_t>,
                        AllocNoThrow<KEY_VALUE_PAIR> > STD_UMAP;
#endif

typedef STD_UMAP::iterator STD_UMAP_ITER;

/* std::map search. */
FORCEINLINE const LINE* StdUMapSearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    STD_UMAP &m = *(STD_UMAP*)data;
    STD_UMAP_ITER it = m.find(key);
    return it != m.end() ? it->second : NULL;
}
#endif // USE_STD_UMAP

#ifndef BSEARCH_H
typedef INT (*CMP_FUNC)(PCVOID key_ptr, PCVOID elem_ptr);
#endif

#ifdef USE_BINARY_SEARCH
FORCEINLINE const LINE* StdBinarySearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    return (const LINE*)bsearch((PVOID)(INT64)key, tbl, tbl_size,
                        sizeof(LINE), (CMP_FUNC)CompareKeyLine);
}
#endif // USE_BINARY_SEARCH


#ifdef USE_BINARY_SEARCH_INLINE

/*
 * Standard bsearch function (inline version).
 */
FORCEINLINE PVOID bsearch_inline(PCVOID key, PCVOID array,
        SIZE_T nelem, SIZE_T elemsize, CMP_FUNC cmpfp)
{
    PBYTE   ptr, base = (PBYTE)array;
    SIZE_T  n;
    INT     cmp;

    while (nelem > 0)
    {
        n = nelem >> 1;
        ptr = base + n * elemsize;
        cmp = (*cmpfp)(key, ptr);
        if (cmp == 0)
            return ptr;
        ptr += elemsize;
        n = nelem - 1;
        base  = cmp > 0? ptr : base;
        nelem = cmp > 0? n   : nelem;
        nelem >>= 1;
    }

    return NULL;
}

/* Inline bsearch */
FORCEINLINE const LINE* BinarySearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    return (const LINE*)bsearch_inline((PVOID)(INT64)key, tbl, tbl_size,
                        sizeof(LINE), (CMP_FUNC)CompareKeyLine);
}
#endif // USE_BINARY_SEARCH_INLINE


#ifdef USE_BINARY_SEARCH_BRANCHLESS
/* Branchless bsearch */
FORCEINLINE const LINE* BinarySearch_BL(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    return (const LINE*)bsearch_branchless_inline((PVOID)(INT64)key, tbl, tbl_size,
                        sizeof(LINE), (CMP_FUNC)CompareKeyLine);
}
#endif // USE_BINARY_SEARCH_BRANCHLESS


#ifdef USE_STD_FIND
FORCEINLINE INT operator == (const LINE &s1, key_t key)
{
    return s1.id == key;
}

FORCEINLINE const LINE* StdFindSearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    return (const LINE*)std::find(tbl, tbl + tbl_size, key);
}
#endif // USE_STD_FIND


#ifdef USE_LOWER_BOUND
FORCEINLINE bool mod_less(const LINE &s1, key_t key)
{
    return s1.id < key;
}

FORCEINLINE const LINE* StdLowerBound(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    const LINE *ep = tbl + tbl_size;
    const LINE *p = (const LINE*)std::lower_bound(tbl, ep, key, mod_less);
    if (p == ep) return NULL;
    return p->id == key ? p : NULL;
}
#endif // USE_LOWER_BOUND


#ifdef USE_DPA_HASH

FORCEINLINE const LINE* DpaHashSearch(const LINE *tbl, UINT tbl_size, key_t key, PVOID data, UINT index)
{
    dpa_u_optional_pointer_t p = dpa_u_map_u_get((dpa_u_map_u_t*)data, key);
    return p.present? (LINE*)p.value : NULL;
}

#endif // USE_DPA_HASH


/*
 * Run the benchmark for a search method
 */
FORCEINLINE VOID RunSearch(
        UINT runs,                          /* number of runs */
        const LINE *tbl, UINT tbl_size,     /* table with line structures */
        UINT *map, UINT map_size,           /* map table with random keys */
        UINT flags,                         /* program start flags defined above */
        SEARCH_FUNC search_fp,              /* search function */
        PVOID data,                         /* search method data */
        PCSTR func_name)                    /* search method name */
{
    UINT64      sum = 0;
    UINT64      tmin = -1, t0, t1, td;
    UINT64      m = 0, n, k;
    UINT        index;
    key_t       key, key2;
    const LINE *lp;
    UINT64      total_runs = runs * map_size;

#define OUTER_LOOPS 5

    for (m = 0; m < OUTER_LOOPS; m++)
    {
        t0 = PerfCountStamp();

        for (k = 0; k < runs; k++)
        {
            for (n = 0; n < map_size; n++)
            {
                index = map[n];     /* index to search */
                ASSERT(index < tbl_size);
                key = tbl[index].id;
                lp = search_fp(tbl, tbl_size, key, data, index);
                ASSERT(lp == &tbl[index]);
                key2 = lp->id;
                ASSERT(key2 == key);
#if STRING_KEYS
                sum += key2[0];
#else
                sum += key2;        /* trick out compiler optimization */
#endif
            }
        }

        t1 = PerfCountStamp();
        td = t1 - t0;
        tmin = MIN(td, tmin);
        sum += tmin;

        if (flags & FLAG_VERBOSE)
            printf("td=%Iu (%Iu) sum=%Ix\n", td, PerfCountToPS(td) / total_runs, sum);
    }

    td = PerfCountToPS(tmin) / total_runs;

    if (flags & FLAG_TABLE)
        printf("%Iu ", td, sum);    // sum is to trick out compiler optimization
    else
        printf("%hs: %Iu ps\n", func_name, td, sum);

    FFLUSH();
}


// Dummy
FORCEINLINE VOID RunDummy(
        UINT runs,
        const LINE *tbl, UINT tbl_size,
        UINT *map, UINT map_size,
        UINT flags,
        SEARCH_FUNC search_fp,
        PVOID data,
        PCSTR func_name)
{
    INT64 td = 0, sum = 0;

    if (flags & FLAG_TABLE)
        printf("%Iu ", td, sum);    // sum is to trick out compiler optimization
    else
        printf("%hs: %Iu ps\n", func_name, td, sum);

    FFLUSH();
}


void usage()
{
    printf(
        "avltest4 -v -f<flags> -r<runs> -t<tbl_size> -m<map_size> -z<hashtbl_size> -s<seed>\n"
        "  -v,-verbose\n"
        "  -f,-flags [1=RAND,2=VERBOSE,4=TABLE,8=NOSTAT,16=NOSLOW,32=HASHCOL]\n"
    );

    exit(1);
}


PCSTR LongSwitches[] = {
    "v" "verbose",
    "f" "flags",
    "r" "runs",
    "t" "tbl_size",
    "m" "map_size",
    "z" "hashtbl_size",
    "s" "seed",
    NULL
};


INT main(INT argc, PSTR argv[])
{
    INT     c;
    UINT    n;
    PSTR    ptr;

    LINE   *tbl;            /* Table of LINE structures which should be searched. */
    UINT   *map;            /* Mapping between random numbers and LINE structures. */

    UINT    flags = 0;      /* Flags defined above */
    UINT    runs = 0;       /* Number of repetitions */
    UINT    tbl_size = 0;   /* Number of LINE structures in table */
    UINT    map_size = 0;   /* Map entries */
    UINT    ht_size = 0;    /* Hash table size */
    UINT    seed = 0;       /* Seed for random generator */


    //g_LogFlags = LOG_FLAG_CONSOLE;  /* Log messages to console */

    while ((c = CmdSwitchA(argv, LongSwitches)) != -1)
    {
        switch (c)
        {
            case 'v':
                flags |= FLAG_VERBOSE;
                break;
#ifdef LOG_H
            case 'd':
                /* set debug mask */
                if (CmdUInt64ParamA(&g_DebugMask)) usage();
                break;
#endif
            case 'f':
                if (CmdUIntParamA(&n)) usage();
                flags |= n;
                break;
            case 'r':
                if (CmdIntParamA((INT*)&runs, 1, BIT(20))) usage();
                break;
            case 't':
                if (CmdIntParamA((INT*)&tbl_size, 1, BIT(30))) usage();
                break;
            case 'm':
                if (CmdIntParamA((INT*)&map_size, 1, BIT(30))) usage();
                break;
            case 'z':
                if (CmdIntParamA((INT*)&ht_size, 1, BIT(30))) usage();
                break;
            case 's':
                if (CmdUIntParamA(&seed)) usage();
                flags |= FLAG_RANDOM;
                break;
            case 'h':
            default:
                usage();
        }
    }

    if ((ptr = CmdParamA()))
        usage();

    if (tbl_size <= 0)
        tbl_size = 256;

    if (map_size <= 0)
    {
        map_size = tbl_size;
        if (flags & FLAG_RANDOM)
            map_size *= 8;  /* 4 kB with default tbl_size fits in L1 cache */
    }

    if (ht_size <= 0)
        ht_size = tbl_size * 2;     /* hash table size is 2x number of line entries */

    if (runs <= 0)
        runs = BIT(20) / map_size;

    if (runs <= 0)
        runs = 1;

    tbl = (LINE*)calloc(tbl_size + 4, sizeof(LINE));
    ASSERT(tbl);
    tbl = (LINE*)ROUND_UP_POWER2((SIZE_T)tbl, 64);

    map = (UINT*)calloc(map_size + 16, sizeof(*map));
    ASSERT(map);
    map = (UINT*)ROUND_UP_POWER2((SIZE_T)map, 64);

#ifdef HIGH_PRIORITY_CLASS
    AdjustPriority(HIGH_PRIORITY_CLASS, THREAD_PRIORITY_HIGHEST);
#endif

    RandSeed(seed);

    /* Init LINE table id's */
    for (n = 0; n < tbl_size; n++)
    {        
#if STRING_KEYS
        wsprintfA(tbl[n].id, "N%.12u", n);
#else
        tbl[n].id = n;
#endif
    }


    /* Init map table */
    for (n = 0; n < map_size; n++)
    {
        if (flags & FLAG_RANDOM)
            map[n] = (UINT)RandRange(0, tbl_size);
        else
            map[n] = n % tbl_size;
        //printf("%u\n", (UINT)map[n]);
    }


    if (!(flags & (FLAG_NOSTAT | FLAG_TABLE)))
    {
        printf("Param: runs=%u flags=%#.2x tbl_size=%u map_size=%u hashtbl_size=%u "
                "total_runs=%u seed=%u\n",
                runs, flags, tbl_size, map_size, ht_size, runs*map_size, seed);
    }


#if USE_AVL_TREE
    /* Init AVL tree */
    AVLTREE tree;           /* AVL Tree structure */
    avlit(&tree);

#if USE_AVLPTRNODE
    /*
     * Use separate node table to make comparison with std::map more fair.
     */
    AVLPTRNODE *node_tbl;

    node_tbl = (AVLPTRNODE*)calloc(tbl_size + 4, sizeof(*node_tbl));
    ASSERT(node_tbl);
    node_tbl = (AVLPTRNODE*)ROUND_UP_POWER2((SIZE_T)node_tbl, 64);

    for (n = 0; n < tbl_size; n++)
    {
        node_tbl[n].data = &tbl[n];
        avlan(&tree, (avlcf)CompareLinePtr, &node_tbl[n].node);
    }

#else // USE_AVLPTRNODE

    for (n = 0; n < tbl_size; n++)
    {
        avlan(&tree, (avlcf)CompareLine, &tbl[n].node);
    }

#endif // USE_AVLPTRNODE

#endif // USE_AVL_TREE


#if USE_HASH_MAP
    /* Robin Hood hash table */
    HASH_TABLE hashtbl;
    HT_STAT    hs;

    /* Init hash table */
    HT_Init(&hashtbl, ht_size, 0, OFFSETOF(LINE, id));

    for (n = 0; n < tbl_size; n++)
    {
        HT_Int_Insert(&hashtbl, &tbl[n]);
    }

    HT_Handle_GetStat(&hashtbl, &hs);

    if (!(flags & (FLAG_NOSTAT | FLAG_TABLE)))
    {
        printf("Hashtbl: table_size=%Iu used=%Iu max_dib=%Iu mean_coll=%Iu/100\n",
                hs.table_size, hs.used_entries, hs.max_dib,
                (100*hs.collisions)/hs.used_entries);
    }
#endif // USE_HASH_MAP


#ifdef USE_DIRECT_HASH
    /*
     * Init direct hash table [hash(key) == key]
     */
    HASH_TABLE hashtbl2;
    UINT ht_size2 = ht_size;
    HT_Init(&hashtbl2, ht_size2, 0, OFFSETOF(LINE, id));

    for (n = 0; n < tbl_size; n++)
    {
        HT_Direct_Insert(&hashtbl2, &tbl[n]);
    }
#endif // USE_DIRECT_HASH


#ifdef USE_DPA_HASH
    /*
     * Daniel Abrecht Hash Table.
     * https://www.mikrocontroller.net/topic/560335#new
     */

    dpa_u_map_u_t dpa_map = {0};

    for (n = 0; n < tbl_size; n++)
    {
        dpa_u_map_u_set(&dpa_map, (key_t)n, &tbl[n]);
    }
#endif // USE_DPA_HASH


#ifdef USE_STD_SET
    STD_SET std_set;

    for (n = 0; n < tbl_size; n++)
    {
        std_set.insert(&tbl[n]);
    }
#endif


#ifdef USE_STD_MAP
    STD_MAP std_map;

    for (n = 0; n < tbl_size; n++)
    {
        std_map.insert(KEY_VALUE_PAIR((key_t)n, &tbl[n]));
    }
#endif


#ifdef USE_STD_UMAP
    STD_UMAP std_umap;

    for (n = 0; n < tbl_size; n++)
    {
        std_umap.insert(KEY_VALUE_PAIR((key_t)n, &tbl[n]));
    }
#endif

    /*
     * Now run the tests
     */

    #define RUN(Func, Data) \
        RunSearch(runs, tbl, tbl_size, map, map_size, flags, Func, Data, TO_STRING(Func))

    #define RUN_DUMMY(Func, Data) \
        RunDummy(runs, tbl, tbl_size, map, map_size, flags, NULL, NULL, TO_STRING(Func))

    if (!(flags & FLAG_NOSTAT) && (flags & FLAG_TABLE))
    {
        printf("Direct Hash Tree");
        if (!(flags & FLAG_NOSLOW))
            printf(" Linear");
        printf("\n");
    }

    RUN(DirectSearch, NULL);

#ifdef USE_HASH_MAP
    RUN(HashSearch, &hashtbl);
#else
    RUN_DUMMY(HashSearch, &hashtbl);
#endif

#ifdef USE_AVL_TREE
    RUN(AVLTreeSearch, &tree);
#else
    RUN_DUMMY(AVLTreeSearch, &tree);
#endif

#ifdef USE_STD_SET
    RUN(StdSetSearch, &std_set);
#else
    RUN_DUMMY(StdSetSearch, &std_set);
#endif

#ifdef USE_STD_MAP
    RUN(StdMapSearch, &std_map);
#else
    RUN_DUMMY(StdMapSearch, &std_map);
#endif

#ifdef USE_STD_UMAP
    RUN(StdUMapSearch, &std_umap);
#else
    RUN_DUMMY(StdUMapSearch, &std_umap);
#endif

#ifdef USE_BINARY_SEARCH
    RUN(StdBinarySearch, NULL);
#else
    RUN_DUMMY(StdBinarySearch, NULL);
#endif

#ifdef USE_BINARY_SEARCH_INLINE
    RUN(BinarySearch, NULL);
#else
    RUN_DUMMY(BinarySearch, NULL);
#endif

#ifdef USE_BINARY_SEARCH_BRANCHLESS
    RUN(BinarySearch_BL, NULL);
#else
    RUN_DUMMY(BinarySearch_BL, NULL);
#endif

#ifdef USE_LOWER_BOUND
    RUN(StdLowerBound, NULL);
#else
    RUN_DUMMY(StdLowerBound, NULL);
#endif

#ifdef USE_DIRECT_HASH
    RUN(HashSearchDirect, &hashtbl2);
#else
    RUN_DUMMY(HashSearchDirect, &hashtbl2);
#endif

#ifdef USE_DPA_HASH
    RUN(DpaHashSearch, &dpa_map);
#else
    RUN_DUMMY(DpaHashSearch, &dpa_map);
#endif

    if (!(flags & FLAG_NOSLOW))
    {
        RUN(LinearSearch, NULL);

#ifdef USE_LINEAR_SEARCH_NB
        RUN(LinearSearch_NB, NULL);
#else
        RUN_DUMMY(LinearSearch_NB, NULL);
#endif

#ifdef USE_STD_FIND
        RUN(StdFindSearch, NULL);
#else
        RUN_DUMMY(StdFindSearch, NULL);
#endif
    }

#if USE_HASH_MAP
    if ((flags & FLAG_HASHCOL))
        printf("%Iu", (100*hs.collisions)/hs.used_entries);
#endif

    if ((flags & FLAG_TABLE))
        printf("\n");

    return 0;
}
