gcc/hash.c

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