Daily bump.
[official-gcc.git] / gcc / hash-table.h
blob12e0c965d13b0757271378d6dab144de66f9326d
1 /* A type-safe hash table template.
2 Copyright (C) 2012-2015 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
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 used 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, bool gather_mem_stats = true,
365 mem_alloc_origin origin = HASH_TABLE_ORIGIN
366 CXX_MEM_STAT_INFO);
367 ~hash_table ();
369 /* Create a hash_table in gc memory. */
370 static hash_table *
371 create_ggc (size_t n CXX_MEM_STAT_INFO)
373 hash_table *table = ggc_alloc<hash_table> ();
374 new (table) hash_table (n, true, true, HASH_TABLE_ORIGIN PASS_MEM_STAT);
375 return table;
378 /* Current size (in entries) of the hash table. */
379 size_t size () const { return m_size; }
381 /* Return the current number of elements in this hash table. */
382 size_t elements () const { return m_n_elements - m_n_deleted; }
384 /* Return the current number of elements in this hash table. */
385 size_t elements_with_deleted () const { return m_n_elements; }
387 /* This function clears all entries in the given hash table. */
388 void empty ();
390 /* This function clears a specified SLOT in a hash table. It is
391 useful when you've already done the lookup and don't want to do it
392 again. */
393 void clear_slot (value_type *);
395 /* This function searches for a hash table entry equal to the given
396 COMPARABLE element starting with the given HASH value. It cannot
397 be used to insert or delete an element. */
398 value_type &find_with_hash (const compare_type &, hashval_t);
400 /* Like find_slot_with_hash, but compute the hash value from the element. */
401 value_type &find (const value_type &value)
403 return find_with_hash (value, Descriptor::hash (value));
406 value_type *find_slot (const value_type &value, insert_option insert)
408 return find_slot_with_hash (value, Descriptor::hash (value), insert);
411 /* This function searches for a hash table slot containing an entry
412 equal to the given COMPARABLE element and starting with the given
413 HASH. To delete an entry, call this with insert=NO_INSERT, then
414 call clear_slot on the slot returned (possibly after doing some
415 checks). To insert an entry, call this with insert=INSERT, then
416 write the value you want into the returned slot. When inserting an
417 entry, NULL may be returned if memory allocation fails. */
418 value_type *find_slot_with_hash (const compare_type &comparable,
419 hashval_t hash, enum insert_option insert);
421 /* This function deletes an element with the given COMPARABLE value
422 from hash table starting with the given HASH. If there is no
423 matching element in the hash table, this function does nothing. */
424 void remove_elt_with_hash (const compare_type &, hashval_t);
426 /* Like remove_elt_with_hash, but compute the hash value from the
427 element. */
428 void remove_elt (const value_type &value)
430 remove_elt_with_hash (value, Descriptor::hash (value));
433 /* This function scans over the entire hash table calling CALLBACK for
434 each live entry. If CALLBACK returns false, the iteration stops.
435 ARGUMENT is passed as CALLBACK's second argument. */
436 template <typename Argument,
437 int (*Callback) (value_type *slot, Argument argument)>
438 void traverse_noresize (Argument argument);
440 /* Like traverse_noresize, but does resize the table when it is too empty
441 to improve effectivity of subsequent calls. */
442 template <typename Argument,
443 int (*Callback) (value_type *slot, Argument argument)>
444 void traverse (Argument argument);
446 class iterator
448 public:
449 iterator () : m_slot (NULL), m_limit (NULL) {}
451 iterator (value_type *slot, value_type *limit) :
452 m_slot (slot), m_limit (limit) {}
454 inline value_type &operator * () { return *m_slot; }
455 void slide ();
456 inline iterator &operator ++ ();
457 bool operator != (const iterator &other) const
459 return m_slot != other.m_slot || m_limit != other.m_limit;
462 private:
463 value_type *m_slot;
464 value_type *m_limit;
467 iterator begin () const
469 iterator iter (m_entries, m_entries + m_size);
470 iter.slide ();
471 return iter;
474 iterator end () const { return iterator (); }
476 double collisions () const
478 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
481 private:
482 template<typename T> friend void gt_ggc_mx (hash_table<T> *);
483 template<typename T> friend void gt_pch_nx (hash_table<T> *);
484 template<typename T> friend void
485 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
486 template<typename T, typename U, typename V> friend void
487 gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
488 template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *,
489 gt_pointer_operator,
490 void *);
491 template<typename T> friend void gt_pch_nx (hash_table<T> *,
492 gt_pointer_operator, void *);
494 template<typename T> friend void gt_cleare_cache (hash_table<T> *);
496 value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
497 value_type *find_empty_slot_for_expand (hashval_t);
498 void expand ();
499 static bool is_deleted (value_type &v)
501 return Descriptor::is_deleted (v);
504 static bool is_empty (value_type &v)
506 return Descriptor::is_empty (v);
509 static void mark_deleted (value_type &v)
511 Descriptor::mark_deleted (v);
514 static void mark_empty (value_type &v)
516 Descriptor::mark_empty (v);
519 /* Table itself. */
520 typename Descriptor::value_type *m_entries;
522 size_t m_size;
524 /* Current number of elements including also deleted elements. */
525 size_t m_n_elements;
527 /* Current number of deleted elements in the table. */
528 size_t m_n_deleted;
530 /* The following member is used for debugging. Its value is number
531 of all calls of `htab_find_slot' for the hash table. */
532 unsigned int m_searches;
534 /* The following member is used for debugging. Its value is number
535 of collisions fixed for time of work with the hash table. */
536 unsigned int m_collisions;
538 /* Current size (in entries) of the hash table, as an index into the
539 table of primes. */
540 unsigned int m_size_prime_index;
542 /* if m_entries is stored in ggc memory. */
543 bool m_ggc;
545 /* If we should gather memory statistics for the table. */
546 bool m_gather_mem_stats;
549 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
550 mem-stats.h after hash_table declaration. */
552 #include "mem-stats.h"
553 #include "hash-map.h"
555 extern mem_alloc_description<mem_usage> hash_table_usage;
557 /* Support function for statistics. */
558 extern void dump_hash_table_loc_statistics (void);
560 template<typename Descriptor, template<typename Type> class Allocator>
561 hash_table<Descriptor, Allocator>::hash_table (size_t size, bool ggc, bool
562 gather_mem_stats,
563 mem_alloc_origin origin
564 MEM_STAT_DECL) :
565 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
566 m_ggc (ggc), m_gather_mem_stats (gather_mem_stats)
568 unsigned int size_prime_index;
570 size_prime_index = hash_table_higher_prime_index (size);
571 size = prime_tab[size_prime_index].prime;
573 if (m_gather_mem_stats)
574 hash_table_usage.register_descriptor (this, origin, ggc
575 FINAL_PASS_MEM_STAT);
577 m_entries = alloc_entries (size PASS_MEM_STAT);
578 m_size = size;
579 m_size_prime_index = size_prime_index;
582 template<typename Descriptor, template<typename Type> class Allocator>
583 hash_table<Descriptor, Allocator>::~hash_table ()
585 for (size_t i = m_size - 1; i < m_size; i--)
586 if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
587 Descriptor::remove (m_entries[i]);
589 if (!m_ggc)
590 Allocator <value_type> ::data_free (m_entries);
591 else
592 ggc_free (m_entries);
594 if (m_gather_mem_stats)
595 hash_table_usage.release_instance_overhead (this,
596 sizeof (value_type) * m_size,
597 true);
600 /* This function returns an array of empty hash table elements. */
602 template<typename Descriptor, template<typename Type> class Allocator>
603 inline typename hash_table<Descriptor, Allocator>::value_type *
604 hash_table<Descriptor, Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
606 value_type *nentries;
608 if (m_gather_mem_stats)
609 hash_table_usage.register_instance_overhead (sizeof (value_type) * n, this);
611 if (!m_ggc)
612 nentries = Allocator <value_type> ::data_alloc (n);
613 else
614 nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
616 gcc_assert (nentries != NULL);
617 for (size_t i = 0; i < n; i++)
618 mark_empty (nentries[i]);
620 return nentries;
623 /* Similar to find_slot, but without several unwanted side effects:
624 - Does not call equal when it finds an existing entry.
625 - Does not change the count of elements/searches/collisions in the
626 hash table.
627 This function also assumes there are no deleted entries in the table.
628 HASH is the hash value for the element to be inserted. */
630 template<typename Descriptor, template<typename Type> class Allocator>
631 typename hash_table<Descriptor, Allocator>::value_type *
632 hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
634 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
635 size_t size = m_size;
636 value_type *slot = m_entries + index;
637 hashval_t hash2;
639 if (is_empty (*slot))
640 return slot;
641 #ifdef ENABLE_CHECKING
642 gcc_checking_assert (!is_deleted (*slot));
643 #endif
645 hash2 = hash_table_mod2 (hash, m_size_prime_index);
646 for (;;)
648 index += hash2;
649 if (index >= size)
650 index -= size;
652 slot = m_entries + index;
653 if (is_empty (*slot))
654 return slot;
655 #ifdef ENABLE_CHECKING
656 gcc_checking_assert (!is_deleted (*slot));
657 #endif
661 /* The following function changes size of memory allocated for the
662 entries and repeatedly inserts the table elements. The occupancy
663 of the table after the call will be about 50%. Naturally the hash
664 table must already exist. Remember also that the place of the
665 table entries is changed. If memory allocation fails, this function
666 will abort. */
668 template<typename Descriptor, template<typename Type> class Allocator>
669 void
670 hash_table<Descriptor, Allocator>::expand ()
672 value_type *oentries = m_entries;
673 unsigned int oindex = m_size_prime_index;
674 size_t osize = size ();
675 value_type *olimit = oentries + osize;
676 size_t elts = elements ();
678 /* Resize only when table after removal of unused elements is either
679 too full or too empty. */
680 unsigned int nindex;
681 size_t nsize;
682 if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
684 nindex = hash_table_higher_prime_index (elts * 2);
685 nsize = prime_tab[nindex].prime;
687 else
689 nindex = oindex;
690 nsize = osize;
693 value_type *nentries = alloc_entries (nsize);
695 if (m_gather_mem_stats)
696 hash_table_usage.release_instance_overhead (this, sizeof (value_type)
697 * osize);
699 m_entries = nentries;
700 m_size = nsize;
701 m_size_prime_index = nindex;
702 m_n_elements -= m_n_deleted;
703 m_n_deleted = 0;
705 value_type *p = oentries;
708 value_type &x = *p;
710 if (!is_empty (x) && !is_deleted (x))
712 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
714 *q = x;
717 p++;
719 while (p < olimit);
721 if (!m_ggc)
722 Allocator <value_type> ::data_free (oentries);
723 else
724 ggc_free (oentries);
727 template<typename Descriptor, template<typename Type> class Allocator>
728 void
729 hash_table<Descriptor, Allocator>::empty ()
731 size_t size = m_size;
732 value_type *entries = m_entries;
733 int i;
735 for (i = size - 1; i >= 0; i--)
736 if (!is_empty (entries[i]) && !is_deleted (entries[i]))
737 Descriptor::remove (entries[i]);
739 /* Instead of clearing megabyte, downsize the table. */
740 if (size > 1024*1024 / sizeof (PTR))
742 int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
743 int nsize = prime_tab[nindex].prime;
745 if (!m_ggc)
746 Allocator <value_type> ::data_free (m_entries);
747 else
748 ggc_free (m_entries);
750 m_entries = alloc_entries (nsize);
751 m_size = nsize;
752 m_size_prime_index = nindex;
754 else
755 memset (entries, 0, size * sizeof (value_type));
756 m_n_deleted = 0;
757 m_n_elements = 0;
760 /* This function clears a specified SLOT in a hash table. It is
761 useful when you've already done the lookup and don't want to do it
762 again. */
764 template<typename Descriptor, template<typename Type> class Allocator>
765 void
766 hash_table<Descriptor, Allocator>::clear_slot (value_type *slot)
768 gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
769 || is_empty (*slot) || is_deleted (*slot)));
771 Descriptor::remove (*slot);
773 mark_deleted (*slot);
774 m_n_deleted++;
777 /* This function searches for a hash table entry equal to the given
778 COMPARABLE element starting with the given HASH value. It cannot
779 be used to insert or delete an element. */
781 template<typename Descriptor, template<typename Type> class Allocator>
782 typename hash_table<Descriptor, Allocator>::value_type &
783 hash_table<Descriptor, Allocator>
784 ::find_with_hash (const compare_type &comparable, hashval_t hash)
786 m_searches++;
787 size_t size = m_size;
788 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
790 value_type *entry = &m_entries[index];
791 if (is_empty (*entry)
792 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
793 return *entry;
795 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
796 for (;;)
798 m_collisions++;
799 index += hash2;
800 if (index >= size)
801 index -= size;
803 entry = &m_entries[index];
804 if (is_empty (*entry)
805 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
806 return *entry;
810 /* This function searches for a hash table slot containing an entry
811 equal to the given COMPARABLE element and starting with the given
812 HASH. To delete an entry, call this with insert=NO_INSERT, then
813 call clear_slot on the slot returned (possibly after doing some
814 checks). To insert an entry, call this with insert=INSERT, then
815 write the value you want into the returned slot. When inserting an
816 entry, NULL may be returned if memory allocation fails. */
818 template<typename Descriptor, template<typename Type> class Allocator>
819 typename hash_table<Descriptor, Allocator>::value_type *
820 hash_table<Descriptor, Allocator>
821 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
822 enum insert_option insert)
824 if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
825 expand ();
827 m_searches++;
829 value_type *first_deleted_slot = NULL;
830 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
831 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
832 value_type *entry = &m_entries[index];
833 size_t size = m_size;
834 if (is_empty (*entry))
835 goto empty_entry;
836 else if (is_deleted (*entry))
837 first_deleted_slot = &m_entries[index];
838 else if (Descriptor::equal (*entry, comparable))
839 return &m_entries[index];
841 for (;;)
843 m_collisions++;
844 index += hash2;
845 if (index >= size)
846 index -= size;
848 entry = &m_entries[index];
849 if (is_empty (*entry))
850 goto empty_entry;
851 else if (is_deleted (*entry))
853 if (!first_deleted_slot)
854 first_deleted_slot = &m_entries[index];
856 else if (Descriptor::equal (*entry, comparable))
857 return &m_entries[index];
860 empty_entry:
861 if (insert == NO_INSERT)
862 return NULL;
864 if (first_deleted_slot)
866 m_n_deleted--;
867 mark_empty (*first_deleted_slot);
868 return first_deleted_slot;
871 m_n_elements++;
872 return &m_entries[index];
875 /* This function deletes an element with the given COMPARABLE value
876 from hash table starting with the given HASH. If there is no
877 matching element in the hash table, this function does nothing. */
879 template<typename Descriptor, template<typename Type> class Allocator>
880 void
881 hash_table<Descriptor, Allocator>
882 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
884 value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
885 if (is_empty (*slot))
886 return;
888 Descriptor::remove (*slot);
890 mark_deleted (*slot);
891 m_n_deleted++;
894 /* This function scans over the entire hash table calling CALLBACK for
895 each live entry. If CALLBACK returns false, the iteration stops.
896 ARGUMENT is passed as CALLBACK's second argument. */
898 template<typename Descriptor,
899 template<typename Type> class Allocator>
900 template<typename Argument,
901 int (*Callback)
902 (typename hash_table<Descriptor, Allocator>::value_type *slot,
903 Argument argument)>
904 void
905 hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
907 value_type *slot = m_entries;
908 value_type *limit = slot + size ();
912 value_type &x = *slot;
914 if (!is_empty (x) && !is_deleted (x))
915 if (! Callback (slot, argument))
916 break;
918 while (++slot < limit);
921 /* Like traverse_noresize, but does resize the table when it is too empty
922 to improve effectivity of subsequent calls. */
924 template <typename Descriptor,
925 template <typename Type> class Allocator>
926 template <typename Argument,
927 int (*Callback)
928 (typename hash_table<Descriptor, Allocator>::value_type *slot,
929 Argument argument)>
930 void
931 hash_table<Descriptor, Allocator>::traverse (Argument argument)
933 size_t size = m_size;
934 if (elements () * 8 < size && size > 32)
935 expand ();
937 traverse_noresize <Argument, Callback> (argument);
940 /* Slide down the iterator slots until an active entry is found. */
942 template<typename Descriptor, template<typename Type> class Allocator>
943 void
944 hash_table<Descriptor, Allocator>::iterator::slide ()
946 for ( ; m_slot < m_limit; ++m_slot )
948 value_type &x = *m_slot;
949 if (!is_empty (x) && !is_deleted (x))
950 return;
952 m_slot = NULL;
953 m_limit = NULL;
956 /* Bump the iterator. */
958 template<typename Descriptor, template<typename Type> class Allocator>
959 inline typename hash_table<Descriptor, Allocator>::iterator &
960 hash_table<Descriptor, Allocator>::iterator::operator ++ ()
962 ++m_slot;
963 slide ();
964 return *this;
968 /* Iterate through the elements of hash_table HTAB,
969 using hash_table <....>::iterator ITER,
970 storing each element in RESULT, which is of type TYPE. */
972 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
973 for ((ITER) = (HTAB).begin (); \
974 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
975 ++(ITER))
977 /* ggc walking routines. */
979 template<typename E>
980 static inline void
981 gt_ggc_mx (hash_table<E> *h)
983 typedef hash_table<E> table;
985 if (!ggc_test_and_set_mark (h->m_entries))
986 return;
988 for (size_t i = 0; i < h->m_size; i++)
990 if (table::is_empty (h->m_entries[i])
991 || table::is_deleted (h->m_entries[i]))
992 continue;
994 E::ggc_mx (h->m_entries[i]);
998 template<typename D>
999 static inline void
1000 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1001 void *cookie)
1003 hash_table<D> *map = static_cast<hash_table<D> *> (h);
1004 gcc_checking_assert (map->m_entries == obj);
1005 for (size_t i = 0; i < map->m_size; i++)
1007 typedef hash_table<D> table;
1008 if (table::is_empty (map->m_entries[i])
1009 || table::is_deleted (map->m_entries[i]))
1010 continue;
1012 D::pch_nx (map->m_entries[i], op, cookie);
1016 template<typename D>
1017 static void
1018 gt_pch_nx (hash_table<D> *h)
1020 bool success
1021 = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1022 gcc_checking_assert (success);
1023 for (size_t i = 0; i < h->m_size; i++)
1025 if (hash_table<D>::is_empty (h->m_entries[i])
1026 || hash_table<D>::is_deleted (h->m_entries[i]))
1027 continue;
1029 D::pch_nx (h->m_entries[i]);
1033 template<typename D>
1034 static inline void
1035 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1037 op (&h->m_entries, cookie);
1040 template<typename H>
1041 inline void
1042 gt_cleare_cache (hash_table<H> *h)
1044 extern void gt_ggc_mx (typename H::value_type &t);
1045 typedef hash_table<H> table;
1046 if (!h)
1047 return;
1049 for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1050 if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1052 int res = H::keep_cache_entry (*iter);
1053 if (res == 0)
1054 h->clear_slot (&*iter);
1055 else if (res != -1)
1056 gt_ggc_mx (*iter);
1060 #endif /* TYPED_HASHTAB_H */