gcc/
[official-gcc.git] / gcc / hash-table.h
blob6df32a2e1aa54ef80d3d2f35ec9e8a173895b7f5
1 /* A type-safe hash table template.
2 Copyright (C) 2012-2014 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
10 version.
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.
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.
26 INTRODUCTION TO TYPES
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
31 the value type.
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.
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
85 policies.
87 * typed_free_remove implements the static 'remove' member function
88 by calling free().
90 * typed_noop_remove implements the static 'remove' member function
91 by doing nothing.
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 *);
121 inline hashval_t
122 some_type_hasher::hash (const value_type *e)
123 { ... compute and return a hash value for E ... }
125 inline bool
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
141 htab_t.
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;
153 HASH TABLE ITERATORS
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 ();
169 ++iter)
170 if ((*iter).status == INFO_READY)
171 consume (&*iter);
173 Or with common sub-expression elimination:
175 for (info_table_type::iterator iter = info_table.begin ();
176 iter != info_table.end ();
177 ++iter)
179 some_info &elem = *iter;
180 if (elem.status == INFO_READY)
181 consume (&elem);
184 One can also use a more typical GCC style:
186 typedef some_info *some_info_p;
187 some_info *elem_ptr;
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)
191 consume (elem_ptr);
196 #ifndef TYPED_HASHTAB_H
197 #define TYPED_HASHTAB_H
199 #ifndef GENERATOR_FILE
200 #include "ggc.h"
201 #else
202 template <typename T>
203 T *ggc_cleared_vec_alloc (size_t);
204 template <typename T>
205 T *ggc_alloc ();
206 #endif
207 #include "hashtab.h"
208 #include <new>
210 template<typename, typename, typename> class hash_map;
211 template<typename, typename> class hash_set;
213 /* The ordinary memory allocator. */
214 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
216 template <typename Type>
217 struct xcallocator
219 static Type *data_alloc (size_t count);
220 static void data_free (Type *memory);
224 /* Allocate memory for COUNT data blocks. */
226 template <typename Type>
227 inline Type *
228 xcallocator <Type>::data_alloc (size_t count)
230 return static_cast <Type *> (xcalloc (count, sizeof (Type)));
234 /* Free memory for data blocks. */
236 template <typename Type>
237 inline void
238 xcallocator <Type>::data_free (Type *memory)
240 return ::free (memory);
244 /* Helpful type for removing with free. */
246 template <typename Type>
247 struct typed_free_remove
249 static inline void remove (Type *p);
253 /* Remove with free. */
255 template <typename Type>
256 inline void
257 typed_free_remove <Type>::remove (Type *p)
259 free (p);
263 /* Helpful type for a no-op remove. */
265 template <typename Type>
266 struct typed_noop_remove
268 static inline void remove (Type *p);
272 /* Remove doing nothing. */
274 template <typename Type>
275 inline void
276 typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED)
281 /* Pointer hash with a no-op remove method. */
283 template <typename Type>
284 struct pointer_hash : typed_noop_remove <Type>
286 typedef Type *value_type;
287 typedef Type *compare_type;
288 typedef int store_values_directly;
290 static inline hashval_t hash (const value_type &);
292 static inline bool equal (const value_type &existing, const compare_type &candidate);
295 template <typename Type>
296 inline hashval_t
297 pointer_hash <Type>::hash (const value_type &candidate)
299 /* This is a really poor hash function, but it is what the current code uses,
300 so I am reusing it to avoid an additional axis in testing. */
301 return (hashval_t) ((intptr_t)candidate >> 3);
304 template <typename Type>
305 inline bool
306 pointer_hash <Type>::equal (const value_type &existing,
307 const compare_type &candidate)
309 return existing == candidate;
312 /* Hasher for entry in gc memory. */
314 template<typename T>
315 struct ggc_hasher
317 typedef T value_type;
318 typedef T compare_type;
319 typedef int store_values_directly;
321 static void remove (T) {}
323 static void
324 ggc_mx (T p)
326 extern void gt_ggc_mx (T &);
327 gt_ggc_mx (p);
330 static void
331 pch_nx (T &p)
333 extern void gt_pch_nx (T &);
334 gt_pch_nx (p);
337 static void
338 pch_nx (T &p, gt_pointer_operator op, void *cookie)
340 op (&p, cookie);
345 /* Table of primes and their inversion information. */
347 struct prime_ent
349 hashval_t prime;
350 hashval_t inv;
351 hashval_t inv_m2; /* inverse of prime-2 */
352 hashval_t shift;
355 extern struct prime_ent const prime_tab[];
358 /* Functions for computing hash table indexes. */
360 extern unsigned int hash_table_higher_prime_index (unsigned long n);
361 extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
362 extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
364 /* The below is some template meta programming to decide if we should use the
365 hash table partial specialization that directly stores value_type instead of
366 pointers to value_type. If the Descriptor type defines the type
367 Descriptor::store_values_directly then values are stored directly otherwise
368 pointers to them are stored. */
369 template<typename T> struct notype { typedef void type; };
371 template<typename T, typename = void>
372 struct storage_tester
374 static const bool value = false;
377 template<typename T>
378 struct storage_tester<T, typename notype<typename
379 T::store_values_directly>::type>
381 static const bool value = true;
384 template<typename Traits>
385 struct has_is_deleted
387 template<typename U, bool (*)(U &)> struct helper {};
388 template<typename U> static char test (helper<U, U::is_deleted> *);
389 template<typename U> static int test (...);
390 static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
393 template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
394 struct is_deleted_helper
396 static inline bool
397 call (Type &v)
399 return Traits::is_deleted (v);
403 template<typename Type, typename Traits>
404 struct is_deleted_helper<Type *, Traits, false>
406 static inline bool
407 call (Type *v)
409 return v == HTAB_DELETED_ENTRY;
413 template<typename Traits>
414 struct has_is_empty
416 template<typename U, bool (*)(U &)> struct helper {};
417 template<typename U> static char test (helper<U, U::is_empty> *);
418 template<typename U> static int test (...);
419 static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
422 template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
423 struct is_empty_helper
425 static inline bool
426 call (Type &v)
428 return Traits::is_empty (v);
432 template<typename Type, typename Traits>
433 struct is_empty_helper<Type *, Traits, false>
435 static inline bool
436 call (Type *v)
438 return v == HTAB_EMPTY_ENTRY;
442 template<typename Traits>
443 struct has_mark_deleted
445 template<typename U, void (*)(U &)> struct helper {};
446 template<typename U> static char test (helper<U, U::mark_deleted> *);
447 template<typename U> static int test (...);
448 static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
451 template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
452 struct mark_deleted_helper
454 static inline void
455 call (Type &v)
457 Traits::mark_deleted (v);
461 template<typename Type, typename Traits>
462 struct mark_deleted_helper<Type *, Traits, false>
464 static inline void
465 call (Type *&v)
467 v = static_cast<Type *> (HTAB_DELETED_ENTRY);
471 template<typename Traits>
472 struct has_mark_empty
474 template<typename U, void (*)(U &)> struct helper {};
475 template<typename U> static char test (helper<U, U::mark_empty> *);
476 template<typename U> static int test (...);
477 static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
480 template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
481 struct mark_empty_helper
483 static inline void
484 call (Type &v)
486 Traits::mark_empty (v);
490 template<typename Type, typename Traits>
491 struct mark_empty_helper<Type *, Traits, false>
493 static inline void
494 call (Type *&v)
496 v = static_cast<Type *> (HTAB_EMPTY_ENTRY);
500 /* User-facing hash table type.
502 The table stores elements of type Descriptor::value_type, or pointers to
503 objects of type value_type if the descriptor does not define the type
504 store_values_directly.
506 It hashes values with the hash member function.
507 The table currently works with relatively weak hash functions.
508 Use typed_pointer_hash <Value> when hashing pointers instead of objects.
510 It compares elements with the equal member function.
511 Two elements with the same hash may not be equal.
512 Use typed_pointer_equal <Value> when hashing pointers instead of objects.
514 It removes elements with the remove member function.
515 This feature is useful for freeing memory.
516 Derive from typed_null_remove <Value> when not freeing objects.
517 Derive from typed_free_remove <Value> when doing a simple object free.
519 Specify the template Allocator to allocate and free memory.
520 The default is xcallocator.
522 Storage is an implementation detail and should not be used outside the
523 hash table code.
526 template <typename Descriptor,
527 template<typename Type> class Allocator= xcallocator,
528 bool Storage = storage_tester<Descriptor>::value>
529 class hash_table
533 template <typename Descriptor,
534 template<typename Type> class Allocator>
535 class hash_table<Descriptor, Allocator, false>
537 typedef typename Descriptor::value_type value_type;
538 typedef typename Descriptor::compare_type compare_type;
540 public:
541 hash_table (size_t);
542 ~hash_table ();
544 /* Current size (in entries) of the hash table. */
545 size_t size () const { return m_size; }
547 /* Return the current number of elements in this hash table. */
548 size_t elements () const { return m_n_elements - m_n_deleted; }
550 /* Return the current number of elements in this hash table. */
551 size_t elements_with_deleted () const { return m_n_elements; }
553 /* This function clears all entries in the given hash table. */
554 void empty ();
556 /* This function clears a specified SLOT in a hash table. It is
557 useful when you've already done the lookup and don't want to do it
558 again. */
560 void clear_slot (value_type **);
562 /* This function searches for a hash table entry equal to the given
563 COMPARABLE element starting with the given HASH value. It cannot
564 be used to insert or delete an element. */
565 value_type *find_with_hash (const compare_type *, hashval_t);
567 /* Like find_slot_with_hash, but compute the hash value from the element. */
568 value_type *find (const value_type *value)
570 return find_with_hash (value, Descriptor::hash (value));
573 value_type **find_slot (const value_type *value, insert_option insert)
575 return find_slot_with_hash (value, Descriptor::hash (value), insert);
578 /* This function searches for a hash table slot containing an entry
579 equal to the given COMPARABLE element and starting with the given
580 HASH. To delete an entry, call this with insert=NO_INSERT, then
581 call clear_slot on the slot returned (possibly after doing some
582 checks). To insert an entry, call this with insert=INSERT, then
583 write the value you want into the returned slot. When inserting an
584 entry, NULL may be returned if memory allocation fails. */
585 value_type **find_slot_with_hash (const compare_type *comparable,
586 hashval_t hash, enum insert_option insert);
588 /* This function deletes an element with the given COMPARABLE value
589 from hash table starting with the given HASH. If there is no
590 matching element in the hash table, this function does nothing. */
591 void remove_elt_with_hash (const compare_type *, hashval_t);
593 /* Like remove_elt_with_hash, but compute the hash value from the element. */
594 void remove_elt (const value_type *value)
596 remove_elt_with_hash (value, Descriptor::hash (value));
599 /* This function scans over the entire hash table calling CALLBACK for
600 each live entry. If CALLBACK returns false, the iteration stops.
601 ARGUMENT is passed as CALLBACK's second argument. */
602 template <typename Argument,
603 int (*Callback) (value_type **slot, Argument argument)>
604 void traverse_noresize (Argument argument);
606 /* Like traverse_noresize, but does resize the table when it is too empty
607 to improve effectivity of subsequent calls. */
608 template <typename Argument,
609 int (*Callback) (value_type **slot, Argument argument)>
610 void traverse (Argument argument);
612 class iterator
614 public:
615 iterator () : m_slot (NULL), m_limit (NULL) {}
617 iterator (value_type **slot, value_type **limit) :
618 m_slot (slot), m_limit (limit) {}
620 inline value_type *operator * () { return *m_slot; }
621 void slide ();
622 inline iterator &operator ++ ();
623 bool operator != (const iterator &other) const
625 return m_slot != other.m_slot || m_limit != other.m_limit;
628 private:
629 value_type **m_slot;
630 value_type **m_limit;
633 iterator begin () const
635 iterator iter (m_entries, m_entries + m_size);
636 iter.slide ();
637 return iter;
640 iterator end () const { return iterator (); }
642 double collisions () const
644 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
647 private:
649 value_type **find_empty_slot_for_expand (hashval_t);
650 void expand ();
652 /* Table itself. */
653 typename Descriptor::value_type **m_entries;
655 size_t m_size;
657 /* Current number of elements including also deleted elements. */
658 size_t m_n_elements;
660 /* Current number of deleted elements in the table. */
661 size_t m_n_deleted;
663 /* The following member is used for debugging. Its value is number
664 of all calls of `htab_find_slot' for the hash table. */
665 unsigned int m_searches;
667 /* The following member is used for debugging. Its value is number
668 of collisions fixed for time of work with the hash table. */
669 unsigned int m_collisions;
671 /* Current size (in entries) of the hash table, as an index into the
672 table of primes. */
673 unsigned int m_size_prime_index;
676 template<typename Descriptor, template<typename Type> class Allocator>
677 hash_table<Descriptor, Allocator, false>::hash_table (size_t size) :
678 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0)
680 unsigned int size_prime_index;
682 size_prime_index = hash_table_higher_prime_index (size);
683 size = prime_tab[size_prime_index].prime;
685 m_entries = Allocator <value_type*> ::data_alloc (size);
686 gcc_assert (m_entries != NULL);
687 m_size = size;
688 m_size_prime_index = size_prime_index;
691 template<typename Descriptor, template<typename Type> class Allocator>
692 hash_table<Descriptor, Allocator, false>::~hash_table ()
694 for (size_t i = m_size - 1; i < m_size; i--)
695 if (m_entries[i] != HTAB_EMPTY_ENTRY && m_entries[i] != HTAB_DELETED_ENTRY)
696 Descriptor::remove (m_entries[i]);
698 Allocator <value_type *> ::data_free (m_entries);
701 /* Similar to find_slot, but without several unwanted side effects:
702 - Does not call equal when it finds an existing entry.
703 - Does not change the count of elements/searches/collisions in the
704 hash table.
705 This function also assumes there are no deleted entries in the table.
706 HASH is the hash value for the element to be inserted. */
708 template<typename Descriptor, template<typename Type> class Allocator>
709 typename hash_table<Descriptor, Allocator, false>::value_type **
710 hash_table<Descriptor, Allocator, false>
711 ::find_empty_slot_for_expand (hashval_t hash)
713 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
714 size_t size = m_size;
715 value_type **slot = m_entries + index;
716 hashval_t hash2;
718 if (*slot == HTAB_EMPTY_ENTRY)
719 return slot;
720 else if (*slot == HTAB_DELETED_ENTRY)
721 abort ();
723 hash2 = hash_table_mod2 (hash, m_size_prime_index);
724 for (;;)
726 index += hash2;
727 if (index >= size)
728 index -= size;
730 slot = m_entries + index;
731 if (*slot == HTAB_EMPTY_ENTRY)
732 return slot;
733 else if (*slot == HTAB_DELETED_ENTRY)
734 abort ();
738 /* The following function changes size of memory allocated for the
739 entries and repeatedly inserts the table elements. The occupancy
740 of the table after the call will be about 50%. Naturally the hash
741 table must already exist. Remember also that the place of the
742 table entries is changed. If memory allocation fails, this function
743 will abort. */
745 template<typename Descriptor, template<typename Type> class Allocator>
746 void
747 hash_table<Descriptor, Allocator, false>::expand ()
749 value_type **oentries = m_entries;
750 unsigned int oindex = m_size_prime_index;
751 size_t osize = size ();
752 value_type **olimit = oentries + osize;
753 size_t elts = elements ();
755 /* Resize only when table after removal of unused elements is either
756 too full or too empty. */
757 unsigned int nindex;
758 size_t nsize;
759 if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
761 nindex = hash_table_higher_prime_index (elts * 2);
762 nsize = prime_tab[nindex].prime;
764 else
766 nindex = oindex;
767 nsize = osize;
770 value_type **nentries = Allocator <value_type *> ::data_alloc (nsize);
771 gcc_assert (nentries != NULL);
772 m_entries = nentries;
773 m_size = nsize;
774 m_size_prime_index = nindex;
775 m_n_elements -= m_n_deleted;
776 m_n_deleted = 0;
778 value_type **p = oentries;
781 value_type *x = *p;
783 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
785 value_type **q = find_empty_slot_for_expand (Descriptor::hash (x));
787 *q = x;
790 p++;
792 while (p < olimit);
794 Allocator <value_type *> ::data_free (oentries);
797 template<typename Descriptor, template<typename Type> class Allocator>
798 void
799 hash_table<Descriptor, Allocator, false>::empty ()
801 size_t size = m_size;
802 value_type **entries = m_entries;
803 int i;
805 for (i = size - 1; i >= 0; i--)
806 if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
807 Descriptor::remove (entries[i]);
809 /* Instead of clearing megabyte, downsize the table. */
810 if (size > 1024*1024 / sizeof (PTR))
812 int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
813 int nsize = prime_tab[nindex].prime;
815 Allocator <value_type *> ::data_free (m_entries);
816 m_entries = Allocator <value_type *> ::data_alloc (nsize);
817 m_size = nsize;
818 m_size_prime_index = nindex;
820 else
821 memset (entries, 0, size * sizeof (value_type *));
822 m_n_deleted = 0;
823 m_n_elements = 0;
826 /* This function clears a specified SLOT in a hash table. It is
827 useful when you've already done the lookup and don't want to do it
828 again. */
830 template<typename Descriptor, template<typename Type> class Allocator>
831 void
832 hash_table<Descriptor, Allocator, false>::clear_slot (value_type **slot)
834 if (slot < m_entries || slot >= m_entries + size ()
835 || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
836 abort ();
838 Descriptor::remove (*slot);
840 *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
841 m_n_deleted++;
844 /* This function searches for a hash table entry equal to the given
845 COMPARABLE element starting with the given HASH value. It cannot
846 be used to insert or delete an element. */
848 template<typename Descriptor, template<typename Type> class Allocator>
849 typename hash_table<Descriptor, Allocator, false>::value_type *
850 hash_table<Descriptor, Allocator, false>
851 ::find_with_hash (const compare_type *comparable, hashval_t hash)
853 m_searches++;
854 size_t size = m_size;
855 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
857 value_type *entry = m_entries[index];
858 if (entry == HTAB_EMPTY_ENTRY
859 || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable)))
860 return entry;
862 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
863 for (;;)
865 m_collisions++;
866 index += hash2;
867 if (index >= size)
868 index -= size;
870 entry = m_entries[index];
871 if (entry == HTAB_EMPTY_ENTRY
872 || (entry != HTAB_DELETED_ENTRY
873 && Descriptor::equal (entry, comparable)))
874 return entry;
878 /* This function searches for a hash table slot containing an entry
879 equal to the given COMPARABLE element and starting with the given
880 HASH. To delete an entry, call this with insert=NO_INSERT, then
881 call clear_slot on the slot returned (possibly after doing some
882 checks). To insert an entry, call this with insert=INSERT, then
883 write the value you want into the returned slot. When inserting an
884 entry, NULL may be returned if memory allocation fails. */
886 template<typename Descriptor, template<typename Type> class Allocator>
887 typename hash_table<Descriptor, Allocator, false>::value_type **
888 hash_table<Descriptor, Allocator, false>
889 ::find_slot_with_hash (const compare_type *comparable, hashval_t hash,
890 enum insert_option insert)
892 if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
893 expand ();
895 m_searches++;
897 value_type **first_deleted_slot = NULL;
898 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
899 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
900 value_type *entry = m_entries[index];
901 size_t size = m_size;
902 if (entry == HTAB_EMPTY_ENTRY)
903 goto empty_entry;
904 else if (entry == HTAB_DELETED_ENTRY)
905 first_deleted_slot = &m_entries[index];
906 else if (Descriptor::equal (entry, comparable))
907 return &m_entries[index];
909 for (;;)
911 m_collisions++;
912 index += hash2;
913 if (index >= size)
914 index -= size;
916 entry = m_entries[index];
917 if (entry == HTAB_EMPTY_ENTRY)
918 goto empty_entry;
919 else if (entry == HTAB_DELETED_ENTRY)
921 if (!first_deleted_slot)
922 first_deleted_slot = &m_entries[index];
924 else if (Descriptor::equal (entry, comparable))
925 return &m_entries[index];
928 empty_entry:
929 if (insert == NO_INSERT)
930 return NULL;
932 if (first_deleted_slot)
934 m_n_deleted--;
935 *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY);
936 return first_deleted_slot;
939 m_n_elements++;
940 return &m_entries[index];
943 /* This function deletes an element with the given COMPARABLE value
944 from hash table starting with the given HASH. If there is no
945 matching element in the hash table, this function does nothing. */
947 template<typename Descriptor, template<typename Type> class Allocator>
948 void
949 hash_table<Descriptor, Allocator, false>
950 ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash)
952 value_type **slot = find_slot_with_hash (comparable, hash, NO_INSERT);
953 if (*slot == HTAB_EMPTY_ENTRY)
954 return;
956 Descriptor::remove (*slot);
958 *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
959 m_n_deleted++;
962 /* This function scans over the entire hash table calling CALLBACK for
963 each live entry. If CALLBACK returns false, the iteration stops.
964 ARGUMENT is passed as CALLBACK's second argument. */
966 template<typename Descriptor, template<typename Type> class Allocator>
967 template<typename Argument,
968 int (*Callback) (typename hash_table<Descriptor, Allocator,
969 false>::value_type **slot,
970 Argument argument)>
971 void
972 hash_table<Descriptor, Allocator, false>::traverse_noresize (Argument argument)
974 value_type **slot = m_entries;
975 value_type **limit = slot + size ();
979 value_type *x = *slot;
981 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
982 if (! Callback (slot, argument))
983 break;
985 while (++slot < limit);
988 /* Like traverse_noresize, but does resize the table when it is too empty
989 to improve effectivity of subsequent calls. */
991 template <typename Descriptor,
992 template <typename Type> class Allocator>
993 template <typename Argument,
994 int (*Callback) (typename hash_table<Descriptor, Allocator,
995 false>::value_type **slot,
996 Argument argument)>
997 void
998 hash_table<Descriptor, Allocator, false>::traverse (Argument argument)
1000 size_t size = m_size;
1001 if (elements () * 8 < size && size > 32)
1002 expand ();
1004 traverse_noresize <Argument, Callback> (argument);
1007 /* Slide down the iterator slots until an active entry is found. */
1009 template<typename Descriptor, template<typename Type> class Allocator>
1010 void
1011 hash_table<Descriptor, Allocator, false>::iterator::slide ()
1013 for ( ; m_slot < m_limit; ++m_slot )
1015 value_type *x = *m_slot;
1016 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
1017 return;
1019 m_slot = NULL;
1020 m_limit = NULL;
1023 /* Bump the iterator. */
1025 template<typename Descriptor, template<typename Type> class Allocator>
1026 inline typename hash_table<Descriptor, Allocator, false>::iterator &
1027 hash_table<Descriptor, Allocator, false>::iterator::operator ++ ()
1029 ++m_slot;
1030 slide ();
1031 return *this;
1034 /* A partial specialization used when values should be stored directly. */
1036 template <typename Descriptor,
1037 template<typename Type> class Allocator>
1038 class hash_table<Descriptor, Allocator, true>
1040 typedef typename Descriptor::value_type value_type;
1041 typedef typename Descriptor::compare_type compare_type;
1043 public:
1044 explicit hash_table (size_t, bool ggc = false);
1045 ~hash_table ();
1047 /* Create a hash_table in gc memory. */
1049 static hash_table *
1050 create_ggc (size_t n)
1052 hash_table *table = ggc_alloc<hash_table> ();
1053 new (table) hash_table (n, true);
1054 return table;
1057 /* Current size (in entries) of the hash table. */
1058 size_t size () const { return m_size; }
1060 /* Return the current number of elements in this hash table. */
1061 size_t elements () const { return m_n_elements - m_n_deleted; }
1063 /* Return the current number of elements in this hash table. */
1064 size_t elements_with_deleted () const { return m_n_elements; }
1066 /* This function clears all entries in the given hash table. */
1067 void empty ();
1069 /* This function clears a specified SLOT in a hash table. It is
1070 useful when you've already done the lookup and don't want to do it
1071 again. */
1073 void clear_slot (value_type *);
1075 /* This function searches for a hash table entry equal to the given
1076 COMPARABLE element starting with the given HASH value. It cannot
1077 be used to insert or delete an element. */
1078 value_type &find_with_hash (const compare_type &, hashval_t);
1080 /* Like find_slot_with_hash, but compute the hash value from the element. */
1081 value_type &find (const value_type &value)
1083 return find_with_hash (value, Descriptor::hash (value));
1086 value_type *find_slot (const value_type &value, insert_option insert)
1088 return find_slot_with_hash (value, Descriptor::hash (value), insert);
1091 /* This function searches for a hash table slot containing an entry
1092 equal to the given COMPARABLE element and starting with the given
1093 HASH. To delete an entry, call this with insert=NO_INSERT, then
1094 call clear_slot on the slot returned (possibly after doing some
1095 checks). To insert an entry, call this with insert=INSERT, then
1096 write the value you want into the returned slot. When inserting an
1097 entry, NULL may be returned if memory allocation fails. */
1098 value_type *find_slot_with_hash (const compare_type &comparable,
1099 hashval_t hash, enum insert_option insert);
1101 /* This function deletes an element with the given COMPARABLE value
1102 from hash table starting with the given HASH. If there is no
1103 matching element in the hash table, this function does nothing. */
1104 void remove_elt_with_hash (const compare_type &, hashval_t);
1106 /* Like remove_elt_with_hash, but compute the hash value from the element. */
1107 void remove_elt (const value_type &value)
1109 remove_elt_with_hash (value, Descriptor::hash (value));
1112 /* This function scans over the entire hash table calling CALLBACK for
1113 each live entry. If CALLBACK returns false, the iteration stops.
1114 ARGUMENT is passed as CALLBACK's second argument. */
1115 template <typename Argument,
1116 int (*Callback) (value_type *slot, Argument argument)>
1117 void traverse_noresize (Argument argument);
1119 /* Like traverse_noresize, but does resize the table when it is too empty
1120 to improve effectivity of subsequent calls. */
1121 template <typename Argument,
1122 int (*Callback) (value_type *slot, Argument argument)>
1123 void traverse (Argument argument);
1125 class iterator
1127 public:
1128 iterator () : m_slot (NULL), m_limit (NULL) {}
1130 iterator (value_type *slot, value_type *limit) :
1131 m_slot (slot), m_limit (limit) {}
1133 inline value_type &operator * () { return *m_slot; }
1134 void slide ();
1135 inline iterator &operator ++ ();
1136 bool operator != (const iterator &other) const
1138 return m_slot != other.m_slot || m_limit != other.m_limit;
1141 private:
1142 value_type *m_slot;
1143 value_type *m_limit;
1146 iterator begin () const
1148 iterator iter (m_entries, m_entries + m_size);
1149 iter.slide ();
1150 return iter;
1153 iterator end () const { return iterator (); }
1155 double collisions () const
1157 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
1160 private:
1161 template<typename T> friend void gt_ggc_mx (hash_table<T> *);
1162 template<typename T> friend void gt_pch_nx (hash_table<T> *);
1163 template<typename T> friend void
1164 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
1165 template<typename T, typename U, typename V> friend void
1166 gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
1167 template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *,
1168 gt_pointer_operator,
1169 void *);
1170 template<typename T> friend void gt_pch_nx (hash_table<T> *,
1171 gt_pointer_operator, void *);
1173 value_type *find_empty_slot_for_expand (hashval_t);
1174 void expand ();
1175 static bool is_deleted (value_type &v)
1177 return is_deleted_helper<value_type, Descriptor>::call (v);
1179 static bool is_empty (value_type &v)
1181 return is_empty_helper<value_type, Descriptor>::call (v);
1184 static void mark_deleted (value_type &v)
1186 return mark_deleted_helper<value_type, Descriptor>::call (v);
1189 static void mark_empty (value_type &v)
1191 return mark_empty_helper<value_type, Descriptor>::call (v);
1194 /* Table itself. */
1195 typename Descriptor::value_type *m_entries;
1197 size_t m_size;
1199 /* Current number of elements including also deleted elements. */
1200 size_t m_n_elements;
1202 /* Current number of deleted elements in the table. */
1203 size_t m_n_deleted;
1205 /* The following member is used for debugging. Its value is number
1206 of all calls of `htab_find_slot' for the hash table. */
1207 unsigned int m_searches;
1209 /* The following member is used for debugging. Its value is number
1210 of collisions fixed for time of work with the hash table. */
1211 unsigned int m_collisions;
1213 /* Current size (in entries) of the hash table, as an index into the
1214 table of primes. */
1215 unsigned int m_size_prime_index;
1217 /* if m_entries is stored in ggc memory. */
1218 bool m_ggc;
1221 template<typename Descriptor, template<typename Type> class Allocator>
1222 hash_table<Descriptor, Allocator, true>::hash_table (size_t size, bool ggc) :
1223 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
1224 m_ggc (ggc)
1226 unsigned int size_prime_index;
1228 size_prime_index = hash_table_higher_prime_index (size);
1229 size = prime_tab[size_prime_index].prime;
1231 if (!m_ggc)
1232 m_entries = Allocator <value_type> ::data_alloc (size);
1233 else
1234 m_entries = ggc_cleared_vec_alloc<value_type> (size);
1236 gcc_assert (m_entries != NULL);
1237 m_size = size;
1238 m_size_prime_index = size_prime_index;
1241 template<typename Descriptor, template<typename Type> class Allocator>
1242 hash_table<Descriptor, Allocator, true>::~hash_table ()
1244 for (size_t i = m_size - 1; i < m_size; i--)
1245 if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
1246 Descriptor::remove (m_entries[i]);
1248 if (!m_ggc)
1249 Allocator <value_type> ::data_free (m_entries);
1250 else
1251 ggc_free (m_entries);
1254 /* Similar to find_slot, but without several unwanted side effects:
1255 - Does not call equal when it finds an existing entry.
1256 - Does not change the count of elements/searches/collisions in the
1257 hash table.
1258 This function also assumes there are no deleted entries in the table.
1259 HASH is the hash value for the element to be inserted. */
1261 template<typename Descriptor, template<typename Type> class Allocator>
1262 typename hash_table<Descriptor, Allocator, true>::value_type *
1263 hash_table<Descriptor, Allocator, true>
1264 ::find_empty_slot_for_expand (hashval_t hash)
1266 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
1267 size_t size = m_size;
1268 value_type *slot = m_entries + index;
1269 hashval_t hash2;
1271 if (is_empty (*slot))
1272 return slot;
1273 else if (is_deleted (*slot))
1274 abort ();
1276 hash2 = hash_table_mod2 (hash, m_size_prime_index);
1277 for (;;)
1279 index += hash2;
1280 if (index >= size)
1281 index -= size;
1283 slot = m_entries + index;
1284 if (is_empty (*slot))
1285 return slot;
1286 else if (is_deleted (*slot))
1287 abort ();
1291 /* The following function changes size of memory allocated for the
1292 entries and repeatedly inserts the table elements. The occupancy
1293 of the table after the call will be about 50%. Naturally the hash
1294 table must already exist. Remember also that the place of the
1295 table entries is changed. If memory allocation fails, this function
1296 will abort. */
1298 template<typename Descriptor, template<typename Type> class Allocator>
1299 void
1300 hash_table<Descriptor, Allocator, true>::expand ()
1302 value_type *oentries = m_entries;
1303 unsigned int oindex = m_size_prime_index;
1304 size_t osize = size ();
1305 value_type *olimit = oentries + osize;
1306 size_t elts = elements ();
1308 /* Resize only when table after removal of unused elements is either
1309 too full or too empty. */
1310 unsigned int nindex;
1311 size_t nsize;
1312 if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
1314 nindex = hash_table_higher_prime_index (elts * 2);
1315 nsize = prime_tab[nindex].prime;
1317 else
1319 nindex = oindex;
1320 nsize = osize;
1323 value_type *nentries;
1324 if (!m_ggc)
1325 nentries = Allocator <value_type> ::data_alloc (nsize);
1326 else
1327 nentries = ggc_cleared_vec_alloc<value_type> (nsize);
1329 gcc_assert (nentries != NULL);
1330 m_entries = nentries;
1331 m_size = nsize;
1332 m_size_prime_index = nindex;
1333 m_n_elements -= m_n_deleted;
1334 m_n_deleted = 0;
1336 value_type *p = oentries;
1339 value_type &x = *p;
1341 if (!is_empty (x) && !is_deleted (x))
1343 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
1345 *q = x;
1348 p++;
1350 while (p < olimit);
1352 if (!m_ggc)
1353 Allocator <value_type> ::data_free (oentries);
1354 else
1355 ggc_free (oentries);
1358 template<typename Descriptor, template<typename Type> class Allocator>
1359 void
1360 hash_table<Descriptor, Allocator, true>::empty ()
1362 size_t size = m_size;
1363 value_type *entries = m_entries;
1364 int i;
1366 for (i = size - 1; i >= 0; i--)
1367 if (!is_empty (entries[i]) && !is_deleted (entries[i]))
1368 Descriptor::remove (entries[i]);
1370 /* Instead of clearing megabyte, downsize the table. */
1371 if (size > 1024*1024 / sizeof (PTR))
1373 int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
1374 int nsize = prime_tab[nindex].prime;
1376 if (!m_ggc)
1378 Allocator <value_type> ::data_free (m_entries);
1379 m_entries = Allocator <value_type> ::data_alloc (nsize);
1381 else
1383 ggc_free (m_entries);
1384 m_entries = ggc_cleared_vec_alloc<value_type> (nsize);
1387 m_size = nsize;
1388 m_size_prime_index = nindex;
1390 else
1391 memset (entries, 0, size * sizeof (value_type));
1392 m_n_deleted = 0;
1393 m_n_elements = 0;
1396 /* This function clears a specified SLOT in a hash table. It is
1397 useful when you've already done the lookup and don't want to do it
1398 again. */
1400 template<typename Descriptor, template<typename Type> class Allocator>
1401 void
1402 hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot)
1404 if (slot < m_entries || slot >= m_entries + size ()
1405 || is_empty (*slot) || is_deleted (*slot))
1406 abort ();
1408 Descriptor::remove (*slot);
1410 mark_deleted (*slot);
1411 m_n_deleted++;
1414 /* This function searches for a hash table entry equal to the given
1415 COMPARABLE element starting with the given HASH value. It cannot
1416 be used to insert or delete an element. */
1418 template<typename Descriptor, template<typename Type> class Allocator>
1419 typename hash_table<Descriptor, Allocator, true>::value_type &
1420 hash_table<Descriptor, Allocator, true>
1421 ::find_with_hash (const compare_type &comparable, hashval_t hash)
1423 m_searches++;
1424 size_t size = m_size;
1425 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
1427 value_type *entry = &m_entries[index];
1428 if (is_empty (*entry)
1429 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1430 return *entry;
1432 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
1433 for (;;)
1435 m_collisions++;
1436 index += hash2;
1437 if (index >= size)
1438 index -= size;
1440 entry = &m_entries[index];
1441 if (is_empty (*entry)
1442 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1443 return *entry;
1447 /* This function searches for a hash table slot containing an entry
1448 equal to the given COMPARABLE element and starting with the given
1449 HASH. To delete an entry, call this with insert=NO_INSERT, then
1450 call clear_slot on the slot returned (possibly after doing some
1451 checks). To insert an entry, call this with insert=INSERT, then
1452 write the value you want into the returned slot. When inserting an
1453 entry, NULL may be returned if memory allocation fails. */
1455 template<typename Descriptor, template<typename Type> class Allocator>
1456 typename hash_table<Descriptor, Allocator, true>::value_type *
1457 hash_table<Descriptor, Allocator, true>
1458 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
1459 enum insert_option insert)
1461 if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
1462 expand ();
1464 m_searches++;
1466 value_type *first_deleted_slot = NULL;
1467 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
1468 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
1469 value_type *entry = &m_entries[index];
1470 size_t size = m_size;
1471 if (is_empty (*entry))
1472 goto empty_entry;
1473 else if (is_deleted (*entry))
1474 first_deleted_slot = &m_entries[index];
1475 else if (Descriptor::equal (*entry, comparable))
1476 return &m_entries[index];
1478 for (;;)
1480 m_collisions++;
1481 index += hash2;
1482 if (index >= size)
1483 index -= size;
1485 entry = &m_entries[index];
1486 if (is_empty (*entry))
1487 goto empty_entry;
1488 else if (is_deleted (*entry))
1490 if (!first_deleted_slot)
1491 first_deleted_slot = &m_entries[index];
1493 else if (Descriptor::equal (*entry, comparable))
1494 return &m_entries[index];
1497 empty_entry:
1498 if (insert == NO_INSERT)
1499 return NULL;
1501 if (first_deleted_slot)
1503 m_n_deleted--;
1504 mark_empty (*first_deleted_slot);
1505 return first_deleted_slot;
1508 m_n_elements++;
1509 return &m_entries[index];
1512 /* This function deletes an element with the given COMPARABLE value
1513 from hash table starting with the given HASH. If there is no
1514 matching element in the hash table, this function does nothing. */
1516 template<typename Descriptor, template<typename Type> class Allocator>
1517 void
1518 hash_table<Descriptor, Allocator, true>
1519 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
1521 value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
1522 if (is_empty (*slot))
1523 return;
1525 Descriptor::remove (*slot);
1527 mark_deleted (*slot);
1528 m_n_deleted++;
1531 /* This function scans over the entire hash table calling CALLBACK for
1532 each live entry. If CALLBACK returns false, the iteration stops.
1533 ARGUMENT is passed as CALLBACK's second argument. */
1535 template<typename Descriptor,
1536 template<typename Type> class Allocator>
1537 template<typename Argument,
1538 int (*Callback) (typename hash_table<Descriptor, Allocator,
1539 true>::value_type *slot,
1540 Argument argument)>
1541 void
1542 hash_table<Descriptor, Allocator, true>::traverse_noresize (Argument argument)
1544 value_type *slot = m_entries;
1545 value_type *limit = slot + size ();
1549 value_type &x = *slot;
1551 if (!is_empty (x) && !is_deleted (x))
1552 if (! Callback (slot, argument))
1553 break;
1555 while (++slot < limit);
1558 /* Like traverse_noresize, but does resize the table when it is too empty
1559 to improve effectivity of subsequent calls. */
1561 template <typename Descriptor,
1562 template <typename Type> class Allocator>
1563 template <typename Argument,
1564 int (*Callback) (typename hash_table<Descriptor, Allocator,
1565 true>::value_type *slot,
1566 Argument argument)>
1567 void
1568 hash_table<Descriptor, Allocator, true>::traverse (Argument argument)
1570 size_t size = m_size;
1571 if (elements () * 8 < size && size > 32)
1572 expand ();
1574 traverse_noresize <Argument, Callback> (argument);
1577 /* Slide down the iterator slots until an active entry is found. */
1579 template<typename Descriptor, template<typename Type> class Allocator>
1580 void
1581 hash_table<Descriptor, Allocator, true>::iterator::slide ()
1583 for ( ; m_slot < m_limit; ++m_slot )
1585 value_type &x = *m_slot;
1586 if (!is_empty (x) && !is_deleted (x))
1587 return;
1589 m_slot = NULL;
1590 m_limit = NULL;
1593 /* Bump the iterator. */
1595 template<typename Descriptor, template<typename Type> class Allocator>
1596 inline typename hash_table<Descriptor, Allocator, true>::iterator &
1597 hash_table<Descriptor, Allocator, true>::iterator::operator ++ ()
1599 ++m_slot;
1600 slide ();
1601 return *this;
1605 /* Iterate through the elements of hash_table HTAB,
1606 using hash_table <....>::iterator ITER,
1607 storing each element in RESULT, which is of type TYPE. */
1609 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1610 for ((ITER) = (HTAB).begin (); \
1611 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1612 ++(ITER))
1614 /* ggc walking routines. */
1616 template<typename E>
1617 static inline void
1618 gt_ggc_mx (hash_table<E> *h)
1620 typedef hash_table<E> table;
1622 if (!ggc_test_and_set_mark (h->m_entries))
1623 return;
1625 for (size_t i = 0; i < h->m_size; i++)
1627 if (table::is_empty (h->m_entries[i])
1628 || table::is_deleted (h->m_entries[i]))
1629 continue;
1631 E::ggc_mx (h->m_entries[i]);
1635 template<typename D>
1636 static inline void
1637 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1638 void *cookie)
1640 hash_table<D> *map = static_cast<hash_table<D> *> (h);
1641 gcc_checking_assert (map->m_entries == obj);
1642 for (size_t i = 0; i < map->m_size; i++)
1644 typedef hash_table<D> table;
1645 if (table::is_empty (map->m_entries[i])
1646 || table::is_deleted (map->m_entries[i]))
1647 continue;
1649 D::pch_nx (map->m_entries[i], op, cookie);
1653 template<typename D>
1654 static void
1655 gt_pch_nx (hash_table<D> *h)
1657 bool success
1658 = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1659 gcc_checking_assert (success);
1660 for (size_t i = 0; i < h->m_size; i++)
1662 if (hash_table<D>::is_empty (h->m_entries[i])
1663 || hash_table<D>::is_deleted (h->m_entries[i]))
1664 continue;
1666 D::pch_nx (h->m_entries[i]);
1670 template<typename D>
1671 static inline void
1672 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1674 op (&h->m_entries, cookie);
1677 #endif /* TYPED_HASHTAB_H */