/*
This file implements a static open-address hashtable which uses
double hashing.
Copyright (C) 2004 The University of Texas at Austin

This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your option)
any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 59
Temple Place - Suite 330, Boston, MA 02111-1307, USA.

Email: usman@cs.njit.edu
Mail: Usman Roshan, Department of Computer Sciences, NJIT-CCS, Computer
Science Department, GITC 4400, University Heights, Newark, NJ 07102
*/
/*
Notes: when inserting key into table, must make sure that
value is NULL.
*/

#include<hashtable2.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<assert.h>
#include<math.h>

void
list_hashtable2_stats(hashtable2 ht)
{
	int             i;

	assert(ht);
	for (i = 0; i < ht->size_; i++) {
		if (ht->table_[i]) {
			lookup_hashtable2(ht, ht->table_[i]->key);
			printf("Entry %d has problength=%d\n", i, probelength_hashtable2(ht));
		}
	}
}

int
probelength_hashtable2(hashtable2 ht)
{
	return ht->probelength_;
}

void
del_hashtable2(hashtable2 ht)
{
	int             i;

	assert(ht);
	for (i = 0; i < ht->size_; i++)
		if (ht->table_[i]) {
			/*
			 * MUST free void* from main program by casting
			 * appropriately
			 */
			assert(ht->table_[i]->value == NULL);

			free(ht->table_[i]);
		}
	free(ht->table_);
	free(ht);
}

/*
 * IMPORTANT: hashtable size MUST be of size of power of 2, otherwise all the
 * possible entries will not be considered
 */
hashtable2
new_hashtable2(long sz)
{
	int             i;
	double          x;
	hashtable2      ht;

	ht = (hashtable2) malloc(sizeof(struct hashtable2_struct));

	/* setting hashtable to be size of power of 2 */
	/* this is required so that proper open addressing can occur, */
	/* i.e. eventually every entry in the table is considered */
	x = ceil(log(sz) / log(2));
	sz = pow(2, x + 1);

	ht->size_ = sz;

	/* allocate memory for table */
	ht->table_ = (hashtable2_node *) malloc(ht->size_ * sizeof(hashtable2_node));

	/* initialize to NULLS */
	for (i = 0; i < ht->size_; i++)
		ht->table_[i] = 0;
	ht->P_ = 2147483647;	/* initialize P (large prime) */
	ht->probelength_ = 0;

	/* initialize hash2_1 and hash2_2 variables */
	srand(time(0));
	ht->a1_ = rand() * (ht->P_ - 1) + 1;
	ht->a2_ = rand() * (ht->P_ - 1) + 1;
	ht->b1_ = rand() * ht->P_;
	ht->b2_ = rand() * ht->P_;

	return ht;
}

/*
 * This is called before hash2_1 and hash2_2. It sets the value of h_ to be
 * used by hash2_1 and hash2_2 and saves excessive calls to the hash
 * function.
 */
unsigned int
hash_2(hashtable2 ht, PTR_TYPE key)
{

	assert(ht);
	assert(key);
	key += (key << 12);
	key ^= (key >> 22);
	key += (key << 4);
	key ^= (key >> 9);
	key += (key << 10);
	key ^= (key >> 2);
	key += (key << 7);
	key ^= (key >> 12);
	ht->h_ = key;
	return key;
}

unsigned long
hash2_1(hashtable2 ht)
{
	assert(ht);
	return ((((ht->a1_ * ht->h_) + ht->b1_) % ht->P_) % ht->size_);
}

unsigned long
hash2_2(hashtable2 ht)
{
	assert(ht);
	return ((((ht->a2_ * ht->h_ + ht->b2_) % ht->P_) % (ht->size_ - 3)) | 1);
}

void
insert_hashtable2(hashtable2 ht, PTR_TYPE key, void *value)
{
	unsigned long   i;
	int             h1, h2;

	assert(ht);
	assert(key);
	hash_2(ht, key);
	/* hash_2(ht, key, ht->a1_, ht->a2_); */
	h1 = hash2_1(ht);
	h2 = hash2_2(ht);

	ht->probelength_ = 0;

	for (i = h1; ht->table_[i]; i = (i + h2) % ht->size_) {
		ht->probelength_++;
		if (ht->table_[i]->key == key) {	/* replace old entry */
			assert(ht->table_[i]->value == NULL);
			ht->table_[i]->value = value;
			return;
		}
	}

	/* printf("insert: for key %d hash value is %i\n", key, i); */
	ht->table_[i] = malloc(sizeof(struct hashtable2_node_struct));
	ht->table_[i]->key = key;
	ht->table_[i]->value = value;
	return;
}

void
set_value_null_hashtable2(hashtable2 ht, PTR_TYPE key)
{
	unsigned long   i;
	int             h1, h2;

	assert(ht);
	assert(key);
	hash_2(ht, key);
	/* hash_2(ht, key, ht->a1_, ht->a2_); */
	h1 = hash2_1(ht);
	h2 = hash2_2(ht);

	ht->probelength_ = 0;

	for (i = h1; ht->table_[i]; i = (i + h2) % ht->size_) {
		ht->probelength_++;
		if (ht->table_[i]->key == key) {	/* delete entry */
			ht->table_[i]->value = NULL;
			return;
		}
	}

	assert(0);
	return;
}

void           *
lookup_hashtable2(hashtable2 ht, PTR_TYPE key)
{
	unsigned long   i;
	int             h1, h2;

	assert(ht);
	assert(key);
	hash_2(ht, key);
	/* hash_2(ht, key, ht->a1_, ht->a2_); */
	h1 = hash2_1(ht);
	h2 = hash2_2(ht);

	ht->probelength_ = 0;

	for (i = h1; ht->table_[i]; i = (i + h2) % ht->size_) {
		ht->probelength_++;
		if (!(ht->table_[i]))
			return 0;
		else if (ht->table_[i] && ht->table_[i]->key == key) {
			return ht->table_[i]->value;
		}
	}
	return 0;
}

/*
 * unsigned int hash_2(hashtable2 ht, unsigned int key) { key *= 2654435761;
 * ht->h_ = key; return key; }
 */

/*
 * unsigned int hash_2(hashtable2 ht, unsigned int c, unsigned int a,
 * unsigned int b){ a=a-b; a=a-c; a=a^(c>>13); b=b-c; b=b-a; b=b^(a<<8);
 * c=c-a; c=c-b; c=c^(b>>13); a=a-b; a=a-c; a=a^(c>>12); b=b-c; b=b-a;
 * b=b^(a<<16); c=c-a; c=c-b; c=c^(b>>5); a=a-b; a=a-c; a=a^(c>>3); b=b-c;
 * b=b-a; b=b^(a<<10); c=c-a; c=c-b; c=c^(b>>15); ht->h_ = c; return c; }
 */