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

/*! \file hashtable.h
\brief Contains definition for a hash table structure which
uses strings as keys
*/

#ifndef HASHTABLE
#define HASHTABLE

typedef struct hashtable_struct* hashtable;

typedef struct hashtable_node_struct* hashtable_node;

struct hashtable_node_struct {
  char* key;
  int value;
};

struct hashtable_struct { 
  
  /*size is size of table*/
  long size_;
  
  /*number of collisions before empty slot is found*/
  int probelength_;
  
  /* hash sets this value.  it is used in hash1 and hash2
     to avoid calling hash again (efficiency reasons) */
  unsigned long h_;
  
  /*random values used in hash functions.*/
  unsigned long a1_, a2_, b1_, b2_, P_;
  
  hashtable_node* table_;
};

/*hash functions*/
unsigned long hash(hashtable ht, const char* str);
unsigned long hash1 (hashtable ht);
unsigned long hash2 (hashtable ht);

/*dictionary operations*/
void  insert_hashtable (hashtable ht, char* key, int value);
int lookup_hashtable (hashtable ht, char* key);

int probelength_hashtable(hashtable ht);
void print_hashtable(hashtable ht);

/*constructor*/
hashtable new_hashtable(long sz);             

/*destructor*/
void del_hashtable(hashtable ht);

#endif