Back to index

cell-binutils  2.17cvs20070401
Classes | Functions | Variables
hash.c File Reference
#include "as.h"
#include "safe-ctype.h"
#include "obstack.h"

Go to the source code of this file.

Classes

struct  hash_entry
struct  hash_control

Functions

void set_gas_hash_table_size (unsigned long size)
static unsigned long get_gas_hash_table_size (void)
struct hash_controlhash_new (void)
void hash_die (struct hash_control *table)
static struct hash_entryhash_lookup (struct hash_control *table, const char *key, size_t len, struct hash_entry ***plist, unsigned long *phash)
const char * hash_insert (struct hash_control *table, const char *key, PTR value)
const char * hash_jam (struct hash_control *table, const char *key, PTR value)
PTR hash_replace (struct hash_control *table, const char *key, PTR value)
PTR hash_find (struct hash_control *table, const char *key)
PTR hash_find_n (struct hash_control *table, const char *key, size_t len)
PTR hash_delete (struct hash_control *table, const char *key)
void hash_traverse (struct hash_control *table, void(*pfn)(const char *key, PTR value))
void hash_print_statistics (FILE *f ATTRIBUTE_UNUSED, const char *name ATTRIBUTE_UNUSED, struct hash_control *table ATTRIBUTE_UNUSED)

Variables

static unsigned long gas_hash_table_size = 65537

Class Documentation

struct hash_entry

Definition at line 38 of file hash.c.

Collaboration diagram for hash_entry:
Class Members
PTR data
unsigned long hash
struct hash_entry * next
const char * string
struct hash_control

Definition at line 52 of file hash.c.

Collaboration diagram for hash_control:
Class Members
unsigned int size
struct hash_entry ** table

Function Documentation

static unsigned long get_gas_hash_table_size ( void  ) [static]

Definition at line 86 of file hash.c.

{
  /* Extend this prime list if you want more granularity of hash table size.  */
  static const unsigned long hash_size_primes[] =
    {
      1021, 4051, 8599, 16699, 65537
    };
  unsigned int index;

  /* Work out the best prime number near the hash_size.
     FIXME: This could be a more sophisticated algorithm,
     but is it really worth implementing it ?   */
  for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
    if (gas_hash_table_size <= hash_size_primes[index])
      break;

  return hash_size_primes[index];
}

Here is the caller graph for this function:

PTR hash_delete ( struct hash_control table,
const char *  key 
)

Definition at line 348 of file hash.c.

