#if HAVE_CONFIG_H
# include <config.h>
#endif
#if HAVE_STDLIB_H
# include <stdlib.h>
#endif
#if HAVE_STDBOOL_H
# include <stdbool.h>
#else
typedef enum {false = 0, true = 1} bool;
#endif
#include <stdio.h>
#include <assert.h>
#ifndef HAVE_DECL_FREE
"this configure-time declaration test was not run"
#endif
#if !HAVE_DECL_FREE
void free ();
#endif
#ifndef HAVE_DECL_MALLOC
"this configure-time declaration test was not run"
#endif
#if !HAVE_DECL_MALLOC
char *malloc ();
#endif
#if USE_OBSTACK
# include "obstack.h"
# ifndef obstack_chunk_alloc
# define obstack_chunk_alloc malloc
# endif
# ifndef obstack_chunk_free
# define obstack_chunk_free free
# endif
#endif
#include "hash.h"
#define DEFAULT_GROWTH_THRESHOLD 0.8
#define DEFAULT_GROWTH_FACTOR 1.414
#define DEFAULT_SHRINK_THRESHOLD 0.0
#define DEFAULT_SHRINK_FACTOR 1.0
static const Hash_tuning default_tuning =
{
DEFAULT_SHRINK_THRESHOLD,
DEFAULT_SHRINK_FACTOR,
DEFAULT_GROWTH_THRESHOLD,
DEFAULT_GROWTH_FACTOR,
false
};
unsigned
hash_get_n_buckets (const Hash_table *table)
{
return table->n_buckets;
}
unsigned
hash_get_n_buckets_used (const Hash_table *table)
{
return table->n_buckets_used;
}
unsigned
hash_get_n_entries (const Hash_table *table)
{
return table->n_entries;
}
unsigned
hash_get_max_bucket_length (const Hash_table *table)
{
struct hash_entry *bucket;
unsigned max_bucket_length = 0;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (bucket->data)
{
struct hash_entry *cursor = bucket;
unsigned bucket_length = 1;
while (cursor = cursor->next, cursor)
bucket_length++;
if (bucket_length > max_bucket_length)
max_bucket_length = bucket_length;
}
}
return max_bucket_length;
}
bool
hash_table_ok (const Hash_table *table)
{
struct hash_entry *bucket;
unsigned n_buckets_used = 0;
unsigned n_entries = 0;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (bucket->data)
{
struct hash_entry *cursor = bucket;
n_buckets_used++;
n_entries++;
while (cursor = cursor->next, cursor)
n_entries++;
}
}
if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
return true;
return false;
}
void
hash_print_statistics (const Hash_table *table, FILE *stream)
{
unsigned n_entries = hash_get_n_entries (table);
unsigned n_buckets = hash_get_n_buckets (table);
unsigned n_buckets_used = hash_get_n_buckets_used (table);
unsigned max_bucket_length = hash_get_max_bucket_length (table);
fprintf (stream, "# entries: %u\n", n_entries);
fprintf (stream, "# buckets: %u\n", n_buckets);
fprintf (stream, "# buckets used: %u (%.2f%%)\n", n_buckets_used,
(100.0 * n_buckets_used) / n_buckets);
fprintf (stream, "max bucket length: %u\n", max_bucket_length);
}
void *
hash_lookup (const Hash_table *table, const void *entry)
{
struct hash_entry *bucket
= table->bucket + table->hasher (entry, table->n_buckets);
struct hash_entry *cursor;
assert (bucket < table->bucket_limit);
if (bucket->data == NULL)
return NULL;
for (cursor = bucket; cursor; cursor = cursor->next)
if (table->comparator (entry, cursor->data))
return cursor->data;
return NULL;
}
void *
hash_get_first (const Hash_table *table)
{
struct hash_entry *bucket;
if (table->n_entries == 0)
return NULL;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
if (bucket->data)
return bucket->data;
assert (0);
return NULL;
}
void *
hash_get_next (const Hash_table *table, const void *entry)
{
struct hash_entry *bucket
= table->bucket + table->hasher (entry, table->n_buckets);
struct hash_entry *cursor;
assert (bucket < table->bucket_limit);
for (cursor = bucket; cursor; cursor = cursor->next)
if (cursor->data == entry && cursor->next)
return cursor->next->data;
while (++bucket < table->bucket_limit)
if (bucket->data)
return bucket->data;
return NULL;
}
unsigned
hash_get_entries (const Hash_table *table, void **buffer,
unsigned buffer_size)
{
unsigned counter = 0;
struct hash_entry *bucket;
struct hash_entry *cursor;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (bucket->data)
{
for (cursor = bucket; cursor; cursor = cursor->next)
{
if (counter >= buffer_size)
return counter;
buffer[counter++] = cursor->data;
}
}
}
return counter;
}
unsigned
hash_do_for_each (const Hash_table *table, Hash_processor processor,
void *processor_data)
{
unsigned counter = 0;
struct hash_entry *bucket;
struct hash_entry *cursor;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (bucket->data)
{
for (cursor = bucket; cursor; cursor = cursor->next)
{
if (!(*processor) (cursor->data, processor_data))
return counter;
counter++;
}
}
}
return counter;
}
#if USE_DIFF_HASH
unsigned
hash_string (const char *string, unsigned n_buckets)
{
# ifndef CHAR_BIT
# define CHAR_BIT 8
# endif
# define ROTATE_LEFT(Value, Shift) \
((Value) << (Shift) | (Value) >> ((sizeof (unsigned) * CHAR_BIT) - (Shift)))
# define HASH_ONE_CHAR(Value, Byte) \
((Byte) + ROTATE_LEFT (Value, 7))
unsigned value = 0;
for (; *string; string++)
value = HASH_ONE_CHAR (value, *(const unsigned char *) string);
return value % n_buckets;
# undef ROTATE_LEFT
# undef HASH_ONE_CHAR
}
#else
unsigned
hash_string (const char *string, unsigned n_buckets)
{
unsigned value = 0;
while (*string)
value = ((value * 31 + (int) *(const unsigned char *) string++)
% n_buckets);
return value;
}
#endif
static bool
is_prime (unsigned long candidate)
{
unsigned long divisor = 3;
unsigned long square = divisor * divisor;
while (square < candidate && (candidate % divisor))
{
divisor++;
square += 4 * divisor;
divisor++;
}
return (candidate % divisor ? true : false);
}
static unsigned long
next_prime (unsigned long candidate)
{
if (candidate < 10)
candidate = 10;
candidate |= 1;
while (!is_prime (candidate))
candidate += 2;
return candidate;
}
void
hash_reset_tuning (Hash_tuning *tuning)
{
*tuning = default_tuning;
}
static bool
check_tuning (Hash_table *table)
{
const Hash_tuning *tuning = table->tuning;
if (tuning->growth_threshold > 0.0
&& tuning->growth_threshold < 1.0
&& tuning->growth_factor > 1.0
&& tuning->shrink_threshold >= 0.0
&& tuning->shrink_threshold < 1.0
&& tuning->shrink_factor > tuning->shrink_threshold
&& tuning->shrink_factor <= 1.0
&& tuning->shrink_threshold < tuning->growth_threshold)
return true;
table->tuning = &default_tuning;
return false;
}
Hash_table *
hash_initialize (unsigned candidate, const Hash_tuning *tuning,
Hash_hasher hasher, Hash_comparator comparator,
Hash_data_freer data_freer)
{
Hash_table *table;
struct hash_entry *bucket;
if (hasher == NULL || comparator == NULL)
return NULL;
table = (Hash_table *) malloc (sizeof (Hash_table));
if (table == NULL)
return NULL;
if (!tuning)
tuning = &default_tuning;
table->tuning = tuning;
if (!check_tuning (table))
{
free (table);
return NULL;
}
table->n_buckets
= next_prime (tuning->is_n_buckets ? candidate
: (unsigned) (candidate / tuning->growth_threshold));
table->bucket = (struct hash_entry *)
malloc (table->n_buckets * sizeof (struct hash_entry));
if (table->bucket == NULL)
{
free (table);
return NULL;
}
table->bucket_limit = table->bucket + table->n_buckets;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
bucket->data = NULL;
bucket->next = NULL;
}
table->n_buckets_used = 0;
table->n_entries = 0;
table->hasher = hasher;
table->comparator = comparator;
table->data_freer = data_freer;
table->free_entry_list = NULL;
#if USE_OBSTACK
obstack_init (&table->entry_stack);
#endif
return table;
}
void
hash_clear (Hash_table *table)
{
struct hash_entry *bucket;
struct hash_entry *cursor;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (bucket->data)
{
for (cursor = bucket->next; cursor; cursor = cursor->next)
{
if (table->data_freer)
(*table->data_freer) (cursor->data);
cursor->data = NULL;
cursor->next = table->free_entry_list;
table->free_entry_list = cursor;
}
if (table->data_freer)
(*table->data_freer) (bucket->data);
bucket->data = NULL;
bucket->next = NULL;
}
}
table->n_buckets_used = 0;
table->n_entries = 0;
}
void
hash_free (Hash_table *table)
{
struct hash_entry *bucket;
struct hash_entry *cursor;
struct hash_entry *next;
if (table->data_freer && table->n_entries)
{
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (bucket->data)
{
for (cursor = bucket; cursor; cursor = cursor->next)
{
(*table->data_freer) (cursor->data);
}
}
}
}
#if USE_OBSTACK
obstack_free (&table->entry_stack, NULL);
#else
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
for (cursor = bucket->next; cursor; cursor = next)
{
next = cursor->next;
free (cursor);
}
}
for (cursor = table->free_entry_list; cursor; cursor = next)
{
next = cursor->next;
free (cursor);
}
#endif
free (table->bucket);
free (table);
}
static struct hash_entry *
allocate_entry (Hash_table *table)
{
struct hash_entry *new;
if (table->free_entry_list)
{
new = table->free_entry_list;
table->free_entry_list = new->next;
}
else
{
#if USE_OBSTACK
new = (struct hash_entry *)
obstack_alloc (&table->entry_stack, sizeof (struct hash_entry));
#else
new = (struct hash_entry *) malloc (sizeof (struct hash_entry));
#endif
}
return new;
}
static void
free_entry (Hash_table *table, struct hash_entry *entry)
{
entry->data = NULL;
entry->next = table->free_entry_list;
table->free_entry_list = entry;
}
static void *
hash_find_entry (Hash_table *table, const void *entry,
struct hash_entry **bucket_head, bool delete)
{
struct hash_entry *bucket
= table->bucket + table->hasher (entry, table->n_buckets);
struct hash_entry *cursor;
assert (bucket < table->bucket_limit);
*bucket_head = bucket;
if (bucket->data == NULL)
return NULL;
if ((*table->comparator) (entry, bucket->data))
{
void *data = bucket->data;
if (delete)
{
if (bucket->next)
{
struct hash_entry *next = bucket->next;
*bucket = *next;
free_entry (table, next);
}
else
{
bucket->data = NULL;
}
}
return data;
}
for (cursor = bucket; cursor->next; cursor = cursor->next)
{
if ((*table->comparator) (entry, cursor->next->data))
{
void *data = cursor->next->data;
if (delete)
{
struct hash_entry *next = cursor->next;
cursor->next = next->next;
free_entry (table, next);
}
return data;
}
}
return NULL;
}
bool
hash_rehash (Hash_table *table, unsigned candidate)
{
Hash_table *new_table;
struct hash_entry *bucket;
struct hash_entry *cursor;
struct hash_entry *next;
new_table = hash_initialize (candidate, table->tuning, table->hasher,
table->comparator, table->data_freer);
if (new_table == NULL)
return false;
#if USE_OBSTACK
obstack_free (&new_table->entry_stack, NULL);
new_table->entry_stack = table->entry_stack;
#endif
new_table->free_entry_list = table->free_entry_list;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
if (bucket->data)
for (cursor = bucket; cursor; cursor = next)
{
void *data = cursor->data;
struct hash_entry *new_bucket
= (new_table->bucket
+ new_table->hasher (data, new_table->n_buckets));
assert (new_bucket < new_table->bucket_limit);
next = cursor->next;
if (new_bucket->data)
{
if (cursor == bucket)
{
struct hash_entry *new_entry = allocate_entry (new_table);
if (new_entry == NULL)
return false;
new_entry->data = data;
new_entry->next = new_bucket->next;
new_bucket->next = new_entry;
}
else
{
cursor->next = new_bucket->next;
new_bucket->next = cursor;
}
}
else
{
new_bucket->data = data;
new_table->n_buckets_used++;
if (cursor != bucket)
free_entry (new_table, cursor);
}
}
free (table->bucket);
table->bucket = new_table->bucket;
table->bucket_limit = new_table->bucket_limit;
table->n_buckets = new_table->n_buckets;
table->n_buckets_used = new_table->n_buckets_used;
table->free_entry_list = new_table->free_entry_list;
#if USE_OBSTACK
table->entry_stack = new_table->entry_stack;
#endif
free (new_table);
return true;
}
void *
hash_insert (Hash_table *table, const void *entry)
{
void *data;
struct hash_entry *bucket;
assert (entry);
if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
return data;
if (bucket->data)
{
struct hash_entry *new_entry = allocate_entry (table);
if (new_entry == NULL)
return NULL;
new_entry->data = (void *) entry;
new_entry->next = bucket->next;
bucket->next = new_entry;
table->n_entries++;
return (void *) entry;
}
bucket->data = (void *) entry;
table->n_entries++;
table->n_buckets_used++;
if (table->n_buckets_used
> table->tuning->growth_threshold * table->n_buckets)
{
check_tuning (table);
if (table->n_buckets_used
> table->tuning->growth_threshold * table->n_buckets)
{
const Hash_tuning *tuning = table->tuning;
unsigned candidate
= (unsigned) (tuning->is_n_buckets
? (table->n_buckets * tuning->growth_factor)
: (table->n_buckets * tuning->growth_factor
* tuning->growth_threshold));
if (!hash_rehash (table, candidate))
entry = NULL;
}
}
return (void *) entry;
}
void *
hash_delete (Hash_table *table, const void *entry)
{
void *data;
struct hash_entry *bucket;
data = hash_find_entry (table, entry, &bucket, true);
if (!data)
return NULL;
table->n_entries--;
if (!bucket->data)
{
table->n_buckets_used--;
if (table->n_buckets_used
< table->tuning->shrink_threshold * table->n_buckets)
{
check_tuning (table);
if (table->n_buckets_used
< table->tuning->shrink_threshold * table->n_buckets)
{
const Hash_tuning *tuning = table->tuning;
unsigned candidate
= (unsigned) (tuning->is_n_buckets
? table->n_buckets * tuning->shrink_factor
: (table->n_buckets * tuning->shrink_factor
* tuning->growth_threshold));
hash_rehash (table, candidate);
}
}
}
return data;
}
#if TESTING
void
hash_print (const Hash_table *table)
{
struct hash_entry *bucket;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
struct hash_entry *cursor;
if (bucket)
printf ("%d:\n", slot);
for (cursor = bucket; cursor; cursor = cursor->next)
{
char *s = (char *) cursor->data;
printf (" %s\n", s);
}
}
}
#endif