1 /* A type-safe hash table template.
2    Copyright (C) 2012-2018 Free Software Foundation, Inc.
3    Contributed by Lawrence Crowl <crowl@google.com>
4 
5 This file is part of GCC.
6 
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.
11 
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.
16 
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/>.  */
20 
21 
22 /* This file implements a typed hash table.
23    The implementation borrows from libiberty's htab_t in hashtab.h.
24 
25 
26    INTRODUCTION TO TYPES
27 
28    Users of the hash table generally need to be aware of three types.
29 
30       1. The type being placed into the hash table.  This type is called
31       the value type.
32 
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.
36 
37          - A typedef named 'value_type' to the value type (from above).
38 
39          - A static member function named 'hash' that takes a value_type
40          (or 'const value_type &') and returns a hashval_t value.
41 
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.
46 
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.
50 
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).
55 
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.
65 
66       3. The type of the hash table itself.  (More later.)
67 
68    In very special circumstances, users may need to know about a fourth type.
69 
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:
73 
74          - A static member function named 'data_alloc'.  This function
75          allocates the data elements in the table.
76 
77          - A static member function named 'data_free'.  This function
78          deallocates the data elements in the table.
79 
80    Hash table are instantiated with two type arguments.
81 
82       * The descriptor type, (2) above.
83 
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.
87 
88 
89    DEFINING A DESCRIPTOR TYPE
90 
91    The first task in using the hash table is to describe the element type.
92    We compose this into a few steps.
93 
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:
97 
98          * typed_free_remove implements the static 'remove' member function
99          by calling free().
100 
101          * typed_noop_remove implements the static 'remove' member function
102          by doing nothing.
103 
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.
108 
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.
115 
116          You can use these policies by simply deriving the descriptor type
117          from one of those class template, with the appropriate argument.
118 
119          Otherwise, you need to write the static 'remove' member function
120          in the descriptor class.
121 
122       2. Choose a hash function.  Write the static 'hash' member function.
123 
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.
127 
128       4. Choose an equality testing function 'equal' that compares a value_type
129 	 and a compare_type.
130 
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.
134 
135    AN EXAMPLE DESCRIPTOR TYPE
136 
137    Suppose you want to put some_type into the hash table.  You could define
138    the descriptor type as follows.
139 
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.
143       {
144         static inline hashval_t hash (const value_type *);
145         static inline bool equal (const value_type *, const compare_type *);
146       };
147 
148       inline hashval_t
149       some_type_hasher::hash (const value_type *e)
150       { ... compute and return a hash value for E ... }
151 
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' ... }
155 
156 
157    AN EXAMPLE HASH_TABLE DECLARATION
158 
159    To instantiate a hash table for some_type:
160 
161       hash_table <some_type_hasher> some_type_hash_table;
162 
163    There is no need to mention some_type directly, as the hash table will
164    obtain it using some_type_hasher::value_type.
165 
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.
169 
170 
171    EASY DESCRIPTORS FOR POINTERS
172 
173    There are four descriptors for pointer elements, one for each of
174    the removal policies above:
175 
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)
180 
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:
184 
185       hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
186 
187 
188    HASH TABLE ITERATORS
189 
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:
192 
193       extern void consume (some_info *);
194 
195    We define a convenience typedef and the hash table:
196 
197       typedef hash_table <some_info_hasher> info_table_type;
198       info_table_type info_table;
199 
200    Then we write the loop in typical C++ style:
201 
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);
207 
208    Or with common sub-expression elimination:
209 
210       for (info_table_type::iterator iter = info_table.begin ();
211            iter != info_table.end ();
212            ++iter)
213         {
214           some_info &elem = *iter;
215           if (elem.status == INFO_READY)
216             consume (&elem);
217         }
218 
219    One can also use a more typical GCC style:
220 
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);
227 
228 */
229 
230 
231 #ifndef TYPED_HASHTAB_H
232 #define TYPED_HASHTAB_H
233 
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"
242 
243 template<typename, typename, typename> class hash_map;
244 template<typename, typename> class hash_set;
245 
246 /* The ordinary memory allocator.  */
247 /* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
248 
249 template <typename Type>
250 struct xcallocator
251 {
252   static Type *data_alloc (size_t count);
253   static void data_free (Type *memory);
254 };
255 
256 
257 /* Allocate memory for COUNT data blocks.  */
258 
259 template <typename Type>
260 inline Type *
data_alloc(size_t count)261 xcallocator <Type>::data_alloc (size_t count)
262 {
263   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
264 }
265 
266 
267 /* Free memory for data blocks.  */
268 
269 template <typename Type>
270 inline void
data_free(Type * memory)271 xcallocator <Type>::data_free (Type *memory)
272 {
273   return ::free (memory);
274 }
275 
276 
277 /* Table of primes and their inversion information.  */
278 
279 struct prime_ent
280 {
281   hashval_t prime;
282   hashval_t inv;
283   hashval_t inv_m2;     /* inverse of prime-2 */
284   hashval_t shift;
285 };
286 
287 extern struct prime_ent const prime_tab[];
288 
289 
290 /* Functions for computing hash table indexes.  */
291 
292 extern unsigned int hash_table_higher_prime_index (unsigned long n)
293    ATTRIBUTE_PURE;
294 
295 /* Return X % Y using multiplicative inverse values INV and SHIFT.
296 
297    The multiplicative inverses computed above are for 32-bit types,
298    and requires that we be able to compute a highpart multiply.
299 
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.  */
305 
306 inline hashval_t
mul_mod(hashval_t x,hashval_t y,hashval_t inv,int shift)307 mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
308 {
309    hashval_t t1, t2, t3, t4, q, r;
310 
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);
317 
318    return r;
319 }
320 
321 /* Compute the primary table index for HASH given current prime index.  */
322 
323 inline hashval_t
hash_table_mod1(hashval_t hash,unsigned int index)324 hash_table_mod1 (hashval_t hash, unsigned int index)
325 {
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);
329 }
330 
331 /* Compute the secondary table index for HASH given current prime index.  */
332 
333 inline hashval_t
hash_table_mod2(hashval_t hash,unsigned int index)334 hash_table_mod2 (hashval_t hash, unsigned int index)
335 {
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);
339 }
340 
341 class mem_usage;
342 
343 /* User-facing hash table type.
344 
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.
348 
349    Specify the template Allocator to allocate and free memory.
350      The default is xcallocator.
351 
352      Storage is an implementation detail and should not be used outside the
353      hash table code.
354 
355 */
356 template <typename Descriptor,
357 	 template<typename Type> class Allocator = xcallocator>
358 class hash_table
359 {
360   typedef typename Descriptor::value_type value_type;
361   typedef typename Descriptor::compare_type compare_type;
362 
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 ();
373 
374   /* Create a hash_table in gc memory.  */
375   static hash_table *
create_ggc(size_t n CXX_MEM_STAT_INFO)376   create_ggc (size_t n CXX_MEM_STAT_INFO)
377   {
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;
382   }
383 
384   /* Current size (in entries) of the hash table.  */
size()385   size_t size () const { return m_size; }
386 
387   /* Return the current number of elements in this hash table. */
elements()388   size_t elements () const { return m_n_elements - m_n_deleted; }
389 
390   /* Return the current number of elements in this hash table. */
elements_with_deleted()391   size_t elements_with_deleted () const { return m_n_elements; }
392 
393   /* This function clears all entries in this hash table.  */
empty()394   void empty () { if (elements ()) empty_slow (); }
395 
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 *);
400 
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);
405 
406   /* Like find_slot_with_hash, but compute the hash value from the element.  */
find(const value_type & value)407   value_type &find (const value_type &value)
408     {
409       return find_with_hash (value, Descriptor::hash (value));
410     }
411 
find_slot(const value_type & value,insert_option insert)412   value_type *find_slot (const value_type &value, insert_option insert)
413     {
414       return find_slot_with_hash (value, Descriptor::hash (value), insert);
415     }
416 
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);
426 
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);
431 
432   /* Like remove_elt_with_hash, but compute the hash value from the
433      element.  */
remove_elt(const value_type & value)434   void remove_elt (const value_type &value)
435     {
436       remove_elt_with_hash (value, Descriptor::hash (value));
437     }
438 
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);
445 
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);
451 
452   class iterator
453   {
454   public:
iterator()455     iterator () : m_slot (NULL), m_limit (NULL) {}
456 
iterator(value_type * slot,value_type * limit)457     iterator (value_type *slot, value_type *limit) :
458       m_slot (slot), m_limit (limit) {}
459 
460     inline value_type &operator * () { return *m_slot; }
461     void slide ();
462     inline iterator &operator ++ ();
463     bool operator != (const iterator &other) const
464       {
465 	return m_slot != other.m_slot || m_limit != other.m_limit;
466       }
467 
468   private:
469     value_type *m_slot;
470     value_type *m_limit;
471   };
472 
begin()473   iterator begin () const
474     {
475       iterator iter (m_entries, m_entries + m_size);
476       iter.slide ();
477       return iter;
478     }
479 
end()480   iterator end () const { return iterator (); }
481 
collisions()482   double collisions () const
483     {
484       return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
485     }
486 
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 *);
499 
500   template<typename T> friend void gt_cleare_cache (hash_table<T> *);
501 
502   void empty_slow ();
503 
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 ();
is_deleted(value_type & v)508   static bool is_deleted (value_type &v)
509   {
510     return Descriptor::is_deleted (v);
511   }
512 
is_empty(value_type & v)513   static bool is_empty (value_type &v)
514   {
515     return Descriptor::is_empty (v);
516   }
517 
mark_deleted(value_type & v)518   static void mark_deleted (value_type &v)
519   {
520     Descriptor::mark_deleted (v);
521   }
522 
mark_empty(value_type & v)523   static void mark_empty (value_type &v)
524   {
525     Descriptor::mark_empty (v);
526   }
527 
528   /* Table itself.  */
529   typename Descriptor::value_type *m_entries;
530 
531   size_t m_size;
532 
533   /* Current number of elements including also deleted elements.  */
534   size_t m_n_elements;
535 
536   /* Current number of deleted elements in the table.  */
537   size_t m_n_deleted;
538 
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;
542 
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;
546 
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;
550 
551   /* if m_entries is stored in ggc memory.  */
552   bool m_ggc;
553 
554   /* If we should gather memory statistics for the table.  */
555   bool m_gather_mem_stats;
556 };
557 
558 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
559    mem-stats.h after hash_table declaration.  */
560 
561 #include "mem-stats.h"
562 #include "hash-map.h"
563 
564 extern mem_alloc_description<mem_usage> hash_table_usage;
565 
566 /* Support function for statistics.  */
567 extern void dump_hash_table_loc_statistics (void);
568 
569 template<typename Descriptor, template<typename Type> class Allocator>
hash_table(size_t size,bool ggc,bool gather_mem_stats,mem_alloc_origin origin MEM_STAT_DECL)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)
576 {
577   unsigned int size_prime_index;
578 
579   size_prime_index = hash_table_higher_prime_index (size);
580   size = prime_tab[size_prime_index].prime;
581 
582   if (m_gather_mem_stats)
583     hash_table_usage.register_descriptor (this, origin, ggc
584 					  FINAL_PASS_MEM_STAT);
585 
586   m_entries = alloc_entries (size PASS_MEM_STAT);
587   m_size = size;
588   m_size_prime_index = size_prime_index;
589 }
590 
591 template<typename Descriptor, template<typename Type> class Allocator>
hash_table(const hash_table & h,bool ggc,bool gather_mem_stats,mem_alloc_origin origin MEM_STAT_DECL)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)
599 {
600   size_t size = h.m_size;
601 
602   if (m_gather_mem_stats)
603     hash_table_usage.register_descriptor (this, origin, ggc
604 					  FINAL_PASS_MEM_STAT);
605 
606   value_type *nentries = alloc_entries (size PASS_MEM_STAT);
607   for (size_t i = 0; i < size; ++i)
608     {
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;
614     }
615   m_entries = nentries;
616   m_size = size;
617   m_size_prime_index = h.m_size_prime_index;
618 }
619 
620 template<typename Descriptor, template<typename Type> class Allocator>
~hash_table()621 hash_table<Descriptor, Allocator>::~hash_table ()
622 {
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]);
626 
627   if (!m_ggc)
628     Allocator <value_type> ::data_free (m_entries);
629   else
630     ggc_free (m_entries);
631 
632   if (m_gather_mem_stats)
633     hash_table_usage.release_instance_overhead (this,
634 						sizeof (value_type) * m_size,
635 						true);
636 }
637 
638 /* This function returns an array of empty hash table elements.  */
639 
640 template<typename Descriptor, template<typename Type> class Allocator>
641 inline typename hash_table<Descriptor, Allocator>::value_type *
alloc_entries(size_t n MEM_STAT_DECL)642 hash_table<Descriptor, Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
643 {
644   value_type *nentries;
645 
646   if (m_gather_mem_stats)
647     hash_table_usage.register_instance_overhead (sizeof (value_type) * n, this);
648 
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);
653 
654   gcc_assert (nentries != NULL);
655   for (size_t i = 0; i < n; i++)
656     mark_empty (nentries[i]);
657 
658   return nentries;
659 }
660 
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.  */
667 
668 template<typename Descriptor, template<typename Type> class Allocator>
669 typename hash_table<Descriptor, Allocator>::value_type *
find_empty_slot_for_expand(hashval_t hash)670 hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
671 {
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;
676 
677   if (is_empty (*slot))
678     return slot;
679   gcc_checking_assert (!is_deleted (*slot));
680 
681   hash2 = hash_table_mod2 (hash, m_size_prime_index);
682   for (;;)
683     {
684       index += hash2;
685       if (index >= size)
686         index -= size;
687 
688       slot = m_entries + index;
689       if (is_empty (*slot))
690         return slot;
691       gcc_checking_assert (!is_deleted (*slot));
692     }
693 }
694 
695 /* Return true if the current table is excessively big for ELTS elements.  */
696 
697 template<typename Descriptor, template<typename Type> class Allocator>
698 inline bool
too_empty_p(unsigned int elts)699 hash_table<Descriptor, Allocator>::too_empty_p (unsigned int elts)
700 {
701   return elts * 8 < m_size && m_size > 32;
702 }
703 
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.  */
710 
711 template<typename Descriptor, template<typename Type> class Allocator>
712 void
expand()713 hash_table<Descriptor, Allocator>::expand ()
714 {
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 ();
720 
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))
726     {
727       nindex = hash_table_higher_prime_index (elts * 2);
728       nsize = prime_tab[nindex].prime;
729     }
730   else
731     {
732       nindex = oindex;
733       nsize = osize;
734     }
735 
736   value_type *nentries = alloc_entries (nsize);
737 
738   if (m_gather_mem_stats)
739     hash_table_usage.release_instance_overhead (this, sizeof (value_type)
740 						    * osize);
741 
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;
747 
748   value_type *p = oentries;
749   do
750     {
751       value_type &x = *p;
752 
753       if (!is_empty (x) && !is_deleted (x))
754         {
755           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
756 
757           *q = x;
758         }
759 
760       p++;
761     }
762   while (p < olimit);
763 
764   if (!m_ggc)
765     Allocator <value_type> ::data_free (oentries);
766   else
767     ggc_free (oentries);
768 }
769 
770 /* Implements empty() in cases where it isn't a no-op.  */
771 
772 template<typename Descriptor, template<typename Type> class Allocator>
773 void
empty_slow()774 hash_table<Descriptor, Allocator>::empty_slow ()
775 {
776   size_t size = m_size;
777   size_t nsize = size;
778   value_type *entries = m_entries;
779   int i;
780 
781   for (i = size - 1; i >= 0; i--)
782     if (!is_empty (entries[i]) && !is_deleted (entries[i]))
783       Descriptor::remove (entries[i]);
784 
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;
790 
791   if (nsize != size)
792     {
793       int nindex = hash_table_higher_prime_index (nsize);
794       int nsize = prime_tab[nindex].prime;
795 
796       if (!m_ggc)
797 	Allocator <value_type> ::data_free (m_entries);
798       else
799 	ggc_free (m_entries);
800 
801       m_entries = alloc_entries (nsize);
802       m_size = nsize;
803       m_size_prime_index = nindex;
804     }
805   else
806     {
807 #ifndef BROKEN_VALUE_INITIALIZATION
808       for ( ; size; ++entries, --size)
809 	*entries = value_type ();
810 #else
811       memset (entries, 0, size * sizeof (value_type));
812 #endif
813     }
814   m_n_deleted = 0;
815   m_n_elements = 0;
816 }
817 
818 /* This function clears a specified SLOT in a hash table.  It is
819    useful when you've already done the lookup and don't want to do it
820    again. */
821 
822 template<typename Descriptor, template<typename Type> class Allocator>
823 void
clear_slot(value_type * slot)824 hash_table<Descriptor, Allocator>::clear_slot (value_type *slot)
825 {
826   gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
827 		         || is_empty (*slot) || is_deleted (*slot)));
828 
829   Descriptor::remove (*slot);
830 
831   mark_deleted (*slot);
832   m_n_deleted++;
833 }
834 
835 /* This function searches for a hash table entry equal to the given
836    COMPARABLE element starting with the given HASH value.  It cannot
837    be used to insert or delete an element. */
838 
839 template<typename Descriptor, template<typename Type> class Allocator>
840 typename hash_table<Descriptor, Allocator>::value_type &
841 hash_table<Descriptor, Allocator>
find_with_hash(const compare_type & comparable,hashval_t hash)842 ::find_with_hash (const compare_type &comparable, hashval_t hash)
843 {
844   m_searches++;
845   size_t size = m_size;
846   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
847 
848   value_type *entry = &m_entries[index];
849   if (is_empty (*entry)
850       || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
851     return *entry;
852 
853   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
854   for (;;)
855     {
856       m_collisions++;
857       index += hash2;
858       if (index >= size)
859         index -= size;
860 
861       entry = &m_entries[index];
862       if (is_empty (*entry)
863           || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
864         return *entry;
865     }
866 }
867 
868 /* This function searches for a hash table slot containing an entry
869    equal to the given COMPARABLE element and starting with the given
870    HASH.  To delete an entry, call this with insert=NO_INSERT, then
871    call clear_slot on the slot returned (possibly after doing some
872    checks).  To insert an entry, call this with insert=INSERT, then
873    write the value you want into the returned slot.  When inserting an
874    entry, NULL may be returned if memory allocation fails. */
875 
876 template<typename Descriptor, template<typename Type> class Allocator>
877 typename hash_table<Descriptor, Allocator>::value_type *
878 hash_table<Descriptor, Allocator>
find_slot_with_hash(const compare_type & comparable,hashval_t hash,enum insert_option insert)879 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
880 		       enum insert_option insert)
881 {
882   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
883     expand ();
884 
885   m_searches++;
886 
887   value_type *first_deleted_slot = NULL;
888   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
889   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
890   value_type *entry = &m_entries[index];
891   size_t size = m_size;
892   if (is_empty (*entry))
893     goto empty_entry;
894   else if (is_deleted (*entry))
895     first_deleted_slot = &m_entries[index];
896   else if (Descriptor::equal (*entry, comparable))
897     return &m_entries[index];
898 
899   for (;;)
900     {
901       m_collisions++;
902       index += hash2;
903       if (index >= size)
904 	index -= size;
905 
906       entry = &m_entries[index];
907       if (is_empty (*entry))
908 	goto empty_entry;
909       else if (is_deleted (*entry))
910 	{
911 	  if (!first_deleted_slot)
912 	    first_deleted_slot = &m_entries[index];
913 	}
914       else if (Descriptor::equal (*entry, comparable))
915 	return &m_entries[index];
916     }
917 
918  empty_entry:
919   if (insert == NO_INSERT)
920     return NULL;
921 
922   if (first_deleted_slot)
923     {
924       m_n_deleted--;
925       mark_empty (*first_deleted_slot);
926       return first_deleted_slot;
927     }
928 
929   m_n_elements++;
930   return &m_entries[index];
931 }
932 
933 /* This function deletes an element with the given COMPARABLE value
934    from hash table starting with the given HASH.  If there is no
935    matching element in the hash table, this function does nothing. */
936 
937 template<typename Descriptor, template<typename Type> class Allocator>
938 void
939 hash_table<Descriptor, Allocator>
remove_elt_with_hash(const compare_type & comparable,hashval_t hash)940 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
941 {
942   value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
943   if (is_empty (*slot))
944     return;
945 
946   Descriptor::remove (*slot);
947 
948   mark_deleted (*slot);
949   m_n_deleted++;
950 }
951 
952 /* This function scans over the entire hash table calling CALLBACK for
953    each live entry.  If CALLBACK returns false, the iteration stops.
954    ARGUMENT is passed as CALLBACK's second argument. */
955 
956 template<typename Descriptor,
957 	  template<typename Type> class Allocator>
958 template<typename Argument,
959 	  int (*Callback)
960      (typename hash_table<Descriptor, Allocator>::value_type *slot,
961       Argument argument)>
962 void
traverse_noresize(Argument argument)963 hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
964 {
965   value_type *slot = m_entries;
966   value_type *limit = slot + size ();
967 
968   do
969     {
970       value_type &x = *slot;
971 
972       if (!is_empty (x) && !is_deleted (x))
973         if (! Callback (slot, argument))
974           break;
975     }
976   while (++slot < limit);
977 }
978 
979 /* Like traverse_noresize, but does resize the table when it is too empty
980    to improve effectivity of subsequent calls.  */
981 
982 template <typename Descriptor,
983 	  template <typename Type> class Allocator>
984 template <typename Argument,
985 	  int (*Callback)
986      (typename hash_table<Descriptor, Allocator>::value_type *slot,
987       Argument argument)>
988 void
traverse(Argument argument)989 hash_table<Descriptor, Allocator>::traverse (Argument argument)
990 {
991   if (too_empty_p (elements ()))
992     expand ();
993 
994   traverse_noresize <Argument, Callback> (argument);
995 }
996 
997 /* Slide down the iterator slots until an active entry is found.  */
998 
999 template<typename Descriptor, template<typename Type> class Allocator>
1000 void
slide()1001 hash_table<Descriptor, Allocator>::iterator::slide ()
1002 {
1003   for ( ; m_slot < m_limit; ++m_slot )
1004     {
1005       value_type &x = *m_slot;
1006       if (!is_empty (x) && !is_deleted (x))
1007         return;
1008     }
1009   m_slot = NULL;
1010   m_limit = NULL;
1011 }
1012 
1013 /* Bump the iterator.  */
1014 
1015 template<typename Descriptor, template<typename Type> class Allocator>
1016 inline typename hash_table<Descriptor, Allocator>::iterator &
1017 hash_table<Descriptor, Allocator>::iterator::operator ++ ()
1018 {
1019   ++m_slot;
1020   slide ();
1021   return *this;
1022 }
1023 
1024 
1025 /* Iterate through the elements of hash_table HTAB,
1026    using hash_table <....>::iterator ITER,
1027    storing each element in RESULT, which is of type TYPE.  */
1028 
1029 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1030   for ((ITER) = (HTAB).begin (); \
1031        (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1032        ++(ITER))
1033 
1034 /* ggc walking routines.  */
1035 
1036 template<typename E>
1037 static inline void
gt_ggc_mx(hash_table<E> * h)1038 gt_ggc_mx (hash_table<E> *h)
1039 {
1040   typedef hash_table<E> table;
1041 
1042   if (!ggc_test_and_set_mark (h->m_entries))
1043     return;
1044 
1045   for (size_t i = 0; i < h->m_size; i++)
1046     {
1047       if (table::is_empty (h->m_entries[i])
1048 	  || table::is_deleted (h->m_entries[i]))
1049 	continue;
1050 
1051       /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1052 	 mark in gt_cleare_cache if appropriate.  */
1053       E::ggc_maybe_mx (h->m_entries[i]);
1054     }
1055 }
1056 
1057 template<typename D>
1058 static inline void
hashtab_entry_note_pointers(void * obj,void * h,gt_pointer_operator op,void * cookie)1059 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1060 			     void *cookie)
1061 {
1062   hash_table<D> *map = static_cast<hash_table<D> *> (h);
1063   gcc_checking_assert (map->m_entries == obj);
1064   for (size_t i = 0; i < map->m_size; i++)
1065     {
1066       typedef hash_table<D> table;
1067       if (table::is_empty (map->m_entries[i])
1068 	  || table::is_deleted (map->m_entries[i]))
1069 	continue;
1070 
1071       D::pch_nx (map->m_entries[i], op, cookie);
1072     }
1073 }
1074 
1075 template<typename D>
1076 static void
gt_pch_nx(hash_table<D> * h)1077 gt_pch_nx (hash_table<D> *h)
1078 {
1079   bool success
1080     = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1081   gcc_checking_assert (success);
1082   for (size_t i = 0; i < h->m_size; i++)
1083     {
1084       if (hash_table<D>::is_empty (h->m_entries[i])
1085 	  || hash_table<D>::is_deleted (h->m_entries[i]))
1086 	continue;
1087 
1088       D::pch_nx (h->m_entries[i]);
1089     }
1090 }
1091 
1092 template<typename D>
1093 static inline void
gt_pch_nx(hash_table<D> * h,gt_pointer_operator op,void * cookie)1094 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1095 {
1096   op (&h->m_entries, cookie);
1097 }
1098 
1099 template<typename H>
1100 inline void
gt_cleare_cache(hash_table<H> * h)1101 gt_cleare_cache (hash_table<H> *h)
1102 {
1103   typedef hash_table<H> table;
1104   if (!h)
1105     return;
1106 
1107   for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1108     if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1109       {
1110 	int res = H::keep_cache_entry (*iter);
1111 	if (res == 0)
1112 	  h->clear_slot (&*iter);
1113 	else if (res != -1)
1114 	  H::ggc_mx (*iter);
1115       }
1116 }
1117 
1118 #endif /* TYPED_HASHTAB_H */
1119