1 /* A type-safe hash table template.
2 Copyright (C) 2012-2019 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 (or 'const value_type &') and returns a hashval_t value.
42 - A typedef named 'compare_type' that is used to test when a 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 and a compare_type, and returns a bool. Both arguments can be
51 - A static function named 'remove' that takes an value_type pointer
52 and frees the memory allocated by it. This function is used when
53 individual elements of the table need to be disposed of (e.g.,
54 when deleting a hash table, removing elements from the table, etc).
56 - An optional static function named 'keep_cache_entry'. This
57 function is provided only for garbage-collected elements that
58 are not marked by the normal gc mark pass. It describes what
59 what should happen to the element at the end of the gc mark phase.
60 The return value should be:
61 - 0 if the element should be deleted
62 - 1 if the element should be kept and needs to be marked
63 - -1 if the element should be kept and is already marked.
64 Returning -1 rather than 1 is purely an optimization.
66 3. The type of the hash table itself. (More later.)
68 In very special circumstances, users may need to know about a fourth type.
70 4. The template type used to describe how hash table memory
71 is allocated. This type is called the allocator type. It is
72 parameterized on the value type. It provides two functions:
74 - A static member function named 'data_alloc'. This function
75 allocates the data elements in the table.
77 - A static member function named 'data_free'. This function
78 deallocates the data elements in the table.
80 Hash table are instantiated with two type arguments.
82 * The descriptor type, (2) above.
84 * The allocator type, (4) above. In general, you will not need to
85 provide your own allocator type. By default, hash tables will use
86 the class template xcallocator, which uses malloc/free for allocation.
89 DEFINING A DESCRIPTOR TYPE
91 The first task in using the hash table is to describe the element type.
92 We compose this into a few steps.
94 1. Decide on a removal policy for values stored in the table.
95 hash-traits.h provides class templates for the four most common
98 * typed_free_remove implements the static 'remove' member function
101 * typed_noop_remove implements the static 'remove' member function
104 * ggc_remove implements the static 'remove' member by doing nothing,
105 but instead provides routines for gc marking and for PCH streaming.
106 Use this for garbage-collected data that needs to be preserved across
109 * ggc_cache_remove is like ggc_remove, except that it does not
110 mark the entries during the normal gc mark phase. Instead it
111 uses 'keep_cache_entry' (described above) to keep elements that
112 were not collected and delete those that were. Use this for
113 garbage-collected caches that should not in themselves stop
114 the data from being collected.
116 You can use these policies by simply deriving the descriptor type
117 from one of those class template, with the appropriate argument.
119 Otherwise, you need to write the static 'remove' member function
120 in the descriptor class.
122 2. Choose a hash function. Write the static 'hash' member function.
124 3. Decide whether the lookup function should take as input an object
125 of type value_type or something more restricted. Define compare_type
128 4. Choose an equality testing function 'equal' that compares a value_type
131 If your elements are pointers, it is usually easiest to start with one
132 of the generic pointer descriptors described below and override the bits
135 AN EXAMPLE DESCRIPTOR TYPE
137 Suppose you want to put some_type into the hash table. You could define
138 the descriptor type as follows.
140 struct some_type_hasher : nofree_ptr_hash <some_type>
141 // Deriving from nofree_ptr_hash means that we get a 'remove' that does
142 // nothing. This choice is good for raw values.
144 static inline hashval_t hash (const value_type *);
145 static inline bool equal (const value_type *, const compare_type *);
149 some_type_hasher::hash (const value_type *e)
150 { ... compute and return a hash value for E ... }
153 some_type_hasher::equal (const value_type *p1, const compare_type *p2)
154 { ... compare P1 vs P2. Return true if they are the 'same' ... }
157 AN EXAMPLE HASH_TABLE DECLARATION
159 To instantiate a hash table for some_type:
161 hash_table <some_type_hasher> some_type_hash_table;
163 There is no need to mention some_type directly, as the hash table will
164 obtain it using some_type_hasher::value_type.
166 You can then use any of the functions in hash_table's public interface.
167 See hash_table for details. The interface is very similar to libiberty's
170 If a hash table is used only in some rare cases, it is possible
171 to construct the hash_table lazily before first use. This is done
174 hash_table <some_type_hasher, true> some_type_hash_table;
176 which will cause whatever methods actually need the allocated entries
177 array to allocate it later.
180 EASY DESCRIPTORS FOR POINTERS
182 There are four descriptors for pointer elements, one for each of
183 the removal policies above:
185 * nofree_ptr_hash (based on typed_noop_remove)
186 * free_ptr_hash (based on typed_free_remove)
187 * ggc_ptr_hash (based on ggc_remove)
188 * ggc_cache_ptr_hash (based on ggc_cache_remove)
190 These descriptors hash and compare elements by their pointer value,
191 rather than what they point to. So, to instantiate a hash table over
192 pointers to whatever_type, without freeing the whatever_types, use:
194 hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
199 The hash table provides standard C++ iterators. For example, consider a
200 hash table of some_info. We wish to consume each element of the table:
202 extern void consume (some_info *);
204 We define a convenience typedef and the hash table:
206 typedef hash_table <some_info_hasher> info_table_type;
207 info_table_type info_table;
209 Then we write the loop in typical C++ style:
211 for (info_table_type::iterator iter = info_table.begin ();
212 iter != info_table.end ();
214 if ((*iter).status == INFO_READY)
217 Or with common sub-expression elimination:
219 for (info_table_type::iterator iter = info_table.begin ();
220 iter != info_table.end ();
223 some_info &elem = *iter;
224 if (elem.status == INFO_READY)
228 One can also use a more typical GCC style:
230 typedef some_info *some_info_p;
232 info_table_type::iterator iter;
233 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
234 if (elem_ptr->status == INFO_READY)
240 #ifndef TYPED_HASHTAB_H
241 #define TYPED_HASHTAB_H
243 #include "statistics.h"
248 #include "mem-stats-traits.h"
249 #include "hash-traits.h"
250 #include "hash-map-traits.h"
252 template<typename
, typename
, typename
> class hash_map
;
253 template<typename
, bool, typename
> class hash_set
;
255 /* The ordinary memory allocator. */
256 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
258 template <typename Type
>
261 static Type
*data_alloc (size_t count
);
262 static void data_free (Type
*memory
);
266 /* Allocate memory for COUNT data blocks. */
268 template <typename Type
>
270 xcallocator
<Type
>::data_alloc (size_t count
)
272 return static_cast <Type
*> (xcalloc (count
, sizeof (Type
)));
276 /* Free memory for data blocks. */
278 template <typename Type
>
280 xcallocator
<Type
>::data_free (Type
*memory
)
282 return ::free (memory
);
286 /* Table of primes and their inversion information. */
292 hashval_t inv_m2
; /* inverse of prime-2 */
296 extern struct prime_ent
const prime_tab
[];
298 /* Limit number of comparisons when calling hash_table<>::verify. */
299 extern unsigned int hash_table_sanitize_eq_limit
;
301 /* Functions for computing hash table indexes. */
303 extern unsigned int hash_table_higher_prime_index (unsigned long n
)
306 /* Return X % Y using multiplicative inverse values INV and SHIFT.
308 The multiplicative inverses computed above are for 32-bit types,
309 and requires that we be able to compute a highpart multiply.
311 FIX: I am not at all convinced that
312 3 loads, 2 multiplications, 3 shifts, and 3 additions
315 on modern systems running a compiler. */
318 mul_mod (hashval_t x
, hashval_t y
, hashval_t inv
, int shift
)
320 hashval_t t1
, t2
, t3
, t4
, q
, r
;
322 t1
= ((uint64_t)x
* inv
) >> 32;
332 /* Compute the primary table index for HASH given current prime index. */
335 hash_table_mod1 (hashval_t hash
, unsigned int index
)
337 const struct prime_ent
*p
= &prime_tab
[index
];
338 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
339 return mul_mod (hash
, p
->prime
, p
->inv
, p
->shift
);
342 /* Compute the secondary table index for HASH given current prime index. */
345 hash_table_mod2 (hashval_t hash
, unsigned int index
)
347 const struct prime_ent
*p
= &prime_tab
[index
];
348 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
349 return 1 + mul_mod (hash
, p
->prime
- 2, p
->inv_m2
, p
->shift
);
354 /* User-facing hash table type.
356 The table stores elements of type Descriptor::value_type and uses
357 the static descriptor functions described at the top of the file
358 to hash, compare and remove elements.
360 Specify the template Allocator to allocate and free memory.
361 The default is xcallocator.
363 Storage is an implementation detail and should not be used outside the
367 template <typename Descriptor
, bool Lazy
= false,
368 template<typename Type
> class Allocator
= xcallocator
>
371 typedef typename
Descriptor::value_type value_type
;
372 typedef typename
Descriptor::compare_type compare_type
;
375 explicit hash_table (size_t, bool ggc
= false,
376 bool sanitize_eq_and_hash
= true,
377 bool gather_mem_stats
= GATHER_STATISTICS
,
378 mem_alloc_origin origin
= HASH_TABLE_ORIGIN
380 explicit hash_table (const hash_table
&, bool ggc
= false,
381 bool sanitize_eq_and_hash
= true,
382 bool gather_mem_stats
= GATHER_STATISTICS
,
383 mem_alloc_origin origin
= HASH_TABLE_ORIGIN
387 /* Create a hash_table in gc memory. */
389 create_ggc (size_t n
, bool sanitize_eq_and_hash
= true CXX_MEM_STAT_INFO
)
391 hash_table
*table
= ggc_alloc
<hash_table
> ();
392 new (table
) hash_table (n
, true, sanitize_eq_and_hash
, GATHER_STATISTICS
,
393 HASH_TABLE_ORIGIN PASS_MEM_STAT
);
397 /* Current size (in entries) of the hash table. */
398 size_t size () const { return m_size
; }
400 /* Return the current number of elements in this hash table. */
401 size_t elements () const { return m_n_elements
- m_n_deleted
; }
403 /* Return the current number of elements in this hash table. */
404 size_t elements_with_deleted () const { return m_n_elements
; }
406 /* This function clears all entries in this hash table. */
407 void empty () { if (elements ()) empty_slow (); }
409 /* Return true when there are no elements in this hash table. */
410 bool is_empty () const { return elements () == 0; }
412 /* This function clears a specified SLOT in a hash table. It is
413 useful when you've already done the lookup and don't want to do it
415 void clear_slot (value_type
*);
417 /* This function searches for a hash table entry equal to the given
418 COMPARABLE element starting with the given HASH value. It cannot
419 be used to insert or delete an element. */
420 value_type
&find_with_hash (const compare_type
&, hashval_t
);
422 /* Like find_slot_with_hash, but compute the hash value from the element. */
423 value_type
&find (const value_type
&value
)
425 return find_with_hash (value
, Descriptor::hash (value
));
428 value_type
*find_slot (const value_type
&value
, insert_option insert
)
430 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
433 /* This function searches for a hash table slot containing an entry
434 equal to the given COMPARABLE element and starting with the given
435 HASH. To delete an entry, call this with insert=NO_INSERT, then
436 call clear_slot on the slot returned (possibly after doing some
437 checks). To insert an entry, call this with insert=INSERT, then
438 write the value you want into the returned slot. When inserting an
439 entry, NULL may be returned if memory allocation fails. */
440 value_type
*find_slot_with_hash (const compare_type
&comparable
,
441 hashval_t hash
, enum insert_option insert
);
443 /* This function deletes an element with the given COMPARABLE value
444 from hash table starting with the given HASH. If there is no
445 matching element in the hash table, this function does nothing. */
446 void remove_elt_with_hash (const compare_type
&, hashval_t
);
448 /* Like remove_elt_with_hash, but compute the hash value from the
450 void remove_elt (const value_type
&value
)
452 remove_elt_with_hash (value
, Descriptor::hash (value
));
455 /* This function scans over the entire hash table calling CALLBACK for
456 each live entry. If CALLBACK returns false, the iteration stops.
457 ARGUMENT is passed as CALLBACK's second argument. */
458 template <typename Argument
,
459 int (*Callback
) (value_type
*slot
, Argument argument
)>
460 void traverse_noresize (Argument argument
);
462 /* Like traverse_noresize, but does resize the table when it is too empty
463 to improve effectivity of subsequent calls. */
464 template <typename Argument
,
465 int (*Callback
) (value_type
*slot
, Argument argument
)>
466 void traverse (Argument argument
);
471 iterator () : m_slot (NULL
), m_limit (NULL
) {}
473 iterator (value_type
*slot
, value_type
*limit
) :
474 m_slot (slot
), m_limit (limit
) {}
476 inline value_type
&operator * () { return *m_slot
; }
478 inline iterator
&operator ++ ();
479 bool operator != (const iterator
&other
) const
481 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
489 iterator
begin () const
491 if (Lazy
&& m_entries
== NULL
)
493 iterator
iter (m_entries
, m_entries
+ m_size
);
498 iterator
end () const { return iterator (); }
500 double collisions () const
502 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
506 template<typename T
> friend void gt_ggc_mx (hash_table
<T
> *);
507 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *);
508 template<typename T
> friend void
509 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator
, void *);
510 template<typename T
, typename U
, typename V
> friend void
511 gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
512 template<typename T
, typename U
>
513 friend void gt_pch_nx (hash_set
<T
, false, U
> *, gt_pointer_operator
, void *);
514 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *,
515 gt_pointer_operator
, void *);
517 template<typename T
> friend void gt_cleare_cache (hash_table
<T
> *);
521 value_type
*alloc_entries (size_t n CXX_MEM_STAT_INFO
) const;
522 value_type
*find_empty_slot_for_expand (hashval_t
);
523 void verify (const compare_type
&comparable
, hashval_t hash
);
524 bool too_empty_p (unsigned int);
526 static bool is_deleted (value_type
&v
)
528 return Descriptor::is_deleted (v
);
531 static bool is_empty (value_type
&v
)
533 return Descriptor::is_empty (v
);
536 static void mark_deleted (value_type
&v
)
538 Descriptor::mark_deleted (v
);
541 static void mark_empty (value_type
&v
)
543 Descriptor::mark_empty (v
);
547 typename
Descriptor::value_type
*m_entries
;
551 /* Current number of elements including also deleted elements. */
554 /* Current number of deleted elements in the table. */
557 /* The following member is used for debugging. Its value is number
558 of all calls of `htab_find_slot' for the hash table. */
559 unsigned int m_searches
;
561 /* The following member is used for debugging. Its value is number
562 of collisions fixed for time of work with the hash table. */
563 unsigned int m_collisions
;
565 /* Current size (in entries) of the hash table, as an index into the
567 unsigned int m_size_prime_index
;
569 /* if m_entries is stored in ggc memory. */
572 /* True if the table should be sanitized for equal and hash functions. */
573 bool m_sanitize_eq_and_hash
;
575 /* If we should gather memory statistics for the table. */
576 #if GATHER_STATISTICS
577 bool m_gather_mem_stats
;
579 static const bool m_gather_mem_stats
= false;
583 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
584 mem-stats.h after hash_table declaration. */
586 #include "mem-stats.h"
587 #include "hash-map.h"
589 extern mem_alloc_description
<mem_usage
>& hash_table_usage (void);
591 /* Support function for statistics. */
592 extern void dump_hash_table_loc_statistics (void);
594 template<typename Descriptor
, bool Lazy
,
595 template<typename Type
> class Allocator
>
596 hash_table
<Descriptor
, Lazy
, Allocator
>::hash_table (size_t size
, bool ggc
,
597 bool sanitize_eq_and_hash
,
598 bool gather_mem_stats
600 mem_alloc_origin origin
602 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
603 m_ggc (ggc
), m_sanitize_eq_and_hash (sanitize_eq_and_hash
)
604 #if GATHER_STATISTICS
605 , m_gather_mem_stats (gather_mem_stats
)
608 unsigned int size_prime_index
;
610 size_prime_index
= hash_table_higher_prime_index (size
);
611 size
= prime_tab
[size_prime_index
].prime
;
613 if (m_gather_mem_stats
)
614 hash_table_usage ().register_descriptor (this, origin
, ggc
615 FINAL_PASS_MEM_STAT
);
620 m_entries
= alloc_entries (size PASS_MEM_STAT
);
622 m_size_prime_index
= size_prime_index
;
625 template<typename Descriptor
, bool Lazy
,
626 template<typename Type
> class Allocator
>
627 hash_table
<Descriptor
, Lazy
, Allocator
>::hash_table (const hash_table
&h
,
629 bool sanitize_eq_and_hash
,
630 bool gather_mem_stats
632 mem_alloc_origin origin
634 m_n_elements (h
.m_n_elements
), m_n_deleted (h
.m_n_deleted
),
635 m_searches (0), m_collisions (0), m_ggc (ggc
),
636 m_sanitize_eq_and_hash (sanitize_eq_and_hash
)
637 #if GATHER_STATISTICS
638 , m_gather_mem_stats (gather_mem_stats
)
641 size_t size
= h
.m_size
;
643 if (m_gather_mem_stats
)
644 hash_table_usage ().register_descriptor (this, origin
, ggc
645 FINAL_PASS_MEM_STAT
);
647 if (Lazy
&& h
.m_entries
== NULL
)
651 value_type
*nentries
= alloc_entries (size PASS_MEM_STAT
);
652 for (size_t i
= 0; i
< size
; ++i
)
654 value_type
&entry
= h
.m_entries
[i
];
655 if (is_deleted (entry
))
656 mark_deleted (nentries
[i
]);
657 else if (!is_empty (entry
))
660 m_entries
= nentries
;
663 m_size_prime_index
= h
.m_size_prime_index
;
666 template<typename Descriptor
, bool Lazy
,
667 template<typename Type
> class Allocator
>
668 hash_table
<Descriptor
, Lazy
, Allocator
>::~hash_table ()
670 if (!Lazy
|| m_entries
)
672 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
673 if (!is_empty (m_entries
[i
]) && !is_deleted (m_entries
[i
]))
674 Descriptor::remove (m_entries
[i
]);
677 Allocator
<value_type
> ::data_free (m_entries
);
679 ggc_free (m_entries
);
680 if (m_gather_mem_stats
)
681 hash_table_usage ().release_instance_overhead (this,
685 else if (m_gather_mem_stats
)
686 hash_table_usage ().unregister_descriptor (this);
689 /* This function returns an array of empty hash table elements. */
691 template<typename Descriptor
, bool Lazy
,
692 template<typename Type
> class Allocator
>
693 inline typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*
694 hash_table
<Descriptor
, Lazy
,
695 Allocator
>::alloc_entries (size_t n MEM_STAT_DECL
) const
697 value_type
*nentries
;
699 if (m_gather_mem_stats
)
700 hash_table_usage ().register_instance_overhead (sizeof (value_type
) * n
, this);
703 nentries
= Allocator
<value_type
> ::data_alloc (n
);
705 nentries
= ::ggc_cleared_vec_alloc
<value_type
> (n PASS_MEM_STAT
);
707 gcc_assert (nentries
!= NULL
);
708 for (size_t i
= 0; i
< n
; i
++)
709 mark_empty (nentries
[i
]);
714 /* Similar to find_slot, but without several unwanted side effects:
715 - Does not call equal when it finds an existing entry.
716 - Does not change the count of elements/searches/collisions in the
718 This function also assumes there are no deleted entries in the table.
719 HASH is the hash value for the element to be inserted. */
721 template<typename Descriptor
, bool Lazy
,
722 template<typename Type
> class Allocator
>
723 typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*
724 hash_table
<Descriptor
, Lazy
,
725 Allocator
>::find_empty_slot_for_expand (hashval_t hash
)
727 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
728 size_t size
= m_size
;
729 value_type
*slot
= m_entries
+ index
;
732 if (is_empty (*slot
))
734 gcc_checking_assert (!is_deleted (*slot
));
736 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
743 slot
= m_entries
+ index
;
744 if (is_empty (*slot
))
746 gcc_checking_assert (!is_deleted (*slot
));
750 /* Return true if the current table is excessively big for ELTS elements. */
752 template<typename Descriptor
, bool Lazy
,
753 template<typename Type
> class Allocator
>
755 hash_table
<Descriptor
, Lazy
, Allocator
>::too_empty_p (unsigned int elts
)
757 return elts
* 8 < m_size
&& m_size
> 32;
760 /* The following function changes size of memory allocated for the
761 entries and repeatedly inserts the table elements. The occupancy
762 of the table after the call will be about 50%. Naturally the hash
763 table must already exist. Remember also that the place of the
764 table entries is changed. If memory allocation fails, this function
767 template<typename Descriptor
, bool Lazy
,
768 template<typename Type
> class Allocator
>
770 hash_table
<Descriptor
, Lazy
, Allocator
>::expand ()
772 value_type
*oentries
= m_entries
;
773 unsigned int oindex
= m_size_prime_index
;
774 size_t osize
= size ();
775 value_type
*olimit
= oentries
+ osize
;
776 size_t elts
= elements ();
778 /* Resize only when table after removal of unused elements is either
779 too full or too empty. */
782 if (elts
* 2 > osize
|| too_empty_p (elts
))
784 nindex
= hash_table_higher_prime_index (elts
* 2);
785 nsize
= prime_tab
[nindex
].prime
;
793 value_type
*nentries
= alloc_entries (nsize
);
795 if (m_gather_mem_stats
)
796 hash_table_usage ().release_instance_overhead (this, sizeof (value_type
)
799 m_entries
= nentries
;
801 m_size_prime_index
= nindex
;
802 m_n_elements
-= m_n_deleted
;
805 value_type
*p
= oentries
;
810 if (!is_empty (x
) && !is_deleted (x
))
812 value_type
*q
= find_empty_slot_for_expand (Descriptor::hash (x
));
822 Allocator
<value_type
> ::data_free (oentries
);
827 /* Implements empty() in cases where it isn't a no-op. */
829 template<typename Descriptor
, bool Lazy
,
830 template<typename Type
> class Allocator
>
832 hash_table
<Descriptor
, Lazy
, Allocator
>::empty_slow ()
834 size_t size
= m_size
;
836 value_type
*entries
= m_entries
;
839 for (i
= size
- 1; i
>= 0; i
--)
840 if (!is_empty (entries
[i
]) && !is_deleted (entries
[i
]))
841 Descriptor::remove (entries
[i
]);
843 /* Instead of clearing megabyte, downsize the table. */
844 if (size
> 1024*1024 / sizeof (value_type
))
845 nsize
= 1024 / sizeof (value_type
);
846 else if (too_empty_p (m_n_elements
))
847 nsize
= m_n_elements
* 2;
851 int nindex
= hash_table_higher_prime_index (nsize
);
852 int nsize
= prime_tab
[nindex
].prime
;
855 Allocator
<value_type
> ::data_free (m_entries
);
857 ggc_free (m_entries
);
859 m_entries
= alloc_entries (nsize
);
861 m_size_prime_index
= nindex
;
865 #ifndef BROKEN_VALUE_INITIALIZATION
866 for ( ; size
; ++entries
, --size
)
867 *entries
= value_type ();
869 memset (entries
, 0, size
* sizeof (value_type
));
876 /* This function clears a specified SLOT in a hash table. It is
877 useful when you've already done the lookup and don't want to do it
880 template<typename Descriptor
, bool Lazy
,
881 template<typename Type
> class Allocator
>
883 hash_table
<Descriptor
, Lazy
, Allocator
>::clear_slot (value_type
*slot
)
885 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
886 || is_empty (*slot
) || is_deleted (*slot
)));
888 Descriptor::remove (*slot
);
890 mark_deleted (*slot
);
894 /* This function searches for a hash table entry equal to the given
895 COMPARABLE element starting with the given HASH value. It cannot
896 be used to insert or delete an element. */
898 template<typename Descriptor
, bool Lazy
,
899 template<typename Type
> class Allocator
>
900 typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
&
901 hash_table
<Descriptor
, Lazy
, Allocator
>
902 ::find_with_hash (const compare_type
&comparable
, hashval_t hash
)
905 size_t size
= m_size
;
906 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
908 if (Lazy
&& m_entries
== NULL
)
909 m_entries
= alloc_entries (size
);
910 value_type
*entry
= &m_entries
[index
];
911 if (is_empty (*entry
)
912 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
915 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
923 entry
= &m_entries
[index
];
924 if (is_empty (*entry
)
925 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
928 if (m_sanitize_eq_and_hash
)
929 verify (comparable
, hash
);
936 /* This function searches for a hash table slot containing an entry
937 equal to the given COMPARABLE element and starting with the given
938 HASH. To delete an entry, call this with insert=NO_INSERT, then
939 call clear_slot on the slot returned (possibly after doing some
940 checks). To insert an entry, call this with insert=INSERT, then
941 write the value you want into the returned slot. When inserting an
942 entry, NULL may be returned if memory allocation fails. */
944 template<typename Descriptor
, bool Lazy
,
945 template<typename Type
> class Allocator
>
946 typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*
947 hash_table
<Descriptor
, Lazy
, Allocator
>
948 ::find_slot_with_hash (const compare_type
&comparable
, hashval_t hash
,
949 enum insert_option insert
)
951 if (Lazy
&& m_entries
== NULL
)
953 if (insert
== INSERT
)
954 m_entries
= alloc_entries (m_size
);
958 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
962 if (m_sanitize_eq_and_hash
)
963 verify (comparable
, hash
);
967 value_type
*first_deleted_slot
= NULL
;
968 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
969 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
970 value_type
*entry
= &m_entries
[index
];
971 size_t size
= m_size
;
972 if (is_empty (*entry
))
974 else if (is_deleted (*entry
))
975 first_deleted_slot
= &m_entries
[index
];
976 else if (Descriptor::equal (*entry
, comparable
))
977 return &m_entries
[index
];
986 entry
= &m_entries
[index
];
987 if (is_empty (*entry
))
989 else if (is_deleted (*entry
))
991 if (!first_deleted_slot
)
992 first_deleted_slot
= &m_entries
[index
];
994 else if (Descriptor::equal (*entry
, comparable
))
995 return &m_entries
[index
];
999 if (insert
== NO_INSERT
)
1002 if (first_deleted_slot
)
1005 mark_empty (*first_deleted_slot
);
1006 return first_deleted_slot
;
1010 return &m_entries
[index
];
1013 /* Report a hash table checking error. */
1015 ATTRIBUTE_NORETURN ATTRIBUTE_COLD
1017 hashtab_chk_error ()
1019 fprintf (stderr
, "hash table checking failed: "
1020 "equal operator returns true for a pair "
1021 "of values with a different hash value\n");
1025 /* Verify that all existing elements in th hash table which are
1026 equal to COMPARABLE have an equal HASH value provided as argument. */
1028 template<typename Descriptor
, bool Lazy
,
1029 template<typename Type
> class Allocator
>
1031 hash_table
<Descriptor
, Lazy
, Allocator
>
1032 ::verify (const compare_type
&comparable
, hashval_t hash
)
1034 for (size_t i
= 0; i
< MIN (hash_table_sanitize_eq_limit
, m_size
); i
++)
1036 value_type
*entry
= &m_entries
[i
];
1037 if (!is_empty (*entry
) && !is_deleted (*entry
)
1038 && hash
!= Descriptor::hash (*entry
)
1039 && Descriptor::equal (*entry
, comparable
))
1040 hashtab_chk_error ();
1044 /* This function deletes an element with the given COMPARABLE value
1045 from hash table starting with the given HASH. If there is no
1046 matching element in the hash table, this function does nothing. */
1048 template<typename Descriptor
, bool Lazy
,
1049 template<typename Type
> class Allocator
>
1051 hash_table
<Descriptor
, Lazy
, Allocator
>
1052 ::remove_elt_with_hash (const compare_type
&comparable
, hashval_t hash
)
1054 value_type
*slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
1058 Descriptor::remove (*slot
);
1060 mark_deleted (*slot
);
1064 /* This function scans over the entire hash table calling CALLBACK for
1065 each live entry. If CALLBACK returns false, the iteration stops.
1066 ARGUMENT is passed as CALLBACK's second argument. */
1068 template<typename Descriptor
, bool Lazy
,
1069 template<typename Type
> class Allocator
>
1070 template<typename Argument
,
1072 (typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*slot
,
1075 hash_table
<Descriptor
, Lazy
, Allocator
>::traverse_noresize (Argument argument
)
1077 if (Lazy
&& m_entries
== NULL
)
1080 value_type
*slot
= m_entries
;
1081 value_type
*limit
= slot
+ size ();
1085 value_type
&x
= *slot
;
1087 if (!is_empty (x
) && !is_deleted (x
))
1088 if (! Callback (slot
, argument
))
1091 while (++slot
< limit
);
1094 /* Like traverse_noresize, but does resize the table when it is too empty
1095 to improve effectivity of subsequent calls. */
1097 template <typename Descriptor
, bool Lazy
,
1098 template <typename Type
> class Allocator
>
1099 template <typename Argument
,
1101 (typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*slot
,
1104 hash_table
<Descriptor
, Lazy
, Allocator
>::traverse (Argument argument
)
1106 if (too_empty_p (elements ()) && (!Lazy
|| m_entries
))
1109 traverse_noresize
<Argument
, Callback
> (argument
);
1112 /* Slide down the iterator slots until an active entry is found. */
1114 template<typename Descriptor
, bool Lazy
,
1115 template<typename Type
> class Allocator
>
1117 hash_table
<Descriptor
, Lazy
, Allocator
>::iterator::slide ()
1119 for ( ; m_slot
< m_limit
; ++m_slot
)
1121 value_type
&x
= *m_slot
;
1122 if (!is_empty (x
) && !is_deleted (x
))
1129 /* Bump the iterator. */
1131 template<typename Descriptor
, bool Lazy
,
1132 template<typename Type
> class Allocator
>
1133 inline typename hash_table
<Descriptor
, Lazy
, Allocator
>::iterator
&
1134 hash_table
<Descriptor
, Lazy
, Allocator
>::iterator::operator ++ ()
1142 /* Iterate through the elements of hash_table HTAB,
1143 using hash_table <....>::iterator ITER,
1144 storing each element in RESULT, which is of type TYPE. */
1146 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1147 for ((ITER) = (HTAB).begin (); \
1148 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1151 /* ggc walking routines. */
1153 template<typename E
>
1155 gt_ggc_mx (hash_table
<E
> *h
)
1157 typedef hash_table
<E
> table
;
1159 if (!ggc_test_and_set_mark (h
->m_entries
))
1162 for (size_t i
= 0; i
< h
->m_size
; i
++)
1164 if (table::is_empty (h
->m_entries
[i
])
1165 || table::is_deleted (h
->m_entries
[i
]))
1168 /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1169 mark in gt_cleare_cache if appropriate. */
1170 E::ggc_maybe_mx (h
->m_entries
[i
]);
1174 template<typename D
>
1176 hashtab_entry_note_pointers (void *obj
, void *h
, gt_pointer_operator op
,
1179 hash_table
<D
> *map
= static_cast<hash_table
<D
> *> (h
);
1180 gcc_checking_assert (map
->m_entries
== obj
);
1181 for (size_t i
= 0; i
< map
->m_size
; i
++)
1183 typedef hash_table
<D
> table
;
1184 if (table::is_empty (map
->m_entries
[i
])
1185 || table::is_deleted (map
->m_entries
[i
]))
1188 D::pch_nx (map
->m_entries
[i
], op
, cookie
);
1192 template<typename D
>
1194 gt_pch_nx (hash_table
<D
> *h
)
1197 = gt_pch_note_object (h
->m_entries
, h
, hashtab_entry_note_pointers
<D
>);
1198 gcc_checking_assert (success
);
1199 for (size_t i
= 0; i
< h
->m_size
; i
++)
1201 if (hash_table
<D
>::is_empty (h
->m_entries
[i
])
1202 || hash_table
<D
>::is_deleted (h
->m_entries
[i
]))
1205 D::pch_nx (h
->m_entries
[i
]);
1209 template<typename D
>
1211 gt_pch_nx (hash_table
<D
> *h
, gt_pointer_operator op
, void *cookie
)
1213 op (&h
->m_entries
, cookie
);
1216 template<typename H
>
1218 gt_cleare_cache (hash_table
<H
> *h
)
1220 typedef hash_table
<H
> table
;
1224 for (typename
table::iterator iter
= h
->begin (); iter
!= h
->end (); ++iter
)
1225 if (!table::is_empty (*iter
) && !table::is_deleted (*iter
))
1227 int res
= H::keep_cache_entry (*iter
);
1229 h
->clear_slot (&*iter
);
1235 #endif /* TYPED_HASHTAB_H */