1/* A type-safe hash table template.
2 Copyright (C) 2012-2017 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
243template<typename, typename, typename> class hash_map;
244template<typename, typename> class hash_set;
245
246/* The ordinary memory allocator. */
247/* FIXME (crowl): This allocator may be extracted for wider sharing later. */
248
249template <typename Type>
250struct 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
259template <typename Type>
260inline Type *
261xcallocator <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
269template <typename Type>
270inline void
271xcallocator <Type>::data_free (Type *memory)
272{
273 return ::free (memory);
274}
275
276
277/* Table of primes and their inversion information. */
278
279struct 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
287extern struct prime_ent const prime_tab[];
288
289
290/* Functions for computing hash table indexes. */
291
292extern 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
306inline hashval_t
307mul_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
323inline hashval_t
324hash_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
333inline hashval_t
334hash_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
341class 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*/
356template <typename Descriptor,
357 template<typename Type> class Allocator = xcallocator>
358class hash_table
359{
360 typedef typename Descriptor::value_type value_type;
361 typedef typename Descriptor::compare_type compare_type;
362
363public:
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 *
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. */
385 size_t size () const { return m_size; }
386
387 /* Return the current number of elements in this hash table. */
388 size_t elements () const { return m_n_elements - m_n_deleted; }
389
390 /* Return the current number of elements in this hash table. */
391 size_t elements_with_deleted () const { return m_n_elements; }
392
393 /* This function clears all entries in this hash table. */
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. */
407 value_type &find (const value_type &value)
408 {
409 return find_with_hash (value, Descriptor::hash (value));
410 }
411
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. */
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:
455 iterator () : m_slot (NULL), m_limit (NULL) {}
456
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
473 iterator begin () const
474 {
475 iterator iter (m_entries, m_entries + m_size);
476 iter.slide ();
477 return iter;
478 }
479
480 iterator end () const { return iterator (); }
481
482 double collisions () const
483 {
484 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
485 }
486
487private:
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 ();
508 static bool is_deleted (value_type &v)
509 {
510 return Descriptor::is_deleted (v);
511 }
512
513 static bool is_empty (value_type &v)
514 {
515 return Descriptor::is_empty (v);
516 }
517
518 static void mark_deleted (value_type &v)
519 {
520 Descriptor::mark_deleted (v);
521 }
522
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
564extern mem_alloc_description<mem_usage> hash_table_usage;
565
566/* Support function for statistics. */
567extern void dump_hash_table_loc_statistics (void);
568
569template<typename Descriptor, template<typename Type> class Allocator>
570hash_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
591template<typename Descriptor, template<typename Type> class Allocator>
592hash_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
620template<typename Descriptor, template<typename Type> class Allocator>
621hash_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
640template<typename Descriptor, template<typename Type> class Allocator>
641inline typename hash_table<Descriptor, Allocator>::value_type *
642hash_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
668template<typename Descriptor, template<typename Type> class Allocator>
669typename hash_table<Descriptor, Allocator>::value_type *
670hash_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
697template<typename Descriptor, template<typename Type> class Allocator>
698inline bool
699hash_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
711template<typename Descriptor, template<typename Type> class Allocator>
712void
713hash_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
772template<typename Descriptor, template<typename Type> class Allocator>
773void
774hash_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 for ( ; size; ++entries, --size)
808 *entries = value_type ();
809 }
810 m_n_deleted = 0;
811 m_n_elements = 0;
812}
813
814/* This function clears a specified SLOT in a hash table. It is
815 useful when you've already done the lookup and don't want to do it
816 again. */
817
818template<typename Descriptor, template<typename Type> class Allocator>
819void
820hash_table<Descriptor, Allocator>::clear_slot (value_type *slot)
821{
822 gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
823 || is_empty (*slot) || is_deleted (*slot)));
824
825 Descriptor::remove (*slot);
826
827 mark_deleted (*slot);
828 m_n_deleted++;
829}
830
831/* This function searches for a hash table entry equal to the given
832 COMPARABLE element starting with the given HASH value. It cannot
833 be used to insert or delete an element. */
834
835template<typename Descriptor, template<typename Type> class Allocator>
836typename hash_table<Descriptor, Allocator>::value_type &
837hash_table<Descriptor, Allocator>
838::find_with_hash (const compare_type &comparable, hashval_t hash)
839{
840 m_searches++;
841 size_t size = m_size;
842 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
843
844 value_type *entry = &m_entries[index];
845 if (is_empty (*entry)
846 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
847 return *entry;
848
849 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
850 for (;;)
851 {
852 m_collisions++;
853 index += hash2;
854 if (index >= size)
855 index -= size;
856
857 entry = &m_entries[index];
858 if (is_empty (*entry)
859 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
860 return *entry;
861 }
862}
863
864/* This function searches for a hash table slot containing an entry
865 equal to the given COMPARABLE element and starting with the given
866 HASH. To delete an entry, call this with insert=NO_INSERT, then
867 call clear_slot on the slot returned (possibly after doing some
868 checks). To insert an entry, call this with insert=INSERT, then
869 write the value you want into the returned slot. When inserting an
870 entry, NULL may be returned if memory allocation fails. */
871
872template<typename Descriptor, template<typename Type> class Allocator>
873typename hash_table<Descriptor, Allocator>::value_type *
874hash_table<Descriptor, Allocator>
875::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
876 enum insert_option insert)
877{
878 if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
879 expand ();
880
881 m_searches++;
882
883 value_type *first_deleted_slot = NULL;
884 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
885 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
886 value_type *entry = &m_entries[index];
887 size_t size = m_size;
888 if (is_empty (*entry))
889 goto empty_entry;
890 else if (is_deleted (*entry))
891 first_deleted_slot = &m_entries[index];
892 else if (Descriptor::equal (*entry, comparable))
893 return &m_entries[index];
894
895 for (;;)
896 {
897 m_collisions++;
898 index += hash2;
899 if (index >= size)
900 index -= size;
901
902 entry = &m_entries[index];
903 if (is_empty (*entry))
904 goto empty_entry;
905 else if (is_deleted (*entry))
906 {
907 if (!first_deleted_slot)
908 first_deleted_slot = &m_entries[index];
909 }
910 else if (Descriptor::equal (*entry, comparable))
911 return &m_entries[index];
912 }
913
914 empty_entry:
915 if (insert == NO_INSERT)
916 return NULL;
917
918 if (first_deleted_slot)
919 {
920 m_n_deleted--;
921 mark_empty (*first_deleted_slot);
922 return first_deleted_slot;
923 }
924
925 m_n_elements++;
926 return &m_entries[index];
927}
928
929/* This function deletes an element with the given COMPARABLE value
930 from hash table starting with the given HASH. If there is no
931 matching element in the hash table, this function does nothing. */
932
933template<typename Descriptor, template<typename Type> class Allocator>
934void
935hash_table<Descriptor, Allocator>
936::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
937{
938 value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
939 if (is_empty (*slot))
940 return;
941
942 Descriptor::remove (*slot);
943
944 mark_deleted (*slot);
945 m_n_deleted++;
946}
947
948/* This function scans over the entire hash table calling CALLBACK for
949 each live entry. If CALLBACK returns false, the iteration stops.
950 ARGUMENT is passed as CALLBACK's second argument. */
951
952template<typename Descriptor,
953 template<typename Type> class Allocator>
954template<typename Argument,
955 int (*Callback)
956 (typename hash_table<Descriptor, Allocator>::value_type *slot,
957 Argument argument)>
958void
959hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
960{
961 value_type *slot = m_entries;
962 value_type *limit = slot + size ();
963
964 do
965 {
966 value_type &x = *slot;
967
968 if (!is_empty (x) && !is_deleted (x))
969 if (! Callback (slot, argument))
970 break;
971 }
972 while (++slot < limit);
973}
974
975/* Like traverse_noresize, but does resize the table when it is too empty
976 to improve effectivity of subsequent calls. */
977
978template <typename Descriptor,
979 template <typename Type> class Allocator>
980template <typename Argument,
981 int (*Callback)
982 (typename hash_table<Descriptor, Allocator>::value_type *slot,
983 Argument argument)>
984void
985hash_table<Descriptor, Allocator>::traverse (Argument argument)
986{
987 if (too_empty_p (elements ()))
988 expand ();
989
990 traverse_noresize <Argument, Callback> (argument);
991}
992
993/* Slide down the iterator slots until an active entry is found. */
994
995template<typename Descriptor, template<typename Type> class Allocator>
996void
997hash_table<Descriptor, Allocator>::iterator::slide ()
998{
999 for ( ; m_slot < m_limit; ++m_slot )
1000 {
1001 value_type &x = *m_slot;
1002 if (!is_empty (x) && !is_deleted (x))
1003 return;
1004 }
1005 m_slot = NULL;
1006 m_limit = NULL;
1007}
1008
1009/* Bump the iterator. */
1010
1011template<typename Descriptor, template<typename Type> class Allocator>
1012inline typename hash_table<Descriptor, Allocator>::iterator &
1013hash_table<Descriptor, Allocator>::iterator::operator ++ ()
1014{
1015 ++m_slot;
1016 slide ();
1017 return *this;
1018}
1019
1020
1021/* Iterate through the elements of hash_table HTAB,
1022 using hash_table <....>::iterator ITER,
1023 storing each element in RESULT, which is of type TYPE. */
1024
1025#define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1026 for ((ITER) = (HTAB).begin (); \
1027 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1028 ++(ITER))
1029
1030/* ggc walking routines. */
1031
1032template<typename E>
1033static inline void
1034gt_ggc_mx (hash_table<E> *h)
1035{
1036 typedef hash_table<E> table;
1037
1038 if (!ggc_test_and_set_mark (h->m_entries))
1039 return;
1040
1041 for (size_t i = 0; i < h->m_size; i++)
1042 {
1043 if (table::is_empty (h->m_entries[i])
1044 || table::is_deleted (h->m_entries[i]))
1045 continue;
1046
1047 /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1048 mark in gt_cleare_cache if appropriate. */
1049 E::ggc_maybe_mx (h->m_entries[i]);
1050 }
1051}
1052
1053template<typename D>
1054static inline void
1055hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1056 void *cookie)
1057{
1058 hash_table<D> *map = static_cast<hash_table<D> *> (h);
1059 gcc_checking_assert (map->m_entries == obj);
1060 for (size_t i = 0; i < map->m_size; i++)
1061 {
1062 typedef hash_table<D> table;
1063 if (table::is_empty (map->m_entries[i])
1064 || table::is_deleted (map->m_entries[i]))
1065 continue;
1066
1067 D::pch_nx (map->m_entries[i], op, cookie);
1068 }
1069}
1070
1071template<typename D>
1072static void
1073gt_pch_nx (hash_table<D> *h)
1074{
1075 bool success
1076 = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1077 gcc_checking_assert (success);
1078 for (size_t i = 0; i < h->m_size; i++)
1079 {
1080 if (hash_table<D>::is_empty (h->m_entries[i])
1081 || hash_table<D>::is_deleted (h->m_entries[i]))
1082 continue;
1083
1084 D::pch_nx (h->m_entries[i]);
1085 }
1086}
1087
1088template<typename D>
1089static inline void
1090gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1091{
1092 op (&h->m_entries, cookie);
1093}
1094
1095template<typename H>
1096inline void
1097gt_cleare_cache (hash_table<H> *h)
1098{
1099 typedef hash_table<H> table;
1100 if (!h)
1101 return;
1102
1103 for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1104 if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1105 {
1106 int res = H::keep_cache_entry (*iter);
1107 if (res == 0)
1108 h->clear_slot (&*iter);
1109 else if (res != -1)
1110 H::ggc_mx (*iter);
1111 }
1112}
1113
1114#endif /* TYPED_HASHTAB_H */
1115