/*
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;
  }*/