OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [libiberty/] [hashtab.c] - Blame information for rev 826

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 274 jeremybenn
/* An expandable hash tables datatype.
2
   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2009
3
   Free Software Foundation, Inc.
4
   Contributed by Vladimir Makarov (vmakarov@cygnus.com).
5
 
6
This file is part of the libiberty library.
7
Libiberty is free software; you can redistribute it and/or
8
modify it under the terms of the GNU Library General Public
9
License as published by the Free Software Foundation; either
10
version 2 of the License, or (at your option) any later version.
11
 
12
Libiberty is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15
Library General Public License for more details.
16
 
17
You should have received a copy of the GNU Library General Public
18
License along with libiberty; see the file COPYING.LIB.  If
19
not, write to the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
20
Boston, MA 02110-1301, USA.  */
21
 
22
/* This package implements basic hash table functionality.  It is possible
23
   to search for an entry, create an entry and destroy an entry.
24
 
25
   Elements in the table are generic pointers.
26
 
27
   The size of the table is not fixed; if the occupancy of the table
28
   grows too high the hash table will be expanded.
29
 
30
   The abstract data implementation is based on generalized Algorithm D
31
   from Knuth's book "The art of computer programming".  Hash table is
32
   expanded by creation of new hash table and transferring elements from
33
   the old table to the new table. */
34
 
35
#ifdef HAVE_CONFIG_H
36
#include "config.h"
37
#endif
38
 
39
#include <sys/types.h>
40
 
41
#ifdef HAVE_STDLIB_H
42
#include <stdlib.h>
43
#endif
44
#ifdef HAVE_STRING_H
45
#include <string.h>
46
#endif
47
#ifdef HAVE_MALLOC_H
48
#include <malloc.h>
49
#endif
50
#ifdef HAVE_LIMITS_H
51
#include <limits.h>
52
#endif
53
#ifdef HAVE_INTTYPES_H
54
#include <inttypes.h>
55
#endif
56
#ifdef HAVE_STDINT_H
57
#include <stdint.h>
58
#endif
59
 
60
#include <stdio.h>
61
 
62
#include "libiberty.h"
63
#include "ansidecl.h"
64
#include "hashtab.h"
65
 
66
#ifndef CHAR_BIT
67
#define CHAR_BIT 8
68
#endif
69
 
70
static unsigned int higher_prime_index (unsigned long);
71
static hashval_t htab_mod_1 (hashval_t, hashval_t, hashval_t, int);
72
static hashval_t htab_mod (hashval_t, htab_t);
73
static hashval_t htab_mod_m2 (hashval_t, htab_t);
74
static hashval_t hash_pointer (const void *);
75
static int eq_pointer (const void *, const void *);
76
static int htab_expand (htab_t);
77
static PTR *find_empty_slot_for_expand (htab_t, hashval_t);
78
 
79
/* At some point, we could make these be NULL, and modify the
80
   hash-table routines to handle NULL specially; that would avoid
81
   function-call overhead for the common case of hashing pointers.  */
82
htab_hash htab_hash_pointer = hash_pointer;
83
htab_eq htab_eq_pointer = eq_pointer;
84
 
85
/* Table of primes and multiplicative inverses.
86
 
87
   Note that these are not minimally reduced inverses.  Unlike when generating
88
   code to divide by a constant, we want to be able to use the same algorithm
89
   all the time.  All of these inverses (are implied to) have bit 32 set.
90
 
91
   For the record, here's the function that computed the table; it's a
92
   vastly simplified version of the function of the same name from gcc.  */
93
 
94
#if 0
95
unsigned int
96
ceil_log2 (unsigned int x)
97
{
98
  int i;
99
  for (i = 31; i >= 0 ; --i)
100
    if (x > (1u << i))
101
      return i+1;
102
  abort ();
103
}
104
 
