1 /* A type-safe hash table template.
2 Copyright (C) 2012-2019 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* This file implements a typed hash table.
23 The implementation borrows from libiberty's htab_t in hashtab.h.
28 Users of the hash table generally need to be aware of three types.
30 1. The type being placed into the hash table. This type is called
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
37 - A typedef named 'value_type' to the value type (from above).
39 - A static member function named 'hash' that takes a value_type
40 (or 'const value_type &') and returns a hashval_t value.
42 - A typedef named 'compare_type' that is used to test when a value
43 is found. This type is the comparison type. Usually, it will be the
44 same as value_type. If it is not the same type, you must generally
45 explicitly compute hash values and pass them to the hash table.
47 - A static member function named 'equal' that takes a value_type
48 and a compare_type, and returns a bool. Both arguments can be
51 - A static function named 'remove' that takes an value_type pointer
52 and frees the memory allocated by it. This function is used when
53 individual elements of the table need to be disposed of (e.g.,
54 when deleting a hash table, removing elements from the table, etc).
56 - An optional static function named 'keep_cache_entry'. This
57 function is provided only for garbage-collected elements that
58 are not marked by the normal gc mark pass. It describes what
59 what should happen to the element at the end of the gc mark phase.
60 The return value should be:
61 - 0 if the element should be deleted
62 - 1 if the element should be kept and needs to be marked
63 - -1 if the element should be kept and is already marked.
64 Returning -1 rather than 1 is purely an optimization.
66 3. The type of the hash table itself. (More later.)
68 In very special circumstances, users may need to know about a fourth type.
70 4. The template type used to describe how hash table memory
71 is allocated. This type is called the allocator type. It is
72 parameterized on the value type. It provides two functions:
74 - A static member function named 'data_alloc'. This function
75 allocates the data elements in the table.
77 - A static member function named 'data_free'. This function
78 deallocates the data elements in the table.
80 Hash table are instantiated with two type arguments.
82 * The descriptor type, (2) above.
84 * The allocator type, (4) above. In general, you will not need to
85 provide your own allocator type. By default, hash tables will use
86 the class template xcallocator, which uses malloc/free for allocation.
89 DEFINING A DESCRIPTOR TYPE
91 The first task in using the hash table is to describe the element type.
92 We compose this into a few steps.
94 1. Decide on a removal policy for values stored in the table.
95 hash-traits.h provides class templates for the four most common
98 * typed_free_remove implements the static 'remove' member function
101 * typed_noop_remove implements the static 'remove' member function
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
109 * ggc_cache_remove is like ggc_remove, except that it does not
110 mark the entries during the normal gc mark phase. Instead it
111 uses 'keep_cache_entry' (described above) to keep elements that
112 were not collected and delete those that were. Use this for
113 garbage-collected caches that should not in themselves stop
114 the data from being collected.
116 You can use these policies by simply deriving the descriptor type
117 from one of those class template, with the appropriate argument.
119 Otherwise, you need to write the static 'remove' member function
120 in the descriptor class.
122 2. Choose a hash function. Write the static 'hash' member function.
124 3. Decide whether the lookup function should take as input an object
125 of type value_type or something more restricted. Define compare_type
128 4. Choose an equality testing function 'equal' that compares a value_type
131 If your elements are pointers, it is usually easiest to start with one
132 of the generic pointer descriptors described below and override the bits
135 AN EXAMPLE DESCRIPTOR TYPE
137 Suppose you want to put some_type into the hash table. You could define
138 the descriptor type as follows.
140 struct some_type_hasher : nofree_ptr_hash <some_type>
141 // Deriving from nofree_ptr_hash means that we get a 'remove' that does
142 // nothing. This choice is good for raw values.
144 static inline hashval_t hash (const value_type *);
145 static inline bool equal (const value_type *, const compare_type *);
149 some_type_hasher::hash (const value_type *e)
150 { ... compute and return a hash value for E ... }
153 some_type_hasher::equal (const value_type *p1, const compare_type *p2)
154 { ... compare P1 vs P2. Return true if they are the 'same' ... }
157 AN EXAMPLE HASH_TABLE DECLARATION
159 To instantiate a hash table for some_type:
161 hash_table <some_type_hasher> some_type_hash_table;
163 There is no need to mention some_type directly, as the hash table will
164 obtain it using some_type_hasher::value_type.
166 You can then use any of the functions in hash_table's public interface.
167 See hash_table for details. The interface is very similar to libiberty's
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
174 hash_table <some_type_hasher, true> some_type_hash_table;
176 which will cause whatever methods actually need the allocated entries
177 array to allocate it later.
180 EASY DESCRIPTORS FOR POINTERS
182 There are four descriptors for pointer elements, one for each of
183 the removal policies above:
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)
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:
194 hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
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:
202 extern void consume (some_info *);
204 We define a convenience typedef and the hash table:
206 typedef hash_table <some_info_hasher> info_table_type;
207 info_table_type info_table;
209 Then we write the loop in typical C++ style:
211 for (info_table_type::iterator iter = info_table.begin ();
212 iter != info_table.end ();
214 if ((*iter).status == INFO_READY)
217 Or with common sub-expression elimination:
219 for (info_table_type::iterator iter = info_table.begin ();
220 iter != info_table.end ();
223 some_info &elem = *iter;
224 if (elem.status == INFO_READY)
228 One can also use a more typical GCC style:
230 typedef some_info *some_info_p;
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)
240 #ifndef TYPED_HASHTAB_H
241 #define TYPED_HASHTAB_H
243 #include "statistics.h"
248 #include "mem-stats-traits.h"
249 #include "hash-traits.h"
250 #include "hash-map-traits.h"
252 template<typename
, typename
, typename
> class hash_map
;
253 template<typename
, bool, typename
> class hash_set
;
255 /* The ordinary memory allocator. */
256 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
258 template <typename Type
>
261 static Type
*data_alloc (size_t count
);
262 static void data_free (Type
*memory
);
266 /* Allocate memory for COUNT data blocks. */
268 template <typename Type
>
270 xcallocator
<Type
>::data_alloc (size_t count
)
272 return static_cast <Type
*> (xcalloc (count
, sizeof (Type
)));
276 /* Free memory for data blocks. */
278 template <typename Type
>
280 xcallocator
<Type
>::data_free (Type
*memory
)
282 return ::free (memory
);
286 /* Table of primes and their inversion information. */
292 hashval_t inv_m2
; /* inverse of prime-2 */
296 extern struct prime_ent
const prime_tab
[];
299 /* Functions for computing hash table indexes. */
301 extern unsigned int hash_table_higher_prime_index (unsigned long n
)
304 /* Return X % Y using multiplicative inverse values INV and SHIFT.
306 The multiplicative inverses computed above are for 32-bit types,
307 and requires that we be able to compute a highpart multiply.
309 FIX: I am not at all convinced that
310 3 loads, 2 multiplications, 3 shifts, and 3 additions
313 on modern systems running a compiler. */
316 mul_mod (hashval_t x
, hashval_t y
, hashval_t inv
, int shift
)
318 hashval_t t1
, t2
, t3
, t4
, q
, r
;
320 t1
= ((uint64_t)x
* inv
) >> 32;
330 /* Compute the primary table index for HASH given current prime index. */
333 hash_table_mod1 (hashval_t hash
, unsigned int index
)
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
);
340 /* Compute the secondary table index for HASH given current prime index. */
343 hash_table_mod2 (hashval_t hash
, unsigned int index
)
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
);
352 /* User-facing hash table type.
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.
358 Specify the template Allocator to allocate and free memory.
359 The default is xcallocator.
361 Storage is an implementation detail and should not be used outside the
365 template <typename Descriptor
, bool Lazy
= false,
366 template<typename Type
> class Allocator
= xcallocator
>
369 typedef typename
Descriptor::value_type value_type
;
370 typedef typename
Descriptor::compare_type compare_type
;
373 explicit hash_table (size_t, bool ggc
= false,
374 bool gather_mem_stats
= GATHER_STATISTICS
,
375 mem_alloc_origin origin
= HASH_TABLE_ORIGIN
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
383 /* Create a hash_table in gc memory. */
385 create_ggc (size_t n CXX_MEM_STAT_INFO
)
387 hash_table
*table
= ggc_alloc
<hash_table
> ();
388 new (table
) hash_table (n
, true, GATHER_STATISTICS
,
389 HASH_TABLE_ORIGIN PASS_MEM_STAT
);
393 /* Current size (in entries) of the hash table. */
394 size_t size () const { return m_size
; }
396 /* Return the current number of elements in this hash table. */
397 size_t elements () const { return m_n_elements
- m_n_deleted
; }
399 /* Return the current number of elements in this hash table. */
400 size_t elements_with_deleted () const { return m_n_elements
; }
402 /* This function clears all entries in this hash table. */
403 void empty () { if (elements ()) empty_slow (); }
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
408 void clear_slot (value_type
*);
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
);
415 /* Like find_slot_with_hash, but compute the hash value from the element. */
416 value_type
&find (const value_type
&value
)
418 return find_with_hash (value
, Descriptor::hash (value
));
421 value_type
*find_slot (const value_type
&value
, insert_option insert
)
423 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
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
);
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
);
441 /* Like remove_elt_with_hash, but compute the hash value from the
443 void remove_elt (const value_type
&value
)
445 remove_elt_with_hash (value
, Descriptor::hash (value
));
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
);
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
);
464 iterator () : m_slot (NULL
), m_limit (NULL
) {}
466 iterator (value_type
*slot
, value_type
*limit
) :
467 m_slot (slot
), m_limit (limit
) {}
469 inline value_type
&operator * () { return *m_slot
; }
471 inline iterator
&operator ++ ();
472 bool operator != (const iterator
&other
) const
474 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
482 iterator
begin () const
484 if (Lazy
&& m_entries
== NULL
)
486 iterator
iter (m_entries
, m_entries
+ m_size
);
491 iterator
end () const { return iterator (); }
493 double collisions () const
495 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
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 *);
510 template<typename T
> friend void gt_cleare_cache (hash_table
<T
> *);
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);
518 static bool is_deleted (value_type
&v
)
520 return Descriptor::is_deleted (v
);
523 static bool is_empty (value_type
&v
)
525 return Descriptor::is_empty (v
);
528 static void mark_deleted (value_type
&v
)
530 Descriptor::mark_deleted (v
);
533 static void mark_empty (value_type
&v
)
535 Descriptor::mark_empty (v
);
539 typename
Descriptor::value_type
*m_entries
;
543 /* Current number of elements including also deleted elements. */
546 /* Current number of deleted elements in the table. */
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
;
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
;
557 /* Current size (in entries) of the hash table, as an index into the
559 unsigned int m_size_prime_index
;
561 /* if m_entries is stored in ggc memory. */
564 /* If we should gather memory statistics for the table. */
565 bool m_gather_mem_stats
;
568 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
569 mem-stats.h after hash_table declaration. */
571 #include "mem-stats.h"
572 #include "hash-map.h"
574 extern mem_alloc_description
<mem_usage
>& hash_table_usage (void);
576 /* Support function for statistics. */
577 extern void dump_hash_table_loc_statistics (void);
579 template<typename Descriptor
, bool Lazy
,
580 template<typename Type
> class Allocator
>
581 hash_table
<Descriptor
, Lazy
, Allocator
>::hash_table (size_t size
, bool ggc
,
582 bool gather_mem_stats
,
583 mem_alloc_origin origin
585 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
586 m_ggc (ggc
), m_gather_mem_stats (gather_mem_stats
)
588 unsigned int size_prime_index
;
590 size_prime_index
= hash_table_higher_prime_index (size
);
591 size
= prime_tab
[size_prime_index
].prime
;
593 if (m_gather_mem_stats
)
594 hash_table_usage ().register_descriptor (this, origin
, ggc
595 FINAL_PASS_MEM_STAT
);
600 m_entries
= alloc_entries (size PASS_MEM_STAT
);
602 m_size_prime_index
= size_prime_index
;
605 template<typename Descriptor
, bool Lazy
,
606 template<typename Type
> class Allocator
>
607 hash_table
<Descriptor
, Lazy
, Allocator
>::hash_table (const hash_table
&h
,
609 bool gather_mem_stats
,
610 mem_alloc_origin origin
612 m_n_elements (h
.m_n_elements
), m_n_deleted (h
.m_n_deleted
),
613 m_searches (0), m_collisions (0), m_ggc (ggc
),
614 m_gather_mem_stats (gather_mem_stats
)
616 size_t size
= h
.m_size
;
618 if (m_gather_mem_stats
)
619 hash_table_usage ().register_descriptor (this, origin
, ggc
620 FINAL_PASS_MEM_STAT
);
622 if (Lazy
&& h
.m_entries
== NULL
)
626 value_type
*nentries
= alloc_entries (size PASS_MEM_STAT
);
627 for (size_t i
= 0; i
< size
; ++i
)
629 value_type
&entry
= h
.m_entries
[i
];
630 if (is_deleted (entry
))
631 mark_deleted (nentries
[i
]);
632 else if (!is_empty (entry
))
635 m_entries
= nentries
;
638 m_size_prime_index
= h
.m_size_prime_index
;
641 template<typename Descriptor
, bool Lazy
,
642 template<typename Type
> class Allocator
>
643 hash_table
<Descriptor
, Lazy
, Allocator
>::~hash_table ()
645 if (!Lazy
|| m_entries
)
647 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
648 if (!is_empty (m_entries
[i
]) && !is_deleted (m_entries
[i
]))
649 Descriptor::remove (m_entries
[i
]);
652 Allocator
<value_type
> ::data_free (m_entries
);
654 ggc_free (m_entries
);
657 if (m_gather_mem_stats
)
658 hash_table_usage ().release_instance_overhead (this,
663 /* This function returns an array of empty hash table elements. */
665 template<typename Descriptor
, bool Lazy
,
666 template<typename Type
> class Allocator
>
667 inline typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*
668 hash_table
<Descriptor
, Lazy
,
669 Allocator
>::alloc_entries (size_t n MEM_STAT_DECL
) const
671 value_type
*nentries
;
673 if (m_gather_mem_stats
)
674 hash_table_usage ().register_instance_overhead (sizeof (value_type
) * n
, this);
677 nentries
= Allocator
<value_type
> ::data_alloc (n
);
679 nentries
= ::ggc_cleared_vec_alloc
<value_type
> (n PASS_MEM_STAT
);
681 gcc_assert (nentries
!= NULL
);
682 for (size_t i
= 0; i
< n
; i
++)
683 mark_empty (nentries
[i
]);
688 /* Similar to find_slot, but without several unwanted side effects:
689 - Does not call equal when it finds an existing entry.
690 - Does not change the count of elements/searches/collisions in the
692 This function also assumes there are no deleted entries in the table.
693 HASH is the hash value for the element to be inserted. */
695 template<typename Descriptor
, bool Lazy
,
696 template<typename Type
> class Allocator
>
697 typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*
698 hash_table
<Descriptor
, Lazy
,
699 Allocator
>::find_empty_slot_for_expand (hashval_t hash
)
701 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
702 size_t size
= m_size
;
703 value_type
*slot
= m_entries
+ index
;
706 if (is_empty (*slot
))
708 gcc_checking_assert (!is_deleted (*slot
));
710 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
717 slot
= m_entries
+ index
;
718 if (is_empty (*slot
))
720 gcc_checking_assert (!is_deleted (*slot
));
724 /* Return true if the current table is excessively big for ELTS elements. */
726 template<typename Descriptor
, bool Lazy
,
727 template<typename Type
> class Allocator
>
729 hash_table
<Descriptor
, Lazy
, Allocator
>::too_empty_p (unsigned int elts
)
731 return elts
* 8 < m_size
&& m_size
> 32;
734 /* The following function changes size of memory allocated for the
735 entries and repeatedly inserts the table elements. The occupancy
736 of the table after the call will be about 50%. Naturally the hash
737 table must already exist. Remember also that the place of the
738 table entries is changed. If memory allocation fails, this function
741 template<typename Descriptor
, bool Lazy
,
742 template<typename Type
> class Allocator
>
744 hash_table
<Descriptor
, Lazy
, Allocator
>::expand ()
746 value_type
*oentries
= m_entries
;
747 unsigned int oindex
= m_size_prime_index
;
748 size_t osize
= size ();
749 value_type
*olimit
= oentries
+ osize
;
750 size_t elts
= elements ();
752 /* Resize only when table after removal of unused elements is either
753 too full or too empty. */
756 if (elts
* 2 > osize
|| too_empty_p (elts
))
758 nindex
= hash_table_higher_prime_index (elts
* 2);
759 nsize
= prime_tab
[nindex
].prime
;
767 value_type
*nentries
= alloc_entries (nsize
);
769 if (m_gather_mem_stats
)
770 hash_table_usage ().release_instance_overhead (this, sizeof (value_type
)
773 m_entries
= nentries
;
775 m_size_prime_index
= nindex
;
776 m_n_elements
-= m_n_deleted
;
779 value_type
*p
= oentries
;
784 if (!is_empty (x
) && !is_deleted (x
))
786 value_type
*q
= find_empty_slot_for_expand (Descriptor::hash (x
));
796 Allocator
<value_type
> ::data_free (oentries
);
801 /* Implements empty() in cases where it isn't a no-op. */
803 template<typename Descriptor
, bool Lazy
,
804 template<typename Type
> class Allocator
>
806 hash_table
<Descriptor
, Lazy
, Allocator
>::empty_slow ()
808 size_t size
= m_size
;
810 value_type
*entries
= m_entries
;
813 for (i
= size
- 1; i
>= 0; i
--)
814 if (!is_empty (entries
[i
]) && !is_deleted (entries
[i
]))
815 Descriptor::remove (entries
[i
]);
817 /* Instead of clearing megabyte, downsize the table. */
818 if (size
> 1024*1024 / sizeof (value_type
))
819 nsize
= 1024 / sizeof (value_type
);
820 else if (too_empty_p (m_n_elements
))
821 nsize
= m_n_elements
* 2;
825 int nindex
= hash_table_higher_prime_index (nsize
);
826 int nsize
= prime_tab
[nindex
].prime
;
829 Allocator
<value_type
> ::data_free (m_entries
);
831 ggc_free (m_entries
);
833 m_entries
= alloc_entries (nsize
);
835 m_size_prime_index
= nindex
;
839 #ifndef BROKEN_VALUE_INITIALIZATION
840 for ( ; size
; ++entries
, --size
)
841 *entries
= value_type ();
843 memset (entries
, 0, size
* sizeof (value_type
));
850 /* This function clears a specified SLOT in a hash table. It is
851 useful when you've already done the lookup and don't want to do it
854 template<typename Descriptor
, bool Lazy
,
855 template<typename Type
> class Allocator
>
857 hash_table
<Descriptor
, Lazy
, Allocator
>::clear_slot (value_type
*slot
)
859 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
860 || is_empty (*slot
) || is_deleted (*slot
)));
862 Descriptor::remove (*slot
);
864 mark_deleted (*slot
);
868 /* This function searches for a hash table entry equal to the given
869 COMPARABLE element starting with the given HASH value. It cannot
870 be used to insert or delete an element. */
872 template<typename Descriptor
, bool Lazy
,
873 template<typename Type
> class Allocator
>
874 typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
&
875 hash_table
<Descriptor
, Lazy
, Allocator
>
876 ::find_with_hash (const compare_type
&comparable
, hashval_t hash
)
879 size_t size
= m_size
;
880 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
882 if (Lazy
&& m_entries
== NULL
)
883 m_entries
= alloc_entries (size
);
884 value_type
*entry
= &m_entries
[index
];
885 if (is_empty (*entry
)
886 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
889 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
897 entry
= &m_entries
[index
];
898 if (is_empty (*entry
)
899 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
904 /* This function searches for a hash table slot containing an entry
905 equal to the given COMPARABLE element and starting with the given
906 HASH. To delete an entry, call this with insert=NO_INSERT, then
907 call clear_slot on the slot returned (possibly after doing some
908 checks). To insert an entry, call this with insert=INSERT, then
909 write the value you want into the returned slot. When inserting an
910 entry, NULL may be returned if memory allocation fails. */
912 template<typename Descriptor
, bool Lazy
,
913 template<typename Type
> class Allocator
>
914 typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*
915 hash_table
<Descriptor
, Lazy
, Allocator
>
916 ::find_slot_with_hash (const compare_type
&comparable
, hashval_t hash
,
917 enum insert_option insert
)
919 if (Lazy
&& m_entries
== NULL
)
921 if (insert
== INSERT
)
922 m_entries
= alloc_entries (m_size
);
926 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
931 value_type
*first_deleted_slot
= NULL
;
932 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
933 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
934 value_type
*entry
= &m_entries
[index
];
935 size_t size
= m_size
;
936 if (is_empty (*entry
))
938 else if (is_deleted (*entry
))
939 first_deleted_slot
= &m_entries
[index
];
940 else if (Descriptor::equal (*entry
, comparable
))
941 return &m_entries
[index
];
950 entry
= &m_entries
[index
];
951 if (is_empty (*entry
))
953 else if (is_deleted (*entry
))
955 if (!first_deleted_slot
)
956 first_deleted_slot
= &m_entries
[index
];
958 else if (Descriptor::equal (*entry
, comparable
))
959 return &m_entries
[index
];
963 if (insert
== NO_INSERT
)
966 if (first_deleted_slot
)
969 mark_empty (*first_deleted_slot
);
970 return first_deleted_slot
;
974 return &m_entries
[index
];
977 /* This function deletes an element with the given COMPARABLE value
978 from hash table starting with the given HASH. If there is no
979 matching element in the hash table, this function does nothing. */
981 template<typename Descriptor
, bool Lazy
,
982 template<typename Type
> class Allocator
>
984 hash_table
<Descriptor
, Lazy
, Allocator
>
985 ::remove_elt_with_hash (const compare_type
&comparable
, hashval_t hash
)
987 value_type
*slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
991 Descriptor::remove (*slot
);
993 mark_deleted (*slot
);
997 /* This function scans over the entire hash table calling CALLBACK for
998 each live entry. If CALLBACK returns false, the iteration stops.
999 ARGUMENT is passed as CALLBACK's second argument. */
1001 template<typename Descriptor
, bool Lazy
,
1002 template<typename Type
> class Allocator
>
1003 template<typename Argument
,
1005 (typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*slot
,
1008 hash_table
<Descriptor
, Lazy
, Allocator
>::traverse_noresize (Argument argument
)
1010 if (Lazy
&& m_entries
== NULL
)
1013 value_type
*slot
= m_entries
;
1014 value_type
*limit
= slot
+ size ();
1018 value_type
&x
= *slot
;
1020 if (!is_empty (x
) && !is_deleted (x
))
1021 if (! Callback (slot
, argument
))
1024 while (++slot
< limit
);
1027 /* Like traverse_noresize, but does resize the table when it is too empty
1028 to improve effectivity of subsequent calls. */
1030 template <typename Descriptor
, bool Lazy
,
1031 template <typename Type
> class Allocator
>
1032 template <typename Argument
,
1034 (typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*slot
,
1037 hash_table
<Descriptor
, Lazy
, Allocator
>::traverse (Argument argument
)
1039 if (too_empty_p (elements ()) && (!Lazy
|| m_entries
))
1042 traverse_noresize
<Argument
, Callback
> (argument
);
1045 /* Slide down the iterator slots until an active entry is found. */
1047 template<typename Descriptor
, bool Lazy
,
1048 template<typename Type
> class Allocator
>
1050 hash_table
<Descriptor
, Lazy
, Allocator
>::iterator::slide ()
1052 for ( ; m_slot
< m_limit
; ++m_slot
)
1054 value_type
&x
= *m_slot
;
1055 if (!is_empty (x
) && !is_deleted (x
))
1062 /* Bump the iterator. */
1064 template<typename Descriptor
, bool Lazy
,
1065 template<typename Type
> class Allocator
>
1066 inline typename hash_table
<Descriptor
, Lazy
, Allocator
>::iterator
&
1067 hash_table
<Descriptor
, Lazy
, Allocator
>::iterator::operator ++ ()
1075 /* Iterate through the elements of hash_table HTAB,
1076 using hash_table <....>::iterator ITER,
1077 storing each element in RESULT, which is of type TYPE. */
1079 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1080 for ((ITER) = (HTAB).begin (); \
1081 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1084 /* ggc walking routines. */
1086 template<typename E
>
1088 gt_ggc_mx (hash_table
<E
> *h
)
1090 typedef hash_table
<E
> table
;
1092 if (!ggc_test_and_set_mark (h
->m_entries
))
1095 for (size_t i
= 0; i
< h
->m_size
; i
++)
1097 if (table::is_empty (h
->m_entries
[i
])
1098 || table::is_deleted (h
->m_entries
[i
]))
1101 /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1102 mark in gt_cleare_cache if appropriate. */
1103 E::ggc_maybe_mx (h
->m_entries
[i
]);
1107 template<typename D
>
1109 hashtab_entry_note_pointers (void *obj
, void *h
, gt_pointer_operator op
,
1112 hash_table
<D
> *map
= static_cast<hash_table
<D
> *> (h
);
1113 gcc_checking_assert (map
->m_entries
== obj
);
1114 for (size_t i
= 0; i
< map
->m_size
; i
++)
1116 typedef hash_table
<D
> table
;
1117 if (table::is_empty (map
->m_entries
[i
])
1118 || table::is_deleted (map
->m_entries
[i
]))
1121 D::pch_nx (map
->m_entries
[i
], op
, cookie
);
1125 template<typename D
>
1127 gt_pch_nx (hash_table
<D
> *h
)
1130 = gt_pch_note_object (h
->m_entries
, h
, hashtab_entry_note_pointers
<D
>);
1131 gcc_checking_assert (success
);
1132 for (size_t i
= 0; i
< h
->m_size
; i
++)
1134 if (hash_table
<D
>::is_empty (h
->m_entries
[i
])
1135 || hash_table
<D
>::is_deleted (h
->m_entries
[i
]))
1138 D::pch_nx (h
->m_entries
[i
]);
1142 template<typename D
>
1144 gt_pch_nx (hash_table
<D
> *h
, gt_pointer_operator op
, void *cookie
)
1146 op (&h
->m_entries
, cookie
);
1149 template<typename H
>
1151 gt_cleare_cache (hash_table
<H
> *h
)
1153 typedef hash_table
<H
> table
;
1157 for (typename
table::iterator iter
= h
->begin (); iter
!= h
->end (); ++iter
)
1158 if (!table::is_empty (*iter
) && !table::is_deleted (*iter
))
1160 int res
= H::keep_cache_entry (*iter
);
1162 h
->clear_slot (&*iter
);
1168 #endif /* TYPED_HASHTAB_H */