gcc/hash.c

   1 /* CYGNUS LOCAL: whole file jason */
   2 /* hash.c -- hash table routines
   3    Copyright (C) 1993, 94 Free Software Foundation, Inc.
   4    Written by Steve Chamberlain <sac@cygnus.com>
   5
   6 This file was lifted from BFD, the Binary File Descriptor library.
   7
   8 This program is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2 of the License, or
  11 (at your option) any later version.
  12
  13 This program is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with this program; if not, write to the Free Software
  20 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  21
  22 #include "config.h"
  23 #include "hash.h"
  24 #include "obstack.h"
  25
  26 extern void free PARAMS ((PTR));
  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 #ifndef NULL
  38 #define NULL 0
  39 #endif
  40
  41 /* Create a new hash table, given a number of entries.  */
  42
  43 boolean
  44 hash_table_init_n (table, newfunc, size)
  45      struct hash_table *table;
  46      struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
  47                                                 struct hash_table *,
  48                                                 const char *));
  49      unsigned int size;
  50 {
  51   unsigned int alloc;
  52
  53   alloc = size * sizeof (struct hash_entry *);
  54   if (!obstack_begin (&table->memory, alloc))
  55     {
  56       error ("no memory");
  57       return false;
  58     }
  59   table->table = ((struct hash_entry **)
  60                   obstack_alloc (&table->memory, alloc));
  61   if (!table->table)
  62     {
  63       error ("no memory");
  64       return false;
  65     }
  66   memset ((PTR) table->table, 0, alloc);
  67   table->size = size;
  68   table->newfunc = newfunc;
  69   return true;
  70 }
  71
  72 /* Create a new hash table with the default number of entries.  */
  73
  74 boolean
  75 hash_table_init (table, newfunc)
  76      struct hash_table *table;
  77      struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
  78                                                 struct hash_table *,
  79                                                 const char *));
  80 {
  81   return hash_table_init_n (table, newfunc, 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 a string in a hash table.  */
  94
  95 struct hash_entry *
  96 hash_lookup (table, string, create, copy)
  97      struct hash_table *table;
  98      const char *string;
  99      boolean create;
 100      boolean copy;
 101 {
 102   register const unsigned char *s;
 103   register unsigned long hash;
 104   register unsigned int c;
 105   struct hash_entry *hashp;
 106   unsigned int len;
 107   unsigned int index;
 108
 109   hash = 0;
 110   len = 0;
 111   s = (const unsigned char *) string;
 112   while ((c = *s++) != '\0')
 113     {
 114       hash += c + (c << 17);
 115       hash ^= hash >> 2;
 116       ++len;
 117     }
 118   hash += len + (len << 17);
 119   hash ^= hash >> 2;
 120
 121   index = hash % table->size;
 122   for (hashp = table->table[index];
 123        hashp != (struct hash_entry *) NULL;
 124        hashp = hashp->next)
 125     {
 126       if (hashp->hash == hash
 127           && strcmp (hashp->string, string) == 0)
 128         return hashp;
 129     }
 130
 131   if (! create)
 132     return (struct hash_entry *) NULL;
 133
 134   hashp = (*table->newfunc) ((struct hash_entry *) NULL, table, string);
 135   if (hashp == (struct hash_entry *) NULL)
 136     return (struct hash_entry *) NULL;
 137   if (copy)
 138     {
 139       char *new;
 140
 141       new = (char *) obstack_alloc (&table->memory, len + 1);
 142       if (!new)
 143         {
 144           error ("no memory");
 145           return (struct hash_entry *) NULL;
 146         }
 147       strcpy (new, string);
 148       string = new;
 149     }
 150   hashp->string = string;
 151   hashp->hash = hash;
 152   hashp->next = table->table[index];
 153   table->table[index] = hashp;
 154
 155   return hashp;
 156 }
 157
 158 /* Base method for creating a new hash table entry.  */
 159
 160 /*ARGSUSED*/
 161 struct hash_entry *
 162 hash_newfunc (entry, table, string)
 163      struct hash_entry *entry;
 164      struct hash_table *table;
 165      const char *string;
 166 {
 167   if (entry == (struct hash_entry *) NULL)
 168     entry = ((struct hash_entry *)
 169              hash_allocate (table, sizeof (struct hash_entry)));
 170   return entry;
 171 }
 172
 173 /* Allocate space in a hash table.  */
 174
 175 PTR
 176 hash_allocate (table, size)
 177      struct hash_table *table;
 178      unsigned int size;
 179 {
 180   PTR ret;
 181
 182   ret = obstack_alloc (&table->memory, size);
 183   if (ret == NULL && size != 0)
 184     error ("no memory");
 185   return ret;
 186 }
 187
 188 /* Traverse a hash table.  */
 189
 190 void
 191 hash_traverse (table, func, info)
 192      struct hash_table *table;
 193      boolean (*func) PARAMS ((struct hash_entry *, PTR));
 194      PTR info;
 195 {
 196   unsigned int i;
 197
 198   for (i = 0; i < table->size; i++)
 199     {
 200       struct hash_entry *p;
 201
 202       for (p = table->table[i]; p != NULL; p = p->next)
 203         {
 204           if (! (*func) (p, info))
 205             return;
 206         }
 207     }
 208 }