/* Test different hash strategies. */
#include <ccan/hash/hash.h>
#include <ccan/short_types/short_types.h>
#include <stddef.h>
#include <sys/time.h>
#include <time.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <err.h>
#include <string.h>

#define INLINE_HASH
#ifdef INLINE_HASH
#include <ccan/hash/hash.c>
#endif

#define NUM_VALUES 2

/* Linked-list style hash.  Linked-list off each bucket. */
struct hash_ll_elem {
	struct hash_ll_elem *next;
	u64 val[NUM_VALUES];
};

static void hash_ll_add(struct hash_ll_elem *htable[],
			unsigned int htable_bits,
			struct hash_ll_elem *new)
{
	u32 h = hash(new->val, NUM_VALUES, 0)
		& ((1 << htable_bits)-1);

	new->next = htable[h];
	htable[h] = new;
}

static struct hash_ll_elem *hash_ll_find(struct hash_ll_elem *htable[],
					 unsigned int htable_bits,
					 const u64 val[])
{
	struct hash_ll_elem *i;
	u32 h = hash(val, NUM_VALUES, 0) & ((1 << htable_bits)-1);

	for (i = htable[h]; i; i = i->next) {
		if (memcmp(val, i->val, sizeof(i->val)) == 0)
			return i;
	}
	return NULL;
}


/* Flat-style hash. Overflow to another bucket. */
struct hash_flat_elem {
	u64 val[NUM_VALUES];
};

static void hash_flat_add_linear(struct hash_flat_elem *htable[],
				 unsigned int htable_bits,
				 struct hash_flat_elem *new)
{
	u32 h = hash(new->val, NUM_VALUES, 0)
		& ((1 << htable_bits)-1);

	while (htable[h]) {
		h = (h + 1) & ((1 << htable_bits)-1);
	}
	htable[h] = new;
}

static struct hash_flat_elem *
hash_flat_find_linear(struct hash_flat_elem *htable[],
		      unsigned int htable_bits,
		      const u64 val[])
{
	struct hash_flat_elem *i;
	u32 h = hash(val, NUM_VALUES, 0) & ((1 << htable_bits)-1);

	while ((i = htable[h]) != NULL) {
		if (memcmp(val, i->val, sizeof(i->val)) == 0)
			return htable[h];
		h = (h + 1) & ((1 << htable_bits)-1);
	}
	return NULL;
}
	
static void hash_flat_add_2hash(struct hash_flat_elem *htable[],
				unsigned int htable_bits,
				struct hash_flat_elem *new)
{
	u32 h = hash(new->val, NUM_VALUES, 0);
	u32 h2 = ((h >> htable_bits) & ((1 << htable_bits)-1));

	h &= ((1 << htable_bits)-1);

	if (h2 == 0)
		h2++;

	while (htable[h]) {
		h = (h + h2) & ((1 << htable_bits)-1);
	}
	htable[h] = new;
}

static struct hash_flat_elem *
hash_flat_find_2hash(struct hash_flat_elem *htable[],
		     unsigned int htable_bits,
		     const u64 val[])
{
	struct hash_flat_elem *i;
	u32 h = hash(val, NUM_VALUES, 0);
	u32 h2 = ((h >> htable_bits) & ((1 << htable_bits)-1));

	h &= ((1 << htable_bits)-1);

	if (h2 == 0)
		h2++;

	while ((i = htable[h]) != NULL) {
		if (memcmp(val, i->val, sizeof(i->val)) == 0)
			return htable[h];
		h = (h + h2) & ((1 << htable_bits)-1);
	}
	return NULL;
}

static void hash_flat_add_linear_steal(struct hash_flat_elem *htable[],
				       unsigned int htable_bits,
				       struct hash_flat_elem *new)
{
	u32 h2, h = hash(new->val, NUM_VALUES, 0);
	h2 = (h >> htable_bits) & 7;
	h &= ((1 << htable_bits)-1);

//	assert(((unsigned long)new & 0x7) == 0);
	while (htable[h]) {
		h = (h + 1) & ((1 << htable_bits)-1);
	}
	htable[h] = (void *)((unsigned long)new | h2);
}

static struct hash_flat_elem *
hash_flat_find_linear_steal(struct hash_flat_elem *htable[],
			    unsigned int htable_bits,
			    const u64 val[])
{
	struct hash_flat_elem *i;
	u32 h2, h = hash(val, NUM_VALUES, 0);
	h2 = (h >> htable_bits) & 7;
	h &= ((1 << htable_bits)-1);

	while ((i = htable[h]) != NULL) {
		u32 hi = ((unsigned long) i) & 0x7;
		if (hi == h2) {
			i = (void *)((unsigned long)i & ~0x7UL);
			if (memcmp(val, i->val, sizeof(i->val)) == 0)
				return i;
		}
		h = (h + 1) & ((1 << htable_bits)-1);
	}
	return NULL;
}

static struct timeval start;

static void timestart(void)
{	
	gettimeofday(&start, NULL);
}

static void timeend(const char *msg, unsigned int num)
{
	struct timeval end;
	gettimeofday(&end, NULL);

	printf("%s %u: %llu\n", msg, num,
	       (end.tv_sec * 1000000ULL + end.tv_usec)
	       - (start.tv_sec * 1000000ULL + start.tv_usec));
}

