#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include <sys/types.h>
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#ifdef HAVE_STRING_H
#include <string.h>
#endif
#include <stdio.h>
#include "libiberty.h"
#include "hashtab.h"
#define EMPTY_ENTRY ((PTR) 0)
#define DELETED_ENTRY ((PTR) 1)
static unsigned long higher_prime_number PARAMS ((unsigned long));
static hashval_t hash_pointer PARAMS ((const void *));
static int eq_pointer PARAMS ((const void *, const void *));
static int htab_expand PARAMS ((htab_t));
static PTR *find_empty_slot_for_expand PARAMS ((htab_t, hashval_t));
htab_hash htab_hash_pointer = hash_pointer;
htab_eq htab_eq_pointer = eq_pointer;
static unsigned long
higher_prime_number (n)
unsigned long n;
{
static const unsigned long primes[] = {
(unsigned long) 7,
(unsigned long) 13,
(unsigned long) 31,
(unsigned long) 61,
(unsigned long) 127,
(unsigned long) 251,
(unsigned long) 509,
(unsigned long) 1021,
(unsigned long) 2039,
(unsigned long) 4093,
(unsigned long) 8191,
(unsigned long) 16381,
(unsigned long) 32749,
(unsigned long) 65521,
(unsigned long) 131071,
(unsigned long) 262139,
(unsigned long) 524287,
(unsigned long) 1048573,
(unsigned long) 2097143,
(unsigned long) 4194301,
(unsigned long) 8388593,
(unsigned long) 16777213,
(unsigned long) 33554393,
(unsigned long) 67108859,
(unsigned long) 134217689,
(unsigned long) 268435399,
(unsigned long) 536870909,
(unsigned long) 1073741789,
(unsigned long) 2147483647,
((unsigned long) 2147483647) + ((unsigned long) 2147483644),
};
const unsigned long *low = &primes[0];
const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
while (low != high)
{
const unsigned long *mid = low + (high - low) / 2;
if (n > *mid)
low = mid + 1;
else
high = mid;
}
if (n > *low)
{
fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
abort ();
}
return *low;
}
static hashval_t
hash_pointer (p)
const PTR p;
{
return (hashval_t) ((long)p >> 3);
}
static int
eq_pointer (p1, p2)
const PTR p1;
const PTR p2;
{
return p1 == p2;
}
htab_t
htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f)
size_t size;
htab_hash hash_f;
htab_eq eq_f;
htab_del del_f;
htab_alloc alloc_f;
htab_free free_f;
{
htab_t result;
size = higher_prime_number (size);
result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
if (result == NULL)
return NULL;
result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
if (result->entries == NULL)
{
if (free_f != NULL)
(*free_f) (result);
return NULL;
}
result->size = size;
result->hash_f = hash_f;
result->eq_f = eq_f;
result->del_f = del_f;
result->alloc_f = alloc_f;
result->free_f = free_f;
return result;
}
#undef htab_create
htab_t
htab_create (size, hash_f, eq_f, del_f)
size_t size;
htab_hash hash_f;
htab_eq eq_f;
htab_del del_f;
{
return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
}
htab_t
htab_try_create (size, hash_f, eq_f, del_f)
size_t size;
htab_hash hash_f;
htab_eq eq_f;
htab_del del_f;
{
return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
}
void
htab_delete (htab)
htab_t htab;
{
int i;
if (htab->del_f)
for (i = htab->size - 1; i >= 0; i--)
if (htab->entries[i] != EMPTY_ENTRY
&& htab->entries[i] != DELETED_ENTRY)
(*htab->del_f) (htab->entries[i]);
if (htab->free_f != NULL)
{
(*htab->free_f) (htab->entries);
(*htab->free_f) (htab);
}
}
void
htab_empty (htab)
htab_t htab;
{
int i;
if (htab->del_f)
for (i = htab->size - 1; i >= 0; i--)
if (htab->entries[i] != EMPTY_ENTRY
&& htab->entries[i] != DELETED_ENTRY)
(*htab->del_f) (htab->entries[i]);
memset (htab->entries, 0, htab->size * sizeof (PTR));
}
static PTR *
find_empty_slot_for_expand (htab, hash)
htab_t htab;
hashval_t hash;
{
size_t size = htab->size;
unsigned int index = hash % size;
PTR *slot = htab->entries + index;
hashval_t hash2;
if (*slot == EMPTY_ENTRY)
return slot;
else if (*slot == DELETED_ENTRY)
abort ();
hash2 = 1 + hash % (size - 2);
for (;;)
{
index += hash2;
if (index >= size)
index -= size;
slot = htab->entries + index;
if (*slot == EMPTY_ENTRY)
return slot;
else if (*slot == DELETED_ENTRY)
abort ();
}
}
static int
htab_expand (htab)
htab_t htab;
{
PTR *oentries;
PTR *olimit;
PTR *p;
PTR *nentries;
oentries = htab->entries;
olimit = oentries + htab->size;
htab->size = higher_prime_number (htab->size * 2);
nentries = (PTR *) (*htab->alloc_f) (htab->size, sizeof (PTR *));
if (nentries == NULL)
return 0;
htab->entries = nentries;
htab->n_elements -= htab->n_deleted;
htab->n_deleted = 0;
p = oentries;
do
{
PTR x = *p;
if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
{
PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
*q = x;
}
p++;
}
while (p < olimit);
if (htab->free_f != NULL)
(*htab->free_f) (oentries);
return 1;
}
PTR
htab_find_with_hash (htab, element, hash)
htab_t htab;
const PTR element;
hashval_t hash;
{
unsigned int index;
hashval_t hash2;
size_t size;
PTR entry;
htab->searches++;
size = htab->size;
index = hash % size;
entry = htab->entries[index];
if (entry == EMPTY_ENTRY
|| (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
return entry;
hash2 = 1 + hash % (size - 2);
for (;;)
{
htab->collisions++;
index += hash2;
if (index >= size)
index -= size;
entry = htab->entries[index];
if (entry == EMPTY_ENTRY
|| (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
return entry;
}
}
PTR
htab_find (htab, element)
htab_t htab;
const PTR element;
{
return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
}
PTR *
htab_find_slot_with_hash (htab, element, hash, insert)
htab_t htab;
const PTR element;
hashval_t hash;
enum insert_option insert;
{
PTR *first_deleted_slot;
unsigned int index;
hashval_t hash2;
size_t size;
PTR entry;
if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
&& htab_expand (htab) == 0)
return NULL;
size = htab->size;
index = hash % size;
htab->searches++;
first_deleted_slot = NULL;
entry = htab->entries[index];
if (entry == EMPTY_ENTRY)
goto empty_entry;
else if (entry == DELETED_ENTRY)
first_deleted_slot = &htab->entries[index];
else if ((*htab->eq_f) (entry, element))
return &htab->entries[index];
hash2 = 1 + hash % (size - 2);
for (;;)
{
htab->collisions++;
index += hash2;
if (index >= size)
index -= size;
entry = htab->entries[index];
if (entry == EMPTY_ENTRY)
goto empty_entry;
else if (entry == DELETED_ENTRY)
{
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
else if ((*htab->eq_f) (entry, element))
return &htab->entries[index];
}
empty_entry:
if (insert == NO_INSERT)
return NULL;
htab->n_elements++;
if (first_deleted_slot)
{
*first_deleted_slot = EMPTY_ENTRY;
return first_deleted_slot;
}
return &htab->entries[index];
}
PTR *
htab_find_slot (htab, element, insert)
htab_t htab;
const PTR element;
enum insert_option insert;
{
return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
insert);
}
void
htab_remove_elt (htab, element)
htab_t htab;
PTR element;
{
PTR *slot;
slot = htab_find_slot (htab, element, NO_INSERT);
if (*slot == EMPTY_ENTRY)
return;
if (htab->del_f)
(*htab->del_f) (*slot);
*slot = DELETED_ENTRY;
htab->n_deleted++;
}
void
htab_clear_slot (htab, slot)
htab_t htab;
PTR *slot;
{
if (slot < htab->entries || slot >= htab->entries + htab->size
|| *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
abort ();
if (htab->del_f)
(*htab->del_f) (*slot);
*slot = DELETED_ENTRY;
htab->n_deleted++;
}
void
htab_traverse (htab, callback, info)
htab_t htab;
htab_trav callback;
PTR info;
{
PTR *slot = htab->entries;
PTR *limit = slot + htab->size;
do
{
PTR x = *slot;
if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
if (!(*callback) (slot, info))
break;
}
while (++slot < limit);
}
size_t
htab_size (htab)
htab_t htab;
{
return htab->size;
}
size_t
htab_elements (htab)
htab_t htab;
{
return htab->n_elements - htab->n_deleted;
}
double
htab_collisions (htab)
htab_t htab;
{
if (htab->searches == 0)
return 0.0;
return (double) htab->collisions / (double) htab->searches;
}
hashval_t
htab_hash_string (p)
const PTR p;
{
const unsigned char *str = (const unsigned char *) p;
hashval_t r = 0;
unsigned char c;
while ((c = *str++) != 0)
r = r * 67 + c - 113;
return r;
}