105
unsigned int
106
choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp)
107
{
108
  unsigned long long mhigh;
109
  double nx;
110
  int lgup, post_shift;
111
  int pow, pow2;
112
  int n = 32, precision = 32;
113
 
114
  lgup = ceil_log2 (d);
115
  pow = n + lgup;
116
  pow2 = n + lgup - precision;
117
 
118
  nx = ldexp (1.0, pow) + ldexp (1.0, pow2);
119
  mhigh = nx / d;
120
 
121
  *shiftp = lgup - 1;
122
  *mlp = mhigh;
123
  return mhigh >> 32;
124
}
125
#endif
126
 
127
struct prime_ent
128
{
129
  hashval_t prime;
130
  hashval_t inv;
131
  hashval_t inv_m2;     /* inverse of prime-2 */
132
  hashval_t shift;
133
};
134
 
135
static struct prime_ent const prime_tab[] = {
136
  {          7, 0x24924925, 0x9999999b, 2 },
137
  {         13, 0x3b13b13c, 0x745d1747, 3 },
138
  {         31, 0x08421085, 0x1a7b9612, 4 },
139
  {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
140
  {        127, 0x02040811, 0x0624dd30, 6 },
141
  {        251, 0x05197f7e, 0x073260a5, 7 },
142
  {        509, 0x01824366, 0x02864fc8, 8 },
143
  {       1021, 0x00c0906d, 0x014191f7, 9 },
144
  {       2039, 0x0121456f, 0x0161e69e, 10 },
145
  {       4093, 0x00300902, 0x00501908, 11 },
146
  {       8191, 0x00080041, 0x00180241, 12 },
147
  {      16381, 0x000c0091, 0x00140191, 13 },
148
  {      32749, 0x002605a5, 0x002a06e6, 14 },
149
  {      65521, 0x000f00e2, 0x00110122, 15 },
150
  {     131071, 0x00008001, 0x00018003, 16 },
151
  {     262139, 0x00014002, 0x0001c004, 17 },
152
  {     524287, 0x00002001, 0x00006001, 18 },
153
  {    1048573, 0x00003001, 0x00005001, 19 },
154
  {    2097143, 0x00004801, 0x00005801, 20 },
155
  {    4194301, 0x00000c01, 0x00001401, 21 },
156
  {    8388593, 0x00001e01, 0x00002201, 22 },
157
  {   16777213, 0x00000301, 0x00000501, 23 },
158
  {   33554393, 0x00001381, 0x00001481, 24 },
159
  {   67108859, 0x00000141, 0x000001c1, 25 },
160
  {  134217689, 0x000004e1, 0x00000521, 26 },
161
  {  268435399, 0x00000391, 0x000003b1, 27 },
162
  {  536870909, 0x00000019, 0x00000029, 28 },
163
  { 1073741789, 0x0000008d, 0x00000095, 29 },
164
  { 2147483647, 0x00000003, 0x00000007, 30 },
165
  /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
166
  { 0xfffffffb, 0x00000006, 0x00000008, 31 }
167
};
168
 
169
/* The following function returns an index into the above table of the
170
   nearest prime number which is greater than N, and near a power of two. */
171
 
172
static unsigned int
173
higher_prime_index (unsigned long n)
174
{
175
  unsigned int low = 0;
176
  unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
177
 
178
  while (low != high)
179
    {
180
      unsigned int mid = low + (high - low) / 2;
181
      if (n > prime_tab[mid].prime)
182
        low = mid + 1;
183
      else
184
        high = mid;
185
    }
186
 
187
  /* If we've run out of primes, abort.  */
188
  if (n > prime_tab[low].prime)
189
    {
190
      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
191
      abort ();
192
    }
193
 
194
  return low;
195
}
196
 
197
/* Returns a hash code for P.  */
198
 
199
static hashval_t
200
hash_pointer (const PTR p)
201
{
202
  return (hashval_t) ((intptr_t)p >> 3);
203
}
204
 
205
/* Returns non-zero if P1 and P2 are equal.  */
206
 
207
static int
208
eq_pointer (const PTR p1, const PTR p2)
209
{
210
  return p1 == p2;
211
}
212
 
213
 
214
/* The parens around the function names in the next two definitions
215
   are essential in order to prevent macro expansions of the name.
216
   The bodies, however, are expanded as expected, so they are not
217
   recursive definitions.  */
218
 
219
/* Return the current size of given hash table.  */
220
 
221
#define htab_size(htab)  ((htab)->size)
222
 
223
size_t
224
(htab_size) (htab_t htab)
225
{
226
  return htab_size (htab);
227
}
228
 
229
/* Return the current number of elements in given hash table. */
230
 
231
#define htab_elements(htab)  ((htab)->n_elements - (htab)->n_deleted)
232
 
233
size_t
234
(htab_elements) (htab_t htab)
235
{
236
  return htab_elements (htab);
237
}
238
 
239
/* Return X % Y.  */
240
 
241
static inline hashval_t
242
htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift)
243
{
244
  /* The multiplicative inverses computed above are for 32-bit types, and
245
     requires that we be able to compute a highpart multiply.  */
246
#ifdef UNSIGNED_64BIT_TYPE
247
  __extension__ typedef UNSIGNED_64BIT_TYPE ull;
248
  if (sizeof (hashval_t) * CHAR_BIT <= 32)
249
    {
250
      hashval_t t1, t2, t3, t4, q, r;
251
 
252
      t1 = ((ull)x * inv) >> 32;
253
      t2 = x - t1;
254
      t3 = t2 >> 1;
255
      t4 = t1 + t3;
256
      q  = t4 >> shift;
257
      r  = x - (q * y);
258
 
259
      return r;
260
    }
261
#endif
262
 
263
  /* Otherwise just use the native division routines.  */
264
  return x % y;
265
}
266
 
