gcc/hash-table.h

   1 /* A type-safe hash table template.
   2    Copyright (C) 2012-2014 Free Software Foundation, Inc.
   3    Contributed by Lawrence Crowl <crowl@google.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21
  22 /* This file implements a typed hash table.
  23    The implementation borrows from libiberty's htab_t in hashtab.h.
  24
  25
  26    INTRODUCTION TO TYPES
  27
  28    Users of the hash table generally need to be aware of three types.
  29
  30       1. The type being placed into the hash table.  This type is called
  31       the value type.
  32
  33       2. The type used to describe how to handle the value type within
  34       the hash table.  This descriptor type provides the hash table with
  35       several things.
  36
  37          - A typedef named 'value_type' to the value type (from above).
  38
  39          - A static member function named 'hash' that takes a value_type
  40          pointer and returns a hashval_t value.
  41
  42          - A typedef named 'compare_type' that is used to test when an value
  43          is found.  This type is the comparison type.  Usually, it will be the
  44          same as value_type.  If it is not the same type, you must generally
  45          explicitly compute hash values and pass them to the hash table.
  46
  47          - A static member function named 'equal' that takes a value_type
  48          pointer and a compare_type pointer, and returns a bool.
  49
  50          - A static function named 'remove' that takes an value_type pointer
  51          and frees the memory allocated by it.  This function is used when
  52          individual elements of the table need to be disposed of (e.g.,
  53          when deleting a hash table, removing elements from the table, etc).
  54
  55       3. The type of the hash table itself.  (More later.)
  56
  57    In very special circumstances, users may need to know about a fourth type.
  58
  59       4. The template type used to describe how hash table memory
  60       is allocated.  This type is called the allocator type.  It is
  61       parameterized on the value type.  It provides four functions.
  62
  63          - A static member function named 'control_alloc'.  This function
  64          allocates the control data blocks for the table.
  65
  66          - A static member function named 'control_free'.  This function
  67          frees the control data blocks for the table.
  68
  69          - A static member function named 'data_alloc'.  This function
  70          allocates the data elements in the table.
  71
  72          - A static member function named 'data_free'.  This function
  73          deallocates the data elements in the table.
  74
  75    Hash table are instantiated with two type arguments.
  76
  77       * The descriptor type, (2) above.
  78
  79       * The allocator type, (4) above.  In general, you will not need to
  80       provide your own allocator type.  By default, hash tables will use
  81       the class template xcallocator, which uses malloc/free for allocation.
  82
  83
  84    DEFINING A DESCRIPTOR TYPE
  85
  86    The first task in using the hash table is to describe the element type.
  87    We compose this into a few steps.
  88
  89       1. Decide on a removal policy for values stored in the table.
  90          This header provides class templates for the two most common
  91          policies.
  92
  93          * typed_free_remove implements the static 'remove' member function
  94          by calling free().
  95
  96          * typed_noop_remove implements the static 'remove' member function
  97          by doing nothing.
  98
  99          You can use these policies by simply deriving the descriptor type
 100          from one of those class template, with the appropriate argument.
 101
 102          Otherwise, you need to write the static 'remove' member function
 103          in the descriptor class.
 104
 105       2. Choose a hash function.  Write the static 'hash' member function.
 106
 107       3. Choose an equality testing function.  In most cases, its two
 108       arguments will be value_type pointers.  If not, the first argument must
 109       be a value_type pointer, and the second argument a compare_type pointer.
 110
 111
 112    AN EXAMPLE DESCRIPTOR TYPE
 113
 114    Suppose you want to put some_type into the hash table.  You could define
 115    the descriptor type as follows.
 116
 117       struct some_type_hasher : typed_noop_remove <some_type>
 118       // Deriving from typed_noop_remove means that we get a 'remove' that does
 119       // nothing.  This choice is good for raw values.
 120       {
 121         typedef some_type value_type;
 122         typedef some_type compare_type;
 123         static inline hashval_t hash (const value_type *);
 124         static inline bool equal (const value_type *, const compare_type *);
 125       };
 126
 127       inline hashval_t
 128       some_type_hasher::hash (const value_type *e)
 129       { ... compute and return a hash value for E ... }
 130
 131       inline bool
 132       some_type_hasher::equal (const value_type *p1, const compare_type *p2)
 133       { ... compare P1 vs P2.  Return true if they are the 'same' ... }
 134
 135
 136    AN EXAMPLE HASH_TABLE DECLARATION
 137
 138    To instantiate a hash table for some_type:
 139
 140       hash_table <some_type_hasher> some_type_hash_table;
 141
 142    There is no need to mention some_type directly, as the hash table will
 143    obtain it using some_type_hasher::value_type.
 144
 145    You can then used any of the functions in hash_table's public interface.
 146    See hash_table for details.  The interface is very similar to libiberty's
 147    htab_t.
 148
 149
 150    EASY DESCRIPTORS FOR POINTERS
 151
 152    The class template pointer_hash provides everything you need to hash
 153    pointers (as opposed to what they point to).  So, to instantiate a hash
 154    table over pointers to whatever_type,
 155
 156       hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
 157
 158
 159    HASH TABLE ITERATORS
 160
 161    The hash table provides standard C++ iterators.  For example, consider a
 162    hash table of some_info.  We wish to consume each element of the table:
 163
 164       extern void consume (some_info *);
 165
 166    We define a convenience typedef and the hash table:
 167
 168       typedef hash_table <some_info_hasher> info_table_type;
 169       info_table_type info_table;
 170
 171    Then we write the loop in typical C++ style:
 172
 173       for (info_table_type::iterator iter = info_table.begin ();
 174            iter != info_table.end ();
 175            ++iter)
 176         if ((*iter).status == INFO_READY)
 177           consume (&*iter);
 178
 179    Or with common sub-expression elimination:
 180
 181       for (info_table_type::iterator iter = info_table.begin ();
 182            iter != info_table.end ();
 183            ++iter)
 184         {
 185           some_info &elem = *iter;
 186           if (elem.status == INFO_READY)
 187             consume (&elem);
 188         }
 189
 190    One can also use a more typical GCC style:
 191
 192       typedef some_info *some_info_p;
 193       some_info *elem_ptr;
 194       info_table_type::iterator iter;
 195       FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
 196         if (elem_ptr->status == INFO_READY)
 197           consume (elem_ptr);
 198
 199 */
 200
 201
 202 #ifndef TYPED_HASHTAB_H
 203 #define TYPED_HASHTAB_H
 204
 205 #include "hashtab.h"
 206
 207
 208 /* The ordinary memory allocator.  */
 209 /* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
 210
 211 template <typename Type>
 212 struct xcallocator
 213 {
 214   static Type *control_alloc (size_t count);
 215   static Type *data_alloc (size_t count);
 216   static void control_free (Type *memory);
 217   static void data_free (Type *memory);
 218 };
 219
 220
 221 /* Allocate memory for COUNT control blocks.  */
 222
 223 template <typename Type>
 224 inline Type *
 225 xcallocator <Type>::control_alloc (size_t count)
 226 {
 227   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
 228 }
 229
 230
 231 /* Allocate memory for COUNT data blocks.  */
 232
 233 template <typename Type>
 234 inline Type *
 235 xcallocator <Type>::data_alloc (size_t count)
 236 {
 237   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
 238 }
 239
 240
 241 /* Free memory for control blocks.  */
 242
 243 template <typename Type>
 244 inline void
 245 xcallocator <Type>::control_free (Type *memory)
 246 {
 247   return ::free (memory);
 248 }
 249
 250
 251 /* Free memory for data blocks.  */
 252
 253 template <typename Type>
 254 inline void
 255 xcallocator <Type>::data_free (Type *memory)
 256 {
 257   return ::free (memory);
 258 }
 259
 260
 261 /* Helpful type for removing with free.  */
 262
 263 template <typename Type>
 264 struct typed_free_remove
 265 {
 266   static inline void remove (Type *p);
 267 };
 268
 269
 270 /* Remove with free.  */
 271
 272 template <typename Type>
 273 inline void
 274 typed_free_remove <Type>::remove (Type *p)
 275 {
 276   free (p);
 277 }
 278
 279
 280 /* Helpful type for a no-op remove.  */
 281
 282 template <typename Type>
 283 struct typed_noop_remove
 284 {
 285   static inline void remove (Type *p);
 286 };
 287
 288
 289 /* Remove doing nothing.  */
 290
 291 template <typename Type>
 292 inline void
 293 typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED)
 294 {
 295 }
 296
 297
 298 /* Pointer hash with a no-op remove method.  */
 299
 300 template <typename Type>
 301 struct pointer_hash : typed_noop_remove <Type>
 302 {
 303   typedef Type value_type;
 304   typedef Type compare_type;
 305
 306   static inline hashval_t
 307   hash (const value_type *);
 308
 309   static inline int
 310   equal (const value_type *existing, const compare_type *candidate);
 311 };
 312
 313 template <typename Type>
 314 inline hashval_t
 315 pointer_hash <Type>::hash (const value_type *candidate)
 316 {
 317   /* This is a really poor hash function, but it is what the current code uses,
 318      so I am reusing it to avoid an additional axis in testing.  */
 319   return (hashval_t) ((intptr_t)candidate >> 3);
 320 }
 321
 322 template <typename Type>
 323 inline int
 324 pointer_hash <Type>::equal (const value_type *existing,
 325                            const compare_type *candidate)
 326 {
 327   return existing == candidate;
 328 }
 329
 330
 331 /* Table of primes and their inversion information.  */
 332
 333 struct prime_ent
 334 {
 335   hashval_t prime;
 336   hashval_t inv;
 337   hashval_t inv_m2;     /* inverse of prime-2 */
 338   hashval_t shift;
 339 };
 340
 341 extern struct prime_ent const prime_tab[];
 342
 343
 344 /* Functions for computing hash table indexes.  */
 345
 346 extern unsigned int hash_table_higher_prime_index (unsigned long n);
 347 extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
 348 extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
 349
 350
 351 /* Internal implementation type.  */
 352
 353 template <typename T>
 354 struct hash_table_control
 355 {
 356   /* Table itself.  */
 357   T **entries;
 358
 359   /* Current size (in entries) of the hash table.  */
 360   size_t size;
 361
 362   /* Current number of elements including also deleted elements.  */
 363   size_t n_elements;
 364
 365   /* Current number of deleted elements in the table.  */
 366   size_t n_deleted;
 367
 368   /* The following member is used for debugging. Its value is number
 369      of all calls of `htab_find_slot' for the hash table. */
 370   unsigned int searches;
 371
 372   /* The following member is used for debugging.  Its value is number
 373      of collisions fixed for time of work with the hash table. */
 374   unsigned int collisions;
 375
 376   /* Current size (in entries) of the hash table, as an index into the
 377      table of primes.  */
 378   unsigned int size_prime_index;
 379 };
 380
 381
 382 /* User-facing hash table type.
 383
 384    The table stores elements of type Descriptor::value_type.
 385
 386    It hashes values with the hash member function.
 387      The table currently works with relatively weak hash functions.
 388      Use typed_pointer_hash <Value> when hashing pointers instead of objects.
 389
 390    It compares elements with the equal member function.
 391      Two elements with the same hash may not be equal.
 392      Use typed_pointer_equal <Value> when hashing pointers instead of objects.
 393
 394    It removes elements with the remove member function.
 395      This feature is useful for freeing memory.
 396      Derive from typed_null_remove <Value> when not freeing objects.
 397      Derive from typed_free_remove <Value> when doing a simple object free.
 398
 399    Specify the template Allocator to allocate and free memory.
 400      The default is xcallocator.
 401
 402 */
 403
 404 template <typename Descriptor,
 405           template <typename Type> class Allocator = xcallocator>
 406 class hash_table
 407 {
 408 public:
 409   typedef typename Descriptor::value_type value_type;
 410   typedef typename Descriptor::compare_type compare_type;
 411
 412   class iterator
 413   {
 414   public:
 415     inline iterator ();
 416     inline iterator (value_type **, value_type **);
 417     inline value_type &operator * ();
 418     void slide ();
 419     inline iterator &operator ++ ();
 420     inline bool operator != (const iterator &) const;
 421   private:
 422     value_type **m_slot;
 423     value_type **m_limit;
 424   };
 425
 426 private:
 427   hash_table_control <value_type> *htab;
 428
 429   value_type **find_empty_slot_for_expand (hashval_t hash);
 430   void expand ();
 431
 432 public:
 433   hash_table ();
 434   void create (size_t initial_slots);
 435   bool is_created ();
 436   void dispose ();
 437   value_type *find (const value_type *value);
 438   value_type *find_with_hash (const compare_type *comparable, hashval_t hash);
 439   value_type **find_slot (const value_type *value, enum insert_option insert);
 440   value_type **find_slot_with_hash (const compare_type *comparable,
 441                                     hashval_t hash, enum insert_option insert);
 442   void empty ();
 443   void clear_slot (value_type **slot);
 444   void remove_elt (const value_type *value);
 445   void remove_elt_with_hash (const compare_type *comparable, hashval_t hash);
 446   size_t size ();
 447   size_t elements ();
 448   size_t elements_with_deleted ();
 449   double collisions ();
 450
 451   template <typename Argument,
 452             int (*Callback) (value_type **slot, Argument argument)>
 453   void traverse_noresize (Argument argument);
 454
 455   template <typename Argument,
 456             int (*Callback) (value_type **slot, Argument argument)>
 457   void traverse (Argument argument);
 458
 459   iterator begin ();
 460   iterator end ();
 461 };
 462
 463
 464 /* Construct the hash table.  The only useful operation next is create.  */
 465
 466 template <typename Descriptor,
 467           template <typename Type> class Allocator>
 468 inline
 469 hash_table <Descriptor, Allocator>::hash_table ()
 470 : htab (NULL)
 471 {
 472 }
 473
 474
 475 /* See if the table has been created, as opposed to constructed.  */
 476
 477 template <typename Descriptor,
 478           template <typename Type> class Allocator>
 479 inline bool
 480 hash_table <Descriptor, Allocator>::is_created ()
 481 {
 482   return htab != NULL;
 483 }
 484
 485
 486 /* Like find_with_hash, but compute the hash value from the element.  */
 487
 488 template <typename Descriptor,
 489           template <typename Type> class Allocator>
 490 inline typename Descriptor::value_type *
 491 hash_table <Descriptor, Allocator>::find (const value_type *value)
 492 {
 493   return find_with_hash (value, Descriptor::hash (value));
 494 }
 495
 496
 497 /* Like find_slot_with_hash, but compute the hash value from the element.  */
 498
 499 template <typename Descriptor,
 500           template <typename Type> class Allocator>
 501 inline typename Descriptor::value_type **
 502 hash_table <Descriptor, Allocator>
 503 ::find_slot (const value_type *value, enum insert_option insert)
 504 {
 505   return find_slot_with_hash (value, Descriptor::hash (value), insert);
 506 }
 507
 508
 509 /* Like remove_elt_with_hash, but compute the hash value from the element.  */
 510
 511 template <typename Descriptor,
 512           template <typename Type> class Allocator>
 513 inline void
 514 hash_table <Descriptor, Allocator>::remove_elt (const value_type *value)
 515 {
 516   remove_elt_with_hash (value, Descriptor::hash (value));
 517 }
 518
 519
 520 /* Return the current size of this hash table.  */
 521
 522 template <typename Descriptor,
 523           template <typename Type> class Allocator>
 524 inline size_t
 525 hash_table <Descriptor, Allocator>::size ()
 526 {
 527   return htab->size;
 528 }
 529
 530
 531 /* Return the current number of elements in this hash table. */
 532
 533 template <typename Descriptor,
 534           template <typename Type> class Allocator>
 535 inline size_t
 536 hash_table <Descriptor, Allocator>::elements ()
 537 {
 538   return htab->n_elements - htab->n_deleted;
 539 }
 540
 541
 542 /* Return the current number of elements in this hash table. */
 543
 544 template <typename Descriptor,
 545           template <typename Type> class Allocator>
 546 inline size_t
 547 hash_table <Descriptor, Allocator>::elements_with_deleted ()
 548 {
 549   return htab->n_elements;
 550 }
 551
 552
 553   /* Return the fraction of fixed collisions during all work with given
 554      hash table. */
 555
 556 template <typename Descriptor,
 557           template <typename Type> class Allocator>
 558 inline double
 559 hash_table <Descriptor, Allocator>::collisions ()
 560 {
 561   if (htab->searches == 0)
 562     return 0.0;
 563
 564   return static_cast <double> (htab->collisions) / htab->searches;
 565 }
 566
 567
 568 /* Create a hash table with at least the given number of INITIAL_SLOTS.  */
 569
 570 template <typename Descriptor,
 571           template <typename Type> class Allocator>
 572 void
 573 hash_table <Descriptor, Allocator>::create (size_t size)
 574 {
 575   unsigned int size_prime_index;
 576
 577   size_prime_index = hash_table_higher_prime_index (size);
 578   size = prime_tab[size_prime_index].prime;
 579
 580   htab = Allocator <hash_table_control <value_type> > ::control_alloc (1);
 581   gcc_assert (htab != NULL);
 582   htab->entries = Allocator <value_type*> ::data_alloc (size);
 583   gcc_assert (htab->entries != NULL);
 584   htab->size = size;
 585   htab->size_prime_index = size_prime_index;
 586 }
 587
 588
 589 /* Dispose of a hash table.  Free all memory and return this hash table to
 590    the non-created state.  Naturally the hash table must already exist.  */
 591
 592 template <typename Descriptor,
 593           template <typename Type> class Allocator>
 594 void
 595 hash_table <Descriptor, Allocator>::dispose ()
 596 {
 597   size_t size = htab->size;
 598   value_type **entries = htab->entries;
 599
 600   for (int i = size - 1; i >= 0; i--)
 601     if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 602       Descriptor::remove (entries[i]);
 603
 604   Allocator <value_type *> ::data_free (entries);
 605   Allocator <hash_table_control <value_type> > ::control_free (htab);
 606   htab = NULL;
 607 }
 608
 609
 610 /* Similar to find_slot, but without several unwanted side effects:
 611     - Does not call equal when it finds an existing entry.
 612     - Does not change the count of elements/searches/collisions in the
 613       hash table.
 614    This function also assumes there are no deleted entries in the table.
 615    HASH is the hash value for the element to be inserted.  */
 616
 617 template <typename Descriptor,
 618           template <typename Type> class Allocator>
 619 typename Descriptor::value_type **
 620 hash_table <Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
 621 {
 622   hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
 623   size_t size = htab->size;
 624   value_type **slot = htab->entries + index;
 625   hashval_t hash2;
 626
 627   if (*slot == HTAB_EMPTY_ENTRY)
 628     return slot;
 629   else if (*slot == HTAB_DELETED_ENTRY)
 630     abort ();
 631
 632   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
 633   for (;;)
 634     {
 635       index += hash2;
 636       if (index >= size)
 637         index -= size;
 638
 639       slot = htab->entries + index;
 640       if (*slot == HTAB_EMPTY_ENTRY)
 641         return slot;
 642       else if (*slot == HTAB_DELETED_ENTRY)
 643         abort ();
 644     }
 645 }
 646
 647
 648 /* The following function changes size of memory allocated for the
 649    entries and repeatedly inserts the table elements.  The occupancy
 650    of the table after the call will be about 50%.  Naturally the hash
 651    table must already exist.  Remember also that the place of the
 652    table entries is changed.  If memory allocation fails, this function
 653    will abort.  */
 654
 655 template <typename Descriptor,
 656           template <typename Type> class Allocator>
 657 void
 658 hash_table <Descriptor, Allocator>::expand ()
 659 {
 660   value_type **oentries;
 661   value_type **olimit;
 662   value_type **p;
 663   value_type **nentries;
 664   size_t nsize, osize, elts;
 665   unsigned int oindex, nindex;
 666
 667   oentries = htab->entries;
 668   oindex = htab->size_prime_index;
 669   osize = htab->size;
 670   olimit = oentries + osize;
 671   elts = elements ();
 672
 673   /* Resize only when table after removal of unused elements is either
 674      too full or too empty.  */
 675   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 676     {
 677       nindex = hash_table_higher_prime_index (elts * 2);
 678       nsize = prime_tab[nindex].prime;
 679     }
 680   else
 681     {
 682       nindex = oindex;
 683       nsize = osize;
 684     }
 685
 686   nentries = Allocator <value_type *> ::data_alloc (nsize);
 687   gcc_assert (nentries != NULL);
 688   htab->entries = nentries;
 689   htab->size = nsize;
 690   htab->size_prime_index = nindex;
 691   htab->n_elements -= htab->n_deleted;
 692   htab->n_deleted = 0;
 693
 694   p = oentries;
 695   do
 696     {
 697       value_type *x = *p;
 698
 699       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 700         {
 701           value_type **q = find_empty_slot_for_expand (Descriptor::hash (x));
 702
 703           *q = x;
 704         }
 705
 706       p++;
 707     }
 708   while (p < olimit);
 709
 710   Allocator <value_type *> ::data_free (oentries);
 711 }
 712
 713
 714 /* This function searches for a hash table entry equal to the given
 715    COMPARABLE element starting with the given HASH value.  It cannot
 716    be used to insert or delete an element. */
 717
 718 template <typename Descriptor,
 719           template <typename Type> class Allocator>
 720 typename Descriptor::value_type *
 721 hash_table <Descriptor, Allocator>
 722 ::find_with_hash (const compare_type *comparable, hashval_t hash)
 723 {
 724   hashval_t index, hash2;
 725   size_t size;
 726   value_type *entry;
 727
 728   htab->searches++;
 729   size = htab->size;
 730   index = hash_table_mod1 (hash, htab->size_prime_index);
 731
 732   entry = htab->entries[index];
 733   if (entry == HTAB_EMPTY_ENTRY
 734       || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable)))
 735     return entry;
 736
 737   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
 738   for (;;)
 739     {
 740       htab->collisions++;
 741       index += hash2;
 742       if (index >= size)
 743         index -= size;
 744
 745       entry = htab->entries[index];
 746       if (entry == HTAB_EMPTY_ENTRY
 747           || (entry != HTAB_DELETED_ENTRY
 748               && Descriptor::equal (entry, comparable)))
 749         return entry;
 750     }
 751 }
 752
 753
 754 /* This function searches for a hash table slot containing an entry
 755    equal to the given COMPARABLE element and starting with the given
 756    HASH.  To delete an entry, call this with insert=NO_INSERT, then
 757    call clear_slot on the slot returned (possibly after doing some
 758    checks).  To insert an entry, call this with insert=INSERT, then
 759    write the value you want into the returned slot.  When inserting an
 760    entry, NULL may be returned if memory allocation fails. */
 761
 762 template <typename Descriptor,
 763           template <typename Type> class Allocator>
 764 typename Descriptor::value_type **
 765 hash_table <Descriptor, Allocator>
 766 ::find_slot_with_hash (const compare_type *comparable, hashval_t hash,
 767                        enum insert_option insert)
 768 {
 769   value_type **first_deleted_slot;
 770   hashval_t index, hash2;
 771   size_t size;
 772   value_type *entry;
 773
 774   size = htab->size;
 775   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
 776     {
 777       expand ();
 778       size = htab->size;
 779     }
 780
 781   index = hash_table_mod1 (hash, htab->size_prime_index);
 782
 783   htab->searches++;
 784   first_deleted_slot = NULL;
 785
 786   entry = htab->entries[index];
 787   if (entry == HTAB_EMPTY_ENTRY)
 788     goto empty_entry;
 789   else if (entry == HTAB_DELETED_ENTRY)
 790     first_deleted_slot = &htab->entries[index];
 791   else if (Descriptor::equal (entry, comparable))
 792     return &htab->entries[index];
 793
 794   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
 795   for (;;)
 796     {
 797       htab->collisions++;
 798       index += hash2;
 799       if (index >= size)
 800         index -= size;
 801
 802       entry = htab->entries[index];
 803       if (entry == HTAB_EMPTY_ENTRY)
 804         goto empty_entry;
 805       else if (entry == HTAB_DELETED_ENTRY)
 806         {
 807           if (!first_deleted_slot)
 808             first_deleted_slot = &htab->entries[index];
 809         }
 810       else if (Descriptor::equal (entry, comparable))
 811         return &htab->entries[index];
 812     }
 813
 814  empty_entry:
 815   if (insert == NO_INSERT)
 816     return NULL;
 817
 818   if (first_deleted_slot)
 819     {
 820       htab->n_deleted--;
 821       *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY);
 822       return first_deleted_slot;
 823     }
 824
 825   htab->n_elements++;
 826   return &htab->entries[index];
 827 }
 828
 829
 830 /* This function clears all entries in the given hash table.  */
 831
 832 template <typename Descriptor,
 833           template <typename Type> class Allocator>
 834 void
 835 hash_table <Descriptor, Allocator>::empty ()
 836 {
 837   size_t size = htab->size;
 838   value_type **entries = htab->entries;
 839   int i;
 840
 841   for (i = size - 1; i >= 0; i--)
 842     if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 843       Descriptor::remove (entries[i]);
 844
 845   /* Instead of clearing megabyte, downsize the table.  */
 846   if (size > 1024*1024 / sizeof (PTR))
 847     {
 848       int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
 849       int nsize = prime_tab[nindex].prime;
 850
 851       Allocator <value_type *> ::data_free (htab->entries);
 852       htab->entries = Allocator <value_type *> ::data_alloc (nsize);
 853       htab->size = nsize;
 854       htab->size_prime_index = nindex;
 855     }
 856   else
 857     memset (entries, 0, size * sizeof (value_type *));
 858   htab->n_deleted = 0;
 859   htab->n_elements = 0;
 860 }
 861
 862
 863 /* This function clears a specified SLOT in a hash table.  It is
 864    useful when you've already done the lookup and don't want to do it
 865    again. */
 866
 867 template <typename Descriptor,
 868           template <typename Type> class Allocator>
 869 void
 870 hash_table <Descriptor, Allocator>::clear_slot (value_type **slot)
 871 {
 872   if (slot < htab->entries || slot >= htab->entries + htab->size
 873       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
 874     abort ();
 875
 876   Descriptor::remove (*slot);
 877
 878   *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
 879   htab->n_deleted++;
 880 }
 881
 882
 883 /* This function deletes an element with the given COMPARABLE value
 884    from hash table starting with the given HASH.  If there is no
 885    matching element in the hash table, this function does nothing. */
 886
 887 template <typename Descriptor,
 888           template <typename Type> class Allocator>
 889 void
 890 hash_table <Descriptor, Allocator>
 891 ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash)
 892 {
 893   value_type **slot;
 894
 895   slot = find_slot_with_hash (comparable, hash, NO_INSERT);
 896   if (*slot == HTAB_EMPTY_ENTRY)
 897     return;
 898
 899   Descriptor::remove (*slot);
 900
 901   *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
 902   htab->n_deleted++;
 903 }
 904
 905
 906 /* This function scans over the entire hash table calling CALLBACK for
 907    each live entry.  If CALLBACK returns false, the iteration stops.
 908    ARGUMENT is passed as CALLBACK's second argument. */
 909
 910 template <typename Descriptor,
 911           template <typename Type> class Allocator>
 912 template <typename Argument,
 913           int (*Callback) (typename Descriptor::value_type **slot, Argument argument)>
 914 void
 915 hash_table <Descriptor, Allocator>::traverse_noresize (Argument argument)
 916 {
 917   value_type **slot;
 918   value_type **limit;
 919
 920   slot = htab->entries;
 921   limit = slot + htab->size;
 922
 923   do
 924     {
 925       value_type *x = *slot;
 926
 927       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 928         if (! Callback (slot, argument))
 929           break;
 930     }
 931   while (++slot < limit);
 932 }
 933
 934
 935 /* Like traverse_noresize, but does resize the table when it is too empty
 936    to improve effectivity of subsequent calls.  */
 937
 938 template <typename Descriptor,
 939           template <typename Type> class Allocator>
 940 template <typename Argument,
 941           int (*Callback) (typename Descriptor::value_type **slot,
 942                            Argument argument)>
 943 void
 944 hash_table <Descriptor, Allocator>::traverse (Argument argument)
 945 {
 946   size_t size = htab->size;
 947   if (elements () * 8 < size && size > 32)
 948     expand ();
 949
 950   traverse_noresize <Argument, Callback> (argument);
 951 }
 952
 953
 954 /* Iterator definitions.  */
 955
 956 /* The default constructor produces the end value.  */
 957
 958 template <typename Descriptor,
 959           template <typename Type> class Allocator>
 960 inline
 961 hash_table <Descriptor, Allocator>::iterator::iterator ()
 962 : m_slot (NULL), m_limit (NULL)
 963 {
 964 }
 965
 966 /* The parameterized constructor produces the begin value.  */
 967
 968 template <typename Descriptor,
 969           template <typename Type> class Allocator>
 970 inline
 971 hash_table <Descriptor, Allocator>::iterator::iterator
 972    (value_type **slot, value_type **limit)
 973 : m_slot (slot), m_limit (limit)
 974 {
 975 }
 976
 977 /* Obtain the element.  */
 978
 979 template <typename Descriptor,
 980           template <typename Type> class Allocator>
 981 inline typename hash_table <Descriptor, Allocator>::value_type &
 982 hash_table <Descriptor, Allocator>::iterator::operator * ()
 983 {
 984   return **m_slot;
 985 }
 986
 987 /* Slide down the iterator slots until an active entry is found.  */
 988
 989 template <typename Descriptor,
 990           template <typename Type> class Allocator>
 991 void
 992 hash_table <Descriptor, Allocator>::iterator::slide ()
 993 {
 994   for ( ; m_slot < m_limit; ++m_slot )
 995     {
 996       value_type *x = *m_slot;
 997       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 998         return;
 999     }
1000   m_slot = NULL;
1001   m_limit = NULL;
1002 }
1003
1004 /* Bump the iterator.  */
1005
1006 template <typename Descriptor,
1007           template <typename Type> class Allocator>
1008 inline typename hash_table <Descriptor, Allocator>::iterator &
1009 hash_table <Descriptor, Allocator>::iterator::operator ++ ()
1010 {
1011   ++m_slot;
1012   slide ();
1013   return *this;
1014 }
1015
1016 /* Compare iterators.  */
1017
1018 template <typename Descriptor,
1019           template <typename Type> class Allocator>
1020 inline bool
1021 hash_table <Descriptor, Allocator>::iterator::
1022   operator != (const iterator &other) const
1023 {
1024   return m_slot != other.m_slot || m_limit != other.m_limit;
1025 }
1026
1027 /* Hash table iterator producers.  */
1028
1029 /* The beginning of a hash table iteration.  */
1030
1031 template <typename Descriptor,
1032           template <typename Type> class Allocator>
1033 inline typename hash_table <Descriptor, Allocator>::iterator
1034 hash_table <Descriptor, Allocator>::begin ()
1035 {
1036   iterator hti (htab->entries, htab->entries + htab->size);
1037   hti.slide ();
1038   return hti;
1039 }
1040
1041 /* The end of a hash table iteration.  */
1042
1043 template <typename Descriptor,
1044           template <typename Type> class Allocator>
1045 inline typename hash_table <Descriptor, Allocator>::iterator
1046 hash_table <Descriptor, Allocator>::end ()
1047 {
1048   return iterator ();
1049 }
1050
1051 /* Iterate through the elements of hash_table HTAB,
1052    using hash_table <....>::iterator ITER,
1053    storing each element in RESULT, which is of type TYPE.  */
1054
1055 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1056   for ((ITER) = (HTAB).begin (); \
1057        (ITER) != (HTAB).end () ? (RESULT = &*(ITER) , true) : false; \
1058        ++(ITER))
1059
1060 #endif /* TYPED_HASHTAB_H */