/*
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
*/
#include<hashtable.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<assert.h>

void print_hashtable(hashtable ht){
  int i;
  
  assert(ht);
  for(i=0;i<ht->size_;i++){
    if(ht->table_[i]){
      printf("Key = %s, lookup value = %d, value = %d\n", ht->table_[i]->key, lookup_hashtable(ht, ht->table_[i]->key), ht->table_[i]->value);
    }
  }
}

int probelength_hashtable(hashtable ht){assert(ht); return ht->probelength_;}

void del_hashtable(hashtable ht){
  int i;
  assert(ht);
  for(i=0;i<ht->size_;i++)
    if(ht->table_[i]) { 
      assert(ht->table_[i]->key); 
      free(ht->table_[i]->key); 
      free(ht->table_[i]); 
    }
  free(ht->table_);
  free(ht);
}

hashtable new_hashtable(long sz){
  int i; double x;
  hashtable ht;
  
  ht = (hashtable) malloc(sizeof(struct hashtable_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_ = (hashtable_node*) malloc(ht->size_*sizeof(hashtable_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 hash1 and hash2 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 hash1 and hash2. It sets the 
   value of h_ to be used by hash1 and hash2 and saves excessive calls
   to the hash function.*/
unsigned long hash(hashtable ht, const char* key) {
  unsigned long g;
  
  assert(ht);
  ht->h_ = 0;
  while(*key) {
    ht->h_ = (ht->h_ << 4) + *key++;
    g = ht->h_ & 0xF0000000L;
    if(g) ht->h_ ^= g >> 24;
    ht->h_ &= ~g;
  }
  return(ht->h_ % ht->P_); /*P_ is a large prime*/
}

unsigned long hash1(hashtable ht) {
  return ((((ht->a1_ * ht->h_) + ht->b1_) % ht->P_) % ht->size_) ;
}

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

void insert_hashtable(hashtable ht, char* key, int value) {
  unsigned long i;
  int h1, h2;

  assert(ht);
  assert(key);
  hash(ht, key);
  h1 = hash1(ht);
  h2 = hash2(ht);
  
  ht->probelength_ = 0;
  
  for(i = h1; ht->table_[i]; i = (i + h2) % ht->size_){
    ht->probelength_++;
    if(!strcmp(ht->table_[i]->key,key)) return;
  }

  ht->table_[i] = malloc(sizeof(struct hashtable_node_struct));
  ht->table_[i]->key = (char*) malloc((strlen(key)+1) * sizeof(char));
  strcpy(ht->table_[i]->key, key);
  ht->table_[i]->value = value;
  return;
}
    
int lookup_hashtable(hashtable ht, char* key) {
  unsigned long i;
  int h1, h2;
  
  assert(ht); assert(key);
  hash(ht, key);
  h1 = hash1(ht);
  h2 = hash2(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] && !strcmp(ht->table_[i]->key,key)) 
      return ht->table_[i]->value;
  }

  /*changed to return -1 from 0*/
  return -1;
}