Back to index

cell-binutils  2.17cvs20070401
Classes | Defines | Functions | Variables
hashtab.c File Reference
#include <sys/types.h>
#include <stdio.h>
#include "libiberty.h"
#include "ansidecl.h"
#include "hashtab.h"

Go to the source code of this file.

Classes

struct  prime_ent

Defines

#define CHAR_BIT   8
#define htab_size(htab)   ((htab)->size)
#define htab_elements(htab)   ((htab)->n_elements - (htab)->n_deleted)
#define mix(a, b, c)

Functions

static unsigned int higher_prime_index (unsigned long)
static hashval_t htab_mod_1 (hashval_t, hashval_t, hashval_t, int)
static hashval_t htab_mod (hashval_t, htab_t)
static hashval_t htab_mod_m2 (hashval_t, htab_t)
static hashval_t hash_pointer (const void *)
static int eq_pointer (const void *, const void *)
static int htab_expand (htab_t)
static PTRfind_empty_slot_for_expand (htab_t, hashval_t)
static hashval_t hash_pointer (const PTR p)
static int eq_pointer (const PTR p1, const PTR p2)
size_t() htab_size (htab_t htab)
size_t() htab_elements (htab_t htab)
htab_t htab_create_alloc (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 htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f, void *alloc_arg, htab_alloc_with_arg alloc_f, htab_free_with_arg free_f)
void htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f, htab_del del_f, PTR alloc_arg, htab_alloc_with_arg alloc_f, htab_free_with_arg free_f)
htab_t htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
htab_t htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
void htab_delete (htab_t htab)
void htab_empty (htab_t htab)
PTR htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
PTR htab_find (htab_t htab, const PTR element)
PTRhtab_find_slot_with_hash (htab_t htab, const PTR element, hashval_t hash, enum insert_option insert)
PTRhtab_find_slot (htab_t htab, const PTR element, enum insert_option insert)
void htab_remove_elt (htab_t htab, PTR element)
void htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
void htab_clear_slot (htab_t htab, PTR *slot)
void htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
void htab_traverse (htab_t htab, htab_trav callback, PTR info)
double htab_collisions (htab_t htab)
hashval_t htab_hash_string (const PTR p)
hashval_t iterative_hash (const PTR k_in, register size_t length, register hashval_t initval)

Variables

htab_hash htab_hash_pointer = hash_pointer
htab_eq htab_eq_pointer = eq_pointer
static struct prime_ent []

Class Documentation

struct prime_ent

Definition at line 124 of file hashtab.c.

Class Members
hashval_t inv
hashval_t inv_m2
hashval_t prime
hashval_t shift

Define Documentation

#define CHAR_BIT   8

Definition at line 64 of file hashtab.c.

#define htab_elements (   htab)    ((htab)->n_elements - (htab)->n_deleted)

Definition at line 228 of file hashtab.c.

#define htab_size (   htab)    ((htab)->size)

Definition at line 218 of file hashtab.c.

#define mix (   a,
  b,
  c 
)
Value:
{ \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<< 8); \
  c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
  a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
  b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
  c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
  a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
  b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
  c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
}

Definition at line 854 of file hashtab.c.


Function Documentation

static int eq_pointer ( const void *  ,
const void *   
) [static]
static int eq_pointer ( const PTR  p1,
const PTR  p2 
) [static]

Definition at line 205 of file hashtab.c.

{
  return p1 == p2;
}
static PTR * find_empty_slot_for_expand ( htab_t  htab,
hashval_t  hash 
) [static]

Definition at line 456 of file hashtab.c.

