1 /* hash.c -- hash table routines
2 Copyright (C) 1993, 1994, 1998 Free Software Foundation, Inc.
3 Written by Steve Chamberlain <sac@cygnus.com>
5 This file was lifted from BFD, the Binary File Descriptor library.
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.
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.
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. */
28 /* Obstack allocation and deallocation routines. */
29 #define obstack_chunk_alloc xmalloc
30 #define obstack_chunk_free free
32 /* The default number of entries to use when creating a hash table. */
33 #define DEFAULT_SIZE (1009)
35 /* Create a new hash table, given a number of entries. */
38 hash_table_init_n (table, newfunc, hash, comp, size)
39 struct hash_table *table;
40 struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
43 unsigned long (*hash) PARAMS ((hash_table_key));
44 boolean (*comp) PARAMS ((hash_table_key, hash_table_key));
49 alloc = size * sizeof (struct hash_entry *);
50 if (!obstack_begin (&table->memory, alloc))
55 table->table = ((struct hash_entry **)
56 obstack_alloc (&table->memory, alloc));
62 memset ((PTR) table->table, 0, alloc);
64 table->newfunc = newfunc;
70 /* Create a new hash table with the default number of entries. */
73 hash_table_init (table, newfunc, hash, comp)
74 struct hash_table *table;
75 struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
78 unsigned long (*hash) PARAMS ((hash_table_key));
79 boolean (*comp) PARAMS ((hash_table_key, hash_table_key));
81 return hash_table_init_n (table, newfunc, hash, comp, DEFAULT_SIZE);
84 /* Free a hash table. */
87 hash_table_free (table)
88 struct hash_table *table;
90 obstack_free (&table->memory, (PTR) NULL);
93 /* Look up KEY in TABLE. If CREATE is non-NULL a new entry is
94 created if one does not previously exist. */
97 hash_lookup (table, key, create, copy)
98 struct hash_table *table;
101 hash_table_key (*copy) PARAMS ((struct obstack* memory,
102 hash_table_key key));
104 register unsigned long hash;
105 struct hash_entry *hashp;
108 hash = (*table->hash)(key);
110 index = hash % table->size;
111 for (hashp = table->table[index];
112 hashp != (struct hash_entry *) NULL;
115 if (hashp->hash == hash
116 && (*table->comp)(hashp->key, key))
121 return (struct hash_entry *) NULL;
123 hashp = (*table->newfunc) ((struct hash_entry *) NULL, table, key);
124 if (hashp == (struct hash_entry *) NULL)
125 return (struct hash_entry *) NULL;
127 key = (*copy) (&table->memory, key);
130 hashp->next = table->table[index];
131 table->table[index] = hashp;
136 /* Base method for creating a new hash table entry. */
140 hash_newfunc (entry, table, p)
141 struct hash_entry *entry;
142 struct hash_table *table;
143 hash_table_key p ATTRIBUTE_UNUSED;
145 if (entry == (struct hash_entry *) NULL)
146 entry = ((struct hash_entry *)
147 hash_allocate (table, sizeof (struct hash_entry)));
151 /* Allocate space in a hash table. */
154 hash_allocate (table, size)
155 struct hash_table *table;
160 ret = obstack_alloc (&table->memory, size);
161 if (ret == NULL && size != 0)
166 /* Traverse a hash table. */
169 hash_traverse (table, func, info)
170 struct hash_table *table;
171 boolean (*func) PARAMS ((struct hash_entry *, hash_table_key));
176 for (i = 0; i < table->size; i++)
178 struct hash_entry *p;
180 for (p = table->table[i]; p != NULL; p = p->next)
182 if (! (*func) (p, info))
188 /* Hash a string. Return a hash-code for the string. */
194 const unsigned char *s;
199 s = (const unsigned char *) k;
203 while ((c = *s++) != '\0')
205 hash += c + (c << 17);
209 hash += len + (len << 17);
215 /* Compare two strings. Return non-zero iff the two strings are
219 string_compare (k1, k2)
223 return (strcmp ((char*) k1, (char*) k2) == 0);
226 /* Copy K to OBSTACK. */
229 string_copy (memory, k)
230 struct obstack* memory;
234 char *string = (char*) k;
236 new = (char *) obstack_alloc (memory, strlen (string) + 1);
242 strcpy (new, string);