gcc/hash.c

   1 /* hash.c -- hash table routines
   2    Copyright (C) 1993, 1994, 1998 Free Software Foundation, Inc.
   3    Written by Steve Chamberlain <sac@cygnus.com>
   4
   5 This file was lifted from BFD, the Binary File Descriptor library.
   6
   7 This program 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 of the License, or
  10 (at your option) any later version.
  11
  12 This program 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 this program; if not, write to the Free Software
  19 Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "hash.h"
  25 #include "obstack.h"
  26 #include "toplev.h"
  27
  28 /* Obstack allocation and deallocation routines.  */
  29 #define obstack_chunk_alloc xmalloc
  30 #define obstack_chunk_free free
  31
  32 /* The default number of entries to use when creating a hash table.  */
  33 #define DEFAULT_SIZE (1009)
  34
  35 /* Create a new hash table, given a number of entries.  */
  36
  37 boolean
  38 hash_table_init_n (table, newfunc, hash, comp, size)
  39      struct hash_table *table;
  40      struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
  41                                             struct hash_table *,
  42                                             hash_table_key));
  43      unsigned long (*hash) PARAMS ((hash_table_key));
  44      boolean (*comp) PARAMS ((hash_table_key, hash_table_key));
  45      unsigned int size;
  46 {
  47   unsigned int alloc;
  48
  49   alloc = size * sizeof (struct hash_entry *);
  50   if (!obstack_begin (&table->memory, alloc))
  51     {
  52       error ("no memory");
  53       return false;
  54     }
  55   table->table = ((struct hash_entry **)
  56                   obstack_alloc (&table->memory, alloc));
  57   if (!table->table)
  58     {
  59       error ("no memory");
  60       return false;
  61     }
  62   memset ((PTR) table->table, 0, alloc);
  63   table->size = size;
  64   table->newfunc = newfunc;
  65   table->hash = hash;
  66   table->comp = comp;
  67   return true;
  68 }
  69
  70 /* Create a new hash table with the default number of entries.  */
  71
  72 boolean
  73 hash_table_init (table, newfunc, hash, comp)
  74      struct hash_table *table;
  75      struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
  76                                             struct hash_table *,
  77                                             hash_table_key));
  78      unsigned long (*hash) PARAMS ((hash_table_key));
  79      boolean (*comp) PARAMS ((hash_table_key, hash_table_key));
  80 {
  81   return hash_table_init_n (table, newfunc, hash, comp, DEFAULT_SIZE);
  82 }
  83
  84 /* Free a hash table.  */
  85
  86 void
  87 hash_table_free (table)
  88      struct hash_table *table;
  89 {
  90   obstack_free (&table->memory, (PTR) NULL);
  91 }
  92
  93 /* Look up KEY in TABLE.  If CREATE is non-NULL a new entry is
  94    created if one does not previously exist.  */
  95
  96 struct hash_entry *
  97 hash_lookup (table, key, create, copy)
  98      struct hash_table *table;
  99      hash_table_key key;
 100      boolean create;
 101      hash_table_key (*copy) PARAMS ((struct obstack* memory,
 102                                      hash_table_key key));
 103 {
 104   register unsigned long hash;
 105   struct hash_entry *hashp;
 106   unsigned int index;
 107
 108   hash = (*table->hash)(key);
 109
 110   index = hash % table->size;
 111   for (hashp = table->table[index];
 112        hashp != (struct hash_entry *) NULL;
 113        hashp = hashp->next)
 114     {
 115       if (hashp->hash == hash
 116           && (*table->comp)(hashp->key, key))
 117         return hashp;
 118     }
 119
 120   if (! create)
 121     return (struct hash_entry *) NULL;
 122
 123   hashp = (*table->newfunc) ((struct hash_entry *) NULL, table, key);
 124   if (hashp == (struct hash_entry *) NULL)
 125     return (struct hash_entry *) NULL;
 126   if (copy)
 127     key = (*copy) (&table->memory, key);
 128   hashp->key = key;
 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 hash_entry *
 140 hash_newfunc (entry, table, p)
 141      struct hash_entry *entry;
 142      struct hash_table *table;
 143      hash_table_key p;
 144 {
 145   if (entry == (struct hash_entry *) NULL)
 146     entry = ((struct hash_entry *)
 147              hash_allocate (table, sizeof (struct hash_entry)));
 148   return entry;
 149 }
 150
 151 /* Allocate space in a hash table.  */
 152
 153 PTR
 154 hash_allocate (table, size)
 155      struct hash_table *table;
 156      unsigned int size;
 157 {
 158   PTR ret;
 159
 160   ret = obstack_alloc (&table->memory, size);
 161   if (ret == NULL && size != 0)
 162     error ("no memory");
 163   return ret;
 164 }
 165
 166 /* Traverse a hash table.  */
 167
 168 void
 169 hash_traverse (table, func, info)
 170      struct hash_table *table;
 171      boolean (*func) PARAMS ((struct hash_entry *, hash_table_key));
 172      PTR info;
 173 {
 174   unsigned int i;
 175
 176   for (i = 0; i < table->size; i++)
 177     {
 178       struct hash_entry *p;
 179
 180       for (p = table->table[i]; p != NULL; p = p->next)
 181         {
 182           if (! (*func) (p, info))
 183             return;
 184         }
 185     }
 186 }
 187
 188 /* Hash a string.  Return a hash-code for the string.  */
 189
 190 unsigned long
 191 string_hash (k)
 192      hash_table_key k;
 193 {
 194   const unsigned char *s;
 195   unsigned long hash;
 196   unsigned char c;
 197   unsigned int len;
 198
 199   s = (const unsigned char *) k;
 200   hash = 0;
 201   len = 0;
 202
 203   while ((c = *s++) != '\0')
 204     {
 205       hash += c + (c << 17);
 206       hash ^= hash >> 2;
 207       ++len;
 208     }
 209   hash += len + (len << 17);
 210   hash ^= hash >> 2;
 211
 212   return hash;
 213 }
 214
 215 /* Compare two strings.  Return non-zero iff the two strings are
 216    the same.  */
 217
 218 boolean
 219 string_compare (k1, k2)
 220      hash_table_key k1;
 221      hash_table_key k2;
 222 {
 223   return (strcmp ((char*) k1, (char*) k2) == 0);
 224 }
 225
 226 /* Copy K to OBSTACK.  */
 227
 228 hash_table_key
 229 string_copy (memory, k)
 230      struct obstack* memory;
 231      hash_table_key k;
 232 {
 233   char *new;
 234   char *string = (char*) k;
 235
 236   new = (char *) obstack_alloc (memory, strlen (string) + 1);
 237   if (!new)
 238     {
 239       error ("no memory");
 240       return NULL;
 241     }
 242   strcpy (new, string);
 243
 244   return new;
 245 }