267
/* Compute the primary hash for HASH given HTAB's current size.  */
268
 
269
static inline hashval_t
270
htab_mod (hashval_t hash, htab_t htab)
271
{
272
  const struct prime_ent *p = &prime_tab[htab->size_prime_index];
273
  return htab_mod_1 (hash, p->prime, p->inv, p->shift);
274
}
275
 
276
/* Compute the secondary hash for HASH given HTAB's current size.  */
277
 
278
static inline hashval_t
279
htab_mod_m2 (hashval_t hash, htab_t htab)
280
{
281
  const struct prime_ent *p = &prime_tab[htab->size_prime_index];
282
  return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
283
}
284
 
285
/* This function creates table with length slightly longer than given
286
   source length.  Created hash table is initiated as empty (all the
287
   hash table entries are HTAB_EMPTY_ENTRY).  The function returns the
288
   created hash table, or NULL if memory allocation fails.  */
289
 
290
htab_t
291
htab_create_alloc (size_t size, htab_hash hash_f, htab_eq eq_f,
292
                   htab_del del_f, htab_alloc alloc_f, htab_free free_f)
293
{
294
  htab_t result;
295
  unsigned int size_prime_index;
296
 
297
  size_prime_index = higher_prime_index (size);
298
  size = prime_tab[size_prime_index].prime;
299
 
300
  result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
301
  if (result == NULL)
302
    return NULL;
303
  result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
304
  if (result->entries == NULL)
305
    {
306
      if (free_f != NULL)
307
        (*free_f) (result);
308
      return NULL;
309
    }
310
  result->size = size;
311
  result->size_prime_index = size_prime_index;
312
  result->hash_f = hash_f;
313
  result->eq_f = eq_f;
314
  result->del_f = del_f;
315
  result->alloc_f = alloc_f;
316
  result->free_f = free_f;
317
  return result;
318
}
319
 
320
/* As above, but use the variants of alloc_f and free_f which accept
321
   an extra argument.  */
322
 
323
htab_t
324
htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f,
325
                      htab_del del_f, void *alloc_arg,
326
                      htab_alloc_with_arg alloc_f,
327
                      htab_free_with_arg free_f)
