]>
Commit | Line | Data |
---|---|---|
a2f945c6 VM |
1 | /* An expandable hash tables datatype. |
2 | Copyright (C) 1999 Free Software Foundation, Inc. | |
3 | Contributed by Vladimir Makarov (vmakarov@cygnus.com). | |
4 | ||
5 | This file is part of the libiberty library. | |
6 | Libiberty is free software; you can redistribute it and/or | |
7 | modify it under the terms of the GNU Library General Public | |
8 | License as published by the Free Software Foundation; either | |
9 | version 2 of the License, or (at your option) any later version. | |
10 | ||
11 | Libiberty is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | Library General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU Library General Public | |
17 | License along with libiberty; see the file COPYING.LIB. If | |
18 | not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
19 | Boston, MA 02111-1307, USA. */ | |
20 | ||
21 | /* This package implements basic hash table functionality. It is possible | |
22 | to search for an entry, create an entry and destroy an entry. | |
23 | ||
24 | Elements in the table are generic pointers. | |
25 | ||
26 | The size of the table is not fixed; if the occupancy of the table | |
27 | grows too high the hash table will be expanded. | |
28 | ||
29 | The abstract data implementation is based on generalized Algorithm D | |
30 | from Knuth's book "The art of computer programming". Hash table is | |
31 | expanded by creation of new hash table and transferring elements from | |
32 | the old table to the new table. */ | |
33 | ||
34 | #ifdef HAVE_CONFIG_H | |
35 | #include "config.h" | |
36 | #endif | |
37 | ||
6de9b8ff PDM |
38 | #include <sys/types.h> |
39 | ||
a2f945c6 VM |
40 | #ifdef HAVE_STDLIB_H |
41 | #include <stdlib.h> | |
42 | #endif | |
43 | ||
36dd3a44 JL |
44 | #include <stdio.h> |
45 | ||
a2f945c6 VM |
46 | #include "libiberty.h" |
47 | #include "hashtab.h" | |
48 | ||
a2f945c6 VM |
49 | /* This macro defines reserved value for empty table entry. */ |
50 | ||
5194cf08 | 51 | #define EMPTY_ENTRY ((void *) 0) |
a2f945c6 VM |
52 | |
53 | /* This macro defines reserved value for table entry which contained | |
54 | a deleted element. */ | |
55 | ||
56 | #define DELETED_ENTRY ((void *) 1) | |
57 | ||
58 | /* The following function returns the nearest prime number which is | |
59 | greater than given source number. */ | |
60 | ||
61 | static unsigned long | |
5194cf08 ZW |
62 | higher_prime_number (n) |
63 | unsigned long n; | |
a2f945c6 VM |
64 | { |
65 | unsigned long i; | |
66 | ||
5194cf08 ZW |
67 | n |= 0x01; /* Force N to be odd. */ |
68 | if (n < 9) | |
69 | return n; /* All odd numbers < 9 are prime. */ | |
70 | ||
71 | next: | |
72 | n += 2; | |
73 | i = 3; | |
74 | do | |
a2f945c6 | 75 | { |
5194cf08 ZW |
76 | if (n % i == 0) |
77 | goto next; | |
78 | i += 2; | |
a2f945c6 | 79 | } |
5194cf08 ZW |
80 | while ((i * i) <= n); |
81 | ||
82 | return n; | |
a2f945c6 VM |
83 | } |
84 | ||
85 | /* This function creates table with length slightly longer than given | |
86 | source length. Created hash table is initiated as empty (all the | |
87 | hash table entries are EMPTY_ENTRY). The function returns the | |
88 | created hash table. */ | |
89 | ||
5194cf08 ZW |
90 | htab_t |
91 | htab_create (size, hash_f, eq_f) | |
a2f945c6 | 92 | size_t size; |
5194cf08 ZW |
93 | htab_hash hash_f; |
94 | htab_eq eq_f; | |
a2f945c6 | 95 | { |
5194cf08 | 96 | htab_t result; |
a2f945c6 VM |
97 | |
98 | size = higher_prime_number (size); | |
5194cf08 ZW |
99 | result = (htab_t) xcalloc (1, sizeof (struct htab)); |
100 | result->entries = (void **) xcalloc (size, sizeof (void *)); | |
a2f945c6 | 101 | result->size = size; |
5194cf08 ZW |
102 | result->hash_f = hash_f; |
103 | result->eq_f = eq_f; | |
a2f945c6 VM |
104 | return result; |
105 | } | |
106 | ||
107 | /* This function frees all memory allocated for given hash table. | |
108 | Naturally the hash table must already exist. */ | |
109 | ||
110 | void | |
5194cf08 ZW |
111 | htab_delete (htab) |
112 | htab_t htab; | |
a2f945c6 VM |
113 | { |
114 | free (htab->entries); | |
115 | free (htab); | |
116 | } | |
117 | ||
118 | /* This function clears all entries in the given hash table. */ | |
119 | ||
120 | void | |
5194cf08 ZW |
121 | htab_empty (htab) |
122 | htab_t htab; | |
a2f945c6 | 123 | { |
5194cf08 | 124 | memset (htab->entries, 0, htab->size * sizeof (void *)); |
a2f945c6 VM |
125 | } |
126 | ||
127 | /* The following function changes size of memory allocated for the | |
128 | entries and repeatedly inserts the table elements. The occupancy | |
129 | of the table after the call will be about 50%. Naturally the hash | |
130 | table must already exist. Remember also that the place of the | |
131 | table entries is changed. */ | |
132 | ||
133 | static void | |
5194cf08 ZW |
134 | htab_expand (htab) |
135 | htab_t htab; | |
a2f945c6 | 136 | { |
5194cf08 ZW |
137 | void **oentries; |
138 | void **olimit; | |
139 | void **p; | |
140 | ||
141 | oentries = htab->entries; | |
142 | olimit = oentries + htab->size; | |
143 | ||
144 | htab->size = higher_prime_number (htab->size * 2); | |
145 | htab->entries = xcalloc (htab->size, sizeof (void **)); | |
146 | ||
147 | htab->n_elements -= htab->n_deleted; | |
148 | htab->n_deleted = 0; | |
149 | ||
150 | p = oentries; | |
151 | do | |
152 | { | |
153 | void *x = *p; | |
154 | if (x != EMPTY_ENTRY && x != DELETED_ENTRY) | |
155 | { | |
156 | void **q = htab_find_slot (htab, x, 1); | |
157 | *q = x; | |
158 | } | |
159 | p++; | |
160 | } | |
161 | while (p < olimit); | |
162 | free (oentries); | |
a2f945c6 VM |
163 | } |
164 | ||
5194cf08 ZW |
165 | /* This function searches for a hash table entry equal to the given |
166 | element. It cannot be used to insert or delete an element. */ | |
167 | ||
168 | void * | |
169 | htab_find (htab, element) | |
170 | htab_t htab; | |
171 | const void *element; | |
a2f945c6 | 172 | { |
5194cf08 ZW |
173 | unsigned int index, hash, hash2; |
174 | size_t size; | |
175 | ||
176 | htab->searches++; | |
177 | size = htab->size; | |
178 | hash = (*htab->hash_f) (element); | |
179 | hash2 = 1 + hash % (size - 2); | |
180 | index = hash % size; | |
a2f945c6 | 181 | |
5194cf08 | 182 | for (;;) |
a2f945c6 | 183 | { |
5194cf08 ZW |
184 | void *entry = htab->entries[index]; |
185 | if (entry == EMPTY_ENTRY) | |
186 | return NULL; | |
187 | else if (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)) | |
188 | return entry; | |
189 | ||
190 | htab->collisions++; | |
191 | index += hash2; | |
192 | if (index >= size) | |
193 | index -= size; | |
a2f945c6 | 194 | } |
5194cf08 ZW |
195 | } |
196 | ||
197 | /* This function searches for a hash table slot containing an entry | |
198 | equal to the given element. To delete an entry, call this with | |
199 | INSERT = 0, then call htab_clear_slot on the slot returned (possibly | |
200 | after doing some checks). To insert an entry, call this with | |
201 | INSERT = 1, then write the value you want into the returned slot. */ | |
202 | ||
203 | void ** | |
204 | htab_find_slot (htab, element, insert) | |
205 | htab_t htab; | |
206 | const void *element; | |
207 | int insert; | |
208 | { | |
209 | void **first_deleted_slot; | |
210 | unsigned int index, hash, hash2; | |
211 | size_t size; | |
212 | ||
213 | if (insert && htab->size * 3 <= htab->n_elements * 4) | |
214 | htab_expand (htab); | |
215 | ||
216 | size = htab->size; | |
217 | hash = (*htab->hash_f) (element); | |
218 | hash2 = 1 + hash % (size - 2); | |
219 | index = hash % size; | |
220 | ||
a2f945c6 | 221 | htab->searches++; |
5194cf08 ZW |
222 | first_deleted_slot = NULL; |
223 | ||
224 | for (;;) | |
a2f945c6 | 225 | { |
5194cf08 ZW |
226 | void *entry = htab->entries[index]; |
227 | if (entry == EMPTY_ENTRY) | |
228 | { | |
229 | if (!insert) | |
230 | return NULL; | |
231 | ||
232 | htab->n_elements++; | |
233 | ||
234 | if (first_deleted_slot) | |
a2f945c6 | 235 | { |
5194cf08 ZW |
236 | *first_deleted_slot = EMPTY_ENTRY; |
237 | return first_deleted_slot; | |
a2f945c6 | 238 | } |
5194cf08 ZW |
239 | |
240 | return &htab->entries[index]; | |
241 | } | |
242 | ||
243 | if (entry == DELETED_ENTRY) | |
244 | { | |
245 | if (!first_deleted_slot) | |
246 | first_deleted_slot = &htab->entries[index]; | |
247 | } | |
248 | else | |
249 | { | |
250 | if ((*htab->eq_f) (entry, element)) | |
251 | return &htab->entries[index]; | |
252 | } | |
253 | ||
254 | htab->collisions++; | |
255 | index += hash2; | |
256 | if (index >= size) | |
257 | index -= size; | |
a2f945c6 | 258 | } |
a2f945c6 VM |
259 | } |
260 | ||
5194cf08 ZW |
261 | /* This function deletes an element with the given value from hash |
262 | table. If there is no matching element in the hash table, this | |
263 | function does nothing. */ | |
a2f945c6 VM |
264 | |
265 | void | |
5194cf08 ZW |
266 | htab_remove_elt (htab, element) |
267 | htab_t htab; | |
268 | void *element; | |
a2f945c6 | 269 | { |
5194cf08 | 270 | void **slot; |
a2f945c6 | 271 | |
5194cf08 ZW |
272 | slot = htab_find_slot (htab, element, 0); |
273 | if (*slot == EMPTY_ENTRY) | |
274 | return; | |
275 | ||
276 | *slot = DELETED_ENTRY; | |
277 | htab->n_deleted++; | |
a2f945c6 VM |
278 | } |
279 | ||
5194cf08 ZW |
280 | /* This function clears a specified slot in a hash table. It is |
281 | useful when you've already done the lookup and don't want to do it | |
282 | again. */ | |
ed38f5d5 ZW |
283 | |
284 | void | |
5194cf08 ZW |
285 | htab_clear_slot (htab, slot) |
286 | htab_t htab; | |
287 | void **slot; | |
ed38f5d5 ZW |
288 | { |
289 | if (slot < htab->entries || slot >= htab->entries + htab->size | |
290 | || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY) | |
291 | abort (); | |
292 | *slot = DELETED_ENTRY; | |
5194cf08 | 293 | htab->n_deleted++; |
ed38f5d5 ZW |
294 | } |
295 | ||
296 | /* This function scans over the entire hash table calling | |
297 | CALLBACK for each live entry. If CALLBACK returns false, | |
298 | the iteration stops. INFO is passed as CALLBACK's second | |
299 | argument. */ | |
300 | ||
301 | void | |
5194cf08 ZW |
302 | htab_traverse (htab, callback, info) |
303 | htab_t htab; | |
304 | htab_trav callback; | |
ed38f5d5 ZW |
305 | void *info; |
306 | { | |
5194cf08 ZW |
307 | void **slot, **limit; |
308 | slot = htab->entries; | |
309 | limit = slot + htab->size; | |
310 | do | |
311 | { | |
312 | void *x = *slot; | |
313 | if (x != EMPTY_ENTRY && x != DELETED_ENTRY) | |
314 | if (!(*callback) (x, info)) | |
315 | break; | |
316 | } | |
317 | while (++slot < limit); | |
ed38f5d5 ZW |
318 | } |
319 | ||
a2f945c6 VM |
320 | /* The following function returns current size of given hash table. */ |
321 | ||
322 | size_t | |
5194cf08 ZW |
323 | htab_size (htab) |
324 | htab_t htab; | |
a2f945c6 VM |
325 | { |
326 | return htab->size; | |
327 | } | |
328 | ||
329 | /* The following function returns current number of elements in given | |
330 | hash table. */ | |
331 | ||
332 | size_t | |
5194cf08 ZW |
333 | htab_elements (htab) |
334 | htab_t htab; | |
a2f945c6 | 335 | { |
5194cf08 | 336 | return htab->n_elements - htab->n_deleted; |
a2f945c6 VM |
337 | } |
338 | ||
339 | /* The following function returns number of percents of fixed | |
340 | collisions during all work with given hash table. */ | |
341 | ||
5194cf08 ZW |
342 | double |
343 | htab_collisions (htab) | |
344 | htab_t htab; | |
a2f945c6 VM |
345 | { |
346 | int searches; | |
347 | ||
348 | searches = htab->searches; | |
349 | if (searches == 0) | |
5194cf08 ZW |
350 | return 0.0; |
351 | return (double)htab->collisions / (double)searches; | |
a2f945c6 | 352 | } |