2
* fcs_hash.c - an implementation of a simplistic (keys only) hash. This
3
* hash uses chaining and re-hashing and was found to be very fast. Not all
4
* of the functions of the hash ADT are implemented, but it is useful enough
7
* Written by Shlomi Fish (shlomif@vipe.technion.ac.il), 2000
9
* This file is in the public domain (it's uncopyrighted).
14
#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH) || (defined(INDIRECT_STACK_STATES) && (FCS_STACK_STORAGE == FCS_STACK_STORAGE_INTERNAL_HASH))
26
#define NUM_PRIMES 136
29
A list of primes in the range between 256 and 2^31. There
30
are roughly 6 in an x .. 2x decade.
32
static const int primes_list[NUM_PRIMES+1] = {
173
static void SFO_hash_rehash(SFO_hash_t * hash);
177
SFO_hash_t * freecell_solver_hash_init(
178
SFO_hash_value_t wanted_size,
179
int (*compare_function)(const void * key1, const void * key2, void * context),
186
/* Find a prime number that is greater than the initial wanted size */
187
for(i=0;i<NUM_PRIMES;i++)
189
if (primes_list[i] > wanted_size)
195
size = primes_list[i];
197
hash = (SFO_hash_t *)malloc(sizeof(SFO_hash_t));
203
/* Allocate a table of size entries */
204
hash->entries = (SFO_hash_symlink_t *)malloc(
205
sizeof(SFO_hash_symlink_t) * size
208
hash->compare_function = compare_function;
209
hash->context = context;
211
/* Initialize all the cells of the hash table to NULL, which indicate
212
that the cork of the linked list is right at the start */
213
memset(hash->entries, 0, sizeof(SFO_hash_symlink_t)*size);
218
void * freecell_solver_hash_insert(
221
SFO_hash_value_t hash_value,
222
int optimize_for_caching
226
SFO_hash_symlink_t * list;
227
SFO_hash_symlink_item_t * item, * last_item;
229
/* Get the index of the appropriate chain in the hash table */
230
place = hash_value % (hash->size);
232
list = &(hash->entries[place]);
233
/* If first_item is non-existent */
234
if (list->first_item == NULL)
236
/* Allocate a first item with that key */
237
item = list->first_item = (SFO_hash_symlink_item_t *)malloc(sizeof(SFO_hash_symlink_item_t));
240
item->hash_value = hash_value;
245
/* Initialize item to the chain's first_item */
246
item = list->first_item;
252
We first compare the hash values, because it is faster than
253
comparing the entire data structure.
257
(item->hash_value == hash_value) &&
258
(!(hash->compare_function(item->key, key, hash->context)))
261
if (optimize_for_caching)
264
* Place the item in the beginning of the chain.
265
* If last_item == NULL it is already the first item so leave
268
if (last_item != NULL)
270
last_item->next = item->next;
271
item->next = list->first_item;
272
list->first_item = item;
277
/* Cache the item before the current in last_item */
279
/* Move to the next item */
283
if (optimize_for_caching)
285
/* Put the new element at the beginning of the list */
286
item = (SFO_hash_symlink_item_t *)malloc(sizeof(SFO_hash_symlink_item_t));
287
item->next = list->first_item;
289
item->hash_value = hash_value;
290
list->first_item = item;
294
/* Put the new element at the end of the list */
295
item = last_item->next = (SFO_hash_symlink_item_t *)malloc(sizeof(SFO_hash_symlink_item_t));
298
item->hash_value = hash_value;
305
if (hash->num_elems > ((hash->size*3)>>2))
307
SFO_hash_rehash(hash);
313
void freecell_solver_hash_free_with_callback(
315
void (*function_ptr)(void * key, void * context)
319
SFO_hash_symlink_item_t * item, * next_item;
321
for(i=0;i<hash->size;i++)
323
item = hash->entries[i].first_item;
326
function_ptr(item->key, hash->context);
327
next_item = item->next;
339
void freecell_solver_hash_free(
344
SFO_hash_symlink_item_t * item, * next_item;
347
for(i=0;i<hash->size;i++)
349
item = hash->entries[i].first_item;
352
next_item = item->next;
366
This function "rehashes" a hash. I.e: it increases the size of its
367
hash table, allowing for smaller chains, and faster lookup.
370
static void SFO_hash_rehash(
374
int old_size, new_size;
376
SFO_hash_t * new_hash;
377
SFO_hash_symlink_item_t * item, * next_item;
380
old_size = hash->size;
382
/* Allocate a new hash with hash_init() */
383
new_hash = freecell_solver_hash_init(
385
hash->compare_function,
389
new_hash->num_elems = hash->num_elems;
391
old_size = hash->size;
392
new_size = new_hash->size;
394
/* Copy the items to the new hash and deallocate the old ones in the
396
for(i=0;i<old_size;i++)
398
item = hash->entries[i].first_item;
399
/* traverse the chain item by item */
402
/* The place in the new hash table */
403
place = item->hash_value % new_size;
405
/* Store the next item in the linked list in a safe place,
406
so we can retrieve it after the assignment */
407
next_item = item->next;
408
/* It is placed in front of the first element in the chain,
409
so it should link to it */
410
item->next = new_hash->entries[place].first_item;
412
/* Make it the first item in its chain */
413
new_hash->entries[place].first_item = item;
415
/* Move to the next item this one. */
420
/* Free the entries of the old hash */
423
/* Copy the new hash to the old one */
426
/* De-allocate the space that was allocated by new_hash's struct
434
static void freecell_solver_hash_c_dummy(); /* ANSI C doesn't allow empty compilation */
436
#endif /* (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH) || defined(INDIRECT_STACK_STATES) */
added
removed
fcs_hash.c