int main(int argc, char *argv[])
{
	unsigned int htable_bits;
	struct hash_ll_elem **lltable, *llentries;
	struct hash_flat_elem **flattable, *flatentries;
	unsigned int i, j;
	unsigned int num_elems;
	void *p;

	if (argc != 2)
		errx(1, "Usage: hashbench <order-of-hashsize>");

	htable_bits = atoi(argv[1]);
	/* This means 50% full */
	num_elems = (1 << htable_bits) / 2;

	/* Flat table tests. */
	flattable = calloc(1 << htable_bits, sizeof(struct hash_flat_elem *));
	flatentries = calloc(num_elems, sizeof(*flatentries));

	/* Make sure it's cache warm, so each cycle even. */
	memset(flattable, 0, sizeof(*flattable) * (1 << htable_bits));
	for (i = 0; i < num_elems; i++) {
		for (j = 0; j < NUM_VALUES; j++)
			flatentries[i].val[j] = i + j;
	}

	timestart();
	for (i = 0; i < num_elems; i++) {
		hash_flat_add_linear(flattable, htable_bits, &flatentries[i]);
	}
	timeend("linear insert", num_elems);

	timestart();
	for (i = 0; i < num_elems; i++) {
		u64 val[NUM_VALUES];
		for (j = 0; j < NUM_VALUES; j++)
			val[j] = i + j;
		p = hash_flat_find_linear(flattable, htable_bits, val);
		assert(p == &flatentries[i]);
	}
	timeend("linear matching lookup", num_elems);

	timestart();
	for (i = 0; i < num_elems; i++) {
		u64 val[NUM_VALUES];
		for (j = 0; j < NUM_VALUES; j++)
			val[j] = (NUM_VALUES << htable_bits) + j;
		p = hash_flat_find_linear(flattable, htable_bits, val);
		assert(!p);
	}
	timeend("linear failing lookup", num_elems);

	/* Make sure it's cache warm, so each cycle even. */
	memset(flattable, 0, sizeof(*flattable) * (1 << htable_bits));
	for (i = 0; i < num_elems; i++) {
		for (j = 0; j < NUM_VALUES; j++)
			flatentries[i].val[j] = i + j;
	}

	timestart();
	for (i = 0; i < num_elems; i++) {
		hash_flat_add_linear_steal(flattable, htable_bits,
					   &flatentries[i]);
	}
	timeend("bitsteal insert", num_elems);

	timestart();
	for (i = 0; i < num_elems; i++) {
		u64 val[NUM_VALUES];
		for (j = 0; j < NUM_VALUES; j++)
			val[j] = i + j;
		p = hash_flat_find_linear_steal(flattable, htable_bits, val);
		assert(p == &flatentries[i]);
	}
	timeend("bitsteal matching lookup", num_elems);

	timestart();
	for (i = 0; i < num_elems; i++) {
		u64 val[NUM_VALUES];
		for (j = 0; j < NUM_VALUES; j++)
			val[j] = (NUM_VALUES << htable_bits) + j;
		p = hash_flat_find_linear_steal(flattable, htable_bits, val);
		assert(!p);
	}
	timeend("bitsteal failing lookup", num_elems);

	/* Make sure it's cache warm, so each cycle even. */
	memset(flattable, 0, sizeof(*flattable) * (1 << htable_bits));
	for (i = 0; i < num_elems; i++) {
		for (j = 0; j < NUM_VALUES; j++)
			flatentries[i].val[j] = i + j;
	}

	timestart();
	for (i = 0; i < num_elems; i++) {
		hash_flat_add_2hash(flattable, htable_bits, &flatentries[i]);
	}
	timeend("secondary insert", num_elems);

	timestart();
	for (i = 0; i < num_elems; i++) {
		u64 val[NUM_VALUES];
		for (j = 0; j < NUM_VALUES; j++)
			val[j] = i + j;
		p = hash_flat_find_2hash(flattable, htable_bits, val);
		assert(p == &flatentries[i]);
	}
	timeend("secondary matching lookup", num_elems);

	timestart();
	for (i = 0; i < num_elems; i++) {
		u64 val[NUM_VALUES];
		for (j = 0; j < NUM_VALUES; j++)
			val[j] = (NUM_VALUES << htable_bits) + j;
		p = hash_flat_find_2hash(flattable, htable_bits, val);
		assert(!p);
	}
	timeend("secondary failing lookup", num_elems);

	free(flattable);
	free(flatentries);
			
	/* Chained table tests. */
	lltable = calloc(1 << htable_bits, sizeof(struct hash_ll_elem *));
	llentries = calloc(num_elems, sizeof(*llentries));

	/* Make sure it's cache warm, so each cycle even. */
	memset(lltable, 0, sizeof(*lltable) * (1 << htable_bits));
	for (i = 0; i < num_elems; i++) {
		for (j = 0; j < NUM_VALUES; j++)
			llentries[i].val[j] = i + j;
	}
	timestart();
	for (i = 0; i < num_elems; i++) {
		hash_ll_add(lltable, htable_bits, &llentries[i]);
	}
	timeend("linked insert", num_elems);

	timestart();
	for (i = 0; i < num_elems; i++) {
		u64 val[NUM_VALUES];
		for (j = 0; j < NUM_VALUES; j++)
			val[j] = i + j;
		p = hash_ll_find(lltable, htable_bits, val);
		assert(p == &llentries[i]);
	}
	timeend("linked matching lookup", num_elems);

	timestart();
	for (i = 0; i < num_elems; i++) {
		u64 val[NUM_VALUES];
		for (j = 0; j < NUM_VALUES; j++)
			val[j] = (NUM_VALUES << htable_bits) + j;
		p = hash_ll_find(lltable, htable_bits, val);
		assert(!p);
	}
	timeend("linked failing lookup", num_elems);
	
	exit(0);
}