/*
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 hashtable2.h \brief Contains definition for a hash table structure
 * which uses pointers as keys and void* for values
 */

#ifndef HASHTABLE2
#define HASHTABLE2

typedef unsigned int PTR_TYPE;

typedef struct hashtable2_struct *hashtable2;

typedef struct hashtable2_node_struct *hashtable2_node;

struct hashtable2_node_struct {
	PTR_TYPE        key;
	void           *value;
};

struct hashtable2_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_;

	hashtable2_node *table_;
};

/* hash functions */
unsigned int    hash_2(hashtable2 ht, PTR_TYPE key);
/*
 * unsigned int hash_2(hashtable2 ht, unsigned int c, unsigned int a,
 * unsigned int b);
 */
inline unsigned long hash2_1(hashtable2 ht);
inline unsigned long hash2_2(hashtable2 ht);

/* dictionary operations */
void            insert_hashtable2(hashtable2 ht, PTR_TYPE key, void *value);
void           *lookup_hashtable2(hashtable2 ht, PTR_TYPE key);
void            set_value_null_hashtable2(hashtable2 ht, PTR_TYPE key);
void            list_hashtable2_stats(hashtable2 ht);
int             probelength_hashtable2(hashtable2 ht);

/* constructor */
hashtable2      new_hashtable2(long sz);

/* destructor */
void            del_hashtable2(hashtable2 ht);

#endif