1 /* A type-safe hash table template.
2 Copyright (C) 2012-2015 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
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 pointer and returns a hashval_t value.
42 - A typedef named 'compare_type' that is used to test when an 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 pointer and a compare_type pointer, and returns a bool.
50 - A static function named 'remove' that takes an value_type pointer
51 and frees the memory allocated by it. This function is used when
52 individual elements of the table need to be disposed of (e.g.,
53 when deleting a hash table, removing elements from the table, etc).
55 - An optional static function named 'keep_cache_entry'. This
56 function is provided only for garbage-collected elements that
57 are not marked by the normal gc mark pass. It describes what
58 what should happen to the element at the end of the gc mark phase.
59 The return value should be:
60 - 0 if the element should be deleted
61 - 1 if the element should be kept and needs to be marked
62 - -1 if the element should be kept and is already marked.
63 Returning -1 rather than 1 is purely an optimization.
65 3. The type of the hash table itself. (More later.)
67 In very special circumstances, users may need to know about a fourth type.
69 4. The template type used to describe how hash table memory
70 is allocated. This type is called the allocator type. It is
71 parameterized on the value type. It provides four functions.
73 - A static member function named 'data_alloc'. This function
74 allocates the data elements in the table.
76 - A static member function named 'data_free'. This function
77 deallocates the data elements in the table.
79 Hash table are instantiated with two type arguments.
81 * The descriptor type, (2) above.
83 * The allocator type, (4) above. In general, you will not need to
84 provide your own allocator type. By default, hash tables will use
85 the class template xcallocator, which uses malloc/free for allocation.
88 DEFINING A DESCRIPTOR TYPE
90 The first task in using the hash table is to describe the element type.
91 We compose this into a few steps.
93 1. Decide on a removal policy for values stored in the table.
94 hash-traits.h provides class templates for the two most common
97 * typed_free_remove implements the static 'remove' member function
100 * typed_noop_remove implements the static 'remove' member function
103 You can use these policies by simply deriving the descriptor type
104 from one of those class template, with the appropriate argument.
106 Otherwise, you need to write the static 'remove' member function
107 in the descriptor class.
109 2. Choose a hash function. Write the static 'hash' member function.
111 3. Choose an equality testing function. In most cases, its two
112 arguments will be value_type pointers. If not, the first argument must
113 be a value_type pointer, and the second argument a compare_type pointer.
116 AN EXAMPLE DESCRIPTOR TYPE
118 Suppose you want to put some_type into the hash table. You could define
119 the descriptor type as follows.
121 struct some_type_hasher : nofree_ptr_hash <some_type>
122 // Deriving from nofree_ptr_hash means that we get a 'remove' that does
123 // nothing. This choice is good for raw values.
125 static inline hashval_t hash (const value_type *);
126 static inline bool equal (const value_type *, const compare_type *);
130 some_type_hasher::hash (const value_type *e)
131 { ... compute and return a hash value for E ... }
134 some_type_hasher::equal (const value_type *p1, const compare_type *p2)
135 { ... compare P1 vs P2. Return true if they are the 'same' ... }
138 AN EXAMPLE HASH_TABLE DECLARATION
140 To instantiate a hash table for some_type:
142 hash_table <some_type_hasher> some_type_hash_table;
144 There is no need to mention some_type directly, as the hash table will
145 obtain it using some_type_hasher::value_type.
147 You can then used any of the functions in hash_table's public interface.
148 See hash_table for details. The interface is very similar to libiberty's
152 EASY DESCRIPTORS FOR POINTERS
154 The class template pointer_hash provides everything you need to hash
155 pointers (as opposed to what they point to). So, to instantiate a hash
156 table over pointers to whatever_type,
158 hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
163 The hash table provides standard C++ iterators. For example, consider a
164 hash table of some_info. We wish to consume each element of the table:
166 extern void consume (some_info *);
168 We define a convenience typedef and the hash table:
170 typedef hash_table <some_info_hasher> info_table_type;
171 info_table_type info_table;
173 Then we write the loop in typical C++ style:
175 for (info_table_type::iterator iter = info_table.begin ();
176 iter != info_table.end ();
178 if ((*iter).status == INFO_READY)
181 Or with common sub-expression elimination:
183 for (info_table_type::iterator iter = info_table.begin ();
184 iter != info_table.end ();
187 some_info &elem = *iter;
188 if (elem.status == INFO_READY)
192 One can also use a more typical GCC style:
194 typedef some_info *some_info_p;
196 info_table_type::iterator iter;
197 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
198 if (elem_ptr->status == INFO_READY)
204 #ifndef TYPED_HASHTAB_H
205 #define TYPED_HASHTAB_H
207 #include "statistics.h"
212 #include "mem-stats-traits.h"
213 #include "hash-traits.h"
214 #include "hash-map-traits.h"
216 template<typename
, typename
, typename
> class hash_map
;
217 template<typename
, typename
> class hash_set
;
219 /* The ordinary memory allocator. */
220 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
222 template <typename Type
>
225 static Type
*data_alloc (size_t count
);
226 static void data_free (Type
*memory
);
230 /* Allocate memory for COUNT data blocks. */
232 template <typename Type
>
234 xcallocator
<Type
>::data_alloc (size_t count
)
236 return static_cast <Type
*> (xcalloc (count
, sizeof (Type
)));
240 /* Free memory for data blocks. */
242 template <typename Type
>
244 xcallocator
<Type
>::data_free (Type
*memory
)
246 return ::free (memory
);
250 /* Table of primes and their inversion information. */
256 hashval_t inv_m2
; /* inverse of prime-2 */
260 extern struct prime_ent
const prime_tab
[];
263 /* Functions for computing hash table indexes. */
265 extern unsigned int hash_table_higher_prime_index (unsigned long n
)
268 /* Return X % Y using multiplicative inverse values INV and SHIFT.
270 The multiplicative inverses computed above are for 32-bit types,
271 and requires that we be able to compute a highpart multiply.
273 FIX: I am not at all convinced that
274 3 loads, 2 multiplications, 3 shifts, and 3 additions
277 on modern systems running a compiler. */
280 mul_mod (hashval_t x
, hashval_t y
, hashval_t inv
, int shift
)
282 hashval_t t1
, t2
, t3
, t4
, q
, r
;
284 t1
= ((uint64_t)x
* inv
) >> 32;
294 /* Compute the primary table index for HASH given current prime index. */
297 hash_table_mod1 (hashval_t hash
, unsigned int index
)
299 const struct prime_ent
*p
= &prime_tab
[index
];
300 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
301 return mul_mod (hash
, p
->prime
, p
->inv
, p
->shift
);
304 /* Compute the secondary table index for HASH given current prime index. */
307 hash_table_mod2 (hashval_t hash
, unsigned int index
)
309 const struct prime_ent
*p
= &prime_tab
[index
];
310 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
311 return 1 + mul_mod (hash
, p
->prime
- 2, p
->inv_m2
, p
->shift
);
314 template<typename Traits
>
315 struct has_is_deleted
317 template<typename U
, bool (*)(U
&)> struct helper
{};
318 template<typename U
> static char test (helper
<U
, U::is_deleted
> *);
319 template<typename U
> static int test (...);
320 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
323 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
324 struct is_deleted_helper
329 return Traits::is_deleted (v
);
333 template<typename Type
, typename Traits
>
334 struct is_deleted_helper
<Type
*, Traits
, false>
339 return v
== HTAB_DELETED_ENTRY
;
343 template<typename Traits
>
346 template<typename U
, bool (*)(U
&)> struct helper
{};
347 template<typename U
> static char test (helper
<U
, U::is_empty
> *);
348 template<typename U
> static int test (...);
349 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
352 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
353 struct is_empty_helper
358 return Traits::is_empty (v
);
362 template<typename Type
, typename Traits
>
363 struct is_empty_helper
<Type
*, Traits
, false>
368 return v
== HTAB_EMPTY_ENTRY
;
372 template<typename Traits
>
373 struct has_mark_deleted
375 template<typename U
, void (*)(U
&)> struct helper
{};
376 template<typename U
> static char test (helper
<U
, U::mark_deleted
> *);
377 template<typename U
> static int test (...);
378 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
381 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
382 struct mark_deleted_helper
387 Traits::mark_deleted (v
);
391 template<typename Type
, typename Traits
>
392 struct mark_deleted_helper
<Type
*, Traits
, false>
397 v
= static_cast<Type
*> (HTAB_DELETED_ENTRY
);
401 template<typename Traits
>
402 struct has_mark_empty
404 template<typename U
, void (*)(U
&)> struct helper
{};
405 template<typename U
> static char test (helper
<U
, U::mark_empty
> *);
406 template<typename U
> static int test (...);
407 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
410 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
411 struct mark_empty_helper
416 Traits::mark_empty (v
);
420 template<typename Type
, typename Traits
>
421 struct mark_empty_helper
<Type
*, Traits
, false>
426 v
= static_cast<Type
*> (HTAB_EMPTY_ENTRY
);
432 /* User-facing hash table type.
434 The table stores elements of type Descriptor::value_type.
436 It hashes values with the hash member function.
437 The table currently works with relatively weak hash functions.
438 Use typed_pointer_hash <Value> when hashing pointers instead of objects.
440 It compares elements with the equal member function.
441 Two elements with the same hash may not be equal.
442 Use typed_pointer_equal <Value> when hashing pointers instead of objects.
444 It removes elements with the remove member function.
445 This feature is useful for freeing memory.
446 Derive from typed_null_remove <Value> when not freeing objects.
447 Derive from typed_free_remove <Value> when doing a simple object free.
449 Specify the template Allocator to allocate and free memory.
450 The default is xcallocator.
452 Storage is an implementation detail and should not be used outside the
456 template <typename Descriptor
,
457 template<typename Type
> class Allocator
= xcallocator
>
460 typedef typename
Descriptor::value_type value_type
;
461 typedef typename
Descriptor::compare_type compare_type
;
464 explicit hash_table (size_t, bool ggc
= false, bool gather_mem_stats
= true,
465 mem_alloc_origin origin
= HASH_TABLE_ORIGIN
469 /* Create a hash_table in gc memory. */
472 create_ggc (size_t n CXX_MEM_STAT_INFO
)
474 hash_table
*table
= ggc_alloc
<hash_table
> ();
475 new (table
) hash_table (n
, true, true, HASH_TABLE_ORIGIN PASS_MEM_STAT
);
479 /* Current size (in entries) of the hash table. */
480 size_t size () const { return m_size
; }
482 /* Return the current number of elements in this hash table. */
483 size_t elements () const { return m_n_elements
- m_n_deleted
; }
485 /* Return the current number of elements in this hash table. */
486 size_t elements_with_deleted () const { return m_n_elements
; }
488 /* This function clears all entries in the given hash table. */
491 /* This function clears a specified SLOT in a hash table. It is
492 useful when you've already done the lookup and don't want to do it
495 void clear_slot (value_type
*);
497 /* This function searches for a hash table entry equal to the given
498 COMPARABLE element starting with the given HASH value. It cannot
499 be used to insert or delete an element. */
500 value_type
&find_with_hash (const compare_type
&, hashval_t
);
502 /* Like find_slot_with_hash, but compute the hash value from the element. */
503 value_type
&find (const value_type
&value
)
505 return find_with_hash (value
, Descriptor::hash (value
));
508 value_type
*find_slot (const value_type
&value
, insert_option insert
)
510 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
513 /* This function searches for a hash table slot containing an entry
514 equal to the given COMPARABLE element and starting with the given
515 HASH. To delete an entry, call this with insert=NO_INSERT, then
516 call clear_slot on the slot returned (possibly after doing some
517 checks). To insert an entry, call this with insert=INSERT, then
518 write the value you want into the returned slot. When inserting an
519 entry, NULL may be returned if memory allocation fails. */
520 value_type
*find_slot_with_hash (const compare_type
&comparable
,
521 hashval_t hash
, enum insert_option insert
);
523 /* This function deletes an element with the given COMPARABLE value
524 from hash table starting with the given HASH. If there is no
525 matching element in the hash table, this function does nothing. */
526 void remove_elt_with_hash (const compare_type
&, hashval_t
);
528 /* Like remove_elt_with_hash, but compute the hash value from the element. */
529 void remove_elt (const value_type
&value
)
531 remove_elt_with_hash (value
, Descriptor::hash (value
));
534 /* This function scans over the entire hash table calling CALLBACK for
535 each live entry. If CALLBACK returns false, the iteration stops.
536 ARGUMENT is passed as CALLBACK's second argument. */
537 template <typename Argument
,
538 int (*Callback
) (value_type
*slot
, Argument argument
)>
539 void traverse_noresize (Argument argument
);
541 /* Like traverse_noresize, but does resize the table when it is too empty
542 to improve effectivity of subsequent calls. */
543 template <typename Argument
,
544 int (*Callback
) (value_type
*slot
, Argument argument
)>
545 void traverse (Argument argument
);
550 iterator () : m_slot (NULL
), m_limit (NULL
) {}
552 iterator (value_type
*slot
, value_type
*limit
) :
553 m_slot (slot
), m_limit (limit
) {}
555 inline value_type
&operator * () { return *m_slot
; }
557 inline iterator
&operator ++ ();
558 bool operator != (const iterator
&other
) const
560 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
568 iterator
begin () const
570 iterator
iter (m_entries
, m_entries
+ m_size
);
575 iterator
end () const { return iterator (); }
577 double collisions () const
579 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
583 template<typename T
> friend void gt_ggc_mx (hash_table
<T
> *);
584 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *);
585 template<typename T
> friend void
586 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator
, void *);
587 template<typename T
, typename U
, typename V
> friend void
588 gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
589 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *,
592 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *,
593 gt_pointer_operator
, void *);
595 template<typename T
> friend void gt_cleare_cache (hash_table
<T
> *);
597 value_type
*alloc_entries (size_t n CXX_MEM_STAT_INFO
) const;
598 value_type
*find_empty_slot_for_expand (hashval_t
);
600 static bool is_deleted (value_type
&v
)
602 return is_deleted_helper
<value_type
, Descriptor
>::call (v
);
604 static bool is_empty (value_type
&v
)
606 return is_empty_helper
<value_type
, Descriptor
>::call (v
);
609 static void mark_deleted (value_type
&v
)
611 return mark_deleted_helper
<value_type
, Descriptor
>::call (v
);
614 static void mark_empty (value_type
&v
)
616 return mark_empty_helper
<value_type
, Descriptor
>::call (v
);
620 typename
Descriptor::value_type
*m_entries
;
624 /* Current number of elements including also deleted elements. */
627 /* Current number of deleted elements in the table. */
630 /* The following member is used for debugging. Its value is number
631 of all calls of `htab_find_slot' for the hash table. */
632 unsigned int m_searches
;
634 /* The following member is used for debugging. Its value is number
635 of collisions fixed for time of work with the hash table. */
636 unsigned int m_collisions
;
638 /* Current size (in entries) of the hash table, as an index into the
640 unsigned int m_size_prime_index
;
642 /* if m_entries is stored in ggc memory. */
645 /* If we should gather memory statistics for the table. */
646 bool m_gather_mem_stats
;
649 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
650 mem-stats.h after hash_table declaration. */
652 #include "mem-stats.h"
653 #include "hash-map.h"
655 extern mem_alloc_description
<mem_usage
> hash_table_usage
;
657 /* Support function for statistics. */
658 extern void dump_hash_table_loc_statistics (void);
660 template<typename Descriptor
, template<typename Type
> class Allocator
>
661 hash_table
<Descriptor
, Allocator
>::hash_table (size_t size
, bool ggc
, bool
663 mem_alloc_origin origin
665 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
666 m_ggc (ggc
), m_gather_mem_stats (gather_mem_stats
)
668 unsigned int size_prime_index
;
670 size_prime_index
= hash_table_higher_prime_index (size
);
671 size
= prime_tab
[size_prime_index
].prime
;
673 if (m_gather_mem_stats
)
674 hash_table_usage
.register_descriptor (this, origin
, ggc
675 FINAL_PASS_MEM_STAT
);
677 m_entries
= alloc_entries (size PASS_MEM_STAT
);
679 m_size_prime_index
= size_prime_index
;
682 template<typename Descriptor
, template<typename Type
> class Allocator
>
683 hash_table
<Descriptor
, Allocator
>::~hash_table ()
685 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
686 if (!is_empty (m_entries
[i
]) && !is_deleted (m_entries
[i
]))
687 Descriptor::remove (m_entries
[i
]);
690 Allocator
<value_type
> ::data_free (m_entries
);
692 ggc_free (m_entries
);
694 if (m_gather_mem_stats
)
695 hash_table_usage
.release_instance_overhead (this,
696 sizeof (value_type
) * m_size
,
700 /* This function returns an array of empty hash table elements. */
702 template<typename Descriptor
, template<typename Type
> class Allocator
>
703 inline typename hash_table
<Descriptor
, Allocator
>::value_type
*
704 hash_table
<Descriptor
, Allocator
>::alloc_entries (size_t n MEM_STAT_DECL
) const
706 value_type
*nentries
;
708 if (m_gather_mem_stats
)
709 hash_table_usage
.register_instance_overhead (sizeof (value_type
) * n
, this);
712 nentries
= Allocator
<value_type
> ::data_alloc (n
);
714 nentries
= ::ggc_cleared_vec_alloc
<value_type
> (n PASS_MEM_STAT
);
716 gcc_assert (nentries
!= NULL
);
717 for (size_t i
= 0; i
< n
; i
++)
718 mark_empty (nentries
[i
]);
723 /* Similar to find_slot, but without several unwanted side effects:
724 - Does not call equal when it finds an existing entry.
725 - Does not change the count of elements/searches/collisions in the
727 This function also assumes there are no deleted entries in the table.
728 HASH is the hash value for the element to be inserted. */
730 template<typename Descriptor
, template<typename Type
> class Allocator
>
731 typename hash_table
<Descriptor
, Allocator
>::value_type
*
732 hash_table
<Descriptor
, Allocator
>::find_empty_slot_for_expand (hashval_t hash
)
734 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
735 size_t size
= m_size
;
736 value_type
*slot
= m_entries
+ index
;
739 if (is_empty (*slot
))
741 #ifdef ENABLE_CHECKING
742 gcc_checking_assert (!is_deleted (*slot
));
745 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
752 slot
= m_entries
+ index
;
753 if (is_empty (*slot
))
755 #ifdef ENABLE_CHECKING
756 gcc_checking_assert (!is_deleted (*slot
));
761 /* The following function changes size of memory allocated for the
762 entries and repeatedly inserts the table elements. The occupancy
763 of the table after the call will be about 50%. Naturally the hash
764 table must already exist. Remember also that the place of the
765 table entries is changed. If memory allocation fails, this function
768 template<typename Descriptor
, template<typename Type
> class Allocator
>
770 hash_table
<Descriptor
, Allocator
>::expand ()
772 value_type
*oentries
= m_entries
;
773 unsigned int oindex
= m_size_prime_index
;
774 size_t osize
= size ();
775 value_type
*olimit
= oentries
+ osize
;
776 size_t elts
= elements ();
778 /* Resize only when table after removal of unused elements is either
779 too full or too empty. */
782 if (elts
* 2 > osize
|| (elts
* 8 < osize
&& osize
> 32))
784 nindex
= hash_table_higher_prime_index (elts
* 2);
785 nsize
= prime_tab
[nindex
].prime
;
793 value_type
*nentries
= alloc_entries (nsize
);
795 if (m_gather_mem_stats
)
796 hash_table_usage
.release_instance_overhead (this, sizeof (value_type
)
799 m_entries
= nentries
;
801 m_size_prime_index
= nindex
;
802 m_n_elements
-= m_n_deleted
;
805 value_type
*p
= oentries
;
810 if (!is_empty (x
) && !is_deleted (x
))
812 value_type
*q
= find_empty_slot_for_expand (Descriptor::hash (x
));
822 Allocator
<value_type
> ::data_free (oentries
);
827 template<typename Descriptor
, template<typename Type
> class Allocator
>
829 hash_table
<Descriptor
, Allocator
>::empty ()
831 size_t size
= m_size
;
832 value_type
*entries
= m_entries
;
835 for (i
= size
- 1; i
>= 0; i
--)
836 if (!is_empty (entries
[i
]) && !is_deleted (entries
[i
]))
837 Descriptor::remove (entries
[i
]);
839 /* Instead of clearing megabyte, downsize the table. */
840 if (size
> 1024*1024 / sizeof (PTR
))
842 int nindex
= hash_table_higher_prime_index (1024 / sizeof (PTR
));
843 int nsize
= prime_tab
[nindex
].prime
;
846 Allocator
<value_type
> ::data_free (m_entries
);
848 ggc_free (m_entries
);
850 m_entries
= alloc_entries (nsize
);
852 m_size_prime_index
= nindex
;
855 memset (entries
, 0, size
* sizeof (value_type
));
860 /* This function clears a specified SLOT in a hash table. It is
861 useful when you've already done the lookup and don't want to do it
864 template<typename Descriptor
, template<typename Type
> class Allocator
>
866 hash_table
<Descriptor
, Allocator
>::clear_slot (value_type
*slot
)
868 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
869 || is_empty (*slot
) || is_deleted (*slot
)));
871 Descriptor::remove (*slot
);
873 mark_deleted (*slot
);
877 /* This function searches for a hash table entry equal to the given
878 COMPARABLE element starting with the given HASH value. It cannot
879 be used to insert or delete an element. */
881 template<typename Descriptor
, template<typename Type
> class Allocator
>
882 typename hash_table
<Descriptor
, Allocator
>::value_type
&
883 hash_table
<Descriptor
, Allocator
>
884 ::find_with_hash (const compare_type
&comparable
, hashval_t hash
)
887 size_t size
= m_size
;
888 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
890 value_type
*entry
= &m_entries
[index
];
891 if (is_empty (*entry
)
892 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
895 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
903 entry
= &m_entries
[index
];
904 if (is_empty (*entry
)
905 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
910 /* This function searches for a hash table slot containing an entry
911 equal to the given COMPARABLE element and starting with the given
912 HASH. To delete an entry, call this with insert=NO_INSERT, then
913 call clear_slot on the slot returned (possibly after doing some
914 checks). To insert an entry, call this with insert=INSERT, then
915 write the value you want into the returned slot. When inserting an
916 entry, NULL may be returned if memory allocation fails. */
918 template<typename Descriptor
, template<typename Type
> class Allocator
>
919 typename hash_table
<Descriptor
, Allocator
>::value_type
*
920 hash_table
<Descriptor
, Allocator
>
921 ::find_slot_with_hash (const compare_type
&comparable
, hashval_t hash
,
922 enum insert_option insert
)
924 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
929 value_type
*first_deleted_slot
= NULL
;
930 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
931 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
932 value_type
*entry
= &m_entries
[index
];
933 size_t size
= m_size
;
934 if (is_empty (*entry
))
936 else if (is_deleted (*entry
))
937 first_deleted_slot
= &m_entries
[index
];
938 else if (Descriptor::equal (*entry
, comparable
))
939 return &m_entries
[index
];
948 entry
= &m_entries
[index
];
949 if (is_empty (*entry
))
951 else if (is_deleted (*entry
))
953 if (!first_deleted_slot
)
954 first_deleted_slot
= &m_entries
[index
];
956 else if (Descriptor::equal (*entry
, comparable
))
957 return &m_entries
[index
];
961 if (insert
== NO_INSERT
)
964 if (first_deleted_slot
)
967 mark_empty (*first_deleted_slot
);
968 return first_deleted_slot
;
972 return &m_entries
[index
];
975 /* This function deletes an element with the given COMPARABLE value
976 from hash table starting with the given HASH. If there is no
977 matching element in the hash table, this function does nothing. */
979 template<typename Descriptor
, template<typename Type
> class Allocator
>
981 hash_table
<Descriptor
, Allocator
>
982 ::remove_elt_with_hash (const compare_type
&comparable
, hashval_t hash
)
984 value_type
*slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
985 if (is_empty (*slot
))
988 Descriptor::remove (*slot
);
990 mark_deleted (*slot
);
994 /* This function scans over the entire hash table calling CALLBACK for
995 each live entry. If CALLBACK returns false, the iteration stops.
996 ARGUMENT is passed as CALLBACK's second argument. */
998 template<typename Descriptor
,
999 template<typename Type
> class Allocator
>
1000 template<typename Argument
,
1002 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
1005 hash_table
<Descriptor
, Allocator
>::traverse_noresize (Argument argument
)
1007 value_type
*slot
= m_entries
;
1008 value_type
*limit
= slot
+ size ();
1012 value_type
&x
= *slot
;
1014 if (!is_empty (x
) && !is_deleted (x
))
1015 if (! Callback (slot
, argument
))
1018 while (++slot
< limit
);
1021 /* Like traverse_noresize, but does resize the table when it is too empty
1022 to improve effectivity of subsequent calls. */
1024 template <typename Descriptor
,
1025 template <typename Type
> class Allocator
>
1026 template <typename Argument
,
1028 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
1031 hash_table
<Descriptor
, Allocator
>::traverse (Argument argument
)
1033 size_t size
= m_size
;
1034 if (elements () * 8 < size
&& size
> 32)
1037 traverse_noresize
<Argument
, Callback
> (argument
);
1040 /* Slide down the iterator slots until an active entry is found. */
1042 template<typename Descriptor
, template<typename Type
> class Allocator
>
1044 hash_table
<Descriptor
, Allocator
>::iterator::slide ()
1046 for ( ; m_slot
< m_limit
; ++m_slot
)
1048 value_type
&x
= *m_slot
;
1049 if (!is_empty (x
) && !is_deleted (x
))
1056 /* Bump the iterator. */
1058 template<typename Descriptor
, template<typename Type
> class Allocator
>
1059 inline typename hash_table
<Descriptor
, Allocator
>::iterator
&
1060 hash_table
<Descriptor
, Allocator
>::iterator::operator ++ ()
1068 /* Iterate through the elements of hash_table HTAB,
1069 using hash_table <....>::iterator ITER,
1070 storing each element in RESULT, which is of type TYPE. */
1072 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1073 for ((ITER) = (HTAB).begin (); \
1074 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1077 /* ggc walking routines. */
1079 template<typename E
>
1081 gt_ggc_mx (hash_table
<E
> *h
)
1083 typedef hash_table
<E
> table
;
1085 if (!ggc_test_and_set_mark (h
->m_entries
))
1088 for (size_t i
= 0; i
< h
->m_size
; i
++)
1090 if (table::is_empty (h
->m_entries
[i
])
1091 || table::is_deleted (h
->m_entries
[i
]))
1094 E::ggc_mx (h
->m_entries
[i
]);
1098 template<typename D
>
1100 hashtab_entry_note_pointers (void *obj
, void *h
, gt_pointer_operator op
,
1103 hash_table
<D
> *map
= static_cast<hash_table
<D
> *> (h
);
1104 gcc_checking_assert (map
->m_entries
== obj
);
1105 for (size_t i
= 0; i
< map
->m_size
; i
++)
1107 typedef hash_table
<D
> table
;
1108 if (table::is_empty (map
->m_entries
[i
])
1109 || table::is_deleted (map
->m_entries
[i
]))
1112 D::pch_nx (map
->m_entries
[i
], op
, cookie
);
1116 template<typename D
>
1118 gt_pch_nx (hash_table
<D
> *h
)
1121 = gt_pch_note_object (h
->m_entries
, h
, hashtab_entry_note_pointers
<D
>);
1122 gcc_checking_assert (success
);
1123 for (size_t i
= 0; i
< h
->m_size
; i
++)
1125 if (hash_table
<D
>::is_empty (h
->m_entries
[i
])
1126 || hash_table
<D
>::is_deleted (h
->m_entries
[i
]))
1129 D::pch_nx (h
->m_entries
[i
]);
1133 template<typename D
>
1135 gt_pch_nx (hash_table
<D
> *h
, gt_pointer_operator op
, void *cookie
)
1137 op (&h
->m_entries
, cookie
);
1140 template<typename H
>
1142 gt_cleare_cache (hash_table
<H
> *h
)
1144 extern void gt_ggc_mx (typename
H::value_type
&t
);
1145 typedef hash_table
<H
> table
;
1149 for (typename
table::iterator iter
= h
->begin (); iter
!= h
->end (); ++iter
)
1150 if (!table::is_empty (*iter
) && !table::is_deleted (*iter
))
1152 int res
= H::keep_cache_entry (*iter
);
1154 h
->clear_slot (&*iter
);
1160 #endif /* TYPED_HASHTAB_H */