Back to index

cell-binutils  2.17cvs20070401
Classes | Defines | Functions | Variables
hash.c File Reference
#include "bfd.h"
#include "sysdep.h"
#include "libbfd.h"
#include "objalloc.h"
#include "libiberty.h"

Go to the source code of this file.

Classes

struct  strtab_hash_entry
struct  bfd_strtab_hash

Defines

#define DEFAULT_SIZE   4051
#define strtab_hash_lookup(t, string, create, copy)

Functions

static unsigned long higher_prime_number (unsigned long n)
bfd_boolean bfd_hash_table_init_n (struct bfd_hash_table *table, struct bfd_hash_entry *(*newfunc)(struct bfd_hash_entry *, struct bfd_hash_table *, const char *), unsigned int entsize, unsigned int size)
bfd_boolean bfd_hash_table_init (struct bfd_hash_table *table, struct bfd_hash_entry *(*newfunc)(struct bfd_hash_entry *, struct bfd_hash_table *, const char *), unsigned int entsize)
void bfd_hash_table_free (struct bfd_hash_table *table)
struct bfd_hash_entrybfd_hash_lookup (struct bfd_hash_table *table, const char *string, bfd_boolean create, bfd_boolean copy)
void bfd_hash_replace (struct bfd_hash_table *table, struct bfd_hash_entry *old, struct bfd_hash_entry *nw)
void * bfd_hash_allocate (struct bfd_hash_table *table, unsigned int size)
struct bfd_hash_entrybfd_hash_newfunc (struct bfd_hash_entry *entry, struct bfd_hash_table *table, const char *string ATTRIBUTE_UNUSED)
void bfd_hash_traverse (struct bfd_hash_table *table, bfd_boolean(*func)(struct bfd_hash_entry *, void *), void *info)
void bfd_hash_set_default_size (bfd_size_type hash_size)
static struct bfd_hash_entrystrtab_hash_newfunc (struct bfd_hash_entry *entry, struct bfd_hash_table *table, const char *string)
struct bfd_strtab_hash_bfd_stringtab_init (void)
struct bfd_strtab_hash_bfd_xcoff_stringtab_init (void)
void _bfd_stringtab_free (struct bfd_strtab_hash *table)
bfd_size_type _bfd_stringtab_add (struct bfd_strtab_hash *tab, const char *str, bfd_boolean hash, bfd_boolean copy)
bfd_size_type _bfd_stringtab_size (struct bfd_strtab_hash *tab)
bfd_boolean _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab)

Variables

static size_t bfd_default_hash_table_size = DEFAULT_SIZE

Class Documentation

struct strtab_hash_entry

Definition at line 621 of file hash.c.

Collaboration diagram for strtab_hash_entry:
Class Members
bfd_size_type index
struct strtab_hash_entry * next
struct bfd_strtab_hash

Definition at line 632 of file hash.c.

Collaboration diagram for bfd_strtab_hash:
Class Members
struct strtab_hash_entry * first
struct strtab_hash_entry * last
bfd_size_type size
bfd_boolean xcoff

Define Documentation

#define DEFAULT_SIZE   4051

Definition at line 301 of file hash.c.

#define strtab_hash_lookup (   t,
  string,
  create,
  copy 
)
Value:
((struct strtab_hash_entry *) \
   bfd_hash_lookup (&(t)->table, (string), (create), (copy)))

Definition at line 678 of file hash.c.


Function Documentation

Definition at line 738 of file hash.c.

