← Back to branch summary

~ubuntu-branches/ubuntu/hoary/binutils/hoary

« back to all changes in this revision

Viewing changes to libiberty/hashtab.c

  • Committer: Bazaar Package Importer
  • Author(s): James Troup
  • Date: 2004-05-19 10:35:44 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20040519103544-17h3o6e8pwndydrg
Tags: 2.14.90.0.7-8
debian/rules: don't use gcc-2.95 on m68k.  Thanks to Adam Conrad for
pointing this out.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libiberty/hashtab.c
 
1
/* An expandable hash tables datatype.  
 
2
   Copyright (C) 1999, 2000, 2001, 2002, 2003 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
#include <sys/types.h>
 
39
 
 
40
#ifdef HAVE_STDLIB_H
 
41
#include <stdlib.h>
 
42
#endif
 
43
 
 
44
#ifdef HAVE_STRING_H
 
45
#include <string.h>
 
46
#endif
 
47
 
 
48
#ifdef HAVE_MALLOC_H
 
49
#include <malloc.h>
 
50
#endif
 
51
 
 
52
#include <stdio.h>
 
53
 
 
54
#include "libiberty.h"
 
55
#include "hashtab.h"
 
56
 
 
57
/* This macro defines reserved value for empty table entry. */
 
58
 
 
59
#define EMPTY_ENTRY    ((PTR) 0)
 
60
 
 
61
/* This macro defines reserved value for table entry which contained
 
62
   a deleted element. */
 
63
 
 
64
#define DELETED_ENTRY  ((PTR) 1)
 
65
 
 
66
static unsigned long higher_prime_number PARAMS ((unsigned long));
 
67
static hashval_t hash_pointer PARAMS ((const void *));
 
68
static int eq_pointer PARAMS ((const void *, const void *));
 
69
static int htab_expand PARAMS ((htab_t));
 
70
static PTR *find_empty_slot_for_expand  PARAMS ((htab_t, hashval_t));
 
71
 
 
72
/* At some point, we could make these be NULL, and modify the
 
73
   hash-table routines to handle NULL specially; that would avoid
 
74
   function-call overhead for the common case of hashing pointers.  */
 
75
htab_hash htab_hash_pointer = hash_pointer;
 
76
htab_eq htab_eq_pointer = eq_pointer;
 
77
 
 
78
/* The following function returns a nearest prime number which is
 
79
   greater than N, and near a power of two. */
 
80
 
 
81
static unsigned long
 
82
higher_prime_number (n)
 
83
     unsigned long n;
 
84
{
 
85
  /* These are primes that are near, but slightly smaller than, a
 
86
     power of two.  */
 
87
  static const unsigned long primes[] = {
 
88
    (unsigned long) 7,
 
89
    (unsigned long) 13,
 
90
    (unsigned long) 31,
 
91
    (unsigned long) 61,
 
92
    (unsigned long) 127,
 
93
    (unsigned long) 251,
 
94
    (unsigned long) 509,
 
95
    (unsigned long) 1021,
 
96
    (unsigned long) 2039,
 
97
    (unsigned long) 4093,
 
98
    (unsigned long) 8191,
 
99
    (unsigned long) 16381,
 
100
    (unsigned long) 32749,
 
101
    (unsigned long) 65521,
 
102
    (unsigned long) 131071,
 
103
    (unsigned long) 262139,
 
104
    (unsigned long) 524287,
 
105
    (unsigned long) 1048573,
 
106
    (unsigned long) 2097143,
 
107
    (unsigned long) 4194301,
 
108
    (unsigned long) 8388593,
 
109
    (unsigned long) 16777213,
 
110
    (unsigned long) 33554393,
 
111
    (unsigned long) 67108859,
 
112
    (unsigned long) 134217689,
 
113
    (unsigned long) 268435399,
 
114
    (unsigned long) 536870909,
 
115
    (unsigned long) 1073741789,
 
116
    (unsigned long) 2147483647,
 
117
                                        /* 4294967291L */
 
118
    ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
 
119
  };
 
120
 
 
121
  const unsigned long *low = &primes[0];
 
122
  const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
 
123
 
 
124
  while (low != high)
 
125
    {
 
126
      const unsigned long *mid = low + (high - low) / 2;
 
127
      if (n > *mid)
 
128
        low = mid + 1;
 
129
      else
 
130
        high = mid;
 
131
    }
 
132
 
 
133
  /* If we've run out of primes, abort.  */
 
134
  if (n > *low)
 
135
    {
 
136
      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
 
137
      abort ();
 
138
    }
 
139
 
 
140
  return *low;
 
141
}
 