{
  hashval_t index = htab_mod (hash, htab);
  size_t size = htab_size (htab);
  PTR *slot = htab->entries + index;
  hashval_t hash2;

  if (*slot == HTAB_EMPTY_ENTRY)
    return slot;
  else if (*slot == HTAB_DELETED_ENTRY)
    abort ();

  hash2 = htab_mod_m2 (hash, htab);
  for (;;)
    {
      index += hash2;
      if (index >= size)
       index -= size;

      slot = htab->entries + index;
      if (*slot == HTAB_EMPTY_ENTRY)
       return slot;
      else if (*slot == HTAB_DELETED_ENTRY)
       abort ();
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static hashval_t hash_pointer ( const void *  ) [static]
static hashval_t hash_pointer ( const PTR  p) [static]

Definition at line 197 of file hashtab.c.

{
  return (hashval_t) ((long)p >> 3);
}
static unsigned int higher_prime_index ( unsigned long  n) [static]

Definition at line 170 of file hashtab.c.

{
  unsigned int low = 0;
  unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);

  while (low != high)
    {
      unsigned int mid = low + (high - low) / 2;
      if (n > prime_tab[mid].prime)
       low = mid + 1;
      else
       high = mid;
    }

  /* If we've run out of primes, abort.  */
  if (n > prime_tab[low].prime)
    {
      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
      abort ();
    }

  return low;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void htab_clear_slot ( htab_t  htab,
PTR slot 
)

Definition at line 718 of file hashtab.c.

{
  if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
      || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
    abort ();

  if (htab->del_f)
    (*htab->del_f) (*slot);

  *slot = HTAB_DELETED_ENTRY;
  htab->n_deleted++;
}

Definition at line 772 of file hashtab.c.

{
  if (htab->searches == 0)
    return 0.0;

  return (double) htab->collisions / (double) htab->searches;
}
htab_t htab_create ( size_t  size,
htab_hash  hash_f,
htab_eq  eq_f,
htab_del  del_f 
)

Definition at line 372 of file hashtab.c.

{
  return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
}

Here is the call graph for this function:

Here is the caller graph for this function:

htab_t htab_create_alloc ( size_t  size,
htab_hash  hash_f,
htab_eq  eq_f,
htab_del  del_f,
htab_alloc  alloc_f,
htab_free  free_f 
)

Definition at line 288 of file hashtab.c.

{
  htab_t result;
  unsigned int size_prime_index;

  size_prime_index = higher_prime_index (size);
  size = prime_tab[size_prime_index].prime;

  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->size_prime_index = size_prime_index;
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

htab_t htab_create_alloc_ex ( size_t  size,
htab_hash  hash_f,
htab_eq  eq_f,
htab_del  del_f,
void *  alloc_arg,
htab_alloc_with_arg  alloc_f,
htab_free_with_arg  free_f 
)

Definition at line 321 of file hashtab.c.

{
  htab_t result;
  unsigned int size_prime_index;

  size_prime_index = higher_prime_index (size);
  size = prime_tab[size_prime_index].prime;

  result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
  if (result == NULL)
    return NULL;
  result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
  if (result->entries == NULL)
    {
      if (free_f != NULL)
       (*free_f) (alloc_arg, result);
      return NULL;
    }
  result->size = size;
  result->size_prime_index = size_prime_index;
  result->hash_f = hash_f;
  result->eq_f = eq_f;
  result->del_f = del_f;
  result->alloc_arg = alloc_arg;
  result->alloc_with_arg_f = alloc_f;
  result->free_with_arg_f = free_f;
  return result;
}

Here is the call graph for this function:

void htab_delete ( htab_t  htab)

Definition at line 387 of file hashtab.c.

{
  size_t size = htab_size (htab);
  PTR *entries = htab->entries;
  int i;

  if (htab->del_f)
    for (i = size - 1; i >= 0; i--)
      if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
       (*htab->del_f) (entries[i]);

  if (htab->free_f != NULL)
    {
      (*htab->free_f) (entries);
      (*htab->free_f) (htab);
    }
  else if (htab->free_with_arg_f != NULL)
    {
      (*htab->free_with_arg_f) (htab->alloc_arg, entries);
      (*htab->free_with_arg_f) (htab->alloc_arg, htab);
    }
}

Here is the caller graph for this function:

Definition at line 231 of file hashtab.c.

{
  return htab_elements (htab);
}
void htab_empty ( htab_t  htab)

Definition at line 413 of file hashtab.c.

{
  size_t size = htab_size (htab);
  PTR *entries = htab->entries;
  int i;

  if (htab->del_f)
    for (i = size - 1; i >= 0; i--)
      if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
       (*htab->del_f) (entries[i]);

  /* Instead of clearing megabyte, downsize the table.  */
  if (size > 1024*1024 / sizeof (PTR))
    {
      int nindex = higher_prime_index (1024 / sizeof (PTR));
      int nsize = prime_tab[nindex].prime;

      if (htab->free_f != NULL)
       (*htab->free_f) (htab->entries);
      else if (htab->free_with_arg_f != NULL)
       (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
      if (htab->alloc_with_arg_f != NULL)
       htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
                                                     sizeof (PTR *));
      else
       htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
     htab->size = nsize;
     htab->size_prime_index = nindex;
    }
  else
    memset (entries, 0, size * sizeof (PTR));
  htab->n_deleted = 0;
  htab->n_elements = 0;
}

Here is the call graph for this function:

static int htab_expand ( htab_t  htab) [static]

Definition at line 492 of file hashtab.c.

{
  PTR *oentries;
  PTR *olimit;
  PTR *p;
  PTR *nentries;
  size_t nsize, osize, elts;
  unsigned int oindex, nindex;

  oentries = htab->entries;
  oindex = htab->size_prime_index;
  osize = htab->size;
  olimit = oentries + osize;
  elts = htab_elements (htab);

  /* Resize only when table after removal of unused elements is either
     too full or too empty.  */
  if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
    {
      nindex = higher_prime_index (elts * 2);
      nsize = prime_tab[nindex].prime;
    }
  else
    {
      nindex = oindex;
      nsize = osize;
    }

  if (htab->alloc_with_arg_f != NULL)
    nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
                                            sizeof (PTR *));
  else
    nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
  if (nentries == NULL)
    return 0;
  htab->entries = nentries;
  htab->size = nsize;
  htab->size_prime_index = nindex;
  htab->n_elements -= htab->n_deleted;
  htab->n_deleted = 0;

  p = oentries;
  do
    {
      PTR x = *p;

      if (x != HTAB_EMPTY_ENTRY && x != HTAB_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);
  else if (htab->free_with_arg_f != NULL)
    (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
  return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PTR htab_find ( htab_t  htab,
const PTR  element 
)

Definition at line 594 of file hashtab.c.

{
  return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
}

Here is the call graph for this function:

PTR* htab_find_slot ( htab_t  htab,
const PTR  element,
enum insert_option  insert 
)

Definition at line 676 of file hashtab.c.

{
  return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
                               insert);
}

Here is the call graph for this function:

PTR* htab_find_slot_with_hash ( htab_t  htab,
const PTR  element,
hashval_t  hash,
enum insert_option  insert 
)

Definition at line 608 of file hashtab.c.

{
  PTR *first_deleted_slot;
  hashval_t index, hash2;
  size_t size;
  PTR entry;

  size = htab_size (htab);
  if (insert == INSERT && size * 3 <= htab->n_elements * 4)
    {
      if (htab_expand (htab) == 0)
       return NULL;
      size = htab_size (htab);
    }

  index = htab_mod (hash, htab);

  htab->searches++;
  first_deleted_slot = NULL;

  entry = htab->entries[index];
  if (entry == HTAB_EMPTY_ENTRY)
    goto empty_entry;
  else if (entry == HTAB_DELETED_ENTRY)
    first_deleted_slot = &htab->entries[index];
  else if ((*htab->eq_f) (entry, element))
    return &htab->entries[index];
      
  hash2 = htab_mod_m2 (hash, htab);
  for (;;)
    {
      htab->collisions++;
      index += hash2;
      if (index >= size)
       index -= size;
      
      entry = htab->entries[index];
      if (entry == HTAB_EMPTY_ENTRY)
       goto empty_entry;
      else if (entry == HTAB_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;

  if (first_deleted_slot)
    {
      htab->n_deleted--;
      *first_deleted_slot = HTAB_EMPTY_ENTRY;
      return first_deleted_slot;
    }

  htab->n_elements++;
  return &htab->entries[index];
}

Here is the call graph for this function:

PTR htab_find_with_hash ( htab_t  htab,
const PTR  element,
hashval_t  hash 
)

Definition at line 560 of file hashtab.c.

{
  hashval_t index, hash2;
  size_t size;
  PTR entry;

  htab->searches++;
  size = htab_size (htab);
  index = htab_mod (hash, htab);

  entry = htab->entries[index];
  if (entry == HTAB_EMPTY_ENTRY
      || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
    return entry;

  hash2 = htab_mod_m2 (hash, htab);
  for (;;)
    {
      htab->collisions++;
      index += hash2;
      if (index >= size)
       index -= size;

      entry = htab->entries[index];
      if (entry == HTAB_EMPTY_ENTRY
         || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
       return entry;
    }
}

Here is the call graph for this function:

Definition at line 806 of file hashtab.c.

{
  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;
}
static hashval_t htab_mod ( hashval_t  hash,
htab_t  htab 
) [inline, static]

Definition at line 267 of file hashtab.c.

{
  const struct prime_ent *p = &prime_tab[htab->size_prime_index];
  return htab_mod_1 (hash, p->prime, p->inv, p->shift);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static hashval_t htab_mod_1 ( hashval_t  x,
hashval_t  y,
hashval_t  inv,
int  shift 
) [inline, static]

Definition at line 239 of file hashtab.c.

{
  /* The multiplicative inverses computed above are for 32-bit types, and
     requires that we be able to compute a highpart multiply.  */
#ifdef UNSIGNED_64BIT_TYPE
  __extension__ typedef UNSIGNED_64BIT_TYPE ull;
  if (sizeof (hashval_t) * CHAR_BIT <= 32)
    {
      hashval_t t1, t2, t3, t4, q, r;

      t1 = ((ull)x * inv) >> 32;
      t2 = x - t1;
      t3 = t2 >> 1;
      t4 = t1 + t3;
      q  = t4 >> shift;
      r  = x - (q * y);

      return r;
    }
#endif

  /* Otherwise just use the native division routines.  */
  return x % y;
}

Here is the caller graph for this function:

static hashval_t htab_mod_m2 ( hashval_t  hash,
htab_t  htab 
) [inline, static]

Definition at line 276 of file hashtab.c.

{
  const struct prime_ent *p = &prime_tab[htab->size_prime_index];
  return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void htab_remove_elt ( htab_t  htab,
PTR  element 
)

Definition at line 687 of file hashtab.c.

{
  htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
}

Here is the call graph for this function:

void htab_remove_elt_with_hash ( htab_t  htab,
PTR  element,
hashval_t  hash 
)

Definition at line 698 of file hashtab.c.

{
  PTR *slot;

  slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
  if (*slot == HTAB_EMPTY_ENTRY)
    return;

  if (htab->del_f)
    (*htab->del_f) (*slot);

  *slot = HTAB_DELETED_ENTRY;
  htab->n_deleted++;
}

Here is the call graph for this function:

void htab_set_functions_ex ( htab_t  htab,
htab_hash  hash_f,
htab_eq  eq_f,
htab_del  del_f,
PTR  alloc_arg,
htab_alloc_with_arg  alloc_f,
htab_free_with_arg  free_f 
)

Definition at line 356 of file hashtab.c.

{
  htab->hash_f = hash_f;
  htab->eq_f = eq_f;
  htab->del_f = del_f;
  htab->alloc_arg = alloc_arg;
  htab->alloc_with_arg_f = alloc_f;
  htab->free_with_arg_f = free_f;
}
size_t() htab_size ( htab_t  htab)

Definition at line 221 of file hashtab.c.

{
  return htab_size (htab);
}
void htab_traverse ( htab_t  htab,
htab_trav  callback,
PTR  info 
)

Definition at line 760 of file hashtab.c.

{
  if (htab_elements (htab) * 8 < htab_size (htab))
    htab_expand (htab);

  htab_traverse_noresize (htab, callback, info);
}

Here is the call graph for this function:

void htab_traverse_noresize ( htab_t  htab,
htab_trav  callback,
PTR  info 
)

Definition at line 737 of file hashtab.c.

{
  PTR *slot;
  PTR *limit;
  
  slot = htab->entries;
  limit = slot + htab_size (htab);

  do
    {
      PTR x = *slot;

      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
       if (!(*callback) (slot, info))
         break;
    }
  while (++slot < limit);
}
htab_t htab_try_create ( size_t  size,
htab_hash  hash_f,
htab_eq  eq_f,
htab_del  del_f 
)

Definition at line 378 of file hashtab.c.

{
  return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hashval_t iterative_hash ( const PTR  k_in,
register size_t  length,
register hashval_t  initval 
)

Definition at line 896 of file hashtab.c.

{
  register const unsigned char *k = (const unsigned char *)k_in;
  register hashval_t a,b,c,len;

  /* Set up the internal state */
  len = length;
  a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
  c = initval;           /* the previous hash value */

  /*---------------------------------------- handle most of the key */
#ifndef WORDS_BIGENDIAN
  /* On a little-endian machine, if the data is 4-byte aligned we can hash
     by word for better speed.  This gives nondeterministic results on
     big-endian machines.  */
  if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0)
    while (len >= 12)    /* aligned */
      {
       a += *(hashval_t *)(k+0);
       b += *(hashval_t *)(k+4);
       c += *(hashval_t *)(k+8);
       mix(a,b,c);
       k += 12; len -= 12;
      }
  else /* unaligned */
#endif
    while (len >= 12)
      {
       a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
       b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
       c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
       mix(a,b,c);
       k += 12; len -= 12;
      }

  /*------------------------------------- handle the last 11 bytes */
  c += length;
  switch(len)              /* all the case statements fall through */
    {
    case 11: c+=((hashval_t)k[10]<<24);
    case 10: c+=((hashval_t)k[9]<<16);
    case 9 : c+=((hashval_t)k[8]<<8);
      /* the first byte of c is reserved for the length */
    case 8 : b+=((hashval_t)k[7]<<24);
    case 7 : b+=((hashval_t)k[6]<<16);
    case 6 : b+=((hashval_t)k[5]<<8);
    case 5 : b+=k[4];
    case 4 : a+=((hashval_t)k[3]<<24);
    case 3 : a+=((hashval_t)k[2]<<16);
    case 2 : a+=((hashval_t)k[1]<<8);
    case 1 : a+=k[0];
      /* case 0: nothing left to add */
    }
  mix(a,b,c);
  /*-------------------------------------------- report the result */
  return c;
}

Variable Documentation

Definition at line 80 of file hashtab.c.

Definition at line 79 of file hashtab.c.

struct prime_ent[] [static]

Definition at line 132 of file hashtab.c.