1 /* A type-safe hash table template.
2 Copyright (C) 2012-2019 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 If a hash table is used only in some rare cases, it is possible
171 to construct the hash_table lazily before first use. This is done
172 through:
173
174 hash_table <some_type_hasher, true> some_type_hash_table;
175
176 which will cause whatever methods actually need the allocated entries
177 array to allocate it later.
178
179
180 EASY DESCRIPTORS FOR POINTERS
181
182 There are four descriptors for pointer elements, one for each of
183 the removal policies above:
184
185 * nofree_ptr_hash (based on typed_noop_remove)
186 * free_ptr_hash (based on typed_free_remove)
187 * ggc_ptr_hash (based on ggc_remove)
188 * ggc_cache_ptr_hash (based on ggc_cache_remove)
189
190 These descriptors hash and compare elements by their pointer value,
191 rather than what they point to. So, to instantiate a hash table over
192 pointers to whatever_type, without freeing the whatever_types, use:
193
194 hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
195
196
197 HASH TABLE ITERATORS
198
199 The hash table provides standard C++ iterators. For example, consider a
200 hash table of some_info. We wish to consume each element of the table:
201
202 extern void consume (some_info *);
203
204 We define a convenience typedef and the hash table:
205
206 typedef hash_table <some_info_hasher> info_table_type;
207 info_table_type info_table;
208
209 Then we write the loop in typical C++ style:
210
211 for (info_table_type::iterator iter = info_table.begin ();
212 iter != info_table.end ();
213 ++iter)
214 if ((*iter).status == INFO_READY)
215 consume (&*iter);
216
217 Or with common sub-expression elimination:
218
219 for (info_table_type::iterator iter = info_table.begin ();
220 iter != info_table.end ();
221 ++iter)
222 {
223 some_info &elem = *iter;
224 if (elem.status == INFO_READY)
225 consume (&elem);
226 }
227
228 One can also use a more typical GCC style:
229
230 typedef some_info *some_info_p;
231 some_info *elem_ptr;
232 info_table_type::iterator iter;
233 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
234 if (elem_ptr->status == INFO_READY)
235 consume (elem_ptr);
236
237 */
238
239
240 #ifndef TYPED_HASHTAB_H
241 #define TYPED_HASHTAB_H
242
243 #include "statistics.h"
244 #include "ggc.h"
245 #include "vec.h"
246 #include "hashtab.h"
247 #include "inchash.h"
248 #include "mem-stats-traits.h"
249 #include "hash-traits.h"
250 #include "hash-map-traits.h"
251
252 template<typename, typename, typename> class hash_map;
253 template<typename, bool, typename> class hash_set;
254
255 /* The ordinary memory allocator. */
256 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
257
258 template <typename Type>
259 struct xcallocator
260 {
261 static Type *data_alloc (size_t count);
262 static void data_free (Type *memory);
263 };
264
265
266 /* Allocate memory for COUNT data blocks. */
267
268 template <typename Type>
269 inline Type *
data_alloc(size_t count)270 xcallocator <Type>::data_alloc (size_t count)
271 {
272 return static_cast <Type *> (xcalloc (count, sizeof (Type)));
273 }
274
275
276 /* Free memory for data blocks. */
277
278 template <typename Type>
279 inline void
data_free(Type * memory)280 xcallocator <Type>::data_free (Type *memory)
281 {
282 return ::free (memory);
283 }
284
285
286 /* Table of primes and their inversion information. */
287
288 struct prime_ent
289 {
290 hashval_t prime;
291 hashval_t inv;
292 hashval_t inv_m2; /* inverse of prime-2 */
293 hashval_t shift;
294 };
295
296 extern struct prime_ent const prime_tab[];
297
298
299 /* Functions for computing hash table indexes. */
300
301 extern unsigned int hash_table_higher_prime_index (unsigned long n)
302 ATTRIBUTE_PURE;
303
304 /* Return X % Y using multiplicative inverse values INV and SHIFT.
305
306 The multiplicative inverses computed above are for 32-bit types,
307 and requires that we be able to compute a highpart multiply.
308
309 FIX: I am not at all convinced that
310 3 loads, 2 multiplications, 3 shifts, and 3 additions
311 will be faster than
312 1 load and 1 modulus
313 on modern systems running a compiler. */
314
315 inline hashval_t
mul_mod(hashval_t x,hashval_t y,hashval_t inv,int shift)316 mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
317 {
318 hashval_t t1, t2, t3, t4, q, r;
319
320 t1 = ((uint64_t)x * inv) >> 32;
321 t2 = x - t1;
322 t3 = t2 >> 1;
323 t4 = t1 + t3;
324 q = t4 >> shift;
325 r = x - (q * y);
326
327 return r;
328 }
329
330 /* Compute the primary table index for HASH given current prime index. */
331
332 inline hashval_t
hash_table_mod1(hashval_t hash,unsigned int index)333 hash_table_mod1 (hashval_t hash, unsigned int index)
334 {
335 const struct prime_ent *p = &prime_tab[index];
336 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
337 return mul_mod (hash, p->prime, p->inv, p->shift);
338 }
339
340 /* Compute the secondary table index for HASH given current prime index. */
341
342 inline hashval_t
hash_table_mod2(hashval_t hash,unsigned int index)343 hash_table_mod2 (hashval_t hash, unsigned int index)
344 {
345 const struct prime_ent *p = &prime_tab[index];
346 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
347 return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
348 }
349
350 class mem_usage;
351
352 /* User-facing hash table type.
353
354 The table stores elements of type Descriptor::value_type and uses
355 the static descriptor functions described at the top of the file
356 to hash, compare and remove elements.
357
358 Specify the template Allocator to allocate and free memory.
359 The default is xcallocator.
360
361 Storage is an implementation detail and should not be used outside the
362 hash table code.
363
364 */
365 template <typename Descriptor, bool Lazy = false,
366 template<typename Type> class Allocator = xcallocator>
367 class hash_table
368 {
369 typedef typename Descriptor::value_type value_type;
370 typedef typename Descriptor::compare_type compare_type;
371
372 public:
373 explicit hash_table (size_t, bool ggc = false,
374 bool gather_mem_stats = GATHER_STATISTICS,
375 mem_alloc_origin origin = HASH_TABLE_ORIGIN
376 CXX_MEM_STAT_INFO);
377 explicit hash_table (const hash_table &, bool ggc = false,
378 bool gather_mem_stats = GATHER_STATISTICS,
379 mem_alloc_origin origin = HASH_TABLE_ORIGIN
380 CXX_MEM_STAT_INFO);
381 ~hash_table ();
382
383 /* Create a hash_table in gc memory. */
384 static hash_table *
create_ggc(size_t n CXX_MEM_STAT_INFO)385 create_ggc (size_t n CXX_MEM_STAT_INFO)
386 {
387 hash_table *table = ggc_alloc<hash_table> ();
388 new (table) hash_table (n, true, GATHER_STATISTICS,
389 HASH_TABLE_ORIGIN PASS_MEM_STAT);
390 return table;
391 }
392
393 /* Current size (in entries) of the hash table. */
size()394 size_t size () const { return m_size; }
395
396 /* Return the current number of elements in this hash table. */
elements()397 size_t elements () const { return m_n_elements - m_n_deleted; }
398
399 /* Return the current number of elements in this hash table. */
elements_with_deleted()400 size_t elements_with_deleted () const { return m_n_elements; }
401
402 /* This function clears all entries in this hash table. */
empty()403 void empty () { if (elements ()) empty_slow (); }
404
405 /* This function clears a specified SLOT in a hash table. It is
406 useful when you've already done the lookup and don't want to do it
407 again. */
408 void clear_slot (value_type *);
409
410 /* This function searches for a hash table entry equal to the given
411 COMPARABLE element starting with the given HASH value. It cannot
412 be used to insert or delete an element. */
413 value_type &find_with_hash (const compare_type &, hashval_t);
414
415 /* Like find_slot_with_hash, but compute the hash value from the element. */
find(const value_type & value)416 value_type &find (const value_type &value)
417 {
418 return find_with_hash (value, Descriptor::hash (value));
419 }
420
find_slot(const value_type & value,insert_option insert)421 value_type *find_slot (const value_type &value, insert_option insert)
422 {
423 return find_slot_with_hash (value, Descriptor::hash (value), insert);
424 }
425
426 /* This function searches for a hash table slot containing an entry
427 equal to the given COMPARABLE element and starting with the given
428 HASH. To delete an entry, call this with insert=NO_INSERT, then
429 call clear_slot on the slot returned (possibly after doing some
430 checks). To insert an entry, call this with insert=INSERT, then
431 write the value you want into the returned slot. When inserting an
432 entry, NULL may be returned if memory allocation fails. */
433 value_type *find_slot_with_hash (const compare_type &comparable,
434 hashval_t hash, enum insert_option insert);
435
436 /* This function deletes an element with the given COMPARABLE value
437 from hash table starting with the given HASH. If there is no
438 matching element in the hash table, this function does nothing. */
439 void remove_elt_with_hash (const compare_type &, hashval_t);
440
441 /* Like remove_elt_with_hash, but compute the hash value from the
442 element. */
remove_elt(const value_type & value)443 void remove_elt (const value_type &value)
444 {
445 remove_elt_with_hash (value, Descriptor::hash (value));
446 }
447
448 /* This function scans over the entire hash table calling CALLBACK for
449 each live entry. If CALLBACK returns false, the iteration stops.
450 ARGUMENT is passed as CALLBACK's second argument. */
451 template <typename Argument,
452 int (*Callback) (value_type *slot, Argument argument)>
453 void traverse_noresize (Argument argument);
454
455 /* Like traverse_noresize, but does resize the table when it is too empty
456 to improve effectivity of subsequent calls. */
457 template <typename Argument,
458 int (*Callback) (value_type *slot, Argument argument)>
459 void traverse (Argument argument);
460
461 class iterator
462 {
463 public:
iterator()464 iterator () : m_slot (NULL), m_limit (NULL) {}
465
iterator(value_type * slot,value_type * limit)466 iterator (value_type *slot, value_type *limit) :
467 m_slot (slot), m_limit (limit) {}
468
469 inline value_type &operator * () { return *m_slot; }
470 void slide ();
471 inline iterator &operator ++ ();
472 bool operator != (const iterator &other) const
473 {
474 return m_slot != other.m_slot || m_limit != other.m_limit;
475 }
476
477 private:
478 value_type *m_slot;
479 value_type *m_limit;
480 };
481
begin()482 iterator begin () const
483 {
484 if (Lazy && m_entries == NULL)
485 return iterator ();
486 iterator iter (m_entries, m_entries + m_size);
487 iter.slide ();
488 return iter;
489 }
490
end()491 iterator end () const { return iterator (); }
492
collisions()493 double collisions () const
494 {
495 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
496 }
497
498 private:
499 template<typename T> friend void gt_ggc_mx (hash_table<T> *);
500 template<typename T> friend void gt_pch_nx (hash_table<T> *);
501 template<typename T> friend void
502 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
503 template<typename T, typename U, typename V> friend void
504 gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
505 template<typename T, typename U>
506 friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
507 template<typename T> friend void gt_pch_nx (hash_table<T> *,
508 gt_pointer_operator, void *);
509
510 template<typename T> friend void gt_cleare_cache (hash_table<T> *);
511
512 void empty_slow ();
513
514 value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
515 value_type *find_empty_slot_for_expand (hashval_t);
516 bool too_empty_p (unsigned int);
517 void expand ();
is_deleted(value_type & v)518 static bool is_deleted (value_type &v)
519 {
520 return Descriptor::is_deleted (v);
521 }
522
is_empty(value_type & v)523 static bool is_empty (value_type &v)
524 {
525 return Descriptor::is_empty (v);
526 }
527
mark_deleted(value_type & v)528 static void mark_deleted (value_type &v)
529 {
530 Descriptor::mark_deleted (v);
531 }
532
mark_empty(value_type & v)533 static void mark_empty (value_type &v)
534 {
535 Descriptor::mark_empty (v);
536 }
537
538 /* Table itself. */
539 typename Descriptor::value_type *m_entries;
540
541 size_t m_size;
542
543 /* Current number of elements including also deleted elements. */
544 size_t m_n_elements;
545
546 /* Current number of deleted elements in the table. */
547 size_t m_n_deleted;
548
549 /* The following member is used for debugging. Its value is number
550 of all calls of `htab_find_slot' for the hash table. */
551 unsigned int m_searches;
552
553 /* The following member is used for debugging. Its value is number
554 of collisions fixed for time of work with the hash table. */
555 unsigned int m_collisions;
556
557 /* Current size (in entries) of the hash table, as an index into the
558 table of primes. */
559 unsigned int m_size_prime_index;
560
561 /* if m_entries is stored in ggc memory. */
562 bool m_ggc;
563
564 /* If we should gather memory statistics for the table. */
565 #if GATHER_STATISTICS
566 bool m_gather_mem_stats;
567 #else
568 static const bool m_gather_mem_stats = false;
569 #endif
570 };
571
572 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
573 mem-stats.h after hash_table declaration. */
574
575 #include "mem-stats.h"
576 #include "hash-map.h"
577
578 extern mem_alloc_description<mem_usage>& hash_table_usage (void);
579
580 /* Support function for statistics. */
581 extern void dump_hash_table_loc_statistics (void);
582
583 template<typename Descriptor, bool Lazy,
584 template<typename Type> class Allocator>
hash_table(size_t size,bool ggc,bool gather_mem_stats ATTRIBUTE_UNUSED,mem_alloc_origin origin MEM_STAT_DECL)585 hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
586 bool gather_mem_stats
587 ATTRIBUTE_UNUSED,
588 mem_alloc_origin origin
589 MEM_STAT_DECL) :
590 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
591 m_ggc (ggc)
592 #if GATHER_STATISTICS
593 , m_gather_mem_stats (gather_mem_stats)
594 #endif
595 {
596 unsigned int size_prime_index;
597
598 size_prime_index = hash_table_higher_prime_index (size);
599 size = prime_tab[size_prime_index].prime;
600
601 if (m_gather_mem_stats)
602 hash_table_usage ().register_descriptor (this, origin, ggc
603 FINAL_PASS_MEM_STAT);
604
605 if (Lazy)
606 m_entries = NULL;
607 else
608 m_entries = alloc_entries (size PASS_MEM_STAT);
609 m_size = size;
610 m_size_prime_index = size_prime_index;
611 }
612
613 template<typename Descriptor, bool Lazy,
614 template<typename Type> class Allocator>
hash_table(const hash_table & h,bool ggc,bool gather_mem_stats ATTRIBUTE_UNUSED,mem_alloc_origin origin MEM_STAT_DECL)615 hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
616 bool ggc,
617 bool gather_mem_stats
618 ATTRIBUTE_UNUSED,
619 mem_alloc_origin origin
620 MEM_STAT_DECL) :
621 m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
622 m_searches (0), m_collisions (0), m_ggc (ggc)
623 #if GATHER_STATISTICS
624 , m_gather_mem_stats (gather_mem_stats)
625 #endif
626 {
627 size_t size = h.m_size;
628
629 if (m_gather_mem_stats)
630 hash_table_usage ().register_descriptor (this, origin, ggc
631 FINAL_PASS_MEM_STAT);
632
633 if (Lazy && h.m_entries == NULL)
634 m_entries = NULL;
635 else
636 {
637 value_type *nentries = alloc_entries (size PASS_MEM_STAT);
638 for (size_t i = 0; i < size; ++i)
639 {
640 value_type &entry = h.m_entries[i];
641 if (is_deleted (entry))
642 mark_deleted (nentries[i]);
643 else if (!is_empty (entry))
644 nentries[i] = entry;
645 }
646 m_entries = nentries;
647 }
648 m_size = size;
649 m_size_prime_index = h.m_size_prime_index;
650 }
651
652 template<typename Descriptor, bool Lazy,
653 template<typename Type> class Allocator>
~hash_table()654 hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
655 {
656 if (!Lazy || m_entries)
657 {
658 for (size_t i = m_size - 1; i < m_size; i--)
659 if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
660 Descriptor::remove (m_entries[i]);
661
662 if (!m_ggc)
663 Allocator <value_type> ::data_free (m_entries);
664 else
665 ggc_free (m_entries);
666 if (m_gather_mem_stats)
667 hash_table_usage ().release_instance_overhead (this,
668 sizeof (value_type)
669 * m_size, true);
670 }
671 else if (m_gather_mem_stats)
672 hash_table_usage ().unregister_descriptor (this);
673 }
674
675 /* This function returns an array of empty hash table elements. */
676
677 template<typename Descriptor, bool Lazy,
678 template<typename Type> class Allocator>
679 inline typename hash_table<Descriptor, Lazy, Allocator>::value_type *
680 hash_table<Descriptor, Lazy,
alloc_entries(size_t n MEM_STAT_DECL)681 Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
682 {
683 value_type *nentries;
684
685 if (m_gather_mem_stats)
686 hash_table_usage ().register_instance_overhead (sizeof (value_type) * n, this);
687
688 if (!m_ggc)
689 nentries = Allocator <value_type> ::data_alloc (n);
690 else
691 nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
692
693 gcc_assert (nentries != NULL);
694 for (size_t i = 0; i < n; i++)
695 mark_empty (nentries[i]);
696
697 return nentries;
698 }
699
700 /* Similar to find_slot, but without several unwanted side effects:
701 - Does not call equal when it finds an existing entry.
702 - Does not change the count of elements/searches/collisions in the
703 hash table.
704 This function also assumes there are no deleted entries in the table.
705 HASH is the hash value for the element to be inserted. */
706
707 template<typename Descriptor, bool Lazy,
708 template<typename Type> class Allocator>
709 typename hash_table<Descriptor, Lazy, Allocator>::value_type *
710 hash_table<Descriptor, Lazy,
find_empty_slot_for_expand(hashval_t hash)711 Allocator>::find_empty_slot_for_expand (hashval_t hash)
712 {
713 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
714 size_t size = m_size;
715 value_type *slot = m_entries + index;
716 hashval_t hash2;
717
718 if (is_empty (*slot))
719 return slot;
720 gcc_checking_assert (!is_deleted (*slot));
721
722 hash2 = hash_table_mod2 (hash, m_size_prime_index);
723 for (;;)
724 {
725 index += hash2;
726 if (index >= size)
727 index -= size;
728
729 slot = m_entries + index;
730 if (is_empty (*slot))
731 return slot;
732 gcc_checking_assert (!is_deleted (*slot));
733 }
734 }
735
736 /* Return true if the current table is excessively big for ELTS elements. */
737
738 template<typename Descriptor, bool Lazy,
739 template<typename Type> class Allocator>
740 inline bool
too_empty_p(unsigned int elts)741 hash_table<Descriptor, Lazy, Allocator>::too_empty_p (unsigned int elts)
742 {
743 return elts * 8 < m_size && m_size > 32;
744 }
745
746 /* The following function changes size of memory allocated for the
747 entries and repeatedly inserts the table elements. The occupancy
748 of the table after the call will be about 50%. Naturally the hash
749 table must already exist. Remember also that the place of the
750 table entries is changed. If memory allocation fails, this function
751 will abort. */
752
753 template<typename Descriptor, bool Lazy,
754 template<typename Type> class Allocator>
755 void
expand()756 hash_table<Descriptor, Lazy, Allocator>::expand ()
757 {
758 value_type *oentries = m_entries;
759 unsigned int oindex = m_size_prime_index;
760 size_t osize = size ();
761 value_type *olimit = oentries + osize;
762 size_t elts = elements ();
763
764 /* Resize only when table after removal of unused elements is either
765 too full or too empty. */
766 unsigned int nindex;
767 size_t nsize;
768 if (elts * 2 > osize || too_empty_p (elts))
769 {
770 nindex = hash_table_higher_prime_index (elts * 2);
771 nsize = prime_tab[nindex].prime;
772 }
773 else
774 {
775 nindex = oindex;
776 nsize = osize;
777 }
778
779 value_type *nentries = alloc_entries (nsize);
780
781 if (m_gather_mem_stats)
782 hash_table_usage ().release_instance_overhead (this, sizeof (value_type)
783 * osize);
784
785 m_entries = nentries;
786 m_size = nsize;
787 m_size_prime_index = nindex;
788 m_n_elements -= m_n_deleted;
789 m_n_deleted = 0;
790
791 value_type *p = oentries;
792 do
793 {
794 value_type &x = *p;
795
796 if (!is_empty (x) && !is_deleted (x))
797 {
798 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
799
800 *q = x;
801 }
802
803 p++;
804 }
805 while (p < olimit);
806
807 if (!m_ggc)
808 Allocator <value_type> ::data_free (oentries);
809 else
810 ggc_free (oentries);
811 }
812
813 /* Implements empty() in cases where it isn't a no-op. */
814
815 template<typename Descriptor, bool Lazy,
816 template<typename Type> class Allocator>
817 void
empty_slow()818 hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
819 {
820 size_t size = m_size;
821 size_t nsize = size;
822 value_type *entries = m_entries;
823 int i;
824
825 for (i = size - 1; i >= 0; i--)
826 if (!is_empty (entries[i]) && !is_deleted (entries[i]))
827 Descriptor::remove (entries[i]);
828
829 /* Instead of clearing megabyte, downsize the table. */
830 if (size > 1024*1024 / sizeof (value_type))
831 nsize = 1024 / sizeof (value_type);
832 else if (too_empty_p (m_n_elements))
833 nsize = m_n_elements * 2;
834
835 if (nsize != size)
836 {
837 int nindex = hash_table_higher_prime_index (nsize);
838 int nsize = prime_tab[nindex].prime;
839
840 if (!m_ggc)
841 Allocator <value_type> ::data_free (m_entries);
842 else
843 ggc_free (m_entries);
844
845 m_entries = alloc_entries (nsize);
846 m_size = nsize;
847 m_size_prime_index = nindex;
848 }
849 else
850 {
851 #ifndef BROKEN_VALUE_INITIALIZATION
852 for ( ; size; ++entries, --size)
853 *entries = value_type ();
854 #else
855 memset (entries, 0, size * sizeof (value_type));
856 #endif
857 }
858 m_n_deleted = 0;
859 m_n_elements = 0;
860 }
861
862 /* This function clears a specified SLOT in a hash table. It is
863 useful when you've already done the lookup and don't want to do it
864 again. */
865
866 template<typename Descriptor, bool Lazy,
867 template<typename Type> class Allocator>
868 void
clear_slot(value_type * slot)869 hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
870 {
871 gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
872 || is_empty (*slot) || is_deleted (*slot)));
873
874 Descriptor::remove (*slot);
875
876 mark_deleted (*slot);
877 m_n_deleted++;
878 }
879
880 /* This function searches for a hash table entry equal to the given
881 COMPARABLE element starting with the given HASH value. It cannot
882 be used to insert or delete an element. */
883
884 template<typename Descriptor, bool Lazy,
885 template<typename Type> class Allocator>
886 typename hash_table<Descriptor, Lazy, Allocator>::value_type &
887 hash_table<Descriptor, Lazy, Allocator>
find_with_hash(const compare_type & comparable,hashval_t hash)888 ::find_with_hash (const compare_type &comparable, hashval_t hash)
889 {
890 m_searches++;
891 size_t size = m_size;
892 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
893
894 if (Lazy && m_entries == NULL)
895 m_entries = alloc_entries (size);
896 value_type *entry = &m_entries[index];
897 if (is_empty (*entry)
898 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
899 return *entry;
900
901 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
902 for (;;)
903 {
904 m_collisions++;
905 index += hash2;
906 if (index >= size)
907 index -= size;
908
909 entry = &m_entries[index];
910 if (is_empty (*entry)
911 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
912 return *entry;
913 }
914 }
915
916 /* This function searches for a hash table slot containing an entry
917 equal to the given COMPARABLE element and starting with the given
918 HASH. To delete an entry, call this with insert=NO_INSERT, then
919 call clear_slot on the slot returned (possibly after doing some
920 checks). To insert an entry, call this with insert=INSERT, then
921 write the value you want into the returned slot. When inserting an
922 entry, NULL may be returned if memory allocation fails. */
923
924 template<typename Descriptor, bool Lazy,
925 template<typename Type> class Allocator>
926 typename hash_table<Descriptor, Lazy, Allocator>::value_type *
927 hash_table<Descriptor, Lazy, Allocator>
find_slot_with_hash(const compare_type & comparable,hashval_t hash,enum insert_option insert)928 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
929 enum insert_option insert)
930 {
931 if (Lazy && m_entries == NULL)
932 {
933 if (insert == INSERT)
934 m_entries = alloc_entries (m_size);
935 else
936 return NULL;
937 }
938 if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
939 expand ();
940
941 m_searches++;
942
943 value_type *first_deleted_slot = NULL;
944 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
945 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
946 value_type *entry = &m_entries[index];
947 size_t size = m_size;
948 if (is_empty (*entry))
949 goto empty_entry;
950 else if (is_deleted (*entry))
951 first_deleted_slot = &m_entries[index];
952 else if (Descriptor::equal (*entry, comparable))
953 return &m_entries[index];
954
955 for (;;)
956 {
957 m_collisions++;
958 index += hash2;
959 if (index >= size)
960 index -= size;
961
962 entry = &m_entries[index];
963 if (is_empty (*entry))
964 goto empty_entry;
965 else if (is_deleted (*entry))
966 {
967 if (!first_deleted_slot)
968 first_deleted_slot = &m_entries[index];
969 }
970 else if (Descriptor::equal (*entry, comparable))
971 return &m_entries[index];
972 }
973
974 empty_entry:
975 if (insert == NO_INSERT)
976 return NULL;
977
978 if (first_deleted_slot)
979 {
980 m_n_deleted--;
981 mark_empty (*first_deleted_slot);
982 return first_deleted_slot;
983 }
984
985 m_n_elements++;
986 return &m_entries[index];
987 }
988
989 /* This function deletes an element with the given COMPARABLE value
990 from hash table starting with the given HASH. If there is no
991 matching element in the hash table, this function does nothing. */
992
993 template<typename Descriptor, bool Lazy,
994 template<typename Type> class Allocator>
995 void
996 hash_table<Descriptor, Lazy, Allocator>
remove_elt_with_hash(const compare_type & comparable,hashval_t hash)997 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
998 {
999 value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
1000 if (slot == NULL)
1001 return;
1002
1003 Descriptor::remove (*slot);
1004
1005 mark_deleted (*slot);
1006 m_n_deleted++;
1007 }
1008
1009 /* This function scans over the entire hash table calling CALLBACK for
1010 each live entry. If CALLBACK returns false, the iteration stops.
1011 ARGUMENT is passed as CALLBACK's second argument. */
1012
1013 template<typename Descriptor, bool Lazy,
1014 template<typename Type> class Allocator>
1015 template<typename Argument,
1016 int (*Callback)
1017 (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
1018 Argument argument)>
1019 void
traverse_noresize(Argument argument)1020 hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
1021 {
1022 if (Lazy && m_entries == NULL)
1023 return;
1024
1025 value_type *slot = m_entries;
1026 value_type *limit = slot + size ();
1027
1028 do
1029 {
1030 value_type &x = *slot;
1031
1032 if (!is_empty (x) && !is_deleted (x))
1033 if (! Callback (slot, argument))
1034 break;
1035 }
1036 while (++slot < limit);
1037 }
1038
1039 /* Like traverse_noresize, but does resize the table when it is too empty
1040 to improve effectivity of subsequent calls. */
1041
1042 template <typename Descriptor, bool Lazy,
1043 template <typename Type> class Allocator>
1044 template <typename Argument,
1045 int (*Callback)
1046 (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
1047 Argument argument)>
1048 void
traverse(Argument argument)1049 hash_table<Descriptor, Lazy, Allocator>::traverse (Argument argument)
1050 {
1051 if (too_empty_p (elements ()) && (!Lazy || m_entries))
1052 expand ();
1053
1054 traverse_noresize <Argument, Callback> (argument);
1055 }
1056
1057 /* Slide down the iterator slots until an active entry is found. */
1058
1059 template<typename Descriptor, bool Lazy,
1060 template<typename Type> class Allocator>
1061 void
slide()1062 hash_table<Descriptor, Lazy, Allocator>::iterator::slide ()
1063 {
1064 for ( ; m_slot < m_limit; ++m_slot )
1065 {
1066 value_type &x = *m_slot;
1067 if (!is_empty (x) && !is_deleted (x))
1068 return;
1069 }
1070 m_slot = NULL;
1071 m_limit = NULL;
1072 }
1073
1074 /* Bump the iterator. */
1075
1076 template<typename Descriptor, bool Lazy,
1077 template<typename Type> class Allocator>
1078 inline typename hash_table<Descriptor, Lazy, Allocator>::iterator &
1079 hash_table<Descriptor, Lazy, Allocator>::iterator::operator ++ ()
1080 {
1081 ++m_slot;
1082 slide ();
1083 return *this;
1084 }
1085
1086
1087 /* Iterate through the elements of hash_table HTAB,
1088 using hash_table <....>::iterator ITER,
1089 storing each element in RESULT, which is of type TYPE. */
1090
1091 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1092 for ((ITER) = (HTAB).begin (); \
1093 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1094 ++(ITER))
1095
1096 /* ggc walking routines. */
1097
1098 template<typename E>
1099 static inline void
gt_ggc_mx(hash_table<E> * h)1100 gt_ggc_mx (hash_table<E> *h)
1101 {
1102 typedef hash_table<E> table;
1103
1104 if (!ggc_test_and_set_mark (h->m_entries))
1105 return;
1106
1107 for (size_t i = 0; i < h->m_size; i++)
1108 {
1109 if (table::is_empty (h->m_entries[i])
1110 || table::is_deleted (h->m_entries[i]))
1111 continue;
1112
1113 /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1114 mark in gt_cleare_cache if appropriate. */
1115 E::ggc_maybe_mx (h->m_entries[i]);
1116 }
1117 }
1118
1119 template<typename D>
1120 static inline void
hashtab_entry_note_pointers(void * obj,void * h,gt_pointer_operator op,void * cookie)1121 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1122 void *cookie)
1123 {
1124 hash_table<D> *map = static_cast<hash_table<D> *> (h);
1125 gcc_checking_assert (map->m_entries == obj);
1126 for (size_t i = 0; i < map->m_size; i++)
1127 {
1128 typedef hash_table<D> table;
1129 if (table::is_empty (map->m_entries[i])
1130 || table::is_deleted (map->m_entries[i]))
1131 continue;
1132
1133 D::pch_nx (map->m_entries[i], op, cookie);
1134 }
1135 }
1136
1137 template<typename D>
1138 static void
gt_pch_nx(hash_table<D> * h)1139 gt_pch_nx (hash_table<D> *h)
1140 {
1141 bool success
1142 = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1143 gcc_checking_assert (success);
1144 for (size_t i = 0; i < h->m_size; i++)
1145 {
1146 if (hash_table<D>::is_empty (h->m_entries[i])
1147 || hash_table<D>::is_deleted (h->m_entries[i]))
1148 continue;
1149
1150 D::pch_nx (h->m_entries[i]);
1151 }
1152 }
1153
1154 template<typename D>
1155 static inline void
gt_pch_nx(hash_table<D> * h,gt_pointer_operator op,void * cookie)1156 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1157 {
1158 op (&h->m_entries, cookie);
1159 }
1160
1161 template<typename H>
1162 inline void
gt_cleare_cache(hash_table<H> * h)1163 gt_cleare_cache (hash_table<H> *h)
1164 {
1165 typedef hash_table<H> table;
1166 if (!h)
1167 return;
1168
1169 for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1170 if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1171 {
1172 int res = H::keep_cache_entry (*iter);
1173 if (res == 0)
1174 h->clear_slot (&*iter);
1175 else if (res != -1)
1176 H::ggc_mx (*iter);
1177 }
1178 }
1179
1180 #endif /* TYPED_HASHTAB_H */
1181