#ifndef CGPERF_HASH_TABLE_C
#define CGPERF_HASH_TABLE_C
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "c_fixing.h"
#include "keyword.h"
#include "hash-table.h"
#include "hash.h"
/*------------------------------------------------------------------------------------------------*/
#include "namespace/hash-table.h"
#include "namespace/keyword.h"
#include "namespace/hash.h"
/*------------------------------------------------------------------------------------------------*/
/*{{{ ht_new */
/*
 * We make the size of the hash table a power of 2. This allows for two optimizations: It eliminates
 * the modulo instruction, and allows for an easy secondary hashing function.
 */
static struct Hash_Table *ht_new(u32 size, bool ignore_length)
{
	struct Hash_Table *t;
	u32 shift;

	t = calloc(1, sizeof(*t));
	t->ignore_length = ignore_length;

	/* there need to be enough spare entries */
	size = size * (u32)ht_size_factor;

	/* find smallest power of 2 that is >= size */
	shift = 0;
	if ((size >> 16) > 0) {
		size = size >> 16;
		shift += 16;
	}
	if ((size >> 8) > 0) {
		size = size >> 8;
		shift += 8;
	}
	if ((size >> 4) > 0) {
		size = size >> 4;
		shift += 4;
	}
	if ((size >> 2) > 0) {
		size = size >> 2;
		shift += 2;
	}
	if ((size >> 1) > 0) {
		size = size >> 1;
		shift += 1;
	}
	t->log_size = shift;
	t->size = 1 << shift;

	t->table = calloc(t->size, sizeof(*(t->table)));
	return t;
}/*}}}*/
/*{{{ ht_del */
static void ht_del(struct Hash_Table *t)
{
	free(t->table);
	free(t);
}/*}}}*/
/*{{{ ht_insert */
/*
 * Attempts to insert ITEM in the table. If there is already an equal entry in it, returns it.
 * Otherwise inserts ITEM and returns NULL.
 */
static struct Keyword *ht_insert(struct Hash_Table *t, struct Keyword *item)
{
	u32 hash_val;
	u32 probe;
	u32 increment;

	hash_val = hashpjw((u8*)item->selchars, item->selchars_length * sizeof(u32));
	probe = hash_val & (t->size - 1);
	increment = (((hash_val >> t->log_size) ^ (t->ignore_length ?  0 : item->allchars_length))
											<< 1) + 1;
	/*
	 * note that because _size is a power of 2 and increment is odd, we have
	 * gcd(increment,_size) = 1, which guarantees that we'll find an empty entry during the loop
	 */
	loop {
		if (t->table[probe] == 0)
			break;
		if (ht_equal(t, t->table[probe], item))
			return t->table[probe];
		++(t->collisions);
		probe = (probe + increment) & (t->size - 1);
	}
	t->table[probe] = item;
	return 0;
}/*}}}*/
/*{{{ ht_equal */
static bool ht_equal(struct Hash_Table *t, struct Keyword *item1, struct Keyword *item2)
{
	return item1->selchars_length == item2->selchars_length
		&& memcmp(item1->selchars, item2->selchars, item1->selchars_length * sizeof(u32))
											== 0
		&& (t->ignore_length || item1->allchars_length == item2->allchars_length);
}/*}}}*/
/*{{{ ht_dump */
static void ht_dump(struct Hash_Table *t)
{
	s32 field_width;
	s32 i;

	field_width = 0;
	{
		s32 i;

		i = t->size - 1;
		loop {
			if (i < 0)
				break;
			if (t->table[i] != 0)
				if (field_width < t->table[i]->selchars_length)
					field_width = t->table[i]->selchars_length;
			i--;
		}
	}
	fprintf(stderr, "\ndumping the hash table\ntotal available table slots = %d, total bytes = %d, total collisions = %d\nlocation, %*s, keyword\n", t->size, t->size * (u32)(sizeof(*(t->table))), t->collisions, field_width, "keysig");

	i = t->size - 1;
	loop {
		if (i < 0)
			break;
		if (t->table[i] != 0) {
			s32 j;

			fprintf(stderr, "%8d, ", i);
			if (field_width > t->table[i]->selchars_length)
				fprintf(stderr, "%*s", field_width - t->table[i]->selchars_length, "");
			j = 0;
			loop {
				if (j >= t->table[i]->selchars_length)
					break;
				putc(t->table[i]->selchars[j], stderr);
				++j;
			}
			fprintf(stderr, ", %.*s\n", t->table[i]->allchars_length, t->table[i]->allchars);
		}
		i--;
	}
	fprintf(stderr, "\nend dumping hash table\n\n");
}/*}}}*/
/*------------------------------------------------------------------------------------------------*/
#define EPILOG
#include "namespace/hash-table.h"
#include "namespace/keyword.h"
#include "namespace/hash.h"
#undef EPILOG
/*------------------------------------------------------------------------------------------------*/
#endif