gcc/hash.c

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