bfd/hash.c

   1 /* hash.c -- hash table routines for BFD
   2    Copyright 1993 Free Software Foundation, Inc.
   3    Written by Steve Chamberlain <sac@cygnus.com>
   4
   5 This file is part of GLD, the Gnu Linker.
   6
   7 GLD is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GLD is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GLD; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20
  21 #include "bfd.h"
  22 #include "sysdep.h"
  23 #include "libbfd.h"
  24 #include "obstack.h"
  25
  26 /* Obstack allocation and deallocation routines.  */
  27 #define obstack_chunk_alloc bfd_xmalloc_by_size_t
  28 #define obstack_chunk_free free
  29
  30 /* The default number of entries to use when creating a hash table.  */
  31 #define DEFAULT_SIZE (4051)
  32
  33 /* Create a new hash table, given a number of entries.  */
  34
  35 boolean
  36 bfd_hash_table_init_n (table, newfunc, size)
  37      struct bfd_hash_table *table;
  38      struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *,
  39                                                 struct bfd_hash_table *,
  40                                                 const char *));
  41      unsigned int size;
  42 {
  43   unsigned int alloc;
  44
  45   alloc = size * sizeof (struct bfd_hash_entry *);
  46   obstack_begin (&table->memory, alloc);
  47   table->table = ((struct bfd_hash_entry **)
  48                   obstack_alloc (&table->memory, alloc));
  49   memset ((PTR) table->table, 0, alloc);
  50   table->size = size;
  51   table->newfunc = newfunc;
  52   return true;
  53 }
  54
  55 /* Create a new hash table with the default number of entries.  */
  56
  57 boolean
  58 bfd_hash_table_init (table, newfunc)
  59      struct bfd_hash_table *table;
  60      struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *,
  61                                                 struct bfd_hash_table *,
  62                                                 const char *));
  63 {
  64   return bfd_hash_table_init_n (table, newfunc, DEFAULT_SIZE);
  65 }
  66
  67 /* Free a hash table.  */
  68
  69 void
  70 bfd_hash_table_free (table)
  71      struct bfd_hash_table *table;
  72 {
  73   obstack_free (&table->memory, (PTR) NULL);
  74 }
  75
  76 /* Look up a string in a hash table.  */
  77
  78 struct bfd_hash_entry *
  79 bfd_hash_lookup (table, string, create, copy)
  80      struct bfd_hash_table *table;
  81      const char *string;
  82      boolean create;
  83      boolean copy;
  84 {
  85   register const unsigned char *s;
  86   register unsigned long hash;
  87   register unsigned int c;
  88   struct bfd_hash_entry *hashp;
  89   unsigned int len;
  90   unsigned int index;
  91
  92   hash = 0;
  93   len = 0;
  94   s = (const unsigned char *) string;
  95   while ((c = *s++) != '\0')
  96     {
  97       hash += c + (c << 17);
  98       hash ^= hash >> 2;
  99       ++len;
 100     }
 101   hash += len + (len << 17);
 102   hash ^= hash >> 2;
 103
 104   index = hash % table->size;
 105   for (hashp = table->table[index];
 106        hashp != (struct bfd_hash_entry *) NULL;
 107        hashp = hashp->next)
 108     {
 109       if (hashp->hash == hash
 110           && strcmp (hashp->string, string) == 0)
 111         return hashp;
 112     }
 113
 114   if (! create)
 115     return (struct bfd_hash_entry *) NULL;
 116
 117   hashp = (*table->newfunc) ((struct bfd_hash_entry *) NULL, table, string);
 118   if (hashp == (struct bfd_hash_entry *) NULL)
 119     return (struct bfd_hash_entry *) NULL;
 120   if (copy)
 121     {
 122       char *new;
 123
 124       new = (char *) obstack_alloc (&table->memory, len + 1);
 125       strcpy (new, string);
 126       string = new;
 127     }
 128   hashp->string = string;
 129   hashp->hash = hash;
 130   hashp->next = table->table[index];
 131   table->table[index] = hashp;
 132
 133   return hashp;
 134 }
 135
 136 /* Base method for creating a new hash table entry.  */
 137
 138 /*ARGSUSED*/
 139 struct bfd_hash_entry *
 140 bfd_hash_newfunc (entry, table, string)
 141      struct bfd_hash_entry *entry;
 142      struct bfd_hash_table *table;
 143      const char *string;
 144 {
 145   if (entry == (struct bfd_hash_entry *) NULL)
 146     entry = ((struct bfd_hash_entry *)
 147              bfd_hash_allocate (table, sizeof (struct bfd_hash_entry)));
 148   return entry;
 149 }
 150
 151 /* Allocate space in a hash table.  */
 152
 153 PTR
 154 bfd_hash_allocate (table, size)
 155      struct bfd_hash_table *table;
 156      size_t size;
 157 {
 158   return obstack_alloc (&table->memory, size);
 159 }
 160
 161 /* Traverse a hash table.  */
 162
 163 void
 164 bfd_hash_traverse (table, func, info)
 165      struct bfd_hash_table *table;
 166      boolean (*func) PARAMS ((struct bfd_hash_entry *, PTR));
 167      PTR info;
 168 {
 169   unsigned int i;
 170
 171   for (i = 0; i < table->size; i++)
 172     {
 173       struct bfd_hash_entry *p;
 174
 175       for (p = table->table[i]; p != NULL; p = p->next)
 176         {
 177           if (! (*func) (p, info))
 178             return;
 179         }
 180     }
 181 }