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
  26 /* Obstack allocation and deallocation routines.  */
  27 #define obstack_chunk_alloc xmalloc
  28 #define obstack_chunk_free free
  29
  30 extern char * xmalloc ();
  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, size)
  39      struct hash_table *table;
  40      struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
  41                                                 struct hash_table *,
  42                                                 const char *));
  43      unsigned int size;
  44 {
  45   unsigned int alloc;
  46
  47   alloc = size * sizeof (struct hash_entry *);
  48   if (!obstack_begin (&table->memory, alloc))
  49     {
  50       error ("no memory");
  51       return false;
  52     }
  53   table->table = ((struct hash_entry **)
  54                   obstack_alloc (&table->memory, alloc));
  55   if (!table->table)
  56     {
  57       error ("no memory");
  58       return false;
  59     }
  60   memset ((PTR) table->table, 0, alloc);
  61   table->size = size;
  62   table->newfunc = newfunc;
  63   return true;
  64 }
  65
  66 /* Create a new hash table with the default number of entries.  */
  67
  68 boolean
  69 hash_table_init (table, newfunc)
  70      struct hash_table *table;
  71      struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
  72                                                 struct hash_table *,
  73                                                 const char *));
  74 {
  75   return hash_table_init_n (table, newfunc, DEFAULT_SIZE);
  76 }
  77
  78 /* Free a hash table.  */
  79
  80 void
  81 hash_table_free (table)
  82      struct hash_table *table;
  83 {
  84   obstack_free (&table->memory, (PTR) NULL);
  85 }
  86
  87 /* Look up a string in a hash table.  */
  88
  89 struct hash_entry *
  90 hash_lookup (table, string, create, copy)
  91      struct hash_table *table;
  92      const char *string;
  93      boolean create;
  94      boolean copy;
  95 {
  96   register const unsigned char *s;
  97   register unsigned long hash;
  98   register unsigned int c;
  99   struct hash_entry *hashp;
 100   unsigned int len;
 101   unsigned int index;
 102
 103   hash = 0;
 104   len = 0;
 105   s = (const unsigned char *) string;
 106   while ((c = *s++) != '\0')
 107     {
 108       hash += c + (c << 17);
 109       hash ^= hash >> 2;
 110       ++len;
 111     }
 112   hash += len + (len << 17);
 113   hash ^= hash >> 2;
 114
 115   index = hash % table->size;
 116   for (hashp = table->table[index];
 117        hashp != (struct hash_entry *) NULL;
 118        hashp = hashp->next)
 119     {
 120       if (hashp->hash == hash
 121           && strcmp (hashp->string, string) == 0)
 122         return hashp;
 123     }
 124
 125   if (! create)
 126     return (struct hash_entry *) NULL;
 127
 128   hashp = (*table->newfunc) ((struct hash_entry *) NULL, table, string);
 129   if (hashp == (struct hash_entry *) NULL)
 130     return (struct hash_entry *) NULL;
 131   if (copy)
 132     {
 133       char *new;
 134
 135       new = (char *) obstack_alloc (&table->memory, len + 1);
 136       if (!new)
 137         {
 138           error ("no memory");
 139           return (struct hash_entry *) NULL;
 140         }
 141       strcpy (new, string);
 142       string = new;
 143     }
 144   hashp->string = string;
 145   hashp->hash = hash;
 146   hashp->next = table->table[index];
 147   table->table[index] = hashp;
 148
 149   return hashp;
 150 }
 151
 152 /* Base method for creating a new hash table entry.  */
 153
 154 /*ARGSUSED*/
 155 struct hash_entry *
 156 hash_newfunc (entry, table, string)
 157      struct hash_entry *entry;
 158      struct hash_table *table;
 159      const char *string;
 160 {
 161   if (entry == (struct hash_entry *) NULL)
 162     entry = ((struct hash_entry *)
 163              hash_allocate (table, sizeof (struct hash_entry)));
 164   return entry;
 165 }
 166
 167 /* Allocate space in a hash table.  */
 168
 169 PTR
 170 hash_allocate (table, size)
 171      struct hash_table *table;
 172      unsigned int size;
 173 {
 174   PTR ret;
 175
 176   ret = obstack_alloc (&table->memory, size);
 177   if (ret == NULL && size != 0)
 178     error ("no memory");
 179   return ret;
 180 }
 181
 182 /* Traverse a hash table.  */
 183
 184 void
 185 hash_traverse (table, func, info)
 186      struct hash_table *table;
 187      boolean (*func) PARAMS ((struct hash_entry *, PTR));
 188      PTR info;
 189 {
 190   unsigned int i;
 191
 192   for (i = 0; i < table->size; i++)
 193     {
 194       struct hash_entry *p;
 195
 196       for (p = table->table[i]; p != NULL; p = p->next)
 197         {
 198           if (! (*func) (p, info))
 199             return;
 200         }
 201     }
 202 }