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