/*
 *  Chained hashing implemention
 *  Copyright (C) 2009 neverfear.org.
 *
 *  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, 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., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
 
 
 
 
 
 
/*
 *    __                 __ _                       _   _             __  
 *   / / ___ ___  _ __  / _(_) __ _ _   _ _ __ __ _| |_(_) ___  _ ___ \ \ 
 *  / / / __/ _ \| '_ \| |_| |/ _` | | | | '__/ _` | __| |/ _ \| '_  \ \ \
 *  \ \| (_| (_) | | | |  _| | (_| | |_| | | | (_| | |_| | (_) | | | | / /
 *   \_\\___\___/|_| |_|_| |_|\__, |\__,_|_|  \__,_|\__|_|\___/|_| |_|/_/ 
 *                            |___/                                      
 *        EDIT THE FOLLOWING DIRECTIVES TO INFLUENCE COMPILATION
 *                                                             
 */
 
// Comment this out and redefine it to use a different hash function
#define HASH            default_hash
 
// Uncomment this to include a main() routine for executable execution
//#define BUILD_EXECUTABLE 
 
 
/*
 *  END OF CONFIGURATION
 *    __    __               __ _                       _   _             __  
 *   / /   / /__ ___  _ __  / _(_) __ _ _   _ _ __ __ _| |_(_) ___  _ ___ \ \ 
 *  / /   / / __/ _ \| '_ \| |_| |/ _` | | | | '__/ _` | __| |/ _ \| '_  \ \ \
 *  \ \  / / (_| (_) | | | |  _| | (_| | |_| | | | (_| | |_| | (_) | | | | / /
 *   \_\/_/ \___\___/|_| |_|_| |_|\__, |\__,_|_|  \__,_|\__|_|\___/|_| |_|/_/ 
 *                                |___/                                      
*/
 
 
 
 
 
struct hashitem {
	char *              key;
	int                 hash;
	void *              data;
	struct hashitem *   next;
};
 
typedef struct hashitem HASHITEM;
 
typedef struct hashitem * HASHCHAIN;
 
struct hashtable {
	int                  size;
	int                  count;  // This field helps us optimise calculating the item count
	HASHCHAIN *          chains;
};
 
typedef struct hashtable HASHTABLE;
 
 
 
HASHTABLE *    create_hash_table    (int size);
 
HASHITEM *     create_hash_item     (char * key,
                                     void * data);
 
unsigned int   default_hash         (char * key);
 
void           insert_item          (HASHTABLE * ht,
                                     HASHITEM * item);
 
void *         get_item_data        (HASHTABLE * ht,
                                     char * key);
 
HASHITEM *     get_item             (HASHTABLE * ht,
                                     char * key);
 
int            get_item_count       (HASHTABLE * hte);
 
double         get_load_factor      (HASHTABLE * ht);
 
void           apply_rehash         (HASHTABLE * srctable,
                                     HASHTABLE * desttable);
 
HASHTABLE *    do_hash_table_resize (HASHTABLE * oldht,
                                     int newhtsize);
 
void           destroy_hash_table   (HASHTABLE * ht);
 
int            get_highest_prime    (int limit);
 
HASHITEM *     clone_hash_item      (HASHITEM * copyme);
 
void           print_hash_table     (HASHTABLE * hash_table,
                                     int indent);
 
void           run_hash_test        (int      item_count,
	                                 char **  item_array,
	                                 int      table_size);