]>
Commit | Line | Data |
---|---|---|
aa32d841 | 1 | /* hash.c -- hash table routines |
400500c4 | 2 | Copyright (C) 1993, 1994, 1998, 2001 Free Software Foundation, Inc. |
aa32d841 JL |
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 | |
63fdf24a JL |
19 | Foundation, 59 Temple Place - Suite 330, |
20 | Boston, MA 02111-1307, USA. */ | |
aa32d841 JL |
21 | |
22 | #include "config.h" | |
b04cd507 | 23 | #include "system.h" |
aa32d841 JL |
24 | #include "hash.h" |
25 | #include "obstack.h" | |
10f0ad3d | 26 | #include "toplev.h" |
aa32d841 | 27 | |
aa32d841 JL |
28 | /* Obstack allocation and deallocation routines. */ |
29 | #define obstack_chunk_alloc xmalloc | |
30 | #define obstack_chunk_free free | |
31 | ||
aa32d841 | 32 | /* The default number of entries to use when creating a hash table. */ |
400500c4 | 33 | #define DEFAULT_SIZE 1009 |
aa32d841 | 34 | |
aa32d841 JL |
35 | /* Create a new hash table, given a number of entries. */ |
36 | ||
400500c4 | 37 | void |
a87ec9e6 | 38 | hash_table_init_n (table, newfunc, hash, comp, size) |
aa32d841 JL |
39 | struct hash_table *table; |
40 | struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *, | |
a87ec9e6 MM |
41 | struct hash_table *, |
42 | hash_table_key)); | |
d25a233e | 43 | unsigned long (*hash) PARAMS ((hash_table_key)); |
d6edb99e | 44 | bool (*comp) PARAMS ((hash_table_key, hash_table_key)); |
aa32d841 JL |
45 | unsigned int size; |
46 | { | |
47 | unsigned int alloc; | |
48 | ||
49 | alloc = size * sizeof (struct hash_entry *); | |
400500c4 | 50 | obstack_begin (&table->memory, alloc); |
aa32d841 JL |
51 | table->table = ((struct hash_entry **) |
52 | obstack_alloc (&table->memory, alloc)); | |
aa32d841 JL |
53 | memset ((PTR) table->table, 0, alloc); |
54 | table->size = size; | |
55 | table->newfunc = newfunc; | |
a87ec9e6 MM |
56 | table->hash = hash; |
57 | table->comp = comp; | |
aa32d841 JL |
58 | } |
59 | ||
60 | /* Create a new hash table with the default number of entries. */ | |
61 | ||
400500c4 | 62 | void |
a87ec9e6 | 63 | hash_table_init (table, newfunc, hash, comp) |
aa32d841 JL |
64 | struct hash_table *table; |
65 | struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *, | |
a87ec9e6 MM |
66 | struct hash_table *, |
67 | hash_table_key)); | |
68 | unsigned long (*hash) PARAMS ((hash_table_key)); | |
d6edb99e | 69 | bool (*comp) PARAMS ((hash_table_key, hash_table_key)); |
aa32d841 | 70 | { |
400500c4 | 71 | hash_table_init_n (table, newfunc, hash, comp, DEFAULT_SIZE); |
aa32d841 JL |
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 | ||
a87ec9e6 MM |
83 | /* Look up KEY in TABLE. If CREATE is non-NULL a new entry is |
84 | created if one does not previously exist. */ | |
aa32d841 JL |
85 | |
86 | struct hash_entry * | |
a87ec9e6 | 87 | hash_lookup (table, key, create, copy) |
aa32d841 | 88 | struct hash_table *table; |
a87ec9e6 | 89 | hash_table_key key; |
37a58036 | 90 | int create; |
a87ec9e6 MM |
91 | hash_table_key (*copy) PARAMS ((struct obstack* memory, |
92 | hash_table_key key)); | |
aa32d841 | 93 | { |
b3694847 | 94 | unsigned long hash; |
aa32d841 | 95 | struct hash_entry *hashp; |
aa32d841 JL |
96 | unsigned int index; |
97 | ||
a87ec9e6 | 98 | hash = (*table->hash)(key); |
aa32d841 JL |
99 | |
100 | index = hash % table->size; | |
400500c4 RK |
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; | |
aa32d841 JL |
105 | |
106 | if (! create) | |
400500c4 | 107 | return 0; |
aa32d841 | 108 | |
a87ec9e6 | 109 | hashp = (*table->newfunc) ((struct hash_entry *) NULL, table, key); |
400500c4 RK |
110 | if (hashp == 0) |
111 | return 0; | |
112 | ||
aa32d841 | 113 | if (copy) |
a87ec9e6 | 114 | key = (*copy) (&table->memory, key); |
400500c4 | 115 | |
a87ec9e6 | 116 | hashp->key = key; |
aa32d841 JL |
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 | ||
aa32d841 | 126 | struct hash_entry * |
a87ec9e6 | 127 | hash_newfunc (entry, table, p) |
aa32d841 JL |
128 | struct hash_entry *entry; |
129 | struct hash_table *table; | |
272df862 | 130 | hash_table_key p ATTRIBUTE_UNUSED; |
aa32d841 | 131 | { |
400500c4 | 132 | if (entry == 0) |
aa32d841 JL |
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 | { | |
400500c4 | 145 | return obstack_alloc (&table->memory, size); |
aa32d841 JL |
146 | } |
147 | ||
148 | /* Traverse a hash table. */ | |
149 | ||
150 | void | |
151 | hash_traverse (table, func, info) | |
152 | struct hash_table *table; | |
d6edb99e | 153 | bool (*func) PARAMS ((struct hash_entry *, hash_table_key)); |
aa32d841 JL |
154 | PTR info; |
155 | { | |
156 | unsigned int i; | |
400500c4 | 157 | struct hash_entry *p; |
aa32d841 JL |
158 | |
159 | for (i = 0; i < table->size; i++) | |
400500c4 RK |
160 | for (p = table->table[i]; p != 0; p = p->next) |
161 | if (! (*func) (p, info)) | |
162 | return; | |
aa32d841 | 163 | } |
a87ec9e6 MM |
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 | } | |
400500c4 | 186 | |
a87ec9e6 MM |
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 | ||
d6edb99e | 196 | bool |
a87ec9e6 MM |
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) | |
400500c4 | 208 | struct obstack *memory; |
a87ec9e6 MM |
209 | hash_table_key k; |
210 | { | |
211 | char *new; | |
400500c4 | 212 | char *string = (char *) k; |
a87ec9e6 MM |
213 | |
214 | new = (char *) obstack_alloc (memory, strlen (string) + 1); | |
a87ec9e6 MM |
215 | strcpy (new, string); |
216 | ||
217 | return new; | |
218 | } |