1/* hash.c -- hash table routines
2   Copyright (C) 1993, 1994, 1998 Free Software Foundation, Inc.
3   Written by Steve Chamberlain <sac@cygnus.com>
4
5This file was lifted from BFD, the Binary File Descriptor library.
6
7This program is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 2 of the License, or
10(at your option) any later version.
11
12This program is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with this program; if not, write to the Free Software
19Foundation, 59 Temple Place - Suite 330,
20Boston, 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
37boolean
38hash_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     boolean (*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  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  table->hash = hash;
66  table->comp = comp;
67  return true;
68}
69
70/* Create a new hash table with the default number of entries.  */
71
72boolean
73hash_table_init (table, newfunc, hash, comp)
74     struct hash_table *table;
75     struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
76					    struct hash_table *,
77					    hash_table_key));
78     unsigned long (*hash) PARAMS ((hash_table_key));
79     boolean (*comp) PARAMS ((hash_table_key, hash_table_key));
80{
81  return hash_table_init_n (table, newfunc, hash, comp, DEFAULT_SIZE);
82}
83
84/* Free a hash table.  */
85
86void
87hash_table_free (table)
88     struct hash_table *table;
89{
90  obstack_free (&table->memory, (PTR) NULL);
91}
92
93/* Look up KEY in TABLE.  If CREATE is non-NULL a new entry is
94   created if one does not previously exist.  */
95
96struct hash_entry *
97hash_lookup (table, key, create, copy)
98     struct hash_table *table;
99     hash_table_key key;
100     boolean create;
101     hash_table_key (*copy) PARAMS ((struct obstack* memory,
102				     hash_table_key key));
103{
104  register unsigned long hash;
105  struct hash_entry *hashp;
106  unsigned int index;
107
108  hash = (*table->hash)(key);
109
110  index = hash % table->size;
111  for (hashp = table->table[index];
112       hashp != (struct hash_entry *) NULL;
113       hashp = hashp->next)
114    {
115      if (hashp->hash == hash
116	  && (*table->comp)(hashp->key, key))
117	return hashp;
118    }
119
120  if (! create)
121    return (struct hash_entry *) NULL;
122
123  hashp = (*table->newfunc) ((struct hash_entry *) NULL, table, key);
124  if (hashp == (struct hash_entry *) NULL)
125    return (struct hash_entry *) NULL;
126  if (copy)
127    key = (*copy) (&table->memory, key);
128  hashp->key = key;
129  hashp->hash = hash;
130  hashp->next = table->table[index];
131  table->table[index] = hashp;
132
133  return hashp;
134}
135
136/* Base method for creating a new hash table entry.  */
137
138/*ARGSUSED*/
139struct hash_entry *
140hash_newfunc (entry, table, p)
141     struct hash_entry *entry;
142     struct hash_table *table;
143     hash_table_key p;
144{
145  if (entry == (struct hash_entry *) NULL)
146    entry = ((struct hash_entry *)
147	     hash_allocate (table, sizeof (struct hash_entry)));
148  return entry;
149}
150
151/* Allocate space in a hash table.  */
152
153PTR
154hash_allocate (table, size)
155     struct hash_table *table;
156     unsigned int size;
157{
158  PTR ret;
159
160  ret = obstack_alloc (&table->memory, size);
161  if (ret == NULL && size != 0)
162    error ("no memory");
163  return ret;
164}
165
166/* Traverse a hash table.  */
167
168void
169hash_traverse (table, func, info)
170     struct hash_table *table;
171     boolean (*func) PARAMS ((struct hash_entry *, hash_table_key));
172     PTR info;
173{
174  unsigned int i;
175
176  for (i = 0; i < table->size; i++)
177    {
178      struct hash_entry *p;
179
180      for (p = table->table[i]; p != NULL; p = p->next)
181	{
182	  if (! (*func) (p, info))
183	    return;
184	}
185    }
186}
187
188/* Hash a string.  Return a hash-code for the string.  */
189
190unsigned long
191string_hash (k)
192     hash_table_key k;
193{
194  const unsigned char *s;
195  unsigned long hash;
196  unsigned char c;
197  unsigned int len;
198
199  s = (const unsigned char *) k;
200  hash = 0;
201  len = 0;
202
203  while ((c = *s++) != '\0')
204    {
205      hash += c + (c << 17);
206      hash ^= hash >> 2;
207      ++len;
208    }
209  hash += len + (len << 17);
210  hash ^= hash >> 2;
211
212  return hash;
213}
214
215/* Compare two strings.  Return non-zero iff the two strings are
216   the same.  */
217
218boolean
219string_compare (k1, k2)
220     hash_table_key k1;
221     hash_table_key k2;
222{
223  return (strcmp ((char*) k1, (char*) k2) == 0);
224}
225
226/* Copy K to OBSTACK.  */
227
228hash_table_key
229string_copy (memory, k)
230     struct obstack* memory;
231     hash_table_key k;
232{
233  char *new;
234  char *string = (char*) k;
235
236  new = (char *) obstack_alloc (memory, strlen (string) + 1);
237  if (!new)
238    {
239      error ("no memory");
240      return NULL;
241    }
242  strcpy (new, string);
243
244  return new;
245}
246