OSDN Git Service

* hashtab.c: Include stdio.h.
[pf3gnuchains/gcc-fork.git] / libiberty / hashtab.c
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
38 #ifdef HAVE_STDLIB_H
39 #include <stdlib.h>
40 #endif
41
42 #include <stdio.h>
43
44 #include "libiberty.h"
45 #include "hashtab.h"
46
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. */
49
50 static int all_searches = 0;
51
52 /* The following variable is used for debugging. Its value is number
53    of collisions fixed for time of work with all hash tables. */
54
55 static int all_collisions = 0;
56
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
59    tables. */
60
61 static int all_expansions = 0;
62
63 /* This macro defines reserved value for empty table entry. */
64
65 #define EMPTY_ENTRY    NULL
66
67 /* This macro defines reserved value for table entry which contained
68    a deleted element. */
69
70 #define DELETED_ENTRY  ((void *) 1)
71
72 /* The following function returns the nearest prime number which is
73    greater than given source number. */
74
75 static unsigned long
76 higher_prime_number (number)
77      unsigned long number;
78 {
79   unsigned long i;
80
81   for (number = (number / 2) * 2 + 3;; number += 2)
82     {
83       for (i = 3; i * i <= number; i += 2)
84         if (number % i == 0)
85           break;
86       if (i * i > number)
87         return number;
88     }
89 }
90
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. */
95
96 hash_table_t
97 create_hash_table (size, hash_function, eq_function)
98      size_t size;
99      unsigned (*hash_function) PARAMS ((hash_table_entry_t));
100      int (*eq_function) PARAMS ((hash_table_entry_t, hash_table_entry_t));
101 {
102   hash_table_t result;
103
104   size = higher_prime_number (size);
105   result = (hash_table_t) xmalloc (sizeof (*result));
106   result->entries
107     = (hash_table_entry_t *) xmalloc (size * sizeof (hash_table_entry_t));
108   result->size = size;
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));
116   return result;
117 }
118
119 /* This function frees all memory allocated for given hash table.
120    Naturally the hash table must already exist. */
121
122 void
123 delete_hash_table (htab)
124      hash_table_t htab;
125 {
126   free (htab->entries);
127   free (htab);
128 }
129
130 /* This function clears all entries in the given hash table.  */
131
132 void
133 empty_hash_table (htab)
134      hash_table_t htab;
135 {
136   memset (htab->entries, 0, htab->size * sizeof (hash_table_entry_t));
137 }
138
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. */
144
145 static void
146 expand_hash_table (htab)
147      hash_table_t htab;
148 {
149   hash_table_t new_htab;
150   hash_table_entry_t *entry_ptr;
151   hash_table_entry_t *new_entry_ptr;
152
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;
156        entry_ptr++)
157     if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
158       {
159         new_entry_ptr = find_hash_table_entry (new_htab, *entry_ptr, 1);
160         *new_entry_ptr = (*entry_ptr);
161       }
162   free (htab->entries);
163   *htab = (*new_htab);
164   free (new_htab);
165 }
166
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'. */
178
179 hash_table_entry_t *
180 find_hash_table_entry (htab, element, reserve)
181      hash_table_t htab;
182      hash_table_entry_t element;
183      int reserve;
184 {
185   hash_table_entry_t *entry_ptr;
186   hash_table_entry_t *first_deleted_entry_ptr;
187   unsigned index, hash_value, secondary_hash_value;
188
189   if (htab->size * 3 <= htab->number_of_elements * 4)
190     {
191       all_expansions++;
192       expand_hash_table (htab);
193     }
194   hash_value = (*htab->hash_function) (element);
195   secondary_hash_value = 1 + hash_value % (htab->size - 2);
196   index = hash_value % htab->size;
197   htab->searches++;
198   all_searches++;
199   first_deleted_entry_ptr = NULL;
200   for (;;htab->collisions++, all_collisions++)
201     {
202       entry_ptr = htab->entries + index;
203       if (*entry_ptr == EMPTY_ENTRY)
204         {
205           if (reserve)
206             {
207               htab->number_of_elements++;
208               if (first_deleted_entry_ptr != NULL)
209                 {
210                   entry_ptr = first_deleted_entry_ptr;
211                   *entry_ptr = EMPTY_ENTRY;
212                 }
213             }
214           break;
215         }
216       else if (*entry_ptr != DELETED_ENTRY)
217         {
218           if ((*htab->eq_function) (*entry_ptr, element))
219             break;
220         }
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)
225         index -= htab->size;
226     }
227   return entry_ptr;
228 }
229
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). */
234
235 void
236 remove_element_from_hash_table_entry (htab, element)
237      hash_table_t htab;
238      hash_table_entry_t element;
239 {
240   hash_table_entry_t *entry_ptr;
241
242   entry_ptr = find_hash_table_entry (htab, element, 0);
243   *entry_ptr = DELETED_ENTRY;
244   htab->number_of_deleted_elements++;
245 }
246
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
249    do it again.  */
250
251 void
252 clear_hash_table_slot (htab, slot)
253      hash_table_t htab;
254      hash_table_entry_t *slot;
255 {
256   if (slot < htab->entries || slot >= htab->entries + htab->size
257       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
258     abort ();
259   *slot = DELETED_ENTRY;
260   htab->number_of_deleted_elements++;
261 }
262
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
266    argument.  */
267
268 void
269 traverse_hash_table (htab, callback, info)
270      hash_table_t htab;
271      int (*callback) PARAMS ((hash_table_entry_t, void *));
272      void *info;
273 {
274   hash_table_entry_t *entry_ptr;
275   for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
276        entry_ptr++)
277     if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
278       if (!callback (*entry_ptr, info))
279         break;
280 }
281
282 /* The following function returns current size of given hash table. */
283
284 size_t
285 hash_table_size (htab)
286      hash_table_t htab;
287 {
288   return htab->size;
289 }
290
291 /* The following function returns current number of elements in given
292    hash table. */
293
294 size_t
295 hash_table_elements_number (htab)
296      hash_table_t htab;
297 {
298   return htab->number_of_elements - htab->number_of_deleted_elements;
299 }
300
301 /* The following function returns number of percents of fixed
302    collisions during all work with given hash table. */
303
304 int
305 hash_table_collisions (htab)
306      hash_table_t htab;
307 {
308   int searches;
309
310   searches = htab->searches;
311   if (searches == 0)
312     searches++;
313   return htab->collisions * 100 / searches;
314 }
315
316 /* The following function returns number of percents of fixed
317    collisions during all work with all hash tables. */
318
319 int
320 all_hash_table_collisions ()
321 {
322   int searches;
323
324   searches = all_searches;
325   if (searches == 0)
326     searches++;
327   return all_collisions * 100 / searches;
328 }