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