/*
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);
inline unsigned long hash1(hashtable ht);
inline 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