1 /* A type-safe hash table template.
2 Copyright (C) 2012-2015 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
5 This file is part of GCC.
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
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
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/>. */
22 /* This file implements a typed hash table.
23 The implementation borrows from libiberty's htab_t in hashtab.h.
28 Users of the hash table generally need to be aware of three types.
30 1. The type being placed into the hash table. This type is called
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
37 - A typedef named 'value_type' to the value type (from above).
39 - A static member function named 'hash' that takes a value_type
40 pointer and returns a hashval_t value.
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.
47 - A static member function named 'equal' that takes a value_type
48 pointer and a compare_type pointer, and returns a bool.
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).
55 3. The type of the hash table itself. (More later.)
57 In very special circumstances, users may need to know about a fourth type.
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.
63 - A static member function named 'data_alloc'. This function
64 allocates the data elements in the table.
66 - A static member function named 'data_free'. This function
67 deallocates the data elements in the table.
69 Hash table are instantiated with two type arguments.
71 * The descriptor type, (2) above.
73 * The allocator type, (4) above. In general, you will not need to
74 provide your own allocator type. By default, hash tables will use
75 the class template xcallocator, which uses malloc/free for allocation.
78 DEFINING A DESCRIPTOR TYPE
80 The first task in using the hash table is to describe the element type.
81 We compose this into a few steps.
83 1. Decide on a removal policy for values stored in the table.
84 This header provides class templates for the two most common
87 * typed_free_remove implements the static 'remove' member function
90 * typed_noop_remove implements the static 'remove' member function
93 You can use these policies by simply deriving the descriptor type
94 from one of those class template, with the appropriate argument.
96 Otherwise, you need to write the static 'remove' member function
97 in the descriptor class.
99 2. Choose a hash function. Write the static 'hash' member function.
101 3. Choose an equality testing function. In most cases, its two
102 arguments will be value_type pointers. If not, the first argument must
103 be a value_type pointer, and the second argument a compare_type pointer.
106 AN EXAMPLE DESCRIPTOR TYPE
108 Suppose you want to put some_type into the hash table. You could define
109 the descriptor type as follows.
111 struct some_type_hasher : typed_noop_remove <some_type>
112 // Deriving from typed_noop_remove means that we get a 'remove' that does
113 // nothing. This choice is good for raw values.
115 typedef some_type value_type;
116 typedef some_type compare_type;
117 static inline hashval_t hash (const value_type *);
118 static inline bool equal (const value_type *, const compare_type *);
122 some_type_hasher::hash (const value_type *e)
123 { ... compute and return a hash value for E ... }
126 some_type_hasher::equal (const value_type *p1, const compare_type *p2)
127 { ... compare P1 vs P2. Return true if they are the 'same' ... }
130 AN EXAMPLE HASH_TABLE DECLARATION
132 To instantiate a hash table for some_type:
134 hash_table <some_type_hasher> some_type_hash_table;
136 There is no need to mention some_type directly, as the hash table will
137 obtain it using some_type_hasher::value_type.
139 You can then used any of the functions in hash_table's public interface.
140 See hash_table for details. The interface is very similar to libiberty's
144 EASY DESCRIPTORS FOR POINTERS
146 The class template pointer_hash provides everything you need to hash
147 pointers (as opposed to what they point to). So, to instantiate a hash
148 table over pointers to whatever_type,
150 hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
155 The hash table provides standard C++ iterators. For example, consider a
156 hash table of some_info. We wish to consume each element of the table:
158 extern void consume (some_info *);
160 We define a convenience typedef and the hash table:
162 typedef hash_table <some_info_hasher> info_table_type;
163 info_table_type info_table;
165 Then we write the loop in typical C++ style:
167 for (info_table_type::iterator iter = info_table.begin ();
168 iter != info_table.end ();
170 if ((*iter).status == INFO_READY)
173 Or with common sub-expression elimination:
175 for (info_table_type::iterator iter = info_table.begin ();
176 iter != info_table.end ();
179 some_info &elem = *iter;
180 if (elem.status == INFO_READY)
184 One can also use a more typical GCC style:
186 typedef some_info *some_info_p;
188 info_table_type::iterator iter;
189 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
190 if (elem_ptr->status == INFO_READY)
196 #ifndef TYPED_HASHTAB_H
197 #define TYPED_HASHTAB_H
203 template<typename
, typename
, typename
> class hash_map
;
204 template<typename
, typename
> class hash_set
;
206 /* The ordinary memory allocator. */
207 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
209 template <typename Type
>
212 static Type
*data_alloc (size_t count
);
213 static void data_free (Type
*memory
);
217 /* Allocate memory for COUNT data blocks. */
219 template <typename Type
>
221 xcallocator
<Type
>::data_alloc (size_t count
)
223 return static_cast <Type
*> (xcalloc (count
, sizeof (Type
)));
227 /* Free memory for data blocks. */
229 template <typename Type
>
231 xcallocator
<Type
>::data_free (Type
*memory
)
233 return ::free (memory
);
237 /* Helpful type for removing with free. */
239 template <typename Type
>
240 struct typed_free_remove
242 static inline void remove (Type
*p
);
246 /* Remove with free. */
248 template <typename Type
>
250 typed_free_remove
<Type
>::remove (Type
*p
)
256 /* Helpful type for a no-op remove. */
258 template <typename Type
>
259 struct typed_noop_remove
261 static inline void remove (Type
*p
);
265 /* Remove doing nothing. */
267 template <typename Type
>
269 typed_noop_remove
<Type
>::remove (Type
*p ATTRIBUTE_UNUSED
)
274 /* Pointer hash with a no-op remove method. */
276 template <typename Type
>
277 struct pointer_hash
: typed_noop_remove
<Type
>
279 typedef Type
*value_type
;
280 typedef Type
*compare_type
;
281 typedef int store_values_directly
;
283 static inline hashval_t
hash (const value_type
&);
285 static inline bool equal (const value_type
&existing
,
286 const compare_type
&candidate
);
289 template <typename Type
>
291 pointer_hash
<Type
>::hash (const value_type
&candidate
)
293 /* This is a really poor hash function, but it is what the current code uses,
294 so I am reusing it to avoid an additional axis in testing. */
295 return (hashval_t
) ((intptr_t)candidate
>> 3);
298 template <typename Type
>
300 pointer_hash
<Type
>::equal (const value_type
&existing
,
301 const compare_type
&candidate
)
303 return existing
== candidate
;
306 /* Hasher for entry in gc memory. */
311 typedef T value_type
;
312 typedef T compare_type
;
313 typedef int store_values_directly
;
315 static void remove (T
) {}
320 extern void gt_ggc_mx (T
&);
327 extern void gt_pch_nx (T
&);
332 pch_nx (T
&p
, gt_pointer_operator op
, void *cookie
)
338 /* Hasher for cache entry in gc memory. */
341 struct ggc_cache_hasher
343 typedef T value_type
;
344 typedef T compare_type
;
345 typedef int store_values_directly
;
347 static void remove (T
&) {}
349 /* Entries are weakly held because this is for caches. */
351 static void ggc_mx (T
&) {}
356 extern void gt_pch_nx (T
&);
361 pch_nx (T
&p
, gt_pointer_operator op
, void *cookie
)
366 /* Clear out entries if they are about to be gc'd. */
369 handle_cache_entry (T
&e
)
371 if (e
!= HTAB_EMPTY_ENTRY
&& e
!= HTAB_DELETED_ENTRY
&& !ggc_marked_p (e
))
372 e
= static_cast<T
> (HTAB_DELETED_ENTRY
);
377 /* Table of primes and their inversion information. */
383 hashval_t inv_m2
; /* inverse of prime-2 */
387 extern struct prime_ent
const prime_tab
[];
390 /* Functions for computing hash table indexes. */
392 extern unsigned int hash_table_higher_prime_index (unsigned long n
)
395 /* Return X % Y using multiplicative inverse values INV and SHIFT.
397 The multiplicative inverses computed above are for 32-bit types,
398 and requires that we be able to compute a highpart multiply.
400 FIX: I am not at all convinced that
401 3 loads, 2 multiplications, 3 shifts, and 3 additions
404 on modern systems running a compiler. */
407 mul_mod (hashval_t x
, hashval_t y
, hashval_t inv
, int shift
)
409 hashval_t t1
, t2
, t3
, t4
, q
, r
;
411 t1
= ((uint64_t)x
* inv
) >> 32;
421 /* Compute the primary table index for HASH given current prime index. */
424 hash_table_mod1 (hashval_t hash
, unsigned int index
)
426 const struct prime_ent
*p
= &prime_tab
[index
];
427 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
428 return mul_mod (hash
, p
->prime
, p
->inv
, p
->shift
);
431 /* Compute the secondary table index for HASH given current prime index. */
434 hash_table_mod2 (hashval_t hash
, unsigned int index
)
436 const struct prime_ent
*p
= &prime_tab
[index
];
437 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
438 return 1 + mul_mod (hash
, p
->prime
- 2, p
->inv_m2
, p
->shift
);
441 /* The below is some template meta programming to decide if we should use the
442 hash table partial specialization that directly stores value_type instead of
443 pointers to value_type. If the Descriptor type defines the type
444 Descriptor::store_values_directly then values are stored directly otherwise
445 pointers to them are stored. */
446 template<typename T
> struct notype
{ typedef void type
; };
448 template<typename T
, typename
= void>
449 struct storage_tester
451 static const bool value
= false;
455 struct storage_tester
<T
, typename notype
<typename
456 T::store_values_directly
>::type
>
458 static const bool value
= true;
461 template<typename Traits
>
462 struct has_is_deleted
464 template<typename U
, bool (*)(U
&)> struct helper
{};
465 template<typename U
> static char test (helper
<U
, U::is_deleted
> *);
466 template<typename U
> static int test (...);
467 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
470 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
471 struct is_deleted_helper
476 return Traits::is_deleted (v
);
480 template<typename Type
, typename Traits
>
481 struct is_deleted_helper
<Type
*, Traits
, false>
486 return v
== HTAB_DELETED_ENTRY
;
490 template<typename Traits
>
493 template<typename U
, bool (*)(U
&)> struct helper
{};
494 template<typename U
> static char test (helper
<U
, U::is_empty
> *);
495 template<typename U
> static int test (...);
496 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
499 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
500 struct is_empty_helper
505 return Traits::is_empty (v
);
509 template<typename Type
, typename Traits
>
510 struct is_empty_helper
<Type
*, Traits
, false>
515 return v
== HTAB_EMPTY_ENTRY
;
519 template<typename Traits
>
520 struct has_mark_deleted
522 template<typename U
, void (*)(U
&)> struct helper
{};
523 template<typename U
> static char test (helper
<U
, U::mark_deleted
> *);
524 template<typename U
> static int test (...);
525 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
528 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
529 struct mark_deleted_helper
534 Traits::mark_deleted (v
);
538 template<typename Type
, typename Traits
>
539 struct mark_deleted_helper
<Type
*, Traits
, false>
544 v
= static_cast<Type
*> (HTAB_DELETED_ENTRY
);
548 template<typename Traits
>
549 struct has_mark_empty
551 template<typename U
, void (*)(U
&)> struct helper
{};
552 template<typename U
> static char test (helper
<U
, U::mark_empty
> *);
553 template<typename U
> static int test (...);
554 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
557 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
558 struct mark_empty_helper
563 Traits::mark_empty (v
);
567 template<typename Type
, typename Traits
>
568 struct mark_empty_helper
<Type
*, Traits
, false>
573 v
= static_cast<Type
*> (HTAB_EMPTY_ENTRY
);
577 /* User-facing hash table type.
579 The table stores elements of type Descriptor::value_type, or pointers to
580 objects of type value_type if the descriptor does not define the type
581 store_values_directly.
583 It hashes values with the hash member function.
584 The table currently works with relatively weak hash functions.
585 Use typed_pointer_hash <Value> when hashing pointers instead of objects.
587 It compares elements with the equal member function.
588 Two elements with the same hash may not be equal.
589 Use typed_pointer_equal <Value> when hashing pointers instead of objects.
591 It removes elements with the remove member function.
592 This feature is useful for freeing memory.
593 Derive from typed_null_remove <Value> when not freeing objects.
594 Derive from typed_free_remove <Value> when doing a simple object free.
596 Specify the template Allocator to allocate and free memory.
597 The default is xcallocator.
599 Storage is an implementation detail and should not be used outside the
603 template <typename Descriptor
,
604 template<typename Type
> class Allocator
= xcallocator
,
605 bool Storage
= storage_tester
<Descriptor
>::value
>
610 template <typename Descriptor
,
611 template<typename Type
> class Allocator
>
612 class hash_table
<Descriptor
, Allocator
, false>
614 typedef typename
Descriptor::value_type value_type
;
615 typedef typename
Descriptor::compare_type compare_type
;
618 hash_table (size_t CXX_MEM_STAT_INFO
);
621 /* Current size (in entries) of the hash table. */
622 size_t size () const { return m_size
; }
624 /* Return the current number of elements in this hash table. */
625 size_t elements () const { return m_n_elements
- m_n_deleted
; }
627 /* Return the current number of elements in this hash table. */
628 size_t elements_with_deleted () const { return m_n_elements
; }
630 /* This function clears all entries in the given hash table. */
633 /* This function clears a specified SLOT in a hash table. It is
634 useful when you've already done the lookup and don't want to do it
637 void clear_slot (value_type
**);
639 /* This function searches for a hash table entry equal to the given
640 COMPARABLE element starting with the given HASH value. It cannot
641 be used to insert or delete an element. */
642 value_type
*find_with_hash (const compare_type
*, hashval_t
);
644 /* Like find_slot_with_hash, but compute the hash value from the element. */
645 value_type
*find (const value_type
*value
)
647 return find_with_hash (value
, Descriptor::hash (value
));
650 value_type
**find_slot (const value_type
*value
, insert_option insert
)
652 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
655 /* This function searches for a hash table slot containing an entry
656 equal to the given COMPARABLE element and starting with the given
657 HASH. To delete an entry, call this with insert=NO_INSERT, then
658 call clear_slot on the slot returned (possibly after doing some
659 checks). To insert an entry, call this with insert=INSERT, then
660 write the value you want into the returned slot. When inserting an
661 entry, NULL may be returned if memory allocation fails. */
662 value_type
**find_slot_with_hash (const compare_type
*comparable
,
663 hashval_t hash
, enum insert_option insert
);
665 /* This function deletes an element with the given COMPARABLE value
666 from hash table starting with the given HASH. If there is no
667 matching element in the hash table, this function does nothing. */
668 void remove_elt_with_hash (const compare_type
*, hashval_t
);
670 /* Like remove_elt_with_hash, but compute the hash value from the element. */
671 void remove_elt (const value_type
*value
)
673 remove_elt_with_hash (value
, Descriptor::hash (value
));
676 /* This function scans over the entire hash table calling CALLBACK for
677 each live entry. If CALLBACK returns false, the iteration stops.
678 ARGUMENT is passed as CALLBACK's second argument. */
679 template <typename Argument
,
680 int (*Callback
) (value_type
**slot
, Argument argument
)>
681 void traverse_noresize (Argument argument
);
683 /* Like traverse_noresize, but does resize the table when it is too empty
684 to improve effectivity of subsequent calls. */
685 template <typename Argument
,
686 int (*Callback
) (value_type
**slot
, Argument argument
)>
687 void traverse (Argument argument
);
692 iterator () : m_slot (NULL
), m_limit (NULL
) {}
694 iterator (value_type
**slot
, value_type
**limit
) :
695 m_slot (slot
), m_limit (limit
) {}
697 inline value_type
*operator * () { return *m_slot
; }
699 inline iterator
&operator ++ ();
700 bool operator != (const iterator
&other
) const
702 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
707 value_type
**m_limit
;
710 iterator
begin () const
712 iterator
iter (m_entries
, m_entries
+ m_size
);
717 iterator
end () const { return iterator (); }
719 double collisions () const
721 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
726 value_type
**find_empty_slot_for_expand (hashval_t
);
730 typename
Descriptor::value_type
**m_entries
;
734 /* Current number of elements including also deleted elements. */
737 /* Current number of deleted elements in the table. */
740 /* The following member is used for debugging. Its value is number
741 of all calls of `htab_find_slot' for the hash table. */
742 unsigned int m_searches
;
744 /* The following member is used for debugging. Its value is number
745 of collisions fixed for time of work with the hash table. */
746 unsigned int m_collisions
;
748 /* Current size (in entries) of the hash table, as an index into the
750 unsigned int m_size_prime_index
;
753 template<typename Descriptor
, template<typename Type
> class Allocator
>
754 hash_table
<Descriptor
, Allocator
, false>::hash_table (size_t size
756 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0)
758 unsigned int size_prime_index
;
760 size_prime_index
= hash_table_higher_prime_index (size
);
761 size
= prime_tab
[size_prime_index
].prime
;
763 m_entries
= Allocator
<value_type
*> ::data_alloc (size
);
764 gcc_assert (m_entries
!= NULL
);
766 m_size_prime_index
= size_prime_index
;
769 template<typename Descriptor
, template<typename Type
> class Allocator
>
770 hash_table
<Descriptor
, Allocator
, false>::~hash_table ()
772 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
773 if (m_entries
[i
] != HTAB_EMPTY_ENTRY
&& m_entries
[i
] != HTAB_DELETED_ENTRY
)
774 Descriptor::remove (m_entries
[i
]);
776 Allocator
<value_type
*> ::data_free (m_entries
);
779 /* Similar to find_slot, but without several unwanted side effects:
780 - Does not call equal when it finds an existing entry.
781 - Does not change the count of elements/searches/collisions in the
783 This function also assumes there are no deleted entries in the table.
784 HASH is the hash value for the element to be inserted. */
786 template<typename Descriptor
, template<typename Type
> class Allocator
>
787 typename hash_table
<Descriptor
, Allocator
, false>::value_type
**
788 hash_table
<Descriptor
, Allocator
, false>
789 ::find_empty_slot_for_expand (hashval_t hash
)
791 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
792 size_t size
= m_size
;
793 value_type
**slot
= m_entries
+ index
;
796 if (*slot
== HTAB_EMPTY_ENTRY
)
798 gcc_checking_assert (*slot
!= HTAB_DELETED_ENTRY
);
800 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
807 slot
= m_entries
+ index
;
808 if (*slot
== HTAB_EMPTY_ENTRY
)
810 gcc_checking_assert (*slot
!= HTAB_DELETED_ENTRY
);
814 /* The following function changes size of memory allocated for the
815 entries and repeatedly inserts the table elements. The occupancy
816 of the table after the call will be about 50%. Naturally the hash
817 table must already exist. Remember also that the place of the
818 table entries is changed. If memory allocation fails, this function
821 template<typename Descriptor
, template<typename Type
> class Allocator
>
823 hash_table
<Descriptor
, Allocator
, false>::expand ()
825 value_type
**oentries
= m_entries
;
826 unsigned int oindex
= m_size_prime_index
;
827 size_t osize
= size ();
828 value_type
**olimit
= oentries
+ osize
;
829 size_t elts
= elements ();
831 /* Resize only when table after removal of unused elements is either
832 too full or too empty. */
835 if (elts
* 2 > osize
|| (elts
* 8 < osize
&& osize
> 32))
837 nindex
= hash_table_higher_prime_index (elts
* 2);
838 nsize
= prime_tab
[nindex
].prime
;
846 value_type
**nentries
= Allocator
<value_type
*> ::data_alloc (nsize
);
847 gcc_assert (nentries
!= NULL
);
848 m_entries
= nentries
;
850 m_size_prime_index
= nindex
;
851 m_n_elements
-= m_n_deleted
;
854 value_type
**p
= oentries
;
859 if (x
!= HTAB_EMPTY_ENTRY
&& x
!= HTAB_DELETED_ENTRY
)
861 value_type
**q
= find_empty_slot_for_expand (Descriptor::hash (x
));
870 Allocator
<value_type
*> ::data_free (oentries
);
873 template<typename Descriptor
, template<typename Type
> class Allocator
>
875 hash_table
<Descriptor
, Allocator
, false>::empty ()
877 size_t size
= m_size
;
878 value_type
**entries
= m_entries
;
881 for (i
= size
- 1; i
>= 0; i
--)
882 if (entries
[i
] != HTAB_EMPTY_ENTRY
&& entries
[i
] != HTAB_DELETED_ENTRY
)
883 Descriptor::remove (entries
[i
]);
885 /* Instead of clearing megabyte, downsize the table. */
886 if (size
> 1024*1024 / sizeof (PTR
))
888 int nindex
= hash_table_higher_prime_index (1024 / sizeof (PTR
));
889 int nsize
= prime_tab
[nindex
].prime
;
891 Allocator
<value_type
*> ::data_free (m_entries
);
892 m_entries
= Allocator
<value_type
*> ::data_alloc (nsize
);
894 m_size_prime_index
= nindex
;
897 memset (entries
, 0, size
* sizeof (value_type
*));
902 /* This function clears a specified SLOT in a hash table. It is
903 useful when you've already done the lookup and don't want to do it
906 template<typename Descriptor
, template<typename Type
> class Allocator
>
908 hash_table
<Descriptor
, Allocator
, false>::clear_slot (value_type
**slot
)
910 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
911 || *slot
== HTAB_EMPTY_ENTRY
912 || *slot
== HTAB_DELETED_ENTRY
));
914 Descriptor::remove (*slot
);
916 *slot
= static_cast <value_type
*> (HTAB_DELETED_ENTRY
);
920 /* This function searches for a hash table entry equal to the given
921 COMPARABLE element starting with the given HASH value. It cannot
922 be used to insert or delete an element. */
924 template<typename Descriptor
, template<typename Type
> class Allocator
>
925 typename hash_table
<Descriptor
, Allocator
, false>::value_type
*
926 hash_table
<Descriptor
, Allocator
, false>
927 ::find_with_hash (const compare_type
*comparable
, hashval_t hash
)
930 size_t size
= m_size
;
931 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
933 value_type
*entry
= m_entries
[index
];
934 if (entry
== HTAB_EMPTY_ENTRY
935 || (entry
!= HTAB_DELETED_ENTRY
&& Descriptor::equal (entry
, comparable
)))
938 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
946 entry
= m_entries
[index
];
947 if (entry
== HTAB_EMPTY_ENTRY
948 || (entry
!= HTAB_DELETED_ENTRY
949 && Descriptor::equal (entry
, comparable
)))
954 /* This function searches for a hash table slot containing an entry
955 equal to the given COMPARABLE element and starting with the given
956 HASH. To delete an entry, call this with insert=NO_INSERT, then
957 call clear_slot on the slot returned (possibly after doing some
958 checks). To insert an entry, call this with insert=INSERT, then
959 write the value you want into the returned slot. When inserting an
960 entry, NULL may be returned if memory allocation fails. */
962 template<typename Descriptor
, template<typename Type
> class Allocator
>
963 typename hash_table
<Descriptor
, Allocator
, false>::value_type
**
964 hash_table
<Descriptor
, Allocator
, false>
965 ::find_slot_with_hash (const compare_type
*comparable
, hashval_t hash
,
966 enum insert_option insert
)
968 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
973 value_type
**first_deleted_slot
= NULL
;
974 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
975 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
976 value_type
*entry
= m_entries
[index
];
977 size_t size
= m_size
;
978 if (entry
== HTAB_EMPTY_ENTRY
)
980 else if (entry
== HTAB_DELETED_ENTRY
)
981 first_deleted_slot
= &m_entries
[index
];
982 else if (Descriptor::equal (entry
, comparable
))
983 return &m_entries
[index
];
992 entry
= m_entries
[index
];
993 if (entry
== HTAB_EMPTY_ENTRY
)
995 else if (entry
== HTAB_DELETED_ENTRY
)
997 if (!first_deleted_slot
)
998 first_deleted_slot
= &m_entries
[index
];
1000 else if (Descriptor::equal (entry
, comparable
))
1001 return &m_entries
[index
];
1005 if (insert
== NO_INSERT
)
1008 if (first_deleted_slot
)
1011 *first_deleted_slot
= static_cast <value_type
*> (HTAB_EMPTY_ENTRY
);
1012 return first_deleted_slot
;
1016 return &m_entries
[index
];
1019 /* This function deletes an element with the given COMPARABLE value
1020 from hash table starting with the given HASH. If there is no
1021 matching element in the hash table, this function does nothing. */
1023 template<typename Descriptor
, template<typename Type
> class Allocator
>
1025 hash_table
<Descriptor
, Allocator
, false>
1026 ::remove_elt_with_hash (const compare_type
*comparable
, hashval_t hash
)
1028 value_type
**slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
1029 if (*slot
== HTAB_EMPTY_ENTRY
)
1032 Descriptor::remove (*slot
);
1034 *slot
= static_cast <value_type
*> (HTAB_DELETED_ENTRY
);
1038 /* This function scans over the entire hash table calling CALLBACK for
1039 each live entry. If CALLBACK returns false, the iteration stops.
1040 ARGUMENT is passed as CALLBACK's second argument. */
1042 template<typename Descriptor
, template<typename Type
> class Allocator
>
1043 template<typename Argument
,
1044 int (*Callback
) (typename hash_table
<Descriptor
, Allocator
,
1045 false>::value_type
**slot
,
1048 hash_table
<Descriptor
, Allocator
, false>::traverse_noresize (Argument argument
)
1050 value_type
**slot
= m_entries
;
1051 value_type
**limit
= slot
+ size ();
1055 value_type
*x
= *slot
;
1057 if (x
!= HTAB_EMPTY_ENTRY
&& x
!= HTAB_DELETED_ENTRY
)
1058 if (! Callback (slot
, argument
))
1061 while (++slot
< limit
);
1064 /* Like traverse_noresize, but does resize the table when it is too empty
1065 to improve effectivity of subsequent calls. */
1067 template <typename Descriptor
,
1068 template <typename Type
> class Allocator
>
1069 template <typename Argument
,
1070 int (*Callback
) (typename hash_table
<Descriptor
, Allocator
,
1071 false>::value_type
**slot
,
1074 hash_table
<Descriptor
, Allocator
, false>::traverse (Argument argument
)
1076 size_t size
= m_size
;
1077 if (elements () * 8 < size
&& size
> 32)
1080 traverse_noresize
<Argument
, Callback
> (argument
);
1083 /* Slide down the iterator slots until an active entry is found. */
1085 template<typename Descriptor
, template<typename Type
> class Allocator
>
1087 hash_table
<Descriptor
, Allocator
, false>::iterator::slide ()
1089 for ( ; m_slot
< m_limit
; ++m_slot
)
1091 value_type
*x
= *m_slot
;
1092 if (x
!= HTAB_EMPTY_ENTRY
&& x
!= HTAB_DELETED_ENTRY
)
1099 /* Bump the iterator. */
1101 template<typename Descriptor
, template<typename Type
> class Allocator
>
1102 inline typename hash_table
<Descriptor
, Allocator
, false>::iterator
&
1103 hash_table
<Descriptor
, Allocator
, false>::iterator::operator ++ ()
1110 /* A partial specialization used when values should be stored directly. */
1112 template <typename Descriptor
,
1113 template<typename Type
> class Allocator
>
1114 class hash_table
<Descriptor
, Allocator
, true>
1116 typedef typename
Descriptor::value_type value_type
;
1117 typedef typename
Descriptor::compare_type compare_type
;
1120 explicit hash_table (size_t, bool ggc
= false CXX_MEM_STAT_INFO
);
1123 /* Create a hash_table in gc memory. */
1126 create_ggc (size_t n
)
1128 hash_table
*table
= ggc_alloc
<hash_table
> ();
1129 new (table
) hash_table (n
, true);
1133 /* Current size (in entries) of the hash table. */
1134 size_t size () const { return m_size
; }
1136 /* Return the current number of elements in this hash table. */
1137 size_t elements () const { return m_n_elements
- m_n_deleted
; }
1139 /* Return the current number of elements in this hash table. */
1140 size_t elements_with_deleted () const { return m_n_elements
; }
1142 /* This function clears all entries in the given hash table. */
1145 /* This function clears a specified SLOT in a hash table. It is
1146 useful when you've already done the lookup and don't want to do it
1149 void clear_slot (value_type
*);
1151 /* This function searches for a hash table entry equal to the given
1152 COMPARABLE element starting with the given HASH value. It cannot
1153 be used to insert or delete an element. */
1154 value_type
&find_with_hash (const compare_type
&, hashval_t
);
1156 /* Like find_slot_with_hash, but compute the hash value from the element. */
1157 value_type
&find (const value_type
&value
)
1159 return find_with_hash (value
, Descriptor::hash (value
));
1162 value_type
*find_slot (const value_type
&value
, insert_option insert
)
1164 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
1167 /* This function searches for a hash table slot containing an entry
1168 equal to the given COMPARABLE element and starting with the given
1169 HASH. To delete an entry, call this with insert=NO_INSERT, then
1170 call clear_slot on the slot returned (possibly after doing some
1171 checks). To insert an entry, call this with insert=INSERT, then
1172 write the value you want into the returned slot. When inserting an
1173 entry, NULL may be returned if memory allocation fails. */
1174 value_type
*find_slot_with_hash (const compare_type
&comparable
,
1175 hashval_t hash
, enum insert_option insert
);
1177 /* This function deletes an element with the given COMPARABLE value
1178 from hash table starting with the given HASH. If there is no
1179 matching element in the hash table, this function does nothing. */
1180 void remove_elt_with_hash (const compare_type
&, hashval_t
);
1182 /* Like remove_elt_with_hash, but compute the hash value from the element. */
1183 void remove_elt (const value_type
&value
)
1185 remove_elt_with_hash (value
, Descriptor::hash (value
));
1188 /* This function scans over the entire hash table calling CALLBACK for
1189 each live entry. If CALLBACK returns false, the iteration stops.
1190 ARGUMENT is passed as CALLBACK's second argument. */
1191 template <typename Argument
,
1192 int (*Callback
) (value_type
*slot
, Argument argument
)>
1193 void traverse_noresize (Argument argument
);
1195 /* Like traverse_noresize, but does resize the table when it is too empty
1196 to improve effectivity of subsequent calls. */
1197 template <typename Argument
,
1198 int (*Callback
) (value_type
*slot
, Argument argument
)>
1199 void traverse (Argument argument
);
1204 iterator () : m_slot (NULL
), m_limit (NULL
) {}
1206 iterator (value_type
*slot
, value_type
*limit
) :
1207 m_slot (slot
), m_limit (limit
) {}
1209 inline value_type
&operator * () { return *m_slot
; }
1211 inline iterator
&operator ++ ();
1212 bool operator != (const iterator
&other
) const
1214 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
1219 value_type
*m_limit
;
1222 iterator
begin () const
1224 iterator
iter (m_entries
, m_entries
+ m_size
);
1229 iterator
end () const { return iterator (); }
1231 double collisions () const
1233 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
1237 template<typename T
> friend void gt_ggc_mx (hash_table
<T
> *);
1238 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *);
1239 template<typename T
> friend void
1240 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator
, void *);
1241 template<typename T
, typename U
, typename V
> friend void
1242 gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
1243 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *,
1244 gt_pointer_operator
,
1246 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *,
1247 gt_pointer_operator
, void *);
1249 value_type
*alloc_entries (size_t n CXX_MEM_STAT_INFO
) const;
1250 value_type
*find_empty_slot_for_expand (hashval_t
);
1252 static bool is_deleted (value_type
&v
)
1254 return is_deleted_helper
<value_type
, Descriptor
>::call (v
);
1256 static bool is_empty (value_type
&v
)
1258 return is_empty_helper
<value_type
, Descriptor
>::call (v
);
1261 static void mark_deleted (value_type
&v
)
1263 return mark_deleted_helper
<value_type
, Descriptor
>::call (v
);
1266 static void mark_empty (value_type
&v
)
1268 return mark_empty_helper
<value_type
, Descriptor
>::call (v
);
1272 typename
Descriptor::value_type
*m_entries
;
1276 /* Current number of elements including also deleted elements. */
1277 size_t m_n_elements
;
1279 /* Current number of deleted elements in the table. */
1282 /* The following member is used for debugging. Its value is number
1283 of all calls of `htab_find_slot' for the hash table. */
1284 unsigned int m_searches
;
1286 /* The following member is used for debugging. Its value is number
1287 of collisions fixed for time of work with the hash table. */
1288 unsigned int m_collisions
;
1290 /* Current size (in entries) of the hash table, as an index into the
1292 unsigned int m_size_prime_index
;
1294 /* if m_entries is stored in ggc memory. */
1298 template<typename Descriptor
, template<typename Type
> class Allocator
>
1299 hash_table
<Descriptor
, Allocator
, true>::hash_table (size_t size
, bool ggc
1301 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
1304 unsigned int size_prime_index
;
1306 size_prime_index
= hash_table_higher_prime_index (size
);
1307 size
= prime_tab
[size_prime_index
].prime
;
1309 m_entries
= alloc_entries (size PASS_MEM_STAT
);
1311 m_size_prime_index
= size_prime_index
;
1314 template<typename Descriptor
, template<typename Type
> class Allocator
>
1315 hash_table
<Descriptor
, Allocator
, true>::~hash_table ()
1317 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
1318 if (!is_empty (m_entries
[i
]) && !is_deleted (m_entries
[i
]))
1319 Descriptor::remove (m_entries
[i
]);
1322 Allocator
<value_type
> ::data_free (m_entries
);
1324 ggc_free (m_entries
);
1327 /* This function returns an array of empty hash table elements. */
1329 template<typename Descriptor
, template<typename Type
> class Allocator
>
1330 inline typename hash_table
<Descriptor
, Allocator
, true>::value_type
*
1331 hash_table
<Descriptor
, Allocator
, true>::alloc_entries
1332 (size_t n MEM_STAT_DECL
) const
1334 value_type
*nentries
;
1337 nentries
= Allocator
<value_type
> ::data_alloc (n
);
1339 nentries
= ::ggc_cleared_vec_alloc
<value_type
> (n PASS_MEM_STAT
);
1341 gcc_assert (nentries
!= NULL
);
1342 for (size_t i
= 0; i
< n
; i
++)
1343 mark_empty (nentries
[i
]);
1348 /* Similar to find_slot, but without several unwanted side effects:
1349 - Does not call equal when it finds an existing entry.
1350 - Does not change the count of elements/searches/collisions in the
1352 This function also assumes there are no deleted entries in the table.
1353 HASH is the hash value for the element to be inserted. */
1355 template<typename Descriptor
, template<typename Type
> class Allocator
>
1356 typename hash_table
<Descriptor
, Allocator
, true>::value_type
*
1357 hash_table
<Descriptor
, Allocator
, true>
1358 ::find_empty_slot_for_expand (hashval_t hash
)
1360 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
1361 size_t size
= m_size
;
1362 value_type
*slot
= m_entries
+ index
;
1365 if (is_empty (*slot
))
1367 #ifdef ENABLE_CHECKING
1368 gcc_checking_assert (!is_deleted (*slot
));
1371 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
1378 slot
= m_entries
+ index
;
1379 if (is_empty (*slot
))
1381 #ifdef ENABLE_CHECKING
1382 gcc_checking_assert (!is_deleted (*slot
));
1387 /* The following function changes size of memory allocated for the
1388 entries and repeatedly inserts the table elements. The occupancy
1389 of the table after the call will be about 50%. Naturally the hash
1390 table must already exist. Remember also that the place of the
1391 table entries is changed. If memory allocation fails, this function
1394 template<typename Descriptor
, template<typename Type
> class Allocator
>
1396 hash_table
<Descriptor
, Allocator
, true>::expand ()
1398 value_type
*oentries
= m_entries
;
1399 unsigned int oindex
= m_size_prime_index
;
1400 size_t osize
= size ();
1401 value_type
*olimit
= oentries
+ osize
;
1402 size_t elts
= elements ();
1404 /* Resize only when table after removal of unused elements is either
1405 too full or too empty. */
1406 unsigned int nindex
;
1408 if (elts
* 2 > osize
|| (elts
* 8 < osize
&& osize
> 32))
1410 nindex
= hash_table_higher_prime_index (elts
* 2);
1411 nsize
= prime_tab
[nindex
].prime
;
1419 value_type
*nentries
= alloc_entries (nsize
);
1420 m_entries
= nentries
;
1422 m_size_prime_index
= nindex
;
1423 m_n_elements
-= m_n_deleted
;
1426 value_type
*p
= oentries
;
1431 if (!is_empty (x
) && !is_deleted (x
))
1433 value_type
*q
= find_empty_slot_for_expand (Descriptor::hash (x
));
1443 Allocator
<value_type
> ::data_free (oentries
);
1445 ggc_free (oentries
);
1448 template<typename Descriptor
, template<typename Type
> class Allocator
>
1450 hash_table
<Descriptor
, Allocator
, true>::empty ()
1452 size_t size
= m_size
;
1453 value_type
*entries
= m_entries
;
1456 for (i
= size
- 1; i
>= 0; i
--)
1457 if (!is_empty (entries
[i
]) && !is_deleted (entries
[i
]))
1458 Descriptor::remove (entries
[i
]);
1460 /* Instead of clearing megabyte, downsize the table. */
1461 if (size
> 1024*1024 / sizeof (PTR
))
1463 int nindex
= hash_table_higher_prime_index (1024 / sizeof (PTR
));
1464 int nsize
= prime_tab
[nindex
].prime
;
1467 Allocator
<value_type
> ::data_free (m_entries
);
1469 ggc_free (m_entries
);
1471 m_entries
= alloc_entries (nsize
);
1473 m_size_prime_index
= nindex
;
1476 memset (entries
, 0, size
* sizeof (value_type
));
1481 /* This function clears a specified SLOT in a hash table. It is
1482 useful when you've already done the lookup and don't want to do it
1485 template<typename Descriptor
, template<typename Type
> class Allocator
>
1487 hash_table
<Descriptor
, Allocator
, true>::clear_slot (value_type
*slot
)
1489 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
1490 || is_empty (*slot
) || is_deleted (*slot
)));
1492 Descriptor::remove (*slot
);
1494 mark_deleted (*slot
);
1498 /* This function searches for a hash table entry equal to the given
1499 COMPARABLE element starting with the given HASH value. It cannot
1500 be used to insert or delete an element. */
1502 template<typename Descriptor
, template<typename Type
> class Allocator
>
1503 typename hash_table
<Descriptor
, Allocator
, true>::value_type
&
1504 hash_table
<Descriptor
, Allocator
, true>
1505 ::find_with_hash (const compare_type
&comparable
, hashval_t hash
)
1508 size_t size
= m_size
;
1509 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
1511 value_type
*entry
= &m_entries
[index
];
1512 if (is_empty (*entry
)
1513 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
1516 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
1524 entry
= &m_entries
[index
];
1525 if (is_empty (*entry
)
1526 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
1531 /* This function searches for a hash table slot containing an entry
1532 equal to the given COMPARABLE element and starting with the given
1533 HASH. To delete an entry, call this with insert=NO_INSERT, then
1534 call clear_slot on the slot returned (possibly after doing some
1535 checks). To insert an entry, call this with insert=INSERT, then
1536 write the value you want into the returned slot. When inserting an
1537 entry, NULL may be returned if memory allocation fails. */
1539 template<typename Descriptor
, template<typename Type
> class Allocator
>
1540 typename hash_table
<Descriptor
, Allocator
, true>::value_type
*
1541 hash_table
<Descriptor
, Allocator
, true>
1542 ::find_slot_with_hash (const compare_type
&comparable
, hashval_t hash
,
1543 enum insert_option insert
)
1545 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
1550 value_type
*first_deleted_slot
= NULL
;
1551 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
1552 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
1553 value_type
*entry
= &m_entries
[index
];
1554 size_t size
= m_size
;
1555 if (is_empty (*entry
))
1557 else if (is_deleted (*entry
))
1558 first_deleted_slot
= &m_entries
[index
];
1559 else if (Descriptor::equal (*entry
, comparable
))
1560 return &m_entries
[index
];
1569 entry
= &m_entries
[index
];
1570 if (is_empty (*entry
))
1572 else if (is_deleted (*entry
))
1574 if (!first_deleted_slot
)
1575 first_deleted_slot
= &m_entries
[index
];
1577 else if (Descriptor::equal (*entry
, comparable
))
1578 return &m_entries
[index
];
1582 if (insert
== NO_INSERT
)
1585 if (first_deleted_slot
)
1588 mark_empty (*first_deleted_slot
);
1589 return first_deleted_slot
;
1593 return &m_entries
[index
];
1596 /* This function deletes an element with the given COMPARABLE value
1597 from hash table starting with the given HASH. If there is no
1598 matching element in the hash table, this function does nothing. */
1600 template<typename Descriptor
, template<typename Type
> class Allocator
>
1602 hash_table
<Descriptor
, Allocator
, true>
1603 ::remove_elt_with_hash (const compare_type
&comparable
, hashval_t hash
)
1605 value_type
*slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
1606 if (is_empty (*slot
))
1609 Descriptor::remove (*slot
);
1611 mark_deleted (*slot
);
1615 /* This function scans over the entire hash table calling CALLBACK for
1616 each live entry. If CALLBACK returns false, the iteration stops.
1617 ARGUMENT is passed as CALLBACK's second argument. */
1619 template<typename Descriptor
,
1620 template<typename Type
> class Allocator
>
1621 template<typename Argument
,
1622 int (*Callback
) (typename hash_table
<Descriptor
, Allocator
,
1623 true>::value_type
*slot
,
1626 hash_table
<Descriptor
, Allocator
, true>::traverse_noresize (Argument argument
)
1628 value_type
*slot
= m_entries
;
1629 value_type
*limit
= slot
+ size ();
1633 value_type
&x
= *slot
;
1635 if (!is_empty (x
) && !is_deleted (x
))
1636 if (! Callback (slot
, argument
))
1639 while (++slot
< limit
);
1642 /* Like traverse_noresize, but does resize the table when it is too empty
1643 to improve effectivity of subsequent calls. */
1645 template <typename Descriptor
,
1646 template <typename Type
> class Allocator
>
1647 template <typename Argument
,
1648 int (*Callback
) (typename hash_table
<Descriptor
, Allocator
,
1649 true>::value_type
*slot
,
1652 hash_table
<Descriptor
, Allocator
, true>::traverse (Argument argument
)
1654 size_t size
= m_size
;
1655 if (elements () * 8 < size
&& size
> 32)
1658 traverse_noresize
<Argument
, Callback
> (argument
);
1661 /* Slide down the iterator slots until an active entry is found. */
1663 template<typename Descriptor
, template<typename Type
> class Allocator
>
1665 hash_table
<Descriptor
, Allocator
, true>::iterator::slide ()
1667 for ( ; m_slot
< m_limit
; ++m_slot
)
1669 value_type
&x
= *m_slot
;
1670 if (!is_empty (x
) && !is_deleted (x
))
1677 /* Bump the iterator. */
1679 template<typename Descriptor
, template<typename Type
> class Allocator
>
1680 inline typename hash_table
<Descriptor
, Allocator
, true>::iterator
&
1681 hash_table
<Descriptor
, Allocator
, true>::iterator::operator ++ ()
1689 /* Iterate through the elements of hash_table HTAB,
1690 using hash_table <....>::iterator ITER,
1691 storing each element in RESULT, which is of type TYPE. */
1693 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1694 for ((ITER) = (HTAB).begin (); \
1695 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1698 /* ggc walking routines. */
1700 template<typename E
>
1702 gt_ggc_mx (hash_table
<E
> *h
)
1704 typedef hash_table
<E
> table
;
1706 if (!ggc_test_and_set_mark (h
->m_entries
))
1709 for (size_t i
= 0; i
< h
->m_size
; i
++)
1711 if (table::is_empty (h
->m_entries
[i
])
1712 || table::is_deleted (h
->m_entries
[i
]))
1715 E::ggc_mx (h
->m_entries
[i
]);
1719 template<typename D
>
1721 hashtab_entry_note_pointers (void *obj
, void *h
, gt_pointer_operator op
,
1724 hash_table
<D
> *map
= static_cast<hash_table
<D
> *> (h
);
1725 gcc_checking_assert (map
->m_entries
== obj
);
1726 for (size_t i
= 0; i
< map
->m_size
; i
++)
1728 typedef hash_table
<D
> table
;
1729 if (table::is_empty (map
->m_entries
[i
])
1730 || table::is_deleted (map
->m_entries
[i
]))
1733 D::pch_nx (map
->m_entries
[i
], op
, cookie
);
1737 template<typename D
>
1739 gt_pch_nx (hash_table
<D
> *h
)
1742 = gt_pch_note_object (h
->m_entries
, h
, hashtab_entry_note_pointers
<D
>);
1743 gcc_checking_assert (success
);
1744 for (size_t i
= 0; i
< h
->m_size
; i
++)
1746 if (hash_table
<D
>::is_empty (h
->m_entries
[i
])
1747 || hash_table
<D
>::is_deleted (h
->m_entries
[i
]))
1750 D::pch_nx (h
->m_entries
[i
]);
1754 template<typename D
>
1756 gt_pch_nx (hash_table
<D
> *h
, gt_pointer_operator op
, void *cookie
)
1758 op (&h
->m_entries
, cookie
);
1761 template<typename H
>
1763 gt_cleare_cache (hash_table
<H
> *h
)
1768 for (typename hash_table
<H
>::iterator iter
= h
->begin (); iter
!= h
->end ();
1770 H::handle_cache_entry (*iter
);
1773 #endif /* TYPED_HASHTAB_H */