142
 
 
143
/* Returns a hash code for P.  */
 
144
 
 
145
static hashval_t
 
146
hash_pointer (p)
 
147
     const PTR p;
 
148
{
 
149
  return (hashval_t) ((long)p >> 3);
 
150
}
 
151
 
 
152
/* Returns non-zero if P1 and P2 are equal.  */
 
153
 
 
154
static int
 
155
eq_pointer (p1, p2)
 
156
     const PTR p1;
 
157
     const PTR p2;
 
158
{
 
159
  return p1 == p2;
 
160
}
 
161
 
 
162
/* This function creates table with length slightly longer than given
 
163
   source length.  Created hash table is initiated as empty (all the
 
164
   hash table entries are EMPTY_ENTRY).  The function returns the
 
165
   created hash table, or NULL if memory allocation fails.  */
 
166
 
 
167
htab_t
 
168
htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f)
 
169
     size_t size;
 
170
     htab_hash hash_f;
 
171
     htab_eq eq_f;
 
172
     htab_del del_f;
 
173
     htab_alloc alloc_f;
 
174
     htab_free free_f;
 
175
{
 
176
  htab_t result;
 
177
 
 
178
  size = higher_prime_number (size);
 
179
  result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
 
180
  if (result == NULL)
 
181
    return NULL;
 
182
  result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
 
183
  if (result->entries == NULL)
 
184
    {
 
185
      if (free_f != NULL)
 
186
        (*free_f) (result);
 
187
      return NULL;
 
188
    }
 
189
  result->size = size;
 
190
  result->hash_f = hash_f;
 
191
  result->eq_f = eq_f;
 
192
  result->del_f = del_f;
 
193
  result->alloc_f = alloc_f;
 
194
  result->free_f = free_f;
 
195
  return result;
 
196
}
 
197
 
 
198
/* As above, but use the variants of alloc_f and free_f which accept
 
199
   an extra argument.  */
 
200
 
 
201
htab_t
 
202
htab_create_alloc_ex (size, hash_f, eq_f, del_f, alloc_arg, alloc_f,
 
203
                      free_f)
 
204
     size_t size;
 
205
     htab_hash hash_f;
 
206
     htab_eq eq_f;
 
207
     htab_del del_f;
 
208
     PTR alloc_arg;
 
209
     htab_alloc_with_arg alloc_f;
 
210
     htab_free_with_arg free_f;
 
211
{
 
212
  htab_t result;
 
213
 
 
214
  size = higher_prime_number (size);
 
215
  result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
 
216
  if (result == NULL)
 
217
    return NULL;
 
218
  result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
 
219
  if (result->entries == NULL)
 
220
    {
 
221
      if (free_f != NULL)
 
222
        (*free_f) (alloc_arg, result);
 
223
      return NULL;
 
224
    }
 
225
  result->size = size;
 
226
  result->hash_f = hash_f;
 
227
  result->eq_f = eq_f;
 
228
  result->del_f = del_f;
 
229
  result->alloc_arg = alloc_arg;
 
230
  result->alloc_with_arg_f = alloc_f;
 
231
  result->free_with_arg_f = free_f;
 
232
  return result;
 
233
}
 
234
 
 
235
/* Update the function pointers and allocation parameter in the htab_t.  */
 
236
 
 
237
void
 
238
htab_set_functions_ex (htab, hash_f, eq_f, del_f, alloc_arg, alloc_f, free_f)
 
239
     htab_t htab;
 
240
     htab_hash hash_f;
 
241
     htab_eq eq_f;
 
242
     htab_del del_f;
 
243
     PTR alloc_arg;
 
244
     htab_alloc_with_arg alloc_f;
 
245
     htab_free_with_arg free_f;
 
246
{
 
247
  htab->hash_f = hash_f;
 
248
  htab->eq_f = eq_f;
 
249
  htab->del_f = del_f;
 
250
  htab->alloc_arg = alloc_arg;
 
251
  htab->alloc_with_arg_f = alloc_f;
 
252
  htab->free_with_arg_f = free_f;
 
253
}
 
254
 
 
255
/* These functions exist solely for backward compatibility.  */
 
256
 
 
257
#undef htab_create
 
258
htab_t
 
