Bug Summary

File:tools/hashtab.c
Warning:line 270, column 35
Result of 'calloc' is converted to a pointer of type 'void *', which is incompatible with sizeof operand type 'void **'

Annotated Source Code

1/* An expandable hash tables datatype.
2 Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov (vmakarov@cygnus.com).
4
5This file is part of the libiberty library.
6Libiberty is free software; you can redistribute it and/or
7modify it under the terms of the GNU Library General Public
8License as published by the Free Software Foundation; either
9version 2 of the License, or (at your option) any later version.
10
11Libiberty is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14Library General Public License for more details.
15
16You should have received a copy of the GNU Library General Public
17License along with libiberty; see the file COPYING.LIB. If
18not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19Boston, 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#include <sys/types.h>
35#include <stdlib.h>
36#include <string.h>
37#include <stdio.h>
38#include "tools/hashtab.h"
39
40/* This macro defines reserved value for empty table entry. */
41
42#define EMPTY_ENTRY((void *) 0) ((void *) 0)
43
44/* This macro defines reserved value for table entry which contained
45 a deleted element. */
46
47#define DELETED_ENTRY((void *) 1) ((void *) 1)
48
49static unsigned long higher_prime_number (unsigned long);
50static hashval_t hash_pointer (const void *);
51static int eq_pointer (const void *, const void *);
52static int htab_expand (htab_t);
53static void **find_empty_slot_for_expand (htab_t, hashval_t);
54
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. */
58htab_hash htab_hash_pointer = hash_pointer;
59htab_eq htab_eq_pointer = eq_pointer;
60
61/* The following function returns a nearest prime number which is
62 greater than N, and near a power of two. */
63
64static unsigned long
65higher_prime_number (n)
66 unsigned long n;
67{
68 /* These are primes that are near, but slightly smaller than, a
69 power of two. */
70 static unsigned long primes[] = {
71 (unsigned long) 2,
72 (unsigned long) 7,
73 (unsigned long) 13,
74 (unsigned long) 31,
75 (unsigned long) 61,
76 (unsigned long) 127,
77 (unsigned long) 251,
78 (unsigned long) 509,
79 (unsigned long) 1021,
80 (unsigned long) 2039,
81 (unsigned long) 4093,
82 (unsigned long) 8191,
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,
101 /* 4294967291L */
102 ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
103 };
104
105 unsigned long* low = &primes[0];
106 unsigned long* high = &primes[sizeof(primes) / sizeof(primes[0])];
107
108 while (low != high)
109 {
110 unsigned long* mid = low + (high - low) / 2;
111 if (n > *mid)
112 low = mid + 1;
113 else
114 high = mid;
115 }
116
117 /* If we've run out of primes, abort. */
118 if (n > *low)
119 {
120 fprintf (stderrstderr, "Cannot find prime bigger than %lu\n", n);
121 abort ();
122 }
123
124 return *low;
125}
126
127/* Returns a hash code for P. */
128
129static hashval_t
130hash_pointer (p)
131 const void * p;
132{
133 return (hashval_t) ((long)p >> 3);
134}
135
136/* Returns non-zero if P1 and P2 are equal. */
137
138static int
139eq_pointer (p1, p2)
140 const void * p1;
141 const void * p2;
142{
143 return p1 == p2;
144}
145
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. */
150
151htab_t
152htab_try_create (size, hash_f, eq_f, del_f)
153 size_t size;
154 htab_hash hash_f;
155 htab_eq eq_f;
156 htab_del del_f;
157{
158 htab_t result;
159
160 size = higher_prime_number (size);
161 result = (htab_t) calloc (1, sizeof (struct htab));
162 if (result == NULL((void*)0))
163 return NULL((void*)0);
164
165 result->entries = (void **) calloc (size, sizeof (void *));
166 if (result->entries == NULL((void*)0))
167 {
168 free (result);
169 return NULL((void*)0);
170 }
171
172 result->size = size;
173 result->hash_f = hash_f;
174 result->eq_f = eq_f;
175 result->del_f = del_f;
176 result->return_allocation_failure = 1;
177 return result;
178}
179
180/* This function frees all memory allocated for given hash table.
181 Naturally the hash table must already exist. */
182
183void
184htab_delete (htab)
185 htab_t htab;
186{
187 int i;
188
189 if (htab->del_f)
190 for (i = htab->size - 1; i >= 0; i--)
191 if (htab->entries[i] != EMPTY_ENTRY((void *) 0)
192 && htab->entries[i] != DELETED_ENTRY((void *) 1))
193 (*htab->del_f) (htab->entries[i]);
194
195 free (htab->entries);
196 free (htab);
197}
198
199/* This function clears all entries in the given hash table. */
200
201void
202htab_empty (htab)
203 htab_t htab;
204{
205 int i;
206
207 if (htab->del_f)
208 for (i = htab->size - 1; i >= 0; i--)
209 if (htab->entries[i] != EMPTY_ENTRY((void *) 0)
210 && htab->entries[i] != DELETED_ENTRY((void *) 1))
211 (*htab->del_f) (htab->entries[i]);
212
213 memset (htab->entries, 0, htab->size * sizeof (void *));
214}
215
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
219 hash table.
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. */
222
223static void **
224find_empty_slot_for_expand (htab, hash)
225 htab_t htab;
226 hashval_t hash;
227{
228 size_t size = htab->size;
229 hashval_t hash2 = 1 + hash % (size - 2);
230 unsigned int index = hash % size;
231
232 for (;;)
233 {
234 void **slot = htab->entries + index;
235
236 if (*slot == EMPTY_ENTRY((void *) 0))
237 return slot;
238 else if (*slot == DELETED_ENTRY((void *) 1))
239 abort ();
240
241 index += hash2;
242 if (index >= size)
243 index -= size;
244 }
245}
246
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. */
254
255static int
256htab_expand (htab)
257 htab_t htab;
258{
259 void **oentries;
260 void **olimit;
261 void **p;
262
263 oentries = htab->entries;
264 olimit = oentries + htab->size;
265
266 htab->size = higher_prime_number (htab->size * 2);
267
268 if (htab->return_allocation_failure)
269 {
270 void **nentries = (void **) calloc (htab->size, sizeof (void **));
Result of 'calloc' is converted to a pointer of type 'void *', which is incompatible with sizeof operand type 'void **'
271 if (nentries == NULL((void*)0))
272 return 0;
273 htab->entries = nentries;
274 }
275
276 htab->n_elements -= htab->n_deleted;
277 htab->n_deleted = 0;
278
279 p = oentries;
280 do
281 {
282 void * x = *p;
283
284 if (x != EMPTY_ENTRY((void *) 0) && x != DELETED_ENTRY((void *) 1))
285 {
286 void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
287
288 *q = x;
289 }
290
291 p++;
292 }
293 while (p < olimit);
294
295 free (oentries);
296 return 1;
297}
298
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. */
301
302void *
303htab_find_with_hash (htab, element, hash)
304 htab_t htab;
305 const void * element;
306 hashval_t hash;
307{
308 unsigned int index;
309 hashval_t hash2;
310 size_t size;
311 void * entry;
312
313 htab->searches++;
314 size = htab->size;
315 index = hash % size;
316
317 entry = htab->entries[index];
318 if (entry == EMPTY_ENTRY((void *) 0)
319 || (entry != DELETED_ENTRY((void *) 1) && (*htab->eq_f) (entry, element)))
320 return entry;
321
322 hash2 = 1 + hash % (size - 2);
323
324 for (;;)
325 {
326 htab->collisions++;
327 index += hash2;
328 if (index >= size)
329 index -= size;
330
331 entry = htab->entries[index];
332 if (entry == EMPTY_ENTRY((void *) 0)
333 || (entry != DELETED_ENTRY((void *) 1) && (*htab->eq_f) (entry, element)))
334 return entry;
335 }
336}
337
338/* Like htab_find_slot_with_hash, but compute the hash value from the
339 element. */
340
341void *
342htab_find (htab, element)
343 htab_t htab;
344 const void * element;
345{
346 return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
347}
348
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
355 fails. */
356
357void **
358htab_find_slot_with_hash (htab, element, hash, insert)
359 htab_t htab;
360 const void * element;
361 hashval_t hash;
362 enum insert_option insert;
363{
364 void **first_deleted_slot;
365 unsigned int index;
366 hashval_t hash2;
367 size_t size;
368
369 if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
370 && htab_expand (htab) == 0)
371 return NULL((void*)0);
372
373 size = htab->size;
374 hash2 = 1 + hash % (size - 2);
375 index = hash % size;
376
377 htab->searches++;
378 first_deleted_slot = NULL((void*)0);
379
380 for (;;)
381 {
382 void * entry = htab->entries[index];
383 if (entry == EMPTY_ENTRY((void *) 0))
384 {
385 if (insert == NO_INSERT)
386 return NULL((void*)0);
387
388 htab->n_elements++;
389
390 if (first_deleted_slot)
391 {
392 *first_deleted_slot = EMPTY_ENTRY((void *) 0);
393 return first_deleted_slot;
394 }
395
396 return &htab->entries[index];
397 }
398
399 if (entry == DELETED_ENTRY((void *) 1))
400 {
401 if (!first_deleted_slot)
402 first_deleted_slot = &htab->entries[index];
403 }
404 else if ((*htab->eq_f) (entry, element))
405 return &htab->entries[index];
406
407 htab->collisions++;
408 index += hash2;
409 if (index >= size)
410 index -= size;
411 }
412}
413
414/* Like htab_find_slot_with_hash, but compute the hash value from the
415 element. */
416
417void **
418htab_find_slot (htab, element, insert)
419 htab_t htab;
420 const void * element;
421 enum insert_option insert;
422{
423 return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
424 insert);
425}
426
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. */
430
431void
432htab_remove_elt (htab, element)
433 htab_t htab;
434 void * element;
435{
436 void **slot;
437
438 slot = htab_find_slot (htab, element, NO_INSERT);
439 if (*slot == EMPTY_ENTRY((void *) 0))
440 return;
441
442 if (htab->del_f)
443 (*htab->del_f) (*slot);
444
445 *slot = DELETED_ENTRY((void *) 1);
446 htab->n_deleted++;
447}
448
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
451 again. */
452
453void
454htab_clear_slot (htab, slot)
455 htab_t htab;
456 void **slot;
457{
458 if (slot < htab->entries || slot >= htab->entries + htab->size
459 || *slot == EMPTY_ENTRY((void *) 0) || *slot == DELETED_ENTRY((void *) 1))
460 abort ();
461
462 if (htab->del_f)
463 (*htab->del_f) (*slot);
464
465 *slot = DELETED_ENTRY((void *) 1);
466 htab->n_deleted++;
467}
468
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
472 argument. */
473
474void
475htab_traverse (htab, callback, info)
476 htab_t htab;
477 htab_trav callback;
478 void * info;
479{
480 void **slot = htab->entries;
481 void **limit = slot + htab->size;
482
483 do
484 {
485 void * x = *slot;
486
487 if (x != EMPTY_ENTRY((void *) 0) && x != DELETED_ENTRY((void *) 1))
488 if (!(*callback) (slot, info))
489 break;
490 }
491 while (++slot < limit);
492}
493
494/* Return the current size of given hash table. */
495
496size_t
497htab_size (htab)
498 htab_t htab;
499{
500 return htab->size;
501}
502
503/* Return the current number of elements in given hash table. */
504
505size_t
506htab_elements (htab)
507 htab_t htab;
508{
509 return htab->n_elements - htab->n_deleted;
510}
511
512/* Return the fraction of fixed collisions during all work with given
513 hash table. */
514
515double
516htab_collisions (htab)
517 htab_t htab;
518{
519 if (htab->searches == 0)
520 return 0.0;
521
522 return (double) htab->collisions / (double) htab->searches;
523}