i386: Use const reference of struct ix86_frame to avoid copy
[official-gcc.git] / gcc / hash-table.h
blob8e22cbb660a52a4e248112911c8c80c2b60123eb
1 /* A type-safe hash table template.
2 Copyright (C) 2012-2018 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 (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
49 const references.
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
96 policies:
98 * typed_free_remove implements the static 'remove' member function
99 by calling free().
101 * typed_noop_remove implements the static 'remove' member function
102 by doing nothing.
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
107 collections.
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
126 accordingly.
128 4. Choose an equality testing function 'equal' that compares a value_type
129 and a compare_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
133 you need to change.
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 *);
148 inline hashval_t
149 some_type_hasher::hash (const value_type *e)
150 { ... compute and return a hash value for E ... }
152 inline bool
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
168 htab_t.
171 EASY DESCRIPTORS FOR POINTERS
173 There are four descriptors for pointer elements, one for each of
174 the removal policies above:
176 * nofree_ptr_hash (based on typed_noop_remove)
177 * free_ptr_hash (based on typed_free_remove)
178 * ggc_ptr_hash (based on ggc_remove)
179 * ggc_cache_ptr_hash (based on ggc_cache_remove)
181 These descriptors hash and compare elements by their pointer value,
182 rather than what they point to. So, to instantiate a hash table over
183 pointers to whatever_type, without freeing the whatever_types, use:
185 hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
188 HASH TABLE ITERATORS
190 The hash table provides standard C++ iterators. For example, consider a
191 hash table of some_info. We wish to consume each element of the table:
193 extern void consume (some_info *);
195 We define a convenience typedef and the hash table:
197 typedef hash_table <some_info_hasher> info_table_type;
198 info_table_type info_table;
200 Then we write the loop in typical C++ style:
202 for (info_table_type::iterator iter = info_table.begin ();
203 iter != info_table.end ();
204 ++iter)
205 if ((*iter).status == INFO_READY)
206 consume (&*iter);
208 Or with common sub-expression elimination:
210 for (info_table_type::iterator iter = info_table.begin ();
211 iter != info_table.end ();
212 ++iter)
214 some_info &elem = *iter;
215 if (elem.status == INFO_READY)
216 consume (&elem);
219 One can also use a more typical GCC style:
221 typedef some_info *some_info_p;
222 some_info *elem_ptr;
223 info_table_type::iterator iter;
224 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
225 if (elem_ptr->status == INFO_READY)
226 consume (elem_ptr);
231 #ifndef TYPED_HASHTAB_H
232 #define TYPED_HASHTAB_H
234 #include "statistics.h"
235 #include "ggc.h"
236 #include "vec.h"
237 #include "hashtab.h"
238 #include "inchash.h"
239 #include "mem-stats-traits.h"
240 #include "hash-traits.h"
241 #include "hash-map-traits.h"
243 template<typename, typename, typename> class hash_map;
244 template<typename, typename> class hash_set;
246 /* The ordinary memory allocator. */
247 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
249 template <typename Type>
250 struct xcallocator
252 static Type *data_alloc (size_t count);
253 static void data_free (Type *memory);
257 /* Allocate memory for COUNT data blocks. */
259 template <typename Type>
260 inline Type *
261 xcallocator <Type>::data_alloc (size_t count)
263 return static_cast <Type *> (xcalloc (count, sizeof (Type)));
267 /* Free memory for data blocks. */
269 template <typename Type>
270 inline void
271 xcallocator <Type>::data_free (Type *memory)
273 return ::free (memory);
277 /* Table of primes and their inversion information. */
279 struct prime_ent
281 hashval_t prime;
282 hashval_t inv;
283 hashval_t inv_m2; /* inverse of prime-2 */
284 hashval_t shift;
287 extern struct prime_ent const prime_tab[];
290 /* Functions for computing hash table indexes. */
292 extern unsigned int hash_table_higher_prime_index (unsigned long n)
293 ATTRIBUTE_PURE;
295 /* Return X % Y using multiplicative inverse values INV and SHIFT.
297 The multiplicative inverses computed above are for 32-bit types,
298 and requires that we be able to compute a highpart multiply.
300 FIX: I am not at all convinced that
301 3 loads, 2 multiplications, 3 shifts, and 3 additions
302 will be faster than
303 1 load and 1 modulus
304 on modern systems running a compiler. */
306 inline hashval_t
307 mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
309 hashval_t t1, t2, t3, t4, q, r;
311 t1 = ((uint64_t)x * inv) >> 32;
312 t2 = x - t1;
313 t3 = t2 >> 1;
314 t4 = t1 + t3;
315 q = t4 >> shift;
316 r = x - (q * y);
318 return r;
321 /* Compute the primary table index for HASH given current prime index. */
323 inline hashval_t
324 hash_table_mod1 (hashval_t hash, unsigned int index)
326 const struct prime_ent *p = &prime_tab[index];
327 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
328 return mul_mod (hash, p->prime, p->inv, p->shift);
331 /* Compute the secondary table index for HASH given current prime index. */
333 inline hashval_t
334 hash_table_mod2 (hashval_t hash, unsigned int index)
336 const struct prime_ent *p = &prime_tab[index];
337 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
338 return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
341 class mem_usage;
343 /* User-facing hash table type.
345 The table stores elements of type Descriptor::value_type and uses
346 the static descriptor functions described at the top of the file
347 to hash, compare and remove elements.
349 Specify the template Allocator to allocate and free memory.
350 The default is xcallocator.
352 Storage is an implementation detail and should not be used outside the
353 hash table code.
356 template <typename Descriptor,
357 template<typename Type> class Allocator = xcallocator>
358 class hash_table
360 typedef typename Descriptor::value_type value_type;
361 typedef typename Descriptor::compare_type compare_type;
363 public:
364 explicit hash_table (size_t, bool ggc = false,
365 bool gather_mem_stats = GATHER_STATISTICS,
366 mem_alloc_origin origin = HASH_TABLE_ORIGIN
367 CXX_MEM_STAT_INFO);
368 explicit hash_table (const hash_table &, bool ggc = false,
369 bool gather_mem_stats = GATHER_STATISTICS,
370 mem_alloc_origin origin = HASH_TABLE_ORIGIN
371 CXX_MEM_STAT_INFO);
372 ~hash_table ();
374 /* Create a hash_table in gc memory. */
375 static hash_table *
376 create_ggc (size_t n CXX_MEM_STAT_INFO)
378 hash_table *table = ggc_alloc<hash_table> ();
379 new (table) hash_table (n, true, GATHER_STATISTICS,
380 HASH_TABLE_ORIGIN PASS_MEM_STAT);
381 return table;
384 /* Current size (in entries) of the hash table. */
385 size_t size () const { return m_size; }
387 /* Return the current number of elements in this hash table. */
388 size_t elements () const { return m_n_elements - m_n_deleted; }
390 /* Return the current number of elements in this hash table. */
391 size_t elements_with_deleted () const { return m_n_elements; }
393 /* This function clears all entries in this hash table. */
394 void empty () { if (elements ()) empty_slow (); }
396 /* This function clears a specified SLOT in a hash table. It is
397 useful when you've already done the lookup and don't want to do it
398 again. */
399 void clear_slot (value_type *);
401 /* This function searches for a hash table entry equal to the given
402 COMPARABLE element starting with the given HASH value. It cannot
403 be used to insert or delete an element. */
404 value_type &find_with_hash (const compare_type &, hashval_t);
406 /* Like find_slot_with_hash, but compute the hash value from the element. */
407 value_type &find (const value_type &value)
409 return find_with_hash (value, Descriptor::hash (value));
412 value_type *find_slot (const value_type &value, insert_option insert)
414 return find_slot_with_hash (value, Descriptor::hash (value), insert);
417 /* This function searches for a hash table slot containing an entry
418 equal to the given COMPARABLE element and starting with the given
419 HASH. To delete an entry, call this with insert=NO_INSERT, then
420 call clear_slot on the slot returned (possibly after doing some
421 checks). To insert an entry, call this with insert=INSERT, then
422 write the value you want into the returned slot. When inserting an
423 entry, NULL may be returned if memory allocation fails. */
424 value_type *find_slot_with_hash (const compare_type &comparable,
425 hashval_t hash, enum insert_option insert);
427 /* This function deletes an element with the given COMPARABLE value
428 from hash table starting with the given HASH. If there is no
429 matching element in the hash table, this function does nothing. */
430 void remove_elt_with_hash (const compare_type &, hashval_t);
432 /* Like remove_elt_with_hash, but compute the hash value from the
433 element. */
434 void remove_elt (const value_type &value)
436 remove_elt_with_hash (value, Descriptor::hash (value));
439 /* This function scans over the entire hash table calling CALLBACK for
440 each live entry. If CALLBACK returns false, the iteration stops.
441 ARGUMENT is passed as CALLBACK's second argument. */
442 template <typename Argument,
443 int (*Callback) (value_type *slot, Argument argument)>
444 void traverse_noresize (Argument argument);
446 /* Like traverse_noresize, but does resize the table when it is too empty
447 to improve effectivity of subsequent calls. */
448 template <typename Argument,
449 int (*Callback) (value_type *slot, Argument argument)>
450 void traverse (Argument argument);
452 class iterator
454 public:
455 iterator () : m_slot (NULL), m_limit (NULL) {}
457 iterator (value_type *slot, value_type *limit) :
458 m_slot (slot), m_limit (limit) {}
460 inline value_type &operator * () { return *m_slot; }
461 void slide ();
462 inline iterator &operator ++ ();
463 bool operator != (const iterator &other) const
465 return m_slot != other.m_slot || m_limit != other.m_limit;
468 private:
469 value_type *m_slot;
470 value_type *m_limit;
473 iterator begin () const
475 iterator iter (m_entries, m_entries + m_size);
476 iter.slide ();
477 return iter;
480 iterator end () const { return iterator (); }
482 double collisions () const
484 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
487 private:
488 template<typename T> friend void gt_ggc_mx (hash_table<T> *);
489 template<typename T> friend void gt_pch_nx (hash_table<T> *);
490 template<typename T> friend void
491 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
492 template<typename T, typename U, typename V> friend void
493 gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
494 template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *,
495 gt_pointer_operator,
496 void *);
497 template<typename T> friend void gt_pch_nx (hash_table<T> *,
498 gt_pointer_operator, void *);
500 template<typename T> friend void gt_cleare_cache (hash_table<T> *);
502 void empty_slow ();
504 value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
505 value_type *find_empty_slot_for_expand (hashval_t);
506 bool too_empty_p (unsigned int);
507 void expand ();
508 static bool is_deleted (value_type &v)
510 return Descriptor::is_deleted (v);
513 static bool is_empty (value_type &v)
515 return Descriptor::is_empty (v);
518 static void mark_deleted (value_type &v)
520 Descriptor::mark_deleted (v);
523 static void mark_empty (value_type &v)
525 Descriptor::mark_empty (v);
528 /* Table itself. */
529 typename Descriptor::value_type *m_entries;
531 size_t m_size;
533 /* Current number of elements including also deleted elements. */
534 size_t m_n_elements;
536 /* Current number of deleted elements in the table. */
537 size_t m_n_deleted;
539 /* The following member is used for debugging. Its value is number
540 of all calls of `htab_find_slot' for the hash table. */
541 unsigned int m_searches;
543 /* The following member is used for debugging. Its value is number
544 of collisions fixed for time of work with the hash table. */
545 unsigned int m_collisions;
547 /* Current size (in entries) of the hash table, as an index into the
548 table of primes. */
549 unsigned int m_size_prime_index;
551 /* if m_entries is stored in ggc memory. */
552 bool m_ggc;
554 /* If we should gather memory statistics for the table. */
555 bool m_gather_mem_stats;
558 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
559 mem-stats.h after hash_table declaration. */
561 #include "mem-stats.h"
562 #include "hash-map.h"
564 extern mem_alloc_description<mem_usage> hash_table_usage;
566 /* Support function for statistics. */
567 extern void dump_hash_table_loc_statistics (void);
569 template<typename Descriptor, template<typename Type> class Allocator>
570 hash_table<Descriptor, Allocator>::hash_table (size_t size, bool ggc, bool
571 gather_mem_stats,
572 mem_alloc_origin origin
573 MEM_STAT_DECL) :
574 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
575 m_ggc (ggc), m_gather_mem_stats (gather_mem_stats)
577 unsigned int size_prime_index;
579 size_prime_index = hash_table_higher_prime_index (size);
580 size = prime_tab[size_prime_index].prime;
582 if (m_gather_mem_stats)
583 hash_table_usage.register_descriptor (this, origin, ggc
584 FINAL_PASS_MEM_STAT);
586 m_entries = alloc_entries (size PASS_MEM_STAT);
587 m_size = size;
588 m_size_prime_index = size_prime_index;
591 template<typename Descriptor, template<typename Type> class Allocator>
592 hash_table<Descriptor, Allocator>::hash_table (const hash_table &h, bool ggc,
593 bool gather_mem_stats,
594 mem_alloc_origin origin
595 MEM_STAT_DECL) :
596 m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
597 m_searches (0), m_collisions (0), m_ggc (ggc),
598 m_gather_mem_stats (gather_mem_stats)
600 size_t size = h.m_size;
602 if (m_gather_mem_stats)
603 hash_table_usage.register_descriptor (this, origin, ggc
604 FINAL_PASS_MEM_STAT);
606 value_type *nentries = alloc_entries (size PASS_MEM_STAT);
607 for (size_t i = 0; i < size; ++i)
609 value_type &entry = h.m_entries[i];
610 if (is_deleted (entry))
611 mark_deleted (nentries[i]);
612 else if (!is_empty (entry))
613 nentries[i] = entry;
615 m_entries = nentries;
616 m_size = size;
617 m_size_prime_index = h.m_size_prime_index;
620 template<typename Descriptor, template<typename Type> class Allocator>
621 hash_table<Descriptor, Allocator>::~hash_table ()
623 for (size_t i = m_size - 1; i < m_size; i--)
624 if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
625 Descriptor::remove (m_entries[i]);
627 if (!m_ggc)
628 Allocator <value_type> ::data_free (m_entries);
629 else
630 ggc_free (m_entries);
632 if (m_gather_mem_stats)
633 hash_table_usage.release_instance_overhead (this,
634 sizeof (value_type) * m_size,
635 true);
638 /* This function returns an array of empty hash table elements. */
640 template<typename Descriptor, template<typename Type> class Allocator>
641 inline typename hash_table<Descriptor, Allocator>::value_type *
642 hash_table<Descriptor, Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
644 value_type *nentries;
646 if (m_gather_mem_stats)
647 hash_table_usage.register_instance_overhead (sizeof (value_type) * n, this);
649 if (!m_ggc)
650 nentries = Allocator <value_type> ::data_alloc (n);
651 else
652 nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
654 gcc_assert (nentries != NULL);
655 for (size_t i = 0; i < n; i++)
656 mark_empty (nentries[i]);
658 return nentries;
661 /* Similar to find_slot, but without several unwanted side effects:
662 - Does not call equal when it finds an existing entry.
663 - Does not change the count of elements/searches/collisions in the
664 hash table.
665 This function also assumes there are no deleted entries in the table.
666 HASH is the hash value for the element to be inserted. */
668 template<typename Descriptor, template<typename Type> class Allocator>
669 typename hash_table<Descriptor, Allocator>::value_type *
670 hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
672 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
673 size_t size = m_size;
674 value_type *slot = m_entries + index;
675 hashval_t hash2;
677 if (is_empty (*slot))
678 return slot;
679 gcc_checking_assert (!is_deleted (*slot));
681 hash2 = hash_table_mod2 (hash, m_size_prime_index);
682 for (;;)
684 index += hash2;
685 if (index >= size)
686 index -= size;
688 slot = m_entries + index;
689 if (is_empty (*slot))
690 return slot;
691 gcc_checking_assert (!is_deleted (*slot));
695 /* Return true if the current table is excessively big for ELTS elements. */
697 template<typename Descriptor, template<typename Type> class Allocator>
698 inline bool
699 hash_table<Descriptor, Allocator>::too_empty_p (unsigned int elts)
701 return elts * 8 < m_size && m_size > 32;
704 /* The following function changes size of memory allocated for the
705 entries and repeatedly inserts the table elements. The occupancy
706 of the table after the call will be about 50%. Naturally the hash
707 table must already exist. Remember also that the place of the
708 table entries is changed. If memory allocation fails, this function
709 will abort. */
711 template<typename Descriptor, template<typename Type> class Allocator>
712 void
713 hash_table<Descriptor, Allocator>::expand ()
715 value_type *oentries = m_entries;
716 unsigned int oindex = m_size_prime_index;
717 size_t osize = size ();
718 value_type *olimit = oentries + osize;
719 size_t elts = elements ();
721 /* Resize only when table after removal of unused elements is either
722 too full or too empty. */
723 unsigned int nindex;
724 size_t nsize;
725 if (elts * 2 > osize || too_empty_p (elts))
727 nindex = hash_table_higher_prime_index (elts * 2);
728 nsize = prime_tab[nindex].prime;
730 else
732 nindex = oindex;
733 nsize = osize;
736 value_type *nentries = alloc_entries (nsize);
738 if (m_gather_mem_stats)
739 hash_table_usage.release_instance_overhead (this, sizeof (value_type)
740 * osize);
742 m_entries = nentries;
743 m_size = nsize;
744 m_size_prime_index = nindex;
745 m_n_elements -= m_n_deleted;
746 m_n_deleted = 0;
748 value_type *p = oentries;
751 value_type &x = *p;
753 if (!is_empty (x) && !is_deleted (x))
755 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
757 *q = x;
760 p++;
762 while (p < olimit);
764 if (!m_ggc)
765 Allocator <value_type> ::data_free (oentries);
766 else
767 ggc_free (oentries);
770 /* Implements empty() in cases where it isn't a no-op. */
772 template<typename Descriptor, template<typename Type> class Allocator>
773 void
774 hash_table<Descriptor, Allocator>::empty_slow ()
776 size_t size = m_size;
777 size_t nsize = size;
778 value_type *entries = m_entries;
779 int i;
781 for (i = size - 1; i >= 0; i--)
782 if (!is_empty (entries[i]) && !is_deleted (entries[i]))
783 Descriptor::remove (entries[i]);
785 /* Instead of clearing megabyte, downsize the table. */
786 if (size > 1024*1024 / sizeof (value_type))
787 nsize = 1024 / sizeof (value_type);
788 else if (too_empty_p (m_n_elements))
789 nsize = m_n_elements * 2;
791 if (nsize != size)
793 int nindex = hash_table_higher_prime_index (nsize);
794 int nsize = prime_tab[nindex].prime;
796 if (!m_ggc)
797 Allocator <value_type> ::data_free (m_entries);
798 else
799 ggc_free (m_entries);
801 m_entries = alloc_entries (nsize);
802 m_size = nsize;
803 m_size_prime_index = nindex;
805 else
807 for ( ; size; ++entries, --size)
808 *entries = value_type ();
810 m_n_deleted = 0;
811 m_n_elements = 0;
814 /* This function clears a specified SLOT in a hash table. It is
815 useful when you've already done the lookup and don't want to do it
816 again. */
818 template<typename Descriptor, template<typename Type> class Allocator>
819 void
820 hash_table<Descriptor, Allocator>::clear_slot (value_type *slot)
822 gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
823 || is_empty (*slot) || is_deleted (*slot)));
825 Descriptor::remove (*slot);
827 mark_deleted (*slot);
828 m_n_deleted++;
831 /* This function searches for a hash table entry equal to the given
832 COMPARABLE element starting with the given HASH value. It cannot
833 be used to insert or delete an element. */
835 template<typename Descriptor, template<typename Type> class Allocator>
836 typename hash_table<Descriptor, Allocator>::value_type &
837 hash_table<Descriptor, Allocator>
838 ::find_with_hash (const compare_type &comparable, hashval_t hash)
840 m_searches++;
841 size_t size = m_size;
842 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
844 value_type *entry = &m_entries[index];
845 if (is_empty (*entry)
846 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
847 return *entry;
849 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
850 for (;;)
852 m_collisions++;
853 index += hash2;
854 if (index >= size)
855 index -= size;
857 entry = &m_entries[index];
858 if (is_empty (*entry)
859 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
860 return *entry;
864 /* This function searches for a hash table slot containing an entry
865 equal to the given COMPARABLE element and starting with the given
866 HASH. To delete an entry, call this with insert=NO_INSERT, then
867 call clear_slot on the slot returned (possibly after doing some
868 checks). To insert an entry, call this with insert=INSERT, then
869 write the value you want into the returned slot. When inserting an
870 entry, NULL may be returned if memory allocation fails. */
872 template<typename Descriptor, template<typename Type> class Allocator>
873 typename hash_table<Descriptor, Allocator>::value_type *
874 hash_table<Descriptor, Allocator>
875 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
876 enum insert_option insert)
878 if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
879 expand ();
881 m_searches++;
883 value_type *first_deleted_slot = NULL;
884 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
885 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
886 value_type *entry = &m_entries[index];
887 size_t size = m_size;
888 if (is_empty (*entry))
889 goto empty_entry;
890 else if (is_deleted (*entry))
891 first_deleted_slot = &m_entries[index];
892 else if (Descriptor::equal (*entry, comparable))
893 return &m_entries[index];
895 for (;;)
897 m_collisions++;
898 index += hash2;
899 if (index >= size)
900 index -= size;
902 entry = &m_entries[index];
903 if (is_empty (*entry))
904 goto empty_entry;
905 else if (is_deleted (*entry))
907 if (!first_deleted_slot)
908 first_deleted_slot = &m_entries[index];
910 else if (Descriptor::equal (*entry, comparable))
911 return &m_entries[index];
914 empty_entry:
915 if (insert == NO_INSERT)
916 return NULL;
918 if (first_deleted_slot)
920 m_n_deleted--;
921 mark_empty (*first_deleted_slot);
922 return first_deleted_slot;
925 m_n_elements++;
926 return &m_entries[index];
929 /* This function deletes an element with the given COMPARABLE value
930 from hash table starting with the given HASH. If there is no
931 matching element in the hash table, this function does nothing. */
933 template<typename Descriptor, template<typename Type> class Allocator>
934 void
935 hash_table<Descriptor, Allocator>
936 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
938 value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
939 if (is_empty (*slot))
940 return;
942 Descriptor::remove (*slot);
944 mark_deleted (*slot);
945 m_n_deleted++;
948 /* This function scans over the entire hash table calling CALLBACK for
949 each live entry. If CALLBACK returns false, the iteration stops.
950 ARGUMENT is passed as CALLBACK's second argument. */
952 template<typename Descriptor,
953 template<typename Type> class Allocator>
954 template<typename Argument,
955 int (*Callback)
956 (typename hash_table<Descriptor, Allocator>::value_type *slot,
957 Argument argument)>
958 void
959 hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
961 value_type *slot = m_entries;
962 value_type *limit = slot + size ();
966 value_type &x = *slot;
968 if (!is_empty (x) && !is_deleted (x))
969 if (! Callback (slot, argument))
970 break;
972 while (++slot < limit);
975 /* Like traverse_noresize, but does resize the table when it is too empty
976 to improve effectivity of subsequent calls. */
978 template <typename Descriptor,
979 template <typename Type> class Allocator>
980 template <typename Argument,
981 int (*Callback)
982 (typename hash_table<Descriptor, Allocator>::value_type *slot,
983 Argument argument)>
984 void
985 hash_table<Descriptor, Allocator>::traverse (Argument argument)
987 if (too_empty_p (elements ()))
988 expand ();
990 traverse_noresize <Argument, Callback> (argument);
993 /* Slide down the iterator slots until an active entry is found. */
995 template<typename Descriptor, template<typename Type> class Allocator>
996 void
997 hash_table<Descriptor, Allocator>::iterator::slide ()
999 for ( ; m_slot < m_limit; ++m_slot )
1001 value_type &x = *m_slot;
1002 if (!is_empty (x) && !is_deleted (x))
1003 return;
1005 m_slot = NULL;
1006 m_limit = NULL;
1009 /* Bump the iterator. */
1011 template<typename Descriptor, template<typename Type> class Allocator>
1012 inline typename hash_table<Descriptor, Allocator>::iterator &
1013 hash_table<Descriptor, Allocator>::iterator::operator ++ ()
1015 ++m_slot;
1016 slide ();
1017 return *this;
1021 /* Iterate through the elements of hash_table HTAB,
1022 using hash_table <....>::iterator ITER,
1023 storing each element in RESULT, which is of type TYPE. */
1025 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1026 for ((ITER) = (HTAB).begin (); \
1027 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1028 ++(ITER))
1030 /* ggc walking routines. */
1032 template<typename E>
1033 static inline void
1034 gt_ggc_mx (hash_table<E> *h)
1036 typedef hash_table<E> table;
1038 if (!ggc_test_and_set_mark (h->m_entries))
1039 return;
1041 for (size_t i = 0; i < h->m_size; i++)
1043 if (table::is_empty (h->m_entries[i])
1044 || table::is_deleted (h->m_entries[i]))
1045 continue;
1047 /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1048 mark in gt_cleare_cache if appropriate. */
1049 E::ggc_maybe_mx (h->m_entries[i]);
1053 template<typename D>
1054 static inline void
1055 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1056 void *cookie)
1058 hash_table<D> *map = static_cast<hash_table<D> *> (h);
1059 gcc_checking_assert (map->m_entries == obj);
1060 for (size_t i = 0; i < map->m_size; i++)
1062 typedef hash_table<D> table;
1063 if (table::is_empty (map->m_entries[i])
1064 || table::is_deleted (map->m_entries[i]))
1065 continue;
1067 D::pch_nx (map->m_entries[i], op, cookie);
1071 template<typename D>
1072 static void
1073 gt_pch_nx (hash_table<D> *h)
1075 bool success
1076 = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1077 gcc_checking_assert (success);
1078 for (size_t i = 0; i < h->m_size; i++)
1080 if (hash_table<D>::is_empty (h->m_entries[i])
1081 || hash_table<D>::is_deleted (h->m_entries[i]))
1082 continue;
1084 D::pch_nx (h->m_entries[i]);
1088 template<typename D>
1089 static inline void
1090 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1092 op (&h->m_entries, cookie);
1095 template<typename H>
1096 inline void
1097 gt_cleare_cache (hash_table<H> *h)
1099 typedef hash_table<H> table;
1100 if (!h)
1101 return;
1103 for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1104 if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1106 int res = H::keep_cache_entry (*iter);
1107 if (res == 0)
1108 h->clear_slot (&*iter);
1109 else if (res != -1)
1110 H::ggc_mx (*iter);
1114 #endif /* TYPED_HASHTAB_H */