1 /* An expandable hash tables datatype.
2 Copyright (C) 1999, 2000, 2001 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. */
34 #include <sys/types.h>
40 /* This macro defines reserved value for empty table entry. */
42 #define EMPTY_ENTRY ((void *) 0)
44 /* This macro defines reserved value for table entry which contained
47 #define DELETED_ENTRY ((void *) 1)
49 static unsigned long higher_prime_number (unsigned long);
50 static hashval_t
hash_pointer (const void *);
51 static int eq_pointer (const void *, const void *);
52 static int htab_expand (htab_t
);
53 static void **find_empty_slot_for_expand (htab_t
, hashval_t
);
55 /* At some point, we could make these be NULL, and modify the
56 hash-table routines to handle NULL specially; that would avoid
57 function-call overhead for the common case of hashing pointers. */
58 htab_hash htab_hash_pointer
= hash_pointer
;
59 htab_eq htab_eq_pointer
= eq_pointer
;
61 /* The following function returns a nearest prime number which is
62 greater than N, and near a power of two. */
65 higher_prime_number (n
)
68 /* These are primes that are near, but slightly smaller than, a
70 static unsigned long primes
[] = {
83 (unsigned long) 16381,
84 (unsigned long) 32749,
85 (unsigned long) 65521,
86 (unsigned long) 131071,
87 (unsigned long) 262139,
88 (unsigned long) 524287,
89 (unsigned long) 1048573,
90 (unsigned long) 2097143,
91 (unsigned long) 4194301,
92 (unsigned long) 8388593,
93 (unsigned long) 16777213,
94 (unsigned long) 33554393,
95 (unsigned long) 67108859,
96 (unsigned long) 134217689,
97 (unsigned long) 268435399,
98 (unsigned long) 536870909,
99 (unsigned long) 1073741789,
100 (unsigned long) 2147483647,
102 ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
105 unsigned long* low
= &primes
[0];
106 unsigned long* high
= &primes
[sizeof(primes
) / sizeof(primes
[0])];
110 unsigned long* mid
= low
+ (high
- low
) / 2;
117 /* If we've run out of primes, abort. */
120 fprintf (stderr
, "Cannot find prime bigger than %lu\n", n
);
127 /* Returns a hash code for P. */
133 return (hashval_t
) ((long)p
>> 3);
136 /* Returns non-zero if P1 and P2 are equal. */
146 /* This function creates table with length slightly longer than given
147 source length. The created hash table is initiated as empty (all the
148 hash table entries are EMPTY_ENTRY). The function returns the created
149 hash table. Memory allocation may fail; it may return NULL. */
152 htab_try_create (size
, hash_f
, eq_f
, del_f
)
160 size
= higher_prime_number (size
);
161 result
= (htab_t
) calloc (1, sizeof (struct htab
));
165 result
->entries
= (void **) calloc (size
, sizeof (void *));
166 if (result
->entries
== NULL
)
173 result
->hash_f
= hash_f
;
175 result
->del_f
= del_f
;
176 result
->return_allocation_failure
= 1;
180 /* This function frees all memory allocated for given hash table.
181 Naturally the hash table must already exist. */
190 for (i
= htab
->size
- 1; i
>= 0; i
--)
191 if (htab
->entries
[i
] != EMPTY_ENTRY
192 && htab
->entries
[i
] != DELETED_ENTRY
)
193 (*htab
->del_f
) (htab
->entries
[i
]);
195 free (htab
->entries
);
199 /* This function clears all entries in the given hash table. */
208 for (i
= htab
->size
- 1; i
>= 0; i
--)
209 if (htab
->entries
[i
] != EMPTY_ENTRY
210 && htab
->entries
[i
] != DELETED_ENTRY
)
211 (*htab
->del_f
) (htab
->entries
[i
]);
213 memset (htab
->entries
, 0, htab
->size
* sizeof (void *));
216 /* Similar to htab_find_slot, but without several unwanted side effects:
217 - Does not call htab->eq_f when it finds an existing entry.
218 - Does not change the count of elements/searches/collisions in the
220 This function also assumes there are no deleted entries in the table.
221 HASH is the hash value for the element to be inserted. */
224 find_empty_slot_for_expand (htab
, hash
)
228 size_t size
= htab
->size
;
229 hashval_t hash2
= 1 + hash
% (size
- 2);
230 unsigned int index
= hash
% size
;
234 void **slot
= htab
->entries
+ index
;
236 if (*slot
== EMPTY_ENTRY
)
238 else if (*slot
== DELETED_ENTRY
)
247 /* The following function changes size of memory allocated for the
248 entries and repeatedly inserts the table elements. The occupancy
249 of the table after the call will be about 50%. Naturally the hash
250 table must already exist. Remember also that the place of the
251 table entries is changed. If memory allocation failures are allowed,
252 this function will return zero, indicating that the table could not be
253 expanded. If all goes well, it will return a non-zero value. */
263 oentries
= htab
->entries
;
264 olimit
= oentries
+ htab
->size
;
266 htab
->size
= higher_prime_number (htab
->size
* 2);
268 if (htab
->return_allocation_failure
)
270 void **nentries
= (void **) calloc (htab
->size
, sizeof (void **));
271 if (nentries
== NULL
)
273 htab
->entries
= nentries
;
276 htab
->n_elements
-= htab
->n_deleted
;
284 if (x
!= EMPTY_ENTRY
&& x
!= DELETED_ENTRY
)
286 void **q
= find_empty_slot_for_expand (htab
, (*htab
->hash_f
) (x
));
299 /* This function searches for a hash table entry equal to the given
300 element. It cannot be used to insert or delete an element. */
303 htab_find_with_hash (htab
, element
, hash
)
305 const void * element
;
317 entry
= htab
->entries
[index
];
318 if (entry
== EMPTY_ENTRY
319 || (entry
!= DELETED_ENTRY
&& (*htab
->eq_f
) (entry
, element
)))
322 hash2
= 1 + hash
% (size
- 2);
331 entry
= htab
->entries
[index
];
332 if (entry
== EMPTY_ENTRY
333 || (entry
!= DELETED_ENTRY
&& (*htab
->eq_f
) (entry
, element
)))
338 /* Like htab_find_slot_with_hash, but compute the hash value from the
342 htab_find (htab
, element
)
344 const void * element
;
346 return htab_find_with_hash (htab
, element
, (*htab
->hash_f
) (element
));
349 /* This function searches for a hash table slot containing an entry
350 equal to the given element. To delete an entry, call this with
351 INSERT = 0, then call htab_clear_slot on the slot returned (possibly
352 after doing some checks). To insert an entry, call this with
353 INSERT = 1, then write the value you want into the returned slot.
354 When inserting an entry, NULL may be returned if memory allocation
358 htab_find_slot_with_hash (htab
, element
, hash
, insert
)
360 const void * element
;
362 enum insert_option insert
;
364 void **first_deleted_slot
;
369 if (insert
== INSERT
&& htab
->size
* 3 <= htab
->n_elements
* 4
370 && htab_expand (htab
) == 0)
374 hash2
= 1 + hash
% (size
- 2);
378 first_deleted_slot
= NULL
;
382 void * entry
= htab
->entries
[index
];
383 if (entry
== EMPTY_ENTRY
)
385 if (insert
== NO_INSERT
)
390 if (first_deleted_slot
)
392 *first_deleted_slot
= EMPTY_ENTRY
;
393 return first_deleted_slot
;
396 return &htab
->entries
[index
];
399 if (entry
== DELETED_ENTRY
)
401 if (!first_deleted_slot
)
402 first_deleted_slot
= &htab
->entries
[index
];
404 else if ((*htab
->eq_f
) (entry
, element
))
405 return &htab
->entries
[index
];
414 /* Like htab_find_slot_with_hash, but compute the hash value from the
418 htab_find_slot (htab
, element
, insert
)
420 const void * element
;
421 enum insert_option insert
;
423 return htab_find_slot_with_hash (htab
, element
, (*htab
->hash_f
) (element
),
427 /* This function deletes an element with the given value from hash
428 table. If there is no matching element in the hash table, this
429 function does nothing. */
432 htab_remove_elt (htab
, element
)
438 slot
= htab_find_slot (htab
, element
, NO_INSERT
);
439 if (*slot
== EMPTY_ENTRY
)
443 (*htab
->del_f
) (*slot
);
445 *slot
= DELETED_ENTRY
;
449 /* This function clears a specified slot in a hash table. It is
450 useful when you've already done the lookup and don't want to do it
454 htab_clear_slot (htab
, slot
)
458 if (slot
< htab
->entries
|| slot
>= htab
->entries
+ htab
->size
459 || *slot
== EMPTY_ENTRY
|| *slot
== DELETED_ENTRY
)
463 (*htab
->del_f
) (*slot
);
465 *slot
= DELETED_ENTRY
;
469 /* This function scans over the entire hash table calling
470 CALLBACK for each live entry. If CALLBACK returns false,
471 the iteration stops. INFO is passed as CALLBACK's second
475 htab_traverse (htab
, callback
, info
)
480 void **slot
= htab
->entries
;
481 void **limit
= slot
+ htab
->size
;
487 if (x
!= EMPTY_ENTRY
&& x
!= DELETED_ENTRY
)
488 if (!(*callback
) (slot
, info
))
491 while (++slot
< limit
);
494 /* Return the current size of given hash table. */
503 /* Return the current number of elements in given hash table. */
509 return htab
->n_elements
- htab
->n_deleted
;
512 /* Return the fraction of fixed collisions during all work with given
516 htab_collisions (htab
)
519 if (htab
->searches
== 0)
522 return (double) htab
->collisions
/ (double) htab
->searches
;