328
{
329
  htab_t result;
330
  unsigned int size_prime_index;
331
 
332
  size_prime_index = higher_prime_index (size);
333
  size = prime_tab[size_prime_index].prime;
334
 
335
  result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
336
  if (result == NULL)
337
    return NULL;
338
  result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
339
  if (result->entries == NULL)
340
    {
341
      if (free_f != NULL)
342
        (*free_f) (alloc_arg, result);
343
      return NULL;
344
    }
345
  result->size = size;
346
  result->size_prime_index = size_prime_index;
347
  result->hash_f = hash_f;
348
  result->eq_f = eq_f;
349
  result->del_f = del_f;
350
  result->alloc_arg = alloc_arg;
351
  result->alloc_with_arg_f = alloc_f;
352
  result->free_with_arg_f = free_f;
353
  return result;
354
}
355
 
356
/* Update the function pointers and allocation parameter in the htab_t.  */
357
 
358
void
359
htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f,
360
                       htab_del del_f, PTR alloc_arg,
361
                       htab_alloc_with_arg alloc_f, htab_free_with_arg free_f)
362
{
363
  htab->hash_f = hash_f;
364
  htab->eq_f = eq_f;
365
  htab->del_f = del_f;
366
  htab->alloc_arg = alloc_arg;
367
  htab->alloc_with_arg_f = alloc_f;
368
  htab->free_with_arg_f = free_f;
369
}
370
 
371
/* These functions exist solely for backward compatibility.  */
372
 
373
#undef htab_create
374
htab_t
375
htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
376
{
377
  return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
378
}
379
 
380
htab_t
381
htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
382
{
383
  return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
384
}
385
 
386
/* This function frees all memory allocated for given hash table.
387
   Naturally the hash table must already exist. */
388
 
389
void
390
htab_delete (htab_t htab)
391
{
392
  size_t size = htab_size (htab);
393
  PTR *entries = htab->entries;
394
  int i;
395
 
396
  if (htab->del_f)
397
    for (i = size - 1; i >= 0; i--)
398
      if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
399
        (*htab->del_f) (entries[i]);
400
 
401
  if (htab->free_f != NULL)
402
    {
403
      (*htab->free_f) (entries);
404
      (*htab->free_f) (htab);
405
    }
406
  else if (htab->free_with_arg_f != NULL)
407
    {
408
      (*htab->free_with_arg_f) (htab->alloc_arg, entries);
409
      (*htab->free_with_arg_f) (htab->alloc_arg, htab);
410
    }
411
}
412
 
413
/* This function clears all entries in the given hash table.  */
414
 
415
void
416
htab_empty (htab_t htab)
417
{
418
  size_t size = htab_size (htab);
419
  PTR *entries = htab->entries;
420
  int i;
421
 
422
  if (htab->del_f)
423
    for (i = size - 1; i >= 0; i--)
424
      if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
425
        (*htab->del_f) (entries[i]);
426
 
427
  /* Instead of clearing megabyte, downsize the table.  */
428
  if (size > 1024*1024 / sizeof (PTR))
429
    {
430
      int nindex = higher_prime_index (1024 / sizeof (PTR));
431
      int nsize = prime_tab[nindex].prime;
432
 
433
      if (htab->free_f != NULL)
434
        (*htab->free_f) (htab->entries);
435
      else if (htab->free_with_arg_f != NULL)
436
        (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
437
      if (htab->alloc_with_arg_f != NULL)
438
        htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
439
                                                           sizeof (PTR *));
440
      else
441
        htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
442
     htab->size = nsize;
443
     htab->size_prime_index = nindex;
444
    }
445
  else
446
    memset (entries, 0, size * sizeof (PTR));
447
  htab->n_deleted = 0;
448
  htab->n_elements = 0;
449
}
450
 
451
/* Similar to htab_find_slot, but without several unwanted side effects:
452
    - Does not call htab->eq_f when it finds an existing entry.
453
    - Does not change the count of elements/searches/collisions in the
454
      hash table.
455
   This function also assumes there are no deleted entries in the table.
456
   HASH is the hash value for the element to be inserted.  */
457
 
