1 /* An expandable hash tables datatype.
2 Copyright (C) 1999, 2000 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov (vmakarov@cygnus.com).
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.
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.
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. */
21 /* This package implements basic hash table functionality. It is possible
22 to search for an entry, create an entry and destroy an entry.
24 Elements in the table are generic pointers.
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.
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. */
38 #include <sys/types.h>
46 #include "libiberty.h"
49 /* This macro defines reserved value for empty table entry. */
51 #define EMPTY_ENTRY ((void *) 0)
53 /* This macro defines reserved value for table entry which contained
56 #define DELETED_ENTRY ((void *) 1)
58 static unsigned long higher_prime_number PARAMS ((unsigned long));
59 static hashval_t hash_pointer PARAMS ((const void *));
60 static int eq_pointer PARAMS ((const void *, const void *));
62 /* At some point, we could make these be NULL, and modify the
63 hash-table routines to handle NULL specially; that would avoid
64 function-call overhead for the common case of hashing pointers. */
65 htab_hash htab_hash_pointer = hash_pointer;
66 htab_eq htab_eq_pointer = eq_pointer;
68 /* The following function returns the nearest prime number which is
69 greater than a given source number, N. */
72 higher_prime_number (n)
77 /* Ensure we have a larger number and then force to odd. */
81 /* All odd numbers < 9 are prime. */
85 /* Otherwise find the next prime using a sieve. */
89 for (i = 3; i * i <= n; i += 2)
99 /* Returns a hash code for P. */
105 return (hashval_t) p;
108 /* Returns non-zero if P1 and P2 are equal. */
118 /* This function creates table with length slightly longer than given
119 source length. Created hash table is initiated as empty (all the
120 hash table entries are EMPTY_ENTRY). The function returns the
121 created hash table. */
124 htab_create (size, hash_f, eq_f, del_f)
132 size = higher_prime_number (size);
133 result = (htab_t) xcalloc (1, sizeof (struct htab));
134 result->entries = (void **) xcalloc (size, sizeof (void *));
136 result->hash_f = hash_f;
138 result->del_f = del_f;
142 /* This function frees all memory allocated for given hash table.
143 Naturally the hash table must already exist. */
152 for (i = htab->size - 1; i >= 0; i--)
153 if (htab->entries[i] != EMPTY_ENTRY
154 && htab->entries[i] != DELETED_ENTRY)
155 (*htab->del_f) (htab->entries[i]);
157 free (htab->entries);
161 /* This function clears all entries in the given hash table. */
170 for (i = htab->size - 1; i >= 0; i--)
171 if (htab->entries[i] != EMPTY_ENTRY
172 && htab->entries[i] != DELETED_ENTRY)
173 (*htab->del_f) (htab->entries[i]);
175 memset (htab->entries, 0, htab->size * sizeof (void *));
178 /* Similar to htab_find_slot, but without several unwanted side effects:
179 - Does not call htab->eq_f when it finds an existing entry.
180 - Does not change the count of elements/searches/collisions in the
182 This function also assumes there are no deleted entries in the table.
183 HASH is the hash value for the element to be inserted. */
186 find_empty_slot_for_expand (htab, hash)
190 size_t size = htab->size;
191 hashval_t hash2 = 1 + hash % (size - 2);
192 unsigned int index = hash % size;
196 void **slot = htab->entries + index;
198 if (*slot == EMPTY_ENTRY)
200 else if (*slot == DELETED_ENTRY)
209 /* The following function changes size of memory allocated for the
210 entries and repeatedly inserts the table elements. The occupancy
211 of the table after the call will be about 50%. Naturally the hash
212 table must already exist. Remember also that the place of the
213 table entries is changed. */
223 oentries = htab->entries;
224 olimit = oentries + htab->size;
226 htab->size = higher_prime_number (htab->size * 2);
227 htab->entries = (void **) xcalloc (htab->size, sizeof (void **));
229 htab->n_elements -= htab->n_deleted;
237 if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
239 void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
251 /* This function searches for a hash table entry equal to the given
252 element. It cannot be used to insert or delete an element. */
255 htab_find_with_hash (htab, element, hash)
269 entry = htab->entries[index];
270 if (entry == EMPTY_ENTRY
271 || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
274 hash2 = 1 + hash % (size - 2);
283 entry = htab->entries[index];
284 if (entry == EMPTY_ENTRY
285 || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
290 /* Like htab_find_slot_with_hash, but compute the hash value from the
294 htab_find (htab, element)
298 return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
301 /* This function searches for a hash table slot containing an entry
302 equal to the given element. To delete an entry, call this with
303 INSERT = 0, then call htab_clear_slot on the slot returned (possibly
304 after doing some checks). To insert an entry, call this with
305 INSERT = 1, then write the value you want into the returned slot. */
308 htab_find_slot_with_hash (htab, element, hash, insert)
312 enum insert_option insert;
314 void **first_deleted_slot;
319 if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4)
323 hash2 = 1 + hash % (size - 2);
327 first_deleted_slot = NULL;
331 void *entry = htab->entries[index];
332 if (entry == EMPTY_ENTRY)
334 if (insert == NO_INSERT)
339 if (first_deleted_slot)
341 *first_deleted_slot = EMPTY_ENTRY;
342 return first_deleted_slot;
345 return &htab->entries[index];
348 if (entry == DELETED_ENTRY)
350 if (!first_deleted_slot)
351 first_deleted_slot = &htab->entries[index];
353 else if ((*htab->eq_f) (entry, element))
354 return &htab->entries[index];
363 /* Like htab_find_slot_with_hash, but compute the hash value from the
367 htab_find_slot (htab, element, insert)
370 enum insert_option insert;
372 return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
376 /* This function deletes an element with the given value from hash
377 table. If there is no matching element in the hash table, this
378 function does nothing. */
381 htab_remove_elt (htab, element)
387 slot = htab_find_slot (htab, element, NO_INSERT);
388 if (*slot == EMPTY_ENTRY)
392 (*htab->del_f) (*slot);
394 *slot = DELETED_ENTRY;
398 /* This function clears a specified slot in a hash table. It is
399 useful when you've already done the lookup and don't want to do it
403 htab_clear_slot (htab, slot)
407 if (slot < htab->entries || slot >= htab->entries + htab->size
408 || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
412 (*htab->del_f) (*slot);
414 *slot = DELETED_ENTRY;
418 /* This function scans over the entire hash table calling
419 CALLBACK for each live entry. If CALLBACK returns false,
420 the iteration stops. INFO is passed as CALLBACK's second
424 htab_traverse (htab, callback, info)
429 void **slot = htab->entries;
430 void **limit = slot + htab->size;
436 if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
437 if (!(*callback) (slot, info))
440 while (++slot < limit);
443 /* Return the current size of given hash table. */
452 /* Return the current number of elements in given hash table. */
458 return htab->n_elements - htab->n_deleted;
461 /* Return the fraction of fixed collisions during all work with given
465 htab_collisions (htab)
468 if (htab->searches == 0)
471 return (double) htab->collisions / (double) htab->searches;