remove unused files
[platform/upstream/gcc48.git] / gcc / hash-table.h
1 /* A type-safe hash table template.
2    Copyright (C) 2012-2013 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
160
161 #ifndef TYPED_HASHTAB_H
162 #define TYPED_HASHTAB_H
163
164 #include "hashtab.h"
165
166
167 /* The ordinary memory allocator.  */
168 /* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
169
170 template <typename Type>
171 struct xcallocator
172 {
173   static Type *control_alloc (size_t count);
174   static Type *data_alloc (size_t count);
175   static void control_free (Type *memory);
176   static void data_free (Type *memory);
177 };
178
179
180 /* Allocate memory for COUNT control blocks.  */
181
182 template <typename Type>
183 inline Type *
184 xcallocator <Type>::control_alloc (size_t count)
185 {
186   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
187 }
188
189
190 /* Allocate memory for COUNT data blocks.  */
191
192 template <typename Type>
193 inline Type *
194 xcallocator <Type>::data_alloc (size_t count)
195 {
196   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
197 }
198
199
200 /* Free memory for control blocks.  */
201
202 template <typename Type>
203 inline void
204 xcallocator <Type>::control_free (Type *memory)
205 {
206   return ::free (memory);
207 }
208
209
210 /* Free memory for data blocks.  */
211
212 template <typename Type>
213 inline void
214 xcallocator <Type>::data_free (Type *memory)
215 {
216   return ::free (memory);
217 }
218
219
220 /* Helpful type for removing with free.  */
221
222 template <typename Type>
223 struct typed_free_remove
224 {
225   static inline void remove (Type *p);
226 };
227
228
229 /* Remove with free.  */
230
231 template <typename Type>
232 inline void
233 typed_free_remove <Type>::remove (Type *p)
234 {
235   free (p);
236 }
237
238
239 /* Helpful type for a no-op remove.  */
240
241 template <typename Type>
242 struct typed_noop_remove
243 {
244   static inline void remove (Type *p);
245 };
246
247
248 /* Remove doing nothing.  */
249
250 template <typename Type>
251 inline void
252 typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED)
253 {
254 }
255
256
257 /* Pointer hash with a no-op remove method.  */
258
259 template <typename Type>
260 struct pointer_hash : typed_noop_remove <Type>
261 {
262   typedef Type value_type;
263   typedef Type compare_type;
264
265   static inline hashval_t
266   hash (const value_type *);
267
268   static inline int
269   equal (const value_type *existing, const compare_type *candidate);
270 };
271
272 template <typename Type>
273 inline hashval_t
274 pointer_hash <Type>::hash (const value_type *candidate)
275 {
276   /* This is a really poor hash function, but it is what the current code uses,
277      so I am reusing it to avoid an additional axis in testing.  */
278   return (hashval_t) ((intptr_t)candidate >> 3);
279 }
280
281 template <typename Type>
282 inline int
283 pointer_hash <Type>::equal (const value_type *existing,
284                            const compare_type *candidate)
285 {
286   return existing == candidate;
287 }
288
289
290 /* Table of primes and their inversion information.  */
291
292 struct prime_ent
293 {
294   hashval_t prime;
295   hashval_t inv;
296   hashval_t inv_m2;     /* inverse of prime-2 */
297   hashval_t shift;
298 };
299
300 extern struct prime_ent const prime_tab[];
301
302
303 /* Functions for computing hash table indexes.  */
304
305 extern unsigned int hash_table_higher_prime_index (unsigned long n);
306 extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
307 extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
308
309
310 /* Internal implementation type.  */
311
312 template <typename T>
313 struct hash_table_control
314 {
315   /* Table itself.  */
316   T **entries;
317
318   /* Current size (in entries) of the hash table.  */
319   size_t size;
320
321   /* Current number of elements including also deleted elements.  */
322   size_t n_elements;
323
324   /* Current number of deleted elements in the table.  */
325   size_t n_deleted;
326
327   /* The following member is used for debugging. Its value is number
328      of all calls of `htab_find_slot' for the hash table. */
329   unsigned int searches;
330
331   /* The following member is used for debugging.  Its value is number
332      of collisions fixed for time of work with the hash table. */
333   unsigned int collisions;
334
335   /* Current size (in entries) of the hash table, as an index into the
336      table of primes.  */
337   unsigned int size_prime_index;
338 };
339
340
341 /* User-facing hash table type.
342
343    The table stores elements of type Descriptor::value_type.
344
345    It hashes values with the hash member function.
346      The table currently works with relatively weak hash functions.
347      Use typed_pointer_hash <Value> when hashing pointers instead of objects.
348
349    It compares elements with the equal member function.
350      Two elements with the same hash may not be equal.
351      Use typed_pointer_equal <Value> when hashing pointers instead of objects.
352
353    It removes elements with the remove member function.
354      This feature is useful for freeing memory.
355      Derive from typed_null_remove <Value> when not freeing objects.
356      Derive from typed_free_remove <Value> when doing a simple object free.
357
358    Specify the template Allocator to allocate and free memory.
359      The default is xcallocator.
360
361 */
362
363 template <typename Descriptor,
364           template <typename Type> class Allocator = xcallocator>
365 class hash_table
366 {
367 public:
368   typedef typename Descriptor::value_type value_type;
369   typedef typename Descriptor::compare_type compare_type;
370
371 private:
372   hash_table_control <value_type> *htab;
373
374   value_type **find_empty_slot_for_expand (hashval_t hash);
375   void expand ();
376
377 public:
378   hash_table ();
379   void create (size_t initial_slots);
380   bool is_created ();
381   void dispose ();
382   value_type *find (const compare_type *comparable);
383   value_type *find_with_hash (const compare_type *comparable, hashval_t hash);
384   value_type **find_slot (const compare_type *comparable,
385                           enum insert_option insert);
386   value_type **find_slot_with_hash (const compare_type *comparable,
387                                     hashval_t hash, enum insert_option insert);
388   void empty ();
389   void clear_slot (value_type **slot);
390   void remove_elt (const compare_type *comparable);
391   void remove_elt_with_hash (const compare_type *comparable, hashval_t hash);
392   size_t size();
393   size_t elements();
394   double collisions();
395
396   template <typename Argument,
397             int (*Callback) (value_type **slot, Argument argument)>
398   void traverse_noresize (Argument argument);
399
400   template <typename Argument,
401             int (*Callback) (value_type **slot, Argument argument)>
402   void traverse (Argument argument);
403 };
404
405
406 /* Construct the hash table.  The only useful operation next is create.  */
407
408 template <typename Descriptor,
409           template <typename Type> class Allocator>
410 inline
411 hash_table <Descriptor, Allocator>::hash_table ()
412 : htab (NULL)
413 {
414 }
415
416
417 /* See if the table has been created, as opposed to constructed.  */
418
419 template <typename Descriptor,
420           template <typename Type> class Allocator>
421 inline bool
422 hash_table <Descriptor, Allocator>::is_created ()
423 {
424   return htab != NULL;
425 }
426
427
428 /* Like find_with_hash, but compute the hash value from the element.  */
429
430 template <typename Descriptor,
431           template <typename Type> class Allocator>
432 inline typename Descriptor::value_type *
433 hash_table <Descriptor, Allocator>::find (const compare_type *comparable)
434 {
435   return find_with_hash (comparable, Descriptor::hash (comparable));
436 }
437
438
439 /* Like find_slot_with_hash, but compute the hash value from the element.  */
440
441 template <typename Descriptor,
442           template <typename Type> class Allocator>
443 inline typename Descriptor::value_type **
444 hash_table <Descriptor, Allocator>
445 ::find_slot (const compare_type *comparable, enum insert_option insert)
446 {
447   return find_slot_with_hash (comparable, Descriptor::hash (comparable), insert);
448 }
449
450
451 /* Like remove_elt_with_hash, but compute the hash value from the element.  */
452
453 template <typename Descriptor,
454           template <typename Type> class Allocator>
455 inline void
456 hash_table <Descriptor, Allocator>::remove_elt (const compare_type *comparable)
457 {
458   remove_elt_with_hash (comparable, Descriptor::hash (comparable));
459 }
460
461
462 /* Return the current size of this hash table.  */
463
464 template <typename Descriptor,
465           template <typename Type> class Allocator>
466 inline size_t
467 hash_table <Descriptor, Allocator>::size()
468 {
469   return htab->size;
470 }
471
472
473 /* Return the current number of elements in this hash table. */
474
475 template <typename Descriptor,
476           template <typename Type> class Allocator>
477 inline size_t
478 hash_table <Descriptor, Allocator>::elements()
479 {
480   return htab->n_elements - htab->n_deleted;
481 }
482
483
484   /* Return the fraction of fixed collisions during all work with given
485      hash table. */
486
487 template <typename Descriptor,
488           template <typename Type> class Allocator>
489 inline double
490 hash_table <Descriptor, Allocator>::collisions()
491 {
492   if (htab->searches == 0)
493     return 0.0;
494
495   return static_cast <double> (htab->collisions) / htab->searches;
496 }
497
498
499 /* Create a hash table with at least the given number of INITIAL_SLOTS.  */
500
501 template <typename Descriptor,
502           template <typename Type> class Allocator>
503 void
504 hash_table <Descriptor, Allocator>::create (size_t size)
505 {
506   unsigned int size_prime_index;
507
508   size_prime_index = hash_table_higher_prime_index (size);
509   size = prime_tab[size_prime_index].prime;
510
511   htab = Allocator <hash_table_control <value_type> > ::control_alloc (1);
512   gcc_assert (htab != NULL);
513   htab->entries = Allocator <value_type*> ::data_alloc (size);
514   gcc_assert (htab->entries != NULL);
515   htab->size = size;
516   htab->size_prime_index = size_prime_index;
517 }
518
519
520 /* Dispose of a hash table.  Free all memory and return this hash table to
521    the non-created state.  Naturally the hash table must already exist.  */
522
523 template <typename Descriptor,
524           template <typename Type> class Allocator>
525 void
526 hash_table <Descriptor, Allocator>::dispose ()
527 {
528   size_t size = htab->size;
529   value_type **entries = htab->entries;
530
531   for (int i = size - 1; i >= 0; i--)
532     if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
533       Descriptor::remove (entries[i]);
534
535   Allocator <value_type *> ::data_free (entries);
536   Allocator <hash_table_control <value_type> > ::control_free (htab);
537   htab = NULL;
538 }
539
540
541 /* Similar to find_slot, but without several unwanted side effects:
542     - Does not call equal when it finds an existing entry.
543     - Does not change the count of elements/searches/collisions in the
544       hash table.
545    This function also assumes there are no deleted entries in the table.
546    HASH is the hash value for the element to be inserted.  */
547
548 template <typename Descriptor,
549           template <typename Type> class Allocator>
550 typename Descriptor::value_type **
551 hash_table <Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
552 {
553   hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
554   size_t size = htab->size;
555   value_type **slot = htab->entries + index;
556   hashval_t hash2;
557
558   if (*slot == HTAB_EMPTY_ENTRY)
559     return slot;
560   else if (*slot == HTAB_DELETED_ENTRY)
561     abort ();
562
563   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
564   for (;;)
565     {
566       index += hash2;
567       if (index >= size)
568         index -= size;
569
570       slot = htab->entries + index;
571       if (*slot == HTAB_EMPTY_ENTRY)
572         return slot;
573       else if (*slot == HTAB_DELETED_ENTRY)
574         abort ();
575     }
576 }
577
578
579 /* The following function changes size of memory allocated for the
580    entries and repeatedly inserts the table elements.  The occupancy
581    of the table after the call will be about 50%.  Naturally the hash
582    table must already exist.  Remember also that the place of the
583    table entries is changed.  If memory allocation fails, this function
584    will abort.  */
585
586 template <typename Descriptor,
587           template <typename Type> class Allocator>
588 void
589 hash_table <Descriptor, Allocator>::expand ()
590 {
591   value_type **oentries;
592   value_type **olimit;
593   value_type **p;
594   value_type **nentries;
595   size_t nsize, osize, elts;
596   unsigned int oindex, nindex;
597
598   oentries = htab->entries;
599   oindex = htab->size_prime_index;
600   osize = htab->size;
601   olimit = oentries + osize;
602   elts = elements ();
603
604   /* Resize only when table after removal of unused elements is either
605      too full or too empty.  */
606   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
607     {
608       nindex = hash_table_higher_prime_index (elts * 2);
609       nsize = prime_tab[nindex].prime;
610     }
611   else
612     {
613       nindex = oindex;
614       nsize = osize;
615     }
616
617   nentries = Allocator <value_type *> ::data_alloc (nsize);
618   gcc_assert (nentries != NULL);
619   htab->entries = nentries;
620   htab->size = nsize;
621   htab->size_prime_index = nindex;
622   htab->n_elements -= htab->n_deleted;
623   htab->n_deleted = 0;
624
625   p = oentries;
626   do
627     {
628       value_type *x = *p;
629
630       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
631         {
632           value_type **q = find_empty_slot_for_expand (Descriptor::hash (x));
633
634           *q = x;
635         }
636
637       p++;
638     }
639   while (p < olimit);
640
641   Allocator <value_type *> ::data_free (oentries);
642 }
643
644
645 /* This function searches for a hash table entry equal to the given
646    COMPARABLE element starting with the given HASH value.  It cannot
647    be used to insert or delete an element. */
648
649 template <typename Descriptor,
650           template <typename Type> class Allocator>
651 typename Descriptor::value_type *
652 hash_table <Descriptor, Allocator>
653 ::find_with_hash (const compare_type *comparable, hashval_t hash)
654 {
655   hashval_t index, hash2;
656   size_t size;
657   value_type *entry;
658
659   htab->searches++;
660   size = htab->size;
661   index = hash_table_mod1 (hash, htab->size_prime_index);
662
663   entry = htab->entries[index];
664   if (entry == HTAB_EMPTY_ENTRY
665       || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable)))
666     return entry;
667
668   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
669   for (;;)
670     {
671       htab->collisions++;
672       index += hash2;
673       if (index >= size)
674         index -= size;
675
676       entry = htab->entries[index];
677       if (entry == HTAB_EMPTY_ENTRY
678           || (entry != HTAB_DELETED_ENTRY
679               && Descriptor::equal (entry, comparable)))
680         return entry;
681     }
682 }
683
684
685 /* This function searches for a hash table slot containing an entry
686    equal to the given COMPARABLE element and starting with the given
687    HASH.  To delete an entry, call this with insert=NO_INSERT, then
688    call clear_slot on the slot returned (possibly after doing some
689    checks).  To insert an entry, call this with insert=INSERT, then
690    write the value you want into the returned slot.  When inserting an
691    entry, NULL may be returned if memory allocation fails. */
692
693 template <typename Descriptor,
694           template <typename Type> class Allocator>
695 typename Descriptor::value_type **
696 hash_table <Descriptor, Allocator>
697 ::find_slot_with_hash (const compare_type *comparable, hashval_t hash,
698                        enum insert_option insert)
699 {
700   value_type **first_deleted_slot;
701   hashval_t index, hash2;
702   size_t size;
703   value_type *entry;
704
705   size = htab->size;
706   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
707     {
708       expand ();
709       size = htab->size;
710     }
711
712   index = hash_table_mod1 (hash, htab->size_prime_index);
713
714   htab->searches++;
715   first_deleted_slot = NULL;
716
717   entry = htab->entries[index];
718   if (entry == HTAB_EMPTY_ENTRY)
719     goto empty_entry;
720   else if (entry == HTAB_DELETED_ENTRY)
721     first_deleted_slot = &htab->entries[index];
722   else if (Descriptor::equal (entry, comparable))
723     return &htab->entries[index];
724
725   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
726   for (;;)
727     {
728       htab->collisions++;
729       index += hash2;
730       if (index >= size)
731         index -= size;
732
733       entry = htab->entries[index];
734       if (entry == HTAB_EMPTY_ENTRY)
735         goto empty_entry;
736       else if (entry == HTAB_DELETED_ENTRY)
737         {
738           if (!first_deleted_slot)
739             first_deleted_slot = &htab->entries[index];
740         }
741       else if (Descriptor::equal (entry, comparable))
742         return &htab->entries[index];
743     }
744
745  empty_entry:
746   if (insert == NO_INSERT)
747     return NULL;
748
749   if (first_deleted_slot)
750     {
751       htab->n_deleted--;
752       *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY);
753       return first_deleted_slot;
754     }
755
756   htab->n_elements++;
757   return &htab->entries[index];
758 }
759
760
761 /* This function clears all entries in the given hash table.  */
762
763 template <typename Descriptor,
764           template <typename Type> class Allocator>
765 void
766 hash_table <Descriptor, Allocator>::empty ()
767 {
768   size_t size = htab->size;
769   value_type **entries = htab->entries;
770   int i;
771
772   for (i = size - 1; i >= 0; i--)
773     if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
774       Descriptor::remove (entries[i]);
775
776   /* Instead of clearing megabyte, downsize the table.  */
777   if (size > 1024*1024 / sizeof (PTR))
778     {
779       int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
780       int nsize = prime_tab[nindex].prime;
781
782       Allocator <value_type *> ::data_free (htab->entries);
783       htab->entries = Allocator <value_type *> ::data_alloc (nsize);
784       htab->size = nsize;
785       htab->size_prime_index = nindex;
786     }
787   else
788     memset (entries, 0, size * sizeof (value_type *));
789   htab->n_deleted = 0;
790   htab->n_elements = 0;
791 }
792
793
794 /* This function clears a specified SLOT in a hash table.  It is
795    useful when you've already done the lookup and don't want to do it
796    again. */
797
798 template <typename Descriptor,
799           template <typename Type> class Allocator>
800 void
801 hash_table <Descriptor, Allocator>::clear_slot (value_type **slot)
802 {
803   if (slot < htab->entries || slot >= htab->entries + htab->size
804       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
805     abort ();
806
807   Descriptor::remove (*slot);
808
809   *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
810   htab->n_deleted++;
811 }
812
813
814 /* This function deletes an element with the given COMPARABLE value
815    from hash table starting with the given HASH.  If there is no
816    matching element in the hash table, this function does nothing. */
817
818 template <typename Descriptor,
819           template <typename Type> class Allocator>
820 void
821 hash_table <Descriptor, Allocator>
822 ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash)
823 {
824   value_type **slot;
825
826   slot = find_slot_with_hash (comparable, hash, NO_INSERT);
827   if (*slot == HTAB_EMPTY_ENTRY)
828     return;
829
830   Descriptor::remove (*slot);
831
832   *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
833   htab->n_deleted++;
834 }
835
836
837 /* This function scans over the entire hash table calling CALLBACK for
838    each live entry.  If CALLBACK returns false, the iteration stops.
839    ARGUMENT is passed as CALLBACK's second argument. */
840
841 template <typename Descriptor,
842           template <typename Type> class Allocator>
843 template <typename Argument,
844           int (*Callback) (typename Descriptor::value_type **slot, Argument argument)>
845 void
846 hash_table <Descriptor, Allocator>::traverse_noresize (Argument argument)
847 {
848   value_type **slot;
849   value_type **limit;
850
851   slot = htab->entries;
852   limit = slot + htab->size;
853
854   do
855     {
856       value_type *x = *slot;
857
858       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
859         if (! Callback (slot, argument))
860           break;
861     }
862   while (++slot < limit);
863 }
864
865
866 /* Like traverse_noresize, but does resize the table when it is too empty
867    to improve effectivity of subsequent calls.  */
868
869 template <typename Descriptor,
870           template <typename Type> class Allocator>
871 template <typename Argument,
872           int (*Callback) (typename Descriptor::value_type **slot,
873                            Argument argument)>
874 void
875 hash_table <Descriptor, Allocator>::traverse (Argument argument)
876 {
877   size_t size = htab->size;
878   if (elements () * 8 < size && size > 32)
879     expand ();
880
881   traverse_noresize <Argument, Callback> (argument);
882 }
883
884 #endif /* TYPED_HASHTAB_H */