458
static PTR *
459
find_empty_slot_for_expand (htab_t htab, hashval_t hash)
460
{
461
  hashval_t index = htab_mod (hash, htab);
462
  size_t size = htab_size (htab);
463
  PTR *slot = htab->entries + index;
464
  hashval_t hash2;
465
 
466
  if (*slot == HTAB_EMPTY_ENTRY)
467
    return slot;
468
  else if (*slot == HTAB_DELETED_ENTRY)
469
    abort ();
470
 
471
  hash2 = htab_mod_m2 (hash, htab);
472
  for (;;)
473
    {
474
      index += hash2;
475
      if (index >= size)
476
        index -= size;
477
 
478
      slot = htab->entries + index;
479
      if (*slot == HTAB_EMPTY_ENTRY)
480
        return slot;
481
      else if (*slot == HTAB_DELETED_ENTRY)
482
        abort ();
483
    }
484
}
485
 
486
/* The following function changes size of memory allocated for the
487
   entries and repeatedly inserts the table elements.  The occupancy
488
   of the table after the call will be about 50%.  Naturally the hash
489
   table must already exist.  Remember also that the place of the
490
   table entries is changed.  If memory allocation failures are allowed,
491
   this function will return zero, indicating that the table could not be
492
   expanded.  If all goes well, it will return a non-zero value.  */
493
 
494
static int
495
htab_expand (htab_t htab)
496
{
497
  PTR *oentries;
498
  PTR *olimit;
499
  PTR *p;
500
  PTR *nentries;
501
  size_t nsize, osize, elts;
502
  unsigned int oindex, nindex;
503
 
504
  oentries = htab->entries;
505
  oindex = htab->size_prime_index;
506
  osize = htab->size;
507
  olimit = oentries + osize;
508
  elts = htab_elements (htab);
509
 
510
  /* Resize only when table after removal of unused elements is either
511
     too full or too empty.  */
512
  if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
513
    {
514
      nindex = higher_prime_index (elts * 2);
515
      nsize = prime_tab[nindex].prime;
516
    }
517
  else
518
    {
519
      nindex = oindex;
520
      nsize = osize;
521
    }
522
 
523
  if (htab->alloc_with_arg_f != NULL)
524
    nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
525
                                                  sizeof (PTR *));
526
  else
527
    nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
528
  if (nentries == NULL)
529
    return 0;
530
  htab->entries = nentries;
531
  htab->size = nsize;
532
  htab->size_prime_index = nindex;
533
  htab->n_elements -= htab->n_deleted;
534
  htab->n_deleted = 0;
535
 
536
  p = oentries;
537
  do
538
    {
539
      PTR x = *p;
540
 
541
      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
542
        {
543
          PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
544
 
545
          *q = x;
546
        }
547
 
548
      p++;
549
    }
550
  while (p < olimit);
551
 
552
  if (htab->free_f != NULL)
553
    (*htab->free_f) (oentries);
554
  else if (htab->free_with_arg_f != NULL)
555
    (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
556
  return 1;
557
}
558
 
559
/* This function searches for a hash table entry equal to the given
560
   element.  It cannot be used to insert or delete an element.  */
561
 
