See also: Heapify

Back to doug's directory

File information
Filename: chainedhashing.h Uploaded: Tue, 3rd Nov 2009 18:20:24
Size (bytes): 3.71 KiB md5 checksum: 9551e4c8857178329a5c89a698b4cb40
Uploader doug Download: chainedhashing.h
Description:

A chained hashing implementation that can be freely included into programs by including chainedhashing.h.

Default hash function is provided by hashlittle() taken from lookup3 by Bob Jenkins. Custom hash function can be used by editing the configuration directives in the header.

/*
 *  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);
 
 
 
 
 
RSS
Powered by Debian, Guinness, and excessive quantities of caffeine and sugar.