#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;
{
unsigned long i;
n++;
n |= 0x01;
if (n < 9)
return n;
next:
for (i = 3; i * i <= n; i += 2)
if (n % i == 0)
{
n += 2;
goto next;
}
return n;
}
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 (size, hash_f, eq_f, del_f)
size_t size;
htab_hash hash_f;
htab_eq eq_f;
htab_del del_f;
{
htab_t result;
size = higher_prime_number (size);
result = (htab_t) xcalloc (1, sizeof (struct htab));
result->entries = (PTR *) xcalloc (size, sizeof (PTR));
result->size = size;
result->hash_f = hash_f;
result->eq_f = eq_f;
result->del_f = del_f;
result->return_allocation_failure = 0;
return result;
}
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;
{
htab_t result;
size = higher_prime_number (size);
result = (htab_t) calloc (1, sizeof (struct htab));
if (result == NULL)
return NULL;
result->entries = (PTR *) calloc (size, sizeof (PTR));
if (result->entries == NULL)
{
free (result);
return NULL;
}
result->size = size;
result->hash_f = hash_f;
result->eq_f = eq_f;
result->del_f = del_f;
result->return_allocation_failure = 1;
return result;
}
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]);
free (htab->entries);
free (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;
hashval_t hash2 = 1 + hash % (size - 2);
unsigned int index = hash % size;
for (;;)
{
PTR *slot = htab->entries + index;
if (*slot == EMPTY_ENTRY)
return slot;
else if (*slot == DELETED_ENTRY)
abort ();
index += hash2;
if (index >= size)
index -= size;
}
}
static int
htab_expand (htab)
htab_t htab;
{
PTR *oentries;
PTR *olimit;
PTR *p;
oentries = htab->entries;
olimit = oentries + htab->size;
htab->size = higher_prime_number (htab->size * 2);
if (htab->return_allocation_failure)
{
PTR *nentries = (PTR *) calloc (htab->size, sizeof (PTR *));
if (nentries == NULL)
return 0;
htab->entries = nentries;
}
else
htab->entries = (PTR *) xcalloc (htab->size, sizeof (PTR *));
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);
free (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;
if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
&& htab_expand (htab) == 0)
return NULL;
size = htab->size;
hash2 = 1 + hash % (size - 2);
index = hash % size;
htab->searches++;
first_deleted_slot = NULL;
for (;;)
{
PTR entry = htab->entries[index];
if (entry == 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];
}
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];
htab->collisions++;
index += hash2;
if (index >= size)
index -= size;
}
}
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;
}