utils.hcu

#ifndef UTILS_HCU
#define UTILS_HCU
#include <cstdint>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <string>
#include "xxhash.hcu"
#include <curand.h>
#include <curand_kernel.h>
#include <math.h>
#include <thrust/device_vector.h>
#include <thrust/host_vector.h>
#include <thrust/sequence.h>
#include <thrust/sort.h>
#include <ctime>
#include <iostream>
#include <random>
#include <functional>
#include <cmath>
#include <chrono>
#include <ctime>
#include <cstdlib>
#define MAX_DEPTH (100)
#define ERR_DEPTH (-1)
#define EMPTY_CELL (0)
#define BLOCK_SIZE (256)
#define clog2(x) ceil(log2((double)x))
#define REPEAT_TIMES 5

class HashTable
{
public:
    HashTable(uint32_t size, uint32_t evict_bound, uint32_t num_funcs);
    ~HashTable();
    virtual int insert(uint32_t *key, uint32_t size) = 0;
    virtual void lookup(uint32_t *key, bool *result, uint32_t size) = 0;
    virtual void remove(uint32_t *key, uint32_t size) = 0;
    virtual void info() = 0;

protected:
    uint32_t *data;
    uint32_t size;
    //
    uint32_t evict_bound;
    uint32_t hash_func_num;

    uint32_t *pos_to_func_map;
    uint32_t *hash_func_seeds;

    // virtual void gen_hash_func_seeds() = 0;
};

template <typename T>
void do_swap(T &a, T &b)
{
    T tmp = a;
    a = b;
    b = tmp;
}

HashTable::HashTable(uint32_t size, uint32_t evict_bound, uint32_t num_funcs) : size(size), evict_bound(evict_bound), hash_func_num(num_funcs)
{
    data = new uint32_t[size];
    pos_to_func_map = new uint32_t[size];
    hash_func_seeds = new uint32_t[hash_func_num + 1];
}

HashTable::~HashTable()
{
    delete[] data;
    delete[] pos_to_func_map;
    delete[] hash_func_seeds;
}

inline double time_func(std::function<void()> f)
{
    float duration;
    // cudaEvent_t start, stop;

    // cudaEventCreate(&start);
    // cudaEventRecord(start, 0);

    auto start = std::chrono::system_clock::now();

    f();

    auto end = std::chrono::system_clock::now();
    auto nano =  std::chrono::duration<double>(end - start).count();

    // cudaEventCreate(&stop);
    // cudaEventRecord(stop, 0);
    // cudaEventSynchronize(stop);

    // cudaEventElapsedTime(&duration, start, stop);

    // return (double)(duration);
    return (double)(nano);
}

void generate_unique_random(uint32_t *data, uint32_t size, float alpha = 1.5)
{
    std::mt19937 mt(time(nullptr));
    uint32_t offset = 1 + mt() % (1 << 10);
    uint32_t bigger_size = size * alpha;
    uint32_t *tmp = new uint32_t[bigger_size];
    for (uint32_t i = 0; i < bigger_size; i++)
    {
        tmp[i] = i + offset;
    }
    for (uint32_t i = 0; i < bigger_size; i++)
    {
        uint32_t j = mt() % (bigger_size - i);
        do_swap(tmp[i], tmp[j]);
    }
    for (uint32_t i = 0; i < size; i++)
    {
        data[i] = tmp[i];
    }
    delete[] tmp;
}

void test_xxhash()
{
    assert(xxhash(12, 12) == 245702375);
}

void test_hashtable(std::string class_name, HashTable &x)
{
    printf("[testing]: test %s\n", class_name.c_str());
    uint32_t keys[12] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    x.insert(keys, 12);
    keys[0] = 12;
    bool lookup_result[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    x.lookup(keys, lookup_result, 12);

    assert(("[failed]:" + class_name + " lookup failed", lookup_result[0] == 0));

    for (int i = 1; i < 12; i++)
    {
        printf("%d ", lookup_result[i]);
        assert(("[failed]: " + class_name + " lookup failed", lookup_result[i] == 1));
    }
    uint32_t delete_list[4] = {1, 2, 3, 4};
    bool delete_result[4] = {0, 0, 0, 0};
    x.remove(delete_list, 4);
    x.lookup(delete_list, delete_result, 4);
    for (int i = 0; i < 4; i++)
    {
        assert(("[failed]: " + class_name + " remove failed", delete_result[i] == 0));
    }
    printf("[success]: %s test success\n", class_name.c_str());
    printf("\n");
}

double average(double *x, int len)
{
    double sum = 0;
    for (int i = 0; i < len; i++)
        sum += x[i];
    return sum / len;
}

double variance(double *x, int len)
{
    double avg = average(x, len), sum;
    for (int i = 0; i < len; i++)
        sum += pow(x[i] - avg, 2);
    return sum / len;
}

double standardDev(double *x, int len)
{
    double var = variance(x, len);
    return sqrt(var);
}
#endif