{
  struct strtab_hash_entry *entry;

  if (hash)
    {
      entry = strtab_hash_lookup (tab, str, TRUE, copy);
      if (entry == NULL)
       return (bfd_size_type) -1;
    }
  else
    {
      entry = bfd_hash_allocate (&tab->table, sizeof (* entry));
      if (entry == NULL)
       return (bfd_size_type) -1;
      if (! copy)
       entry->root.string = str;
      else
       {
         char *n;

         n = bfd_hash_allocate (&tab->table, strlen (str) + 1);
         if (n == NULL)
           return (bfd_size_type) -1;
         entry->root.string = n;
       }
      entry->index = (bfd_size_type) -1;
      entry->next = NULL;
    }

  if (entry->index == (bfd_size_type) -1)
    {
      entry->index = tab->size;
      tab->size += strlen (str) + 1;
      if (tab->xcoff)
       {
         entry->index += 2;
         tab->size += 2;
       }
      if (tab->first == NULL)
       tab->first = entry;
      else
       tab->last->next = entry;
      tab->last = entry;
    }

  return entry->index;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 802 of file hash.c.

{
  bfd_boolean xcoff;
  struct strtab_hash_entry *entry;

  xcoff = tab->xcoff;

  for (entry = tab->first; entry != NULL; entry = entry->next)
    {
      const char *str;
      size_t len;

      str = entry->root.string;
      len = strlen (str) + 1;

      if (xcoff)
       {
         bfd_byte buf[2];

         /* The output length includes the null byte.  */
         bfd_put_16 (abfd, (bfd_vma) len, buf);
         if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2)
           return FALSE;
       }

      if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len)
       return FALSE;
    }

  return TRUE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 727 of file hash.c.

{
  bfd_hash_table_free (&table->table);
  free (table);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 685 of file hash.c.

{
  struct bfd_strtab_hash *table;
  bfd_size_type amt = sizeof (* table);

  table = bfd_malloc (amt);
  if (table == NULL)
    return NULL;

  if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
                         sizeof (struct strtab_hash_entry)))
    {
      free (table);
      return NULL;
    }

  table->size = 0;
  table->first = NULL;
  table->last = NULL;
  table->xcoff = FALSE;

  return table;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 793 of file hash.c.

{
  return tab->size;
}

Here is the caller graph for this function:

Definition at line 714 of file hash.c.

{
  struct bfd_strtab_hash *ret;

  ret = _bfd_stringtab_init ();
  if (ret != NULL)
    ret->xcoff = TRUE;
  return ret;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* bfd_hash_allocate ( struct bfd_hash_table table,
unsigned int  size 
)

Definition at line 544 of file hash.c.

{
  void * ret;

  ret = objalloc_alloc ((struct objalloc *) table->memory, size);
  if (ret == NULL && size != 0)
    bfd_set_error (bfd_error_no_memory);
  return ret;
}

Here is the call graph for this function:

struct bfd_hash_entry* bfd_hash_lookup ( struct bfd_hash_table table,
const char *  string,
bfd_boolean  create,
bfd_boolean  copy 
) [read]

Definition at line 416 of file hash.c.

{
  const unsigned char *s;
  unsigned long hash;
  unsigned int c;
  struct bfd_hash_entry *hashp;
  unsigned int len;
  unsigned int index;

  hash = 0;
  len = 0;
  s = (const unsigned char *) string;
  while ((c = *s++) != '\0')
    {
      hash += c + (c << 17);
      hash ^= hash >> 2;
    }
  len = (s - (const unsigned char *) string) - 1;
  hash += len + (len << 17);
  hash ^= hash >> 2;

  index = hash % table->size;
  for (hashp = table->table[index];
       hashp != NULL;
       hashp = hashp->next)
    {
      if (hashp->hash == hash
         && strcmp (hashp->string, string) == 0)
       return hashp;
    }

  if (! create)
    return NULL;

  hashp = (*table->newfunc) (NULL, table, string);
  if (hashp == NULL)
    return NULL;
  if (copy)
    {
      char *new;

      new = objalloc_alloc ((struct objalloc *) table->memory, len + 1);
      if (!new)
       {
         bfd_set_error (bfd_error_no_memory);
         return NULL;
       }
      memcpy (new, string, len + 1);
      string = new;
    }
  hashp->string = string;
  hashp->hash = hash;
  hashp->next = table->table[index];
  table->table[index] = hashp;
  table->count++;

  if (!table->frozen && table->count > table->size * 3 / 4)
    {
      unsigned long newsize = higher_prime_number (table->size);
      struct bfd_hash_entry **newtable;
      unsigned int hi;
      unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);

      /* If we can't find a higher prime, or we can't possibly alloc
        that much memory, don't try to grow the table.  */
      if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize)
       {
         table->frozen = 1;
         return hashp;
       }

      newtable = ((struct bfd_hash_entry **)
                objalloc_alloc ((struct objalloc *) table->memory, alloc));
      memset ((PTR) newtable, 0, alloc);

      for (hi = 0; hi < table->size; hi ++)
       while (table->table[hi])
         {
           struct bfd_hash_entry *chain = table->table[hi];
           struct bfd_hash_entry *chain_end = chain;
           int index;

           while (chain_end->next && chain_end->next->hash == chain->hash)
             chain_end = chain_end->next;

           table->table[hi] = chain_end->next;
           index = chain->hash % newsize;
           chain_end->next = newtable[index];
           newtable[index] = chain;
         }
      table->table = newtable;
      table->size = newsize;
    }

  return hashp;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct bfd_hash_entry* bfd_hash_newfunc ( struct bfd_hash_entry entry,
struct bfd_hash_table table,
const char *string  ATTRIBUTE_UNUSED 
) [read]

