1 /* An expandable hash tables datatype.
2 Copyright (C) 1999 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. */
44 #include "libiberty.h"
47 /* The following variable is used for debugging. Its value is number
48 of all calls of `find_hash_table_entry' for all hash tables. */
50 static int all_searches = 0;
52 /* The following variable is used for debugging. Its value is number
53 of collisions fixed for time of work with all hash tables. */
55 static int all_collisions = 0;
57 /* The following variable is used for debugging. Its value is number
58 of all table expansions fixed for time of work with all hash
61 static int all_expansions = 0;
63 /* This macro defines reserved value for empty table entry. */
65 #define EMPTY_ENTRY NULL
67 /* This macro defines reserved value for table entry which contained
70 #define DELETED_ENTRY ((void *) 1)
72 /* The following function returns the nearest prime number which is
73 greater than given source number. */
76 higher_prime_number (number)
81 for (number = (number / 2) * 2 + 3;; number += 2)
83 for (i = 3; i * i <= number; i += 2)
91 /* This function creates table with length slightly longer than given
92 source length. Created hash table is initiated as empty (all the
93 hash table entries are EMPTY_ENTRY). The function returns the
94 created hash table. */
97 create_hash_table (size, hash_function, eq_function)
99 unsigned (*hash_function) PARAMS ((hash_table_entry_t));
100 int (*eq_function) PARAMS ((hash_table_entry_t, hash_table_entry_t));
104 size = higher_prime_number (size);
105 result = (hash_table_t) xmalloc (sizeof (*result));
107 = (hash_table_entry_t *) xmalloc (size * sizeof (hash_table_entry_t));
109 result->hash_function = hash_function;
110 result->eq_function = eq_function;
111 result->number_of_elements = 0;
112 result->number_of_deleted_elements = 0;
113 result->searches = 0;
114 result->collisions = 0;
115 memset (result->entries, 0, size * sizeof (hash_table_entry_t));
119 /* This function frees all memory allocated for given hash table.
120 Naturally the hash table must already exist. */
123 delete_hash_table (htab)
126 free (htab->entries);
130 /* This function clears all entries in the given hash table. */
133 empty_hash_table (htab)
136 memset (htab->entries, 0, htab->size * sizeof (hash_table_entry_t));
139 /* The following function changes size of memory allocated for the
140 entries and repeatedly inserts the table elements. The occupancy
141 of the table after the call will be about 50%. Naturally the hash
142 table must already exist. Remember also that the place of the
143 table entries is changed. */
146 expand_hash_table (htab)
149 hash_table_t new_htab;
150 hash_table_entry_t *entry_ptr;
151 hash_table_entry_t *new_entry_ptr;
153 new_htab = create_hash_table (htab->number_of_elements * 2,
154 htab->hash_function, htab->eq_function);
155 for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
157 if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
159 new_entry_ptr = find_hash_table_entry (new_htab, *entry_ptr, 1);
160 *new_entry_ptr = (*entry_ptr);
162 free (htab->entries);
167 /* This function searches for hash table entry which contains element
168 equal to given value or empty entry in which given value can be
169 placed (if the element with given value does not exist in the
170 table). The function works in two regimes. The first regime is
171 used only for search. The second is used for search and
172 reservation empty entry for given value. The table is expanded if
173 occupancy (taking into accout also deleted elements) is more than
174 75%. Naturally the hash table must already exist. If reservation
175 flag is TRUE then the element with given value should be inserted
176 into the table entry before another call of
177 `find_hash_table_entry'. */
180 find_hash_table_entry (htab, element, reserve)
182 hash_table_entry_t element;
185 hash_table_entry_t *entry_ptr;
186 hash_table_entry_t *first_deleted_entry_ptr;
187 unsigned index, hash_value, secondary_hash_value;
189 if (htab->size * 3 <= htab->number_of_elements * 4)
192 expand_hash_table (htab);
194 hash_value = (*htab->hash_function) (element);
195 secondary_hash_value = 1 + hash_value % (htab->size - 2);
196 index = hash_value % htab->size;
199 first_deleted_entry_ptr = NULL;
200 for (;;htab->collisions++, all_collisions++)
202 entry_ptr = htab->entries + index;
203 if (*entry_ptr == EMPTY_ENTRY)
207 htab->number_of_elements++;
208 if (first_deleted_entry_ptr != NULL)
210 entry_ptr = first_deleted_entry_ptr;
211 *entry_ptr = EMPTY_ENTRY;
216 else if (*entry_ptr != DELETED_ENTRY)
218 if ((*htab->eq_function) (*entry_ptr, element))
221 else if (first_deleted_entry_ptr == NULL)
222 first_deleted_entry_ptr = entry_ptr;
223 index += secondary_hash_value;
224 if (index >= htab->size)
230 /* This function deletes element with given value from hash table.
231 The hash table entry value will be `DELETED_ENTRY' after the
232 function call. Naturally the hash table must already exist. Hash
233 table entry for given value should be not empty (or deleted). */
236 remove_element_from_hash_table_entry (htab, element)
238 hash_table_entry_t element;
240 hash_table_entry_t *entry_ptr;
242 entry_ptr = find_hash_table_entry (htab, element, 0);
243 *entry_ptr = DELETED_ENTRY;
244 htab->number_of_deleted_elements++;
247 /* This function clears a specified slot in a hash table.
248 It is useful when you've already done the lookup and don't want to
252 clear_hash_table_slot (htab, slot)
254 hash_table_entry_t *slot;
256 if (slot < htab->entries || slot >= htab->entries + htab->size
257 || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
259 *slot = DELETED_ENTRY;
260 htab->number_of_deleted_elements++;
263 /* This function scans over the entire hash table calling
264 CALLBACK for each live entry. If CALLBACK returns false,
265 the iteration stops. INFO is passed as CALLBACK's second
269 traverse_hash_table (htab, callback, info)
271 int (*callback) PARAMS ((hash_table_entry_t, void *));
274 hash_table_entry_t *entry_ptr;
275 for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
277 if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
278 if (!callback (*entry_ptr, info))
282 /* The following function returns current size of given hash table. */
285 hash_table_size (htab)
291 /* The following function returns current number of elements in given
295 hash_table_elements_number (htab)
298 return htab->number_of_elements - htab->number_of_deleted_elements;
301 /* The following function returns number of percents of fixed
302 collisions during all work with given hash table. */
305 hash_table_collisions (htab)
310 searches = htab->searches;
313 return htab->collisions * 100 / searches;
316 /* The following function returns number of percents of fixed
317 collisions during all work with all hash tables. */
320 all_hash_table_collisions ()
324 searches = all_searches;
327 return all_collisions * 100 / searches;