1/*********************************************************************** 2* 3* hash.c 4* 5* Implementation of hash tables. Each item inserted must include 6* a hash_bucket member. 7* 8* Copyright (C) 2002 Roaring Penguin Software Inc. 9* 10* This software may be distributed under the terms of the GNU General 11* Public License, Version 2 or (at your option) any later version. 12* 13* LIC: GPL 14* 15***********************************************************************/ 16 17static char const RCSID[] = 18"$Id$"; 19 20#include "hash.h" 21 22#include <limits.h> 23#define BITS_IN_int ( sizeof(int) * CHAR_BIT ) 24#define THREE_QUARTERS ((int) ((BITS_IN_int * 3) / 4)) 25#define ONE_EIGHTH ((int) (BITS_IN_int / 8)) 26#define HIGH_BITS ( ~((unsigned int)(~0) >> ONE_EIGHTH )) 27 28#define GET_BUCKET(tab, data) ((hash_bucket *) ((char *) (data) + (tab)->hash_offset)) 29 30#define GET_ITEM(tab, bucket) ((void *) (((char *) (void *) bucket) - (tab)->hash_offset)) 31 32static void *hash_next_cursor(hash_table *tab, hash_bucket *b); 33 34/********************************************************************** 35* %FUNCTION: hash_init 36* %ARGUMENTS: 37* tab -- hash table 38* hash_offset -- offset of hash_bucket data member in inserted items 39* compute -- pointer to function to compute hash value 40* compare -- pointer to comparison function. Returns 0 if items are equal, 41* non-zero otherwise. 42* %RETURNS: 43* Nothing 44* %DESCRIPTION: 45* Initializes a hash table. 46***********************************************************************/ 47void 48hash_init(hash_table *tab, 49 size_t hash_offset, 50 unsigned int (*compute)(void *data), 51 int (*compare)(void *item1, void *item2)) 52{ 53 size_t i; 54 55 tab->hash_offset = hash_offset; 56 tab->compute_hash = compute; 57 tab->compare = compare; 58 for (i=0; i<HASHTAB_SIZE; i++) { 59 tab->buckets[i] = NULL; 60 } 61 tab->num_entries = 0; 62} 63 64/********************************************************************** 65* %FUNCTION: hash_insert 66* %ARGUMENTS: 67* tab -- hash table to insert into 68* item -- the item we're inserting 69* %RETURNS: 70* Nothing 71* %DESCRIPTION: 72* Inserts an item into the hash table. It must not currently be in any 73* hash table. 74***********************************************************************/ 75void 76hash_insert(hash_table *tab, 77 void *item) 78{ 79 hash_bucket *b = GET_BUCKET(tab, item); 80 unsigned int val = tab->compute_hash(item); 81 b->hashval = val; 82 val %= HASHTAB_SIZE; 83 b->prev = NULL; 84 b->next = tab->buckets[val]; 85 if (b->next) { 86 b->next->prev = b; 87 } 88 tab->buckets[val] = b; 89 tab->num_entries++; 90} 91 92/********************************************************************** 93* %FUNCTION: hash_remove 94* %ARGUMENTS: 95* tab -- hash table 96* item -- item in hash table 97* %RETURNS: 98* Nothing 99* %DESCRIPTION: 100* Removes item from hash table 101***********************************************************************/ 102void 103hash_remove(hash_table *tab, 104 void *item) 105{ 106 hash_bucket *b = GET_BUCKET(tab, item); 107 unsigned int val = b->hashval % HASHTAB_SIZE; 108 109 if (b->prev) { 110 b->prev->next = b->next; 111 } else { 112 tab->buckets[val] = b->next; 113 } 114 if (b->next) { 115 b->next->prev = b->prev; 116 } 117 tab->num_entries--; 118} 119 120/********************************************************************** 121* %FUNCTION: hash_find 122* %ARGUMENTS: 123* tab -- hash table 124* item -- item equal to one we're seeking (in the compare-function sense) 125* %RETURNS: 126* A pointer to the item in the hash table, or NULL if no such item 127* %DESCRIPTION: 128* Searches hash table for item. 129***********************************************************************/ 130void * 131hash_find(hash_table *tab, 132 void *item) 133{ 134 unsigned int val = tab->compute_hash(item) % HASHTAB_SIZE; 135 hash_bucket *b; 136 for (b = tab->buckets[val]; b; b = b->next) { 137 void *item2 = GET_ITEM(tab, b); 138 if (!tab->compare(item, item2)) return item2; 139 } 140 return NULL; 141} 142 143/********************************************************************** 144* %FUNCTION: hash_find_next 145* %ARGUMENTS: 146* tab -- hash table 147* item -- an item returned by hash_find or hash_find_next 148* %RETURNS: 149* A pointer to the next equal item in the hash table, or NULL if no such item 150* %DESCRIPTION: 151* Searches hash table for anoter item equivalent to this one. Search 152* starts from item. 153***********************************************************************/ 154void * 155hash_find_next(hash_table *tab, 156 void *item) 157{ 158 hash_bucket *b = GET_BUCKET(tab, item); 159 for (b = b->next; b; b = b->next) { 160 void *item2 = GET_ITEM(tab, b); 161 if (!tab->compare(item, item2)) return item2; 162 } 163 return NULL; 164} 165/********************************************************************** 166* %FUNCTION: hash_start 167* %ARGUMENTS: 168* tab -- hash table 169* cursor -- a void pointer to keep track of location 170* %RETURNS: 171* "first" entry in hash table, or NULL if table is empty 172* %DESCRIPTION: 173* Starts an iterator -- sets cursor so hash_next will return next entry. 174***********************************************************************/ 175void * 176hash_start(hash_table *tab, void **cursor) 177{ 178 int i; 179 for (i=0; i<HASHTAB_SIZE; i++) { 180 if (tab->buckets[i]) { 181 /* Point cursor to NEXT item so it is valid 182 even if current item is free'd */ 183 *cursor = hash_next_cursor(tab, tab->buckets[i]); 184 return GET_ITEM(tab, tab->buckets[i]); 185 } 186 } 187 *cursor = NULL; 188 return NULL; 189} 190 191/********************************************************************** 192* %FUNCTION: hash_next 193* %ARGUMENTS: 194* tab -- hash table 195* cursor -- cursor into hash table 196* %RETURNS: 197* Next item in table, or NULL. 198* %DESCRIPTION: 199* Steps cursor to next item in table. 200***********************************************************************/ 201void * 202hash_next(hash_table *tab, void **cursor) 203{ 204 hash_bucket *b; 205 206 if (!*cursor) return NULL; 207 208 b = (hash_bucket *) *cursor; 209 *cursor = hash_next_cursor(tab, b); 210 return GET_ITEM(tab, b); 211} 212 213/********************************************************************** 214* %FUNCTION: hash_next_cursor 215* %ARGUMENTS: 216* tab -- a hash table 217* b -- a hash bucket 218* %RETURNS: 219* Cursor value for bucket following b in hash table. 220***********************************************************************/ 221static void * 222hash_next_cursor(hash_table *tab, hash_bucket *b) 223{ 224 unsigned int i; 225 if (!b) return NULL; 226 if (b->next) return b->next; 227 228 i = b->hashval % HASHTAB_SIZE; 229 for (++i; i<HASHTAB_SIZE; ++i) { 230 if (tab->buckets[i]) return tab->buckets[i]; 231 } 232 return NULL; 233} 234 235size_t 236hash_num_entries(hash_table *tab) 237{ 238 return tab->num_entries; 239} 240 241/********************************************************************** 242* %FUNCTION: hash_pjw 243* %ARGUMENTS: 244* str -- a zero-terminated string 245* %RETURNS: 246* A hash value using the hashpjw algorithm 247* %DESCRIPTION: 248* An adaptation of Peter Weinberger's (PJW) generic hashing 249* algorithm based on Allen Holub's version. Accepts a pointer 250* to a datum to be hashed and returns an unsigned integer. 251***********************************************************************/ 252unsigned int 253hash_pjw(char const * str) 254{ 255 unsigned int hash_value, i; 256 257 for (hash_value = 0; *str; ++str) { 258 hash_value = ( hash_value << ONE_EIGHTH ) + *str; 259 if (( i = hash_value & HIGH_BITS ) != 0 ) { 260 hash_value = 261 ( hash_value ^ ( i >> THREE_QUARTERS )) & 262 ~HIGH_BITS; 263 } 264 } 265 return hash_value; 266} 267