{
  struct hash_entry *p;
  struct hash_entry **list;

  p = hash_lookup (table, key, strlen (key), &list, NULL);
  if (p == NULL)
    return NULL;

  if (p != *list)
    abort ();

#ifdef HASH_STATISTICS
  ++table->deletions;
#endif

  *list = p->next;

  /* Note that we never reclaim the memory for this entry.  If gas
     ever starts deleting hash table entries in a big way, this will
     have to change.  */

  return p->data;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void hash_die ( struct hash_control table)

Definition at line 138 of file hash.c.

{
  obstack_free (&table->memory, 0);
  free (table);
}

Here is the call graph for this function:

Here is the caller graph for this function:

PTR hash_find ( struct hash_control table,
const char *  key 
)

Definition at line 318 of file hash.c.

{
  struct hash_entry *p;

  p = hash_lookup (table, key, strlen (key), NULL, NULL);
  if (p == NULL)
    return NULL;

  return p->data;
}

Here is the call graph for this function:

PTR hash_find_n ( struct hash_control table,
const char *  key,
size_t  len 
)

Definition at line 333 of file hash.c.

{
  struct hash_entry *p;

  p = hash_lookup (table, key, len, NULL, NULL);
  if (p == NULL)
    return NULL;

  return p->data;
}

Here is the call graph for this function:

Here is the caller graph for this function:

const char* hash_insert ( struct hash_control table,
const char *  key,
PTR  value 
)

Definition at line 226 of file hash.c.

{
  struct hash_entry *p;
  struct hash_entry **list;
  unsigned long hash;

  p = hash_lookup (table, key, strlen (key), &list, &hash);
  if (p != NULL)
    return "exists";

#ifdef HASH_STATISTICS
  ++table->insertions;
#endif

  p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
  p->string = key;
  p->hash = hash;
  p->data = value;

  p->next = *list;
  *list = p;

  return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

const char* hash_jam ( struct hash_control table,
const char *  key,
PTR  value 
)

Definition at line 256 of file hash.c.

{
  struct hash_entry *p;
  struct hash_entry **list;
  unsigned long hash;

  p = hash_lookup (table, key, strlen (key), &list, &hash);
  if (p != NULL)
    {
#ifdef HASH_STATISTICS
      ++table->replacements;
#endif

      p->data = value;
    }
  else
    {
#ifdef HASH_STATISTICS
      ++table->insertions;
#endif

      p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
      p->string = key;
      p->hash = hash;
      p->data = value;

      p->next = *list;
      *list = p;
    }

  return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct hash_entry* hash_lookup ( struct hash_control table,
const char *  key,
size_t  len,
struct hash_entry ***  plist,
unsigned long phash 
) [static, read]

Definition at line 154 of file hash.c.

{
  unsigned long hash;
  size_t n;
  unsigned int c;
  unsigned int index;
  struct hash_entry **list;
  struct hash_entry *p;
  struct hash_entry *prev;

#ifdef HASH_STATISTICS
  ++table->lookups;
#endif

  hash = 0;
  for (n = 0; n < len; n++)
    {
      c = key[n];
      hash += c + (c << 17);
      hash ^= hash >> 2;
    }
  hash += len + (len << 17);
  hash ^= hash >> 2;

  if (phash != NULL)
    *phash = hash;

  index = hash % table->size;
  list = table->table + index;

  if (plist != NULL)
    *plist = list;

  prev = NULL;
  for (p = *list; p != NULL; p = p->next)
    {
#ifdef HASH_STATISTICS
      ++table->hash_compares;
#endif

      if (p->hash == hash)
       {
#ifdef HASH_STATISTICS
         ++table->string_compares;
#endif

         if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
           {
             if (prev != NULL)
              {
                prev->next = p->next;
                p->next = *list;
                *list = p;
              }

             return p;
           }
       }

      prev = p;
    }

  return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct hash_control* hash_new ( void  ) [read]

Definition at line 108 of file hash.c.

{
  unsigned long size;
  unsigned long alloc;
  struct hash_control *ret;

  size = get_gas_hash_table_size ();

  ret = xmalloc (sizeof *ret);
  obstack_begin (&ret->memory, chunksize);
  alloc = size * sizeof (struct hash_entry *);
  ret->table = obstack_alloc (&ret->memory, alloc);
  memset (ret->table, 0, alloc);
  ret->size = size;

#ifdef HASH_STATISTICS
  ret->lookups = 0;
  ret->hash_compares = 0;
  ret->string_compares = 0;
  ret->insertions = 0;
  ret->replacements = 0;
  ret->deletions = 0;
#endif

  return ret;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void hash_print_statistics ( FILE *f  ATTRIBUTE_UNUSED,
const char *name  ATTRIBUTE_UNUSED,
struct hash_control *table  ATTRIBUTE_UNUSED 
)

Definition at line 395 of file hash.c.

{
#ifdef HASH_STATISTICS
  unsigned int i;
  unsigned long total;
  unsigned long empty;

  fprintf (f, "%s hash statistics:\n", name);
  fprintf (f, "\t%lu lookups\n", table->lookups);
  fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
  fprintf (f, "\t%lu string comparisons\n", table->string_compares);
  fprintf (f, "\t%lu insertions\n", table->insertions);
  fprintf (f, "\t%lu replacements\n", table->replacements);
  fprintf (f, "\t%lu deletions\n", table->deletions);

  total = 0;
  empty = 0;
  for (i = 0; i < table->size; ++i)
    {
      struct hash_entry *p;

      if (table->table[i] == NULL)
       ++empty;
      else
       {
         for (p = table->table[i]; p != NULL; p = p->next)
           ++total;
       }
    }

  fprintf (f, "\t%g average chain length\n", (double) total / table->size);
  fprintf (f, "\t%lu empty slots\n", empty);
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

PTR hash_replace ( struct hash_control table,
const char *  key,
PTR  value 
)

Definition at line 294 of file hash.c.

{
  struct hash_entry *p;
  PTR ret;

  p = hash_lookup (table, key, strlen (key), NULL, NULL);
  if (p == NULL)
    return NULL;

#ifdef HASH_STATISTICS
  ++table->replacements;
#endif

  ret = p->data;

  p->data = value;

  return ret;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void hash_traverse ( struct hash_control table,
void(*)(const char *key, PTR value pfn 
)

Definition at line 377 of file hash.c.

{
  unsigned int i;

  for (i = 0; i < table->size; ++i)
    {
      struct hash_entry *p;

      for (p = table->table[i]; p != NULL; p = p->next)
       (*pfn) (p->string, p->data);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 79 of file hash.c.

{
  gas_hash_table_size = size;
}

Here is the caller graph for this function:


Variable Documentation

unsigned long gas_hash_table_size = 65537 [static]

Definition at line 76 of file hash.c.