562
PTR
563
htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
564
{
565
  hashval_t index, hash2;
566
  size_t size;
567
  PTR entry;
568
 
569
  htab->searches++;
570
  size = htab_size (htab);
571
  index = htab_mod (hash, htab);
572
 
573
  entry = htab->entries[index];
574
  if (entry == HTAB_EMPTY_ENTRY
575
      || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
576
    return entry;
577
 
578
  hash2 = htab_mod_m2 (hash, htab);
579
  for (;;)
580
    {
581
      htab->collisions++;
582
      index += hash2;
583
      if (index >= size)
584
        index -= size;
585
 
586
      entry = htab->entries[index];
587
      if (entry == HTAB_EMPTY_ENTRY
588
          || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
589
        return entry;
590
    }
591
}
592
 
593
/* Like htab_find_slot_with_hash, but compute the hash value from the
594
   element.  */
595
 
596
PTR
597
htab_find (htab_t htab, const PTR element)
598
{
599
  return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
600
}
601
 
602
/* This function searches for a hash table slot containing an entry
603
   equal to the given element.  To delete an entry, call this with
604
   insert=NO_INSERT, then call htab_clear_slot on the slot returned
605
   (possibly after doing some checks).  To insert an entry, call this
606
   with insert=INSERT, then write the value you want into the returned
607
   slot.  When inserting an entry, NULL may be returned if memory
608
   allocation fails.  */
609
 
610
PTR *
611
htab_find_slot_with_hash (htab_t htab, const PTR element,
612
                          hashval_t hash, enum insert_option insert)
613
{
614
  PTR *first_deleted_slot;
615
  hashval_t index, hash2;
616
  size_t size;
617
  PTR entry;
618
 
619
  size = htab_size (htab);
620
  if (insert == INSERT && size * 3 <= htab->n_elements * 4)
621
    {
622
      if (htab_expand (htab) == 0)
623
        return NULL;
624
      size = htab_size (htab);
625
    }
626
 
627
  index = htab_mod (hash, htab);
628
 
629
  htab->searches++;
630
  first_deleted_slot = NULL;
631
 
632
  entry = htab->entries[index];
633
  if (entry == HTAB_EMPTY_ENTRY)
634
    goto empty_entry;
635
  else if (entry == HTAB_DELETED_ENTRY)
636
    first_deleted_slot = &htab->entries[index];
637
  else if ((*htab->eq_f) (entry, element))
638
    return &htab->entries[index];
639
 
640
  hash2 = htab_mod_m2 (hash, htab);
641
  for (;;)
642
    {
643
      htab->collisions++;
644
      index += hash2;
645
      if (index >= size)
646
        index -= size;
647
 
648
      entry = htab->entries[index];
649
      if (entry == HTAB_EMPTY_ENTRY)
650
        goto empty_entry;
651
      else if (entry == HTAB_DELETED_ENTRY)
652
        {
653
          if (!first_deleted_slot)
654
            first_deleted_slot = &htab->entries[index];
655
        }
656
      else if ((*htab->eq_f) (entry, element))
657
        return &htab->entries[index];
658
    }
659
 
660
 empty_entry:
661
  if (insert == NO_INSERT)
662
    return NULL;
663
 
664
  if (first_deleted_slot)
665
    {
666
      htab->n_deleted--;
667
      *first_deleted_slot = HTAB_EMPTY_ENTRY;
668
      return first_deleted_slot;
669
    }
670
 
671
  htab->n_elements++;
672
  return &htab->entries[index];
673
}
674
 
675
/* Like htab_find_slot_with_hash, but compute the hash value from the
676
   element.  */
677
 
678
PTR *
679
htab_find_slot (htab_t htab, const PTR element, enum insert_option insert)
680
{
681
  return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
682
                                   insert);
683
}
684
 
685
/* This function deletes an element with the given value from hash
686
   table (the hash is computed from the element).  If there is no matching
687
   element in the hash table, this function does nothing.  */
688
 
689
void
690
htab_remove_elt (htab_t htab, PTR element)
691
{
692
  htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
693
}
694
 
695
 
696
/* This function deletes an element with the given value from hash
697
   table.  If there is no matching element in the hash table, this
698
   function does nothing.  */
699
 
700
void
701
htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
702
{
703
  PTR *slot;
704
 
705
  slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
706
  if (*slot == HTAB_EMPTY_ENTRY)
707
    return;
708
 
709
  if (htab->del_f)
710
    (*htab->del_f) (*slot);
711
 
712
  *slot = HTAB_DELETED_ENTRY;
713
  htab->n_deleted++;
714
}
715
 
716
/* This function clears a specified slot in a hash table.  It is
717
   useful when you've already done the lookup and don't want to do it
718
   again.  */
719
 
720
void
721
htab_clear_slot (htab_t htab, PTR *slot)
722
{
723
  if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
724
      || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
725
    abort ();
726
 
727
  if (htab->del_f)
728
    (*htab->del_f) (*slot);
729
 
730
  *slot = HTAB_DELETED_ENTRY;
731
  htab->n_deleted++;
732
}
733
 
734
/* This function scans over the entire hash table calling
735
   CALLBACK for each live entry.  If CALLBACK returns false,
736
   the iteration stops.  INFO is passed as CALLBACK's second
737
   argument.  */
738
 
739
void
740
htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
741
{
742
  PTR *slot;
743
  PTR *limit;
744
 
745
  slot = htab->entries;
746
  limit = slot + htab_size (htab);
747
 
748
  do
749
    {
750
      PTR x = *slot;
751
 
752
      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
753
        if (!(*callback) (slot, info))
754
          break;
755
    }
756
  while (++slot < limit);
757
}
758
 
759
/* Like htab_traverse_noresize, but does resize the table when it is
760
   too empty to improve effectivity of subsequent calls.  */
761
 
762
void
763
htab_traverse (htab_t htab, htab_trav callback, PTR info)
764
{
765
  size_t size = htab_size (htab);
766
  if (htab_elements (htab) * 8 < size && size > 32)
767
    htab_expand (htab);
768
 
769
  htab_traverse_noresize (htab, callback, info);
770
}
771
 
772
/* Return the fraction of fixed collisions during all work with given
773
   hash table. */
774
 
775
double
776
htab_collisions (htab_t htab)
777
{
778
  if (htab->searches == 0)
779
    return 0.0;
780
 
781
  return (double) htab->collisions / (double) htab->searches;
782
}
783
 
784
/* Hash P as a null-terminated string.
785
 
786
   Copied from gcc/hashtable.c.  Zack had the following to say with respect
787
   to applicability, though note that unlike hashtable.c, this hash table
788
   implementation re-hashes rather than chain buckets.
789
 
790
   http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
791
   From: Zack Weinberg <zackw@panix.com>
792
   Date: Fri, 17 Aug 2001 02:15:56 -0400
793
 
794
   I got it by extracting all the identifiers from all the source code
795
   I had lying around in mid-1999, and testing many recurrences of
796
   the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
797
   prime numbers or the appropriate identity.  This was the best one.
798
   I don't remember exactly what constituted "best", except I was
799
   looking at bucket-length distributions mostly.
800
 
801
   So it should be very good at hashing identifiers, but might not be
802
   as good at arbitrary strings.
803
 
804
   I'll add that it thoroughly trounces the hash functions recommended
805
   for this use at http://burtleburtle.net/bob/hash/index.html, both
806
   on speed and bucket distribution.  I haven't tried it against the
807
   function they just started using for Perl's hashes.  */
808
 
809
hashval_t
810
htab_hash_string (const PTR p)
811
{
812
  const unsigned char *str = (const unsigned char *) p;
813
  hashval_t r = 0;
814
  unsigned char c;
815
 
816
  while ((c = *str++) != 0)
817
    r = r * 67 + c - 113;
818
 
819
  return r;
820
}
821
 
822
/* DERIVED FROM:
823
--------------------------------------------------------------------
824
lookup2.c, by Bob Jenkins, December 1996, Public Domain.
825
hash(), hash2(), hash3, and mix() are externally useful functions.
826
Routines to test the hash are included if SELF_TEST is defined.
827
You can use this free for any purpose.  It has no warranty.
828
--------------------------------------------------------------------
829
*/
830
 
831
/*
832
--------------------------------------------------------------------
833
mix -- mix 3 32-bit values reversibly.
834
For every delta with one or two bit set, and the deltas of all three
835
  high bits or all three low bits, whether the original value of a,b,c
836
  is almost all zero or is uniformly distributed,
837
* If mix() is run forward or backward, at least 32 bits in a,b,c
838
  have at least 1/4 probability of changing.
839
* If mix() is run forward, every bit of c will change between 1/3 and
840
  2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
841
mix() was built out of 36 single-cycle latency instructions in a
842
  structure that could supported 2x parallelism, like so:
843
      a -= b;
844
      a -= c; x = (c>>13);
845
      b -= c; a ^= x;
846
      b -= a; x = (a<<8);
847
      c -= a; b ^= x;
848
      c -= b; x = (b>>13);
849
      ...
850
  Unfortunately, superscalar Pentiums and Sparcs can't take advantage
851
  of that parallelism.  They've also turned some of those single-cycle
852
  latency instructions into multi-cycle latency instructions.  Still,
853
  this is the fastest good hash I could find.  There were about 2^^68
854
  to choose from.  I only looked at a billion or so.
855
--------------------------------------------------------------------
856
*/
857
/* same, but slower, works on systems that might have 8 byte hashval_t's */
858
#define mix(a,b,c) \
859
{ \
860
  a -= b; a -= c; a ^= (c>>13); \
861
  b -= c; b -= a; b ^= (a<< 8); \
862
  c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
863
  a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
864
  b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
865
  c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
866
  a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
867
  b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
868
  c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
869
}
870
 
871
/*
872
--------------------------------------------------------------------
873
hash() -- hash a variable-length key into a 32-bit value
874
  k     : the key (the unaligned variable-length array of bytes)
875
  len   : the length of the key, counting by bytes
876
  level : can be any 4-byte value
877
Returns a 32-bit value.  Every bit of the key affects every bit of
878
the return value.  Every 1-bit and 2-bit delta achieves avalanche.
879
About 36+6len instructions.
880
 
881
The best hash table sizes are powers of 2.  There is no need to do
882
mod a prime (mod is sooo slow!).  If you need less than 32 bits,
883
use a bitmask.  For example, if you need only 10 bits, do
884
  h = (h & hashmask(10));
885
In which case, the hash table should have hashsize(10) elements.
886
 
887
If you are hashing n strings (ub1 **)k, do it like this:
888
  for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
889
 
890
By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
891
code any way you wish, private, educational, or commercial.  It's free.
892
 
893
See http://burtleburtle.net/bob/hash/evahash.html
894
Use for hash table lookup, or anything where one collision in 2^32 is
895
acceptable.  Do NOT use for cryptographic purposes.
896
--------------------------------------------------------------------
897
*/
898
 
899
hashval_t
900
iterative_hash (const PTR k_in /* the key */,
901
                register size_t  length /* the length of the key */,
902
                register hashval_t initval /* the previous hash, or
903
                                              an arbitrary value */)
904
{
905
  register const unsigned char *k = (const unsigned char *)k_in;
906
  register hashval_t a,b,c,len;
907
 
908
  /* Set up the internal state */
909
  len = length;
910
  a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
911
  c = initval;           /* the previous hash value */
912
 
913
  /*---------------------------------------- handle most of the key */
914
#ifndef WORDS_BIGENDIAN
915
  /* On a little-endian machine, if the data is 4-byte aligned we can hash
916
     by word for better speed.  This gives nondeterministic results on
917
     big-endian machines.  */
918
  if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0)
919
    while (len >= 12)    /* aligned */
920
      {
921
        a += *(hashval_t *)(k+0);
922
        b += *(hashval_t *)(k+4);
923
        c += *(hashval_t *)(k+8);
924
        mix(a,b,c);
925
        k += 12; len -= 12;
926
      }
927
  else /* unaligned */
928
#endif
929
    while (len >= 12)
930
      {
931
        a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
932
        b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
933
        c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
934
        mix(a,b,c);
935
        k += 12; len -= 12;
936
      }
937
 
938
  /*------------------------------------- handle the last 11 bytes */
939
  c += length;
940
  switch(len)              /* all the case statements fall through */
941
    {
942
    case 11: c+=((hashval_t)k[10]<<24);
943
    case 10: c+=((hashval_t)k[9]<<16);
944
    case 9 : c+=((hashval_t)k[8]<<8);
945
      /* the first byte of c is reserved for the length */
946
    case 8 : b+=((hashval_t)k[7]<<24);
947
    case 7 : b+=((hashval_t)k[6]<<16);
948
    case 6 : b+=((hashval_t)k[5]<<8);
949
    case 5 : b+=k[4];
950
    case 4 : a+=((hashval_t)k[3]<<24);
951
    case 3 : a+=((hashval_t)k[2]<<16);
952
    case 2 : a+=((hashval_t)k[1]<<8);
953
    case 1 : a+=k[0];
954
      /* case 0: nothing left to add */
955
    }
956
  mix(a,b,c);
957
  /*-------------------------------------------- report the result */
958
  return c;
959
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.