Definition at line 558 of file hash.c.

{
  if (entry == NULL)
    entry = bfd_hash_allocate (table, sizeof (* entry));
  return entry;
}

Here is the call graph for this function:

Definition at line 519 of file hash.c.

{
  unsigned int index;
  struct bfd_hash_entry **pph;

  index = old->hash % table->size;
  for (pph = &table->table[index];
       (*pph) != NULL;
       pph = &(*pph)->next)
    {
      if (*pph == old)
       {
         *pph = nw;
         return;
       }
    }

  abort ();
}

Here is the caller graph for this function:

Definition at line 590 of file hash.c.

{
  /* Extend this prime list if you want more granularity of hash table size.  */
  static const bfd_size_type hash_size_primes[] =
    {
      251, 509, 1021, 2039, 4051, 8599, 16699, 32749
    };
  size_t index;

  /* Work out best prime number near the hash_size.  */
  for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
    if (hash_size <= hash_size_primes[index])
      break;

  bfd_default_hash_table_size = hash_size_primes[index];
}

Here is the caller graph for this function:

Definition at line 407 of file hash.c.

{
  objalloc_free (table->memory);
  table->memory = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 394 of file hash.c.

Here is the call graph for this function:

Definition at line 359 of file hash.c.

{
  unsigned int alloc;

  alloc = size * sizeof (struct bfd_hash_entry *);

  table->memory = (void *) objalloc_create ();
  if (table->memory == NULL)
    {
      bfd_set_error (bfd_error_no_memory);
      return FALSE;
    }
  table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc);
  if (table->table == NULL)
    {
      bfd_set_error (bfd_error_no_memory);
      return FALSE;
    }
  memset ((void *) table->table, 0, alloc);
  table->size = size;
  table->entsize = entsize;
  table->count = 0;
  table->frozen = 0;
  table->newfunc = newfunc;
  return TRUE;
}

Here is the call graph for this function:

void bfd_hash_traverse ( struct bfd_hash_table table,
bfd_boolean(*)(struct bfd_hash_entry *, void *)  func,
void *  info 
)

Definition at line 570 of file hash.c.

{
  unsigned int i;

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

      for (p = table->table[i]; p != NULL; p = p->next)
       if (! (*func) (p, info))
         goto out;
    }
 out:
  table->frozen = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static unsigned long higher_prime_number ( unsigned long  n) [static]

Definition at line 308 of file hash.c.

{
  /* These are primes that are near, but slightly smaller than, a
     power of two.  */
  static const unsigned long primes[] = {
    (unsigned long) 127,
    (unsigned long) 2039,
    (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,
                                   /* 4294967291L */
    ((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)
    return 0;

  return *low;
}

Here is the caller graph for this function:

static struct bfd_hash_entry* strtab_hash_newfunc ( struct bfd_hash_entry entry,
struct bfd_hash_table table,
const char *  string 
) [static, read]

Definition at line 649 of file hash.c.

{
  struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;

  /* Allocate the structure if it has not already been allocated by a
     subclass.  */
  if (ret == NULL)
    ret = bfd_hash_allocate (table, sizeof (* ret));
  if (ret == NULL)
    return NULL;

  /* Call the allocation method of the superclass.  */
  ret = (struct strtab_hash_entry *)
        bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);

  if (ret)
    {
      /* Initialize the local fields.  */
      ret->index = (bfd_size_type) -1;
      ret->next = NULL;
    }

  return (struct bfd_hash_entry *) ret;
}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

Definition at line 354 of file hash.c.