259
htab_create (size, hash_f, eq_f, del_f)
 
260
     size_t size;
 
261
     htab_hash hash_f;
 
262
     htab_eq eq_f;
 
263
     htab_del del_f;
 
264
{
 
265
  return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
 
266
}
 
267
 
 
268
htab_t
 
269
htab_try_create (size, hash_f, eq_f, del_f)
 
270
     size_t size;
 
271
     htab_hash hash_f;
 
272
     htab_eq eq_f;
 
273
     htab_del del_f;
 
274
{
 
275
  return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
 
276
}
 
277
 
 
278
/* This function frees all memory allocated for given hash table.
 
279
   Naturally the hash table must already exist. */
 
280
 
 
281
void
 
282
htab_delete (htab)
 
283
     htab_t htab;
 
284
{
 
285
  int i;
 
286
 
 
287
  if (htab->del_f)
 
288
    for (i = htab->size - 1; i >= 0; i--)
 
289
      if (htab->entries[i] != EMPTY_ENTRY
 
290
          && htab->entries[i] != DELETED_ENTRY)
 
291
        (*htab->del_f) (htab->entries[i]);
 
292
 
 
293
  if (htab->free_f != NULL)
 
294
    {
 
295
      (*htab->free_f) (htab->entries);
 
296
      (*htab->free_f) (htab);
 
297
    }
 
298
  else if (htab->free_with_arg_f != NULL)
 
299
    {
 
300
      (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
 
301
      (*htab->free_with_arg_f) (htab->alloc_arg, htab);
 
302
    }
 
303
}
 
304
 
 
305
/* This function clears all entries in the given hash table.  */
 
306
 
 
307
void
 
308
htab_empty (htab)
 
309
     htab_t htab;
 
310
{
 
311
  int i;
 
312
 
 
313
  if (htab->del_f)
 
314
    for (i = htab->size - 1; i >= 0; i--)
 
315
      if (htab->entries[i] != EMPTY_ENTRY
 
316
          && htab->entries[i] != DELETED_ENTRY)
 
317
        (*htab->del_f) (htab->entries[i]);
 
318
 
 
319
  memset (htab->entries, 0, htab->size * sizeof (PTR));
 
320
}
 
321
 
 
322
/* Similar to htab_find_slot, but without several unwanted side effects:
 
323
    - Does not call htab->eq_f when it finds an existing entry.
 
324
    - Does not change the count of elements/searches/collisions in the
 
325
      hash table.
 
326
   This function also assumes there are no deleted entries in the table.
 
327
   HASH is the hash value for the element to be inserted.  */
 
328
 
 
329
static PTR *
 
330
find_empty_slot_for_expand (htab, hash)
 
331
     htab_t htab;
 
332
     hashval_t hash;
 
333
{
 
334
  size_t size = htab->size;
 
335
  unsigned int index = hash % size;
 
336
  PTR *slot = htab->entries + index;
 
337
  hashval_t hash2;
 
338
 
 
339
  if (*slot == EMPTY_ENTRY)
 
340
    return slot;
 
341
  else if (*slot == DELETED_ENTRY)
 
342
    abort ();
 
343
 
 
344
  hash2 = 1 + hash % (size - 2);
 
345
  for (;;)
 
346
    {
 
347
      index += hash2;
 
348
      if (index >= size)
 
349
        index -= size;
 
350
 
 
351
      slot = htab->entries + index;
 
352
      if (*slot == EMPTY_ENTRY)
 
353
        return slot;
 
354
      else if (*slot == DELETED_ENTRY)
 
355
        abort ();
 
356
    }
 
357
}
 
358
 
 
359
/* The following function changes size of memory allocated for the
 
360
   entries and repeatedly inserts the table elements.  The occupancy
 
361
   of the table after the call will be about 50%.  Naturally the hash
 
362
   table must already exist.  Remember also that the place of the
 
363
   table entries is changed.  If memory allocation failures are allowed,
 
364
   this function will return zero, indicating that the table could not be
 
365
   expanded.  If all goes well, it will return a non-zero value.  */
 
366
 
 
367
static int
 
368
htab_expand (htab)
 
369
     htab_t htab;
 
370
{
 
371
  PTR *oentries;
 
372
  PTR *olimit;
 
373
  PTR *p;
 
374
  PTR *nentries;
 
375
  size_t nsize;
 
376
 
 
377
  oentries = htab->entries;
 
378
  olimit = oentries + htab->size;
 
379
 
 
380
  /* Resize only when table after removal of unused elements is either
 
381
     too full or too empty.  */
 
382
  if ((htab->n_elements - htab->n_deleted) * 2 > htab->size
 
383
      || ((htab->n_elements - htab->n_deleted) * 8 < htab->size
 
384
          && htab->size > 32))
 
385
    nsize = higher_prime_number ((htab->n_elements - htab->n_deleted) * 2);
 
386
  else
 
387
    nsize = htab->size;
 
388
 
 
389
  if (htab->alloc_with_arg_f != NULL)
 
390
    nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
 
391
                                                  sizeof (PTR *));
 
392
  else
 
393
    nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
 
394
  if (nentries == NULL)
 
395
    return 0;
 
396
  htab->entries = nentries;
 
397
  htab->size = nsize;
 
398
 
 
399
  htab->n_elements -= htab->n_deleted;
 
400
  htab->n_deleted = 0;
 
401
 
 
402
  p = oentries;
 
403
  do
 
404
    {
 
405
      PTR x = *p;
 
406
 
 
407
      if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 
408
        {
 
409
          PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 
410
 
 
411
          *q = x;
 
412
        }
 
413
 
 
414
      p++;
 
415
    }
 
416
  while (p < olimit);
 
417
 
 
418
  if (htab->free_f != NULL)
 
419
    (*htab->free_f) (oentries);
 
420
  else if (htab->free_with_arg_f != NULL)
 
421
    (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
 
422
  return 1;
 
423
}
 
424
 
 
425
/* This function searches for a hash table entry equal to the given
 
426
   element.  It cannot be used to insert or delete an element.  */
 
427
 
 
428
PTR
 
429
htab_find_with_hash (htab, element, hash)
 
430
     htab_t htab;
 
431
     const PTR element;
 
432
     hashval_t hash;
 
433
{
 
434
  unsigned int index;
 
435
  hashval_t hash2;
 
436
  size_t size;
 
437
  PTR entry;
 
438
 
 
439
  htab->searches++;
 
440
  size = htab->size;
 
441
  index = hash % size;
 
442
 
 
443
  entry = htab->entries[index];
 
444
  if (entry == EMPTY_ENTRY
 
445
      || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 
446
    return entry;
 
447
 
 
448
  hash2 = 1 + hash % (size - 2);
 
449
 
 
450
  for (;;)
 
451
    {
 
452
      htab->collisions++;
 
453
      index += hash2;
 
454
      if (index >= size)
 
455
        index -= size;
 
456
 
 
457
      entry = htab->entries[index];
 
458
      if (entry == EMPTY_ENTRY
 
459
          || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 
460
        return entry;
 
461
    }
 
462
}
 
463
 
 
464
/* Like htab_find_slot_with_hash, but compute the hash value from the
 
465
   element.  */
 
466
 
 
467
PTR
 
468
htab_find (htab, element)
 
469
     htab_t htab;
 
470
     const PTR element;
 
471
{
 
472
  return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 
473
}
 
474
 
 
475
/* This function searches for a hash table slot containing an entry
 
476
   equal to the given element.  To delete an entry, call this with
 
477
   INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 
478
   after doing some checks).  To insert an entry, call this with
 
479
   INSERT = 1, then write the value you want into the returned slot.
 
480
   When inserting an entry, NULL may be returned if memory allocation
 
481
   fails.  */
 
482
 
 
483
PTR *
 
484
htab_find_slot_with_hash (htab, element, hash, insert)
 
485
     htab_t htab;
 
486
     const PTR element;
 
487
     hashval_t hash;
 
488
     enum insert_option insert;
 
489
{
 
490
  PTR *first_deleted_slot;
 
491
  unsigned int index;
 
492
  hashval_t hash2;
 
493
  size_t size;
 
494
  PTR entry;
 
495
 
 
496
  if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
 
497
      && htab_expand (htab) == 0)
 
498
    return NULL;
 
499
 
 
500
  size = htab->size;
 
501
  index = hash % size;
 
502
 
 
503
  htab->searches++;
 
504
  first_deleted_slot = NULL;
 
505
 
 
506
  entry = htab->entries[index];
 
507
  if (entry == EMPTY_ENTRY)
 
508
    goto empty_entry;
 
509
  else if (entry == DELETED_ENTRY)
 
510
    first_deleted_slot = &htab->entries[index];
 
511
  else if ((*htab->eq_f) (entry, element))
 
512
    return &htab->entries[index];
 
513
      
 
514
  hash2 = 1 + hash % (size - 2);
 
515
  for (;;)
 
516
    {
 
517
      htab->collisions++;
 
518
      index += hash2;
 
519
      if (index >= size)
 
520
        index -= size;
 
521
      
 
522
      entry = htab->entries[index];
 
523
      if (entry == EMPTY_ENTRY)
 
524
        goto empty_entry;
 
525
      else if (entry == DELETED_ENTRY)
 
526
        {
 
527
          if (!first_deleted_slot)
 
528
            first_deleted_slot = &htab->entries[index];
 
529
        }
 
530
      else if ((*htab->eq_f) (entry, element))
 
531
        return &htab->entries[index];
 
532
    }
 
533
 
 
534
 empty_entry:
 
535
  if (insert == NO_INSERT)
 
536
    return NULL;
 
537
 
 
538
  htab->n_elements++;
 
539
 
 
540
  if (first_deleted_slot)
 
541
    {
 
542
      *first_deleted_slot = EMPTY_ENTRY;
 
543
      return first_deleted_slot;
 
544
    }
 
545
 
 
546
  return &htab->entries[index];
 
547
}
 
548
 
 
549
/* Like htab_find_slot_with_hash, but compute the hash value from the
 
550
   element.  */
 
551
 
 
552
PTR *
 
553
htab_find_slot (htab, element, insert)
 
554
     htab_t htab;
 
555
     const PTR element;
 
556
     enum insert_option insert;
 
557
{
 
558
  return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 
559
                                   insert);
 
560
}
 
561
 
 
562
/* This function deletes an element with the given value from hash
 
563
   table.  If there is no matching element in the hash table, this
 
564
   function does nothing.  */
 
565
 
 
566
void
 
567
htab_remove_elt (htab, element)
 
568
     htab_t htab;
 
569
     PTR element;
 
570
{
 
571
  PTR *slot;
 
572
 
 
573
  slot = htab_find_slot (htab, element, NO_INSERT);
 
574
  if (*slot == EMPTY_ENTRY)
 
575
    return;
 
576
 
 
577
  if (htab->del_f)
 
578
    (*htab->del_f) (*slot);
 
579
 
 
580
  *slot = DELETED_ENTRY;
 
581
  htab->n_deleted++;
 
582
}
 
583
 
 
584
/* This function clears a specified slot in a hash table.  It is
 
585
   useful when you've already done the lookup and don't want to do it
 
586
   again.  */
 
587
 
 
588
void
 
589
htab_clear_slot (htab, slot)
 
590
     htab_t htab;
 
591
     PTR *slot;
 
592
{
 
593
  if (slot < htab->entries || slot >= htab->entries + htab->size
 
594
      || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 
595
    abort ();
 
596
 
 
597
  if (htab->del_f)
 
598
    (*htab->del_f) (*slot);
 
599
 
 
600
  *slot = DELETED_ENTRY;
 
601
  htab->n_deleted++;
 
602
}
 
603
 
 
604
/* This function scans over the entire hash table calling
 
605
   CALLBACK for each live entry.  If CALLBACK returns false,
 
606
   the iteration stops.  INFO is passed as CALLBACK's second
 
607
   argument.  */
 
608
 
 
609
void
 
610
htab_traverse_noresize (htab, callback, info)
 
611
     htab_t htab;
 
612
     htab_trav callback;
 
613
     PTR info;
 
614
{
 
615
  PTR *slot;
 
616
  PTR *limit;
 
617
 
 
618
  slot = htab->entries;
 
619
  limit = slot + htab->size;
 
620
 
 
621
  do
 
622
    {
 
623
      PTR x = *slot;
 
624
 
 
625
      if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 
626
        if (!(*callback) (slot, info))
 
627
          break;
 
628
    }
 
629
  while (++slot < limit);
 
630
}
 
631
 
 
632
/* Like htab_traverse_noresize, but does resize the table when it is
 
633
   too empty to improve effectivity of subsequent calls.  */
 
634
 
 
635
void
 
636
htab_traverse (htab, callback, info)
 
637
     htab_t htab;
 
638
     htab_trav callback;
 
639
     PTR info;
 
640
{
 
641
  if ((htab->n_elements - htab->n_deleted) * 8 < htab->size)
 
642
    htab_expand (htab);
 
643
 
 
644
  htab_traverse_noresize (htab, callback, info);
 
645
}
 
646
 
 
647
/* Return the current size of given hash table. */
 
648
 
 
649
size_t
 
650
htab_size (htab)
 
651
     htab_t htab;
 
652
{
 
653
  return htab->size;
 
654
}
 
655
 
 
656
/* Return the current number of elements in given hash table. */
 
657
 
 
658
size_t
 
659
htab_elements (htab)
 
660
     htab_t htab;
 
661
{
 
662
  return htab->n_elements - htab->n_deleted;
 
663
}
 
664
 
 
665
/* Return the fraction of fixed collisions during all work with given
 
666
   hash table. */
 
667
 
 
668
double
 
669
htab_collisions (htab)
 
670
     htab_t htab;
 
671
{
 
672
  if (htab->searches == 0)
 
673
    return 0.0;
 
674
 
 
675
  return (double) htab->collisions / (double) htab->searches;
 
676
}
 
677
 
 
678
/* Hash P as a null-terminated string.
 
679
 
 
680
   Copied from gcc/hashtable.c.  Zack had the following to say with respect
 
681
   to applicability, though note that unlike hashtable.c, this hash table
 
682
   implementation re-hashes rather than chain buckets.
 
683
 
 
684
   http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 
685
   From: Zack Weinberg <zackw@panix.com>
 
686
   Date: Fri, 17 Aug 2001 02:15:56 -0400
 
687
 
 
688
   I got it by extracting all the identifiers from all the source code
 
689
   I had lying around in mid-1999, and testing many recurrences of
 
690
   the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 
691
   prime numbers or the appropriate identity.  This was the best one.
 
692
   I don't remember exactly what constituted "best", except I was
 
693
   looking at bucket-length distributions mostly.
 
694
   
 
695
   So it should be very good at hashing identifiers, but might not be
 
696
   as good at arbitrary strings.
 
697
   
 
698
   I'll add that it thoroughly trounces the hash functions recommended
 
699
   for this use at http://burtleburtle.net/bob/hash/index.html, both
 
700
   on speed and bucket distribution.  I haven't tried it against the
 
701
   function they just started using for Perl's hashes.  */
 
702
 
 
703
hashval_t
 
704
htab_hash_string (p)
 
705
     const PTR p;
 
706
{
 
707
  const unsigned char *str = (const unsigned char *) p;
 
708
  hashval_t r = 0;
 
709
  unsigned char c;
 
710
 
 
711
  while ((c = *str++) != 0)
 
712
    r = r * 67 + c - 113;
 
713
 
 
714
  return r;
 
715
}
 
716
 
 
717
/* DERIVED FROM:
 
718
--------------------------------------------------------------------
 
719
lookup2.c, by Bob Jenkins, December 1996, Public Domain.
 
720
hash(), hash2(), hash3, and mix() are externally useful functions.
 
721
Routines to test the hash are included if SELF_TEST is defined.
 
722
You can use this free for any purpose.  It has no warranty.
 
723
--------------------------------------------------------------------
 
724
*/
 
725
 
 
726
/*
 
727
--------------------------------------------------------------------
 
728
mix -- mix 3 32-bit values reversibly.
 
729
For every delta with one or two bit set, and the deltas of all three
 
730
  high bits or all three low bits, whether the original value of a,b,c
 
731
  is almost all zero or is uniformly distributed,
 
732
* If mix() is run forward or backward, at least 32 bits in a,b,c
 
733
  have at least 1/4 probability of changing.
 
734
* If mix() is run forward, every bit of c will change between 1/3 and
 
735
  2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 
736
mix() was built out of 36 single-cycle latency instructions in a 
 
737
  structure that could supported 2x parallelism, like so:
 
738
      a -= b; 
 
739
      a -= c; x = (c>>13);
 
740
      b -= c; a ^= x;
 
741
      b -= a; x = (a<<8);
 
742
      c -= a; b ^= x;
 
743
      c -= b; x = (b>>13);
 
744
      ...
 
745
  Unfortunately, superscalar Pentiums and Sparcs can't take advantage 
 
746
  of that parallelism.  They've also turned some of those single-cycle
 
747
  latency instructions into multi-cycle latency instructions.  Still,
 
748
  this is the fastest good hash I could find.  There were about 2^^68
 
749
  to choose from.  I only looked at a billion or so.
 
750
--------------------------------------------------------------------
 
751
*/
 
752
/* same, but slower, works on systems that might have 8 byte hashval_t's */
 
753
#define mix(a,b,c) \
 
754
{ \
 
755
  a -= b; a -= c; a ^= (c>>13); \
 
756
  b -= c; b -= a; b ^= (a<< 8); \
 
757
  c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
 
758
  a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
 
759
  b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
 
760
  c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
 
761
  a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
 
762
  b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
 
763
  c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
 
764
}
 
765
 
 
766
/*
 
767
--------------------------------------------------------------------
 
768
hash() -- hash a variable-length key into a 32-bit value
 
769
  k     : the key (the unaligned variable-length array of bytes)
 
770
  len   : the length of the key, counting by bytes
 
771
  level : can be any 4-byte value
 
772
Returns a 32-bit value.  Every bit of the key affects every bit of
 
773
the return value.  Every 1-bit and 2-bit delta achieves avalanche.
 
774
About 36+6len instructions.
 
775
 
 
776
The best hash table sizes are powers of 2.  There is no need to do
 
777
mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 
778
use a bitmask.  For example, if you need only 10 bits, do
 
779
  h = (h & hashmask(10));
 
780
In which case, the hash table should have hashsize(10) elements.
 
781
 
 
782
If you are hashing n strings (ub1 **)k, do it like this:
 
783
  for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
 
784
 
 
785
By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
 
786
code any way you wish, private, educational, or commercial.  It's free.
 
787
 
 
788
See http://burtleburtle.net/bob/hash/evahash.html
 
789
Use for hash table lookup, or anything where one collision in 2^32 is
 
790
acceptable.  Do NOT use for cryptographic purposes.
 
791
--------------------------------------------------------------------
 
792
*/
 
793
 
 
794
hashval_t iterative_hash (k_in, length, initval)
 
795
     const PTR k_in;               /* the key */
 
796
     register size_t  length;      /* the length of the key */
 
797
     register hashval_t  initval;  /* the previous hash, or an arbitrary value */
 
798
{
 
799
  register const unsigned char *k = (const unsigned char *)k_in;
 
800
  register hashval_t a,b,c,len;
 
801
 
 
802
  /* Set up the internal state */
 
803
  len = length;
 
804
  a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
 
805
  c = initval;           /* the previous hash value */
 
806
 
 
807
  /*---------------------------------------- handle most of the key */
 
808
#ifndef WORDS_BIGENDIAN
 
809
  /* On a little-endian machine, if the data is 4-byte aligned we can hash
 
810
     by word for better speed.  This gives nondeterministic results on
 
811
     big-endian machines.  */
 
812
  if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0)
 
813
    while (len >= 12)    /* aligned */
 
814
      {
 
815
        a += *(hashval_t *)(k+0);
 
816
        b += *(hashval_t *)(k+4);
 
817
        c += *(hashval_t *)(k+8);
 
818
        mix(a,b,c);
 
819
        k += 12; len -= 12;
 
820
      }
 
821
  else /* unaligned */
 
822
#endif
 
823
    while (len >= 12)
 
824
      {
 
825
        a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
 
826
        b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
 
827
        c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
 
828
        mix(a,b,c);
 
829
        k += 12; len -= 12;
 
830
      }
 
831
 
 
832
  /*------------------------------------- handle the last 11 bytes */
 
833
  c += length;
 
834
  switch(len)              /* all the case statements fall through */
 
835
    {
 
836
    case 11: c+=((hashval_t)k[10]<<24);
 
837
    case 10: c+=((hashval_t)k[9]<<16);
 
838
    case 9 : c+=((hashval_t)k[8]<<8);
 
839
      /* the first byte of c is reserved for the length */
 
840
    case 8 : b+=((hashval_t)k[7]<<24);
 
841
    case 7 : b+=((hashval_t)k[6]<<16);
 
842
    case 6 : b+=((hashval_t)k[5]<<8);
 
843
    case 5 : b+=k[4];
 
844
    case 4 : a+=((hashval_t)k[3]<<24);
 
845
    case 3 : a+=((hashval_t)k[2]<<16);
 
846
    case 2 : a+=((hashval_t)k[1]<<8);
 
847
    case 1 : a+=k[0];
 
848
      /* case 0: nothing left to add */
 
849
    }
 
850
  mix(a,b,c);
 
851
  /*-------------------------------------------- report the result */
 
852
  return c;
 
853
}