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 3. The type of the hash table itself. (More later.)
57 In very special circumstances, users may need to know about a fourth type.
59 4. The template type used to describe how hash table memory
60 is allocated. This type is called the allocator type. It is
61 parameterized on the value type. It provides four functions.
63 - A static member function named 'data_alloc'. This function
64 allocates the data elements in the table.
66 - A static member function named 'data_free'. This function
67 deallocates the data elements in the table.
69 Hash table are instantiated with two type arguments.
71 * The descriptor type, (2) above.
73 * The allocator type, (4) above. In general, you will not need to
74 provide your own allocator type. By default, hash tables will use
75 the class template xcallocator, which uses malloc/free for allocation.
78 DEFINING A DESCRIPTOR TYPE
80 The first task in using the hash table is to describe the element type.
81 We compose this into a few steps.
83 1. Decide on a removal policy for values stored in the table.
84 This header provides class templates for the two most common
87 * typed_free_remove implements the static 'remove' member function
90 * typed_noop_remove implements the static 'remove' member function
93 You can use these policies by simply deriving the descriptor type
94 from one of those class template, with the appropriate argument.
96 Otherwise, you need to write the static 'remove' member function
97 in the descriptor class.
99 2. Choose a hash function. Write the static 'hash' member function.
101 3. Choose an equality testing function. In most cases, its two
102 arguments will be value_type pointers. If not, the first argument must
103 be a value_type pointer, and the second argument a compare_type pointer.
106 AN EXAMPLE DESCRIPTOR TYPE
108 Suppose you want to put some_type into the hash table. You could define
109 the descriptor type as follows.
111 struct some_type_hasher : typed_noop_remove <some_type>
112 // Deriving from typed_noop_remove means that we get a 'remove' that does
113 // nothing. This choice is good for raw values.
115 typedef some_type value_type;
116 typedef some_type compare_type;
117 static inline hashval_t hash (const value_type *);
118 static inline bool equal (const value_type *, const compare_type *);
122 some_type_hasher::hash (const value_type *e)
123 { ... compute and return a hash value for E ... }
126 some_type_hasher::equal (const value_type *p1, const compare_type *p2)
127 { ... compare P1 vs P2. Return true if they are the 'same' ... }
130 AN EXAMPLE HASH_TABLE DECLARATION
132 To instantiate a hash table for some_type:
134 hash_table <some_type_hasher> some_type_hash_table;
136 There is no need to mention some_type directly, as the hash table will
137 obtain it using some_type_hasher::value_type.
139 You can then used any of the functions in hash_table's public interface.
140 See hash_table for details. The interface is very similar to libiberty's
144 EASY DESCRIPTORS FOR POINTERS
146 The class template pointer_hash provides everything you need to hash
147 pointers (as opposed to what they point to). So, to instantiate a hash
148 table over pointers to whatever_type,
150 hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
155 The hash table provides standard C++ iterators. For example, consider a
156 hash table of some_info. We wish to consume each element of the table:
158 extern void consume (some_info *);
160 We define a convenience typedef and the hash table:
162 typedef hash_table <some_info_hasher> info_table_type;
163 info_table_type info_table;
165 Then we write the loop in typical C++ style:
167 for (info_table_type::iterator iter = info_table.begin ();
168 iter != info_table.end ();
170 if ((*iter).status == INFO_READY)
173 Or with common sub-expression elimination:
175 for (info_table_type::iterator iter = info_table.begin ();
176 iter != info_table.end ();
179 some_info &elem = *iter;
180 if (elem.status == INFO_READY)
184 One can also use a more typical GCC style:
186 typedef some_info *some_info_p;
188 info_table_type::iterator iter;
189 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
190 if (elem_ptr->status == INFO_READY)
196 #ifndef TYPED_HASHTAB_H
197 #define TYPED_HASHTAB_H
203 template<typename
, typename
, typename
> class hash_map
;
204 template<typename
, typename
> class hash_set
;
206 /* The ordinary memory allocator. */
207 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
209 template <typename Type
>
212 static Type
*data_alloc (size_t count
);
213 static void data_free (Type
*memory
);
217 /* Allocate memory for COUNT data blocks. */
219 template <typename Type
>
221 xcallocator
<Type
>::data_alloc (size_t count
)
223 return static_cast <Type
*> (xcalloc (count
, sizeof (Type
)));
227 /* Free memory for data blocks. */
229 template <typename Type
>
231 xcallocator
<Type
>::data_free (Type
*memory
)
233 return ::free (memory
);
237 /* Helpful type for removing with free. */
239 template <typename Type
>
240 struct typed_free_remove
242 static inline void remove (Type
*p
);
246 /* Remove with free. */
248 template <typename Type
>
250 typed_free_remove
<Type
>::remove (Type
*p
)
256 /* Helpful type for a no-op remove. */
258 template <typename Type
>
259 struct typed_noop_remove
261 static inline void remove (Type
*p
);
265 /* Remove doing nothing. */
267 template <typename Type
>
269 typed_noop_remove
<Type
>::remove (Type
*p ATTRIBUTE_UNUSED
)
274 /* Pointer hash with a no-op remove method. */
276 template <typename Type
>
277 struct pointer_hash
: typed_noop_remove
<Type
>
279 typedef Type
*value_type
;
280 typedef Type
*compare_type
;
282 static inline hashval_t
hash (const value_type
&);
284 static inline bool equal (const value_type
&existing
,
285 const compare_type
&candidate
);
288 template <typename Type
>
290 pointer_hash
<Type
>::hash (const value_type
&candidate
)
292 /* This is a really poor hash function, but it is what the current code uses,
293 so I am reusing it to avoid an additional axis in testing. */
294 return (hashval_t
) ((intptr_t)candidate
>> 3);
297 template <typename Type
>
299 pointer_hash
<Type
>::equal (const value_type
&existing
,
300 const compare_type
&candidate
)
302 return existing
== candidate
;
305 /* Hasher for entry in gc memory. */
310 typedef T value_type
;
311 typedef T compare_type
;
313 static void remove (T
) {}
318 extern void gt_ggc_mx (T
&);
325 extern void gt_pch_nx (T
&);
330 pch_nx (T
&p
, gt_pointer_operator op
, void *cookie
)
336 /* Hasher for cache entry in gc memory. */
339 struct ggc_cache_hasher
341 typedef T value_type
;
342 typedef T compare_type
;
344 static void remove (T
&) {}
346 /* Entries are weakly held because this is for caches. */
348 static void ggc_mx (T
&) {}
353 extern void gt_pch_nx (T
&);
358 pch_nx (T
&p
, gt_pointer_operator op
, void *cookie
)
363 /* Clear out entries if they are about to be gc'd. */
366 handle_cache_entry (T
&e
)
368 if (e
!= HTAB_EMPTY_ENTRY
&& e
!= HTAB_DELETED_ENTRY
&& !ggc_marked_p (e
))
369 e
= static_cast<T
> (HTAB_DELETED_ENTRY
);
374 /* Table of primes and their inversion information. */
380 hashval_t inv_m2
; /* inverse of prime-2 */
384 extern struct prime_ent
const prime_tab
[];
387 /* Functions for computing hash table indexes. */
389 extern unsigned int hash_table_higher_prime_index (unsigned long n
)
392 /* Return X % Y using multiplicative inverse values INV and SHIFT.
394 The multiplicative inverses computed above are for 32-bit types,
395 and requires that we be able to compute a highpart multiply.
397 FIX: I am not at all convinced that
398 3 loads, 2 multiplications, 3 shifts, and 3 additions
401 on modern systems running a compiler. */
404 mul_mod (hashval_t x
, hashval_t y
, hashval_t inv
, int shift
)
406 hashval_t t1
, t2
, t3
, t4
, q
, r
;
408 t1
= ((uint64_t)x
* inv
) >> 32;
418 /* Compute the primary table index for HASH given current prime index. */
421 hash_table_mod1 (hashval_t hash
, unsigned int index
)
423 const struct prime_ent
*p
= &prime_tab
[index
];
424 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
425 return mul_mod (hash
, p
->prime
, p
->inv
, p
->shift
);
428 /* Compute the secondary table index for HASH given current prime index. */
431 hash_table_mod2 (hashval_t hash
, unsigned int index
)
433 const struct prime_ent
*p
= &prime_tab
[index
];
434 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
435 return 1 + mul_mod (hash
, p
->prime
- 2, p
->inv_m2
, p
->shift
);
438 template<typename Traits
>
439 struct has_is_deleted
441 template<typename U
, bool (*)(U
&)> struct helper
{};
442 template<typename U
> static char test (helper
<U
, U::is_deleted
> *);
443 template<typename U
> static int test (...);
444 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
447 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
448 struct is_deleted_helper
453 return Traits::is_deleted (v
);
457 template<typename Type
, typename Traits
>
458 struct is_deleted_helper
<Type
*, Traits
, false>
463 return v
== HTAB_DELETED_ENTRY
;
467 template<typename Traits
>
470 template<typename U
, bool (*)(U
&)> struct helper
{};
471 template<typename U
> static char test (helper
<U
, U::is_empty
> *);
472 template<typename U
> static int test (...);
473 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
476 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
477 struct is_empty_helper
482 return Traits::is_empty (v
);
486 template<typename Type
, typename Traits
>
487 struct is_empty_helper
<Type
*, Traits
, false>
492 return v
== HTAB_EMPTY_ENTRY
;
496 template<typename Traits
>
497 struct has_mark_deleted
499 template<typename U
, void (*)(U
&)> struct helper
{};
500 template<typename U
> static char test (helper
<U
, U::mark_deleted
> *);
501 template<typename U
> static int test (...);
502 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
505 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
506 struct mark_deleted_helper
511 Traits::mark_deleted (v
);
515 template<typename Type
, typename Traits
>
516 struct mark_deleted_helper
<Type
*, Traits
, false>
521 v
= static_cast<Type
*> (HTAB_DELETED_ENTRY
);
525 template<typename Traits
>
526 struct has_mark_empty
528 template<typename U
, void (*)(U
&)> struct helper
{};
529 template<typename U
> static char test (helper
<U
, U::mark_empty
> *);
530 template<typename U
> static int test (...);
531 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
534 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
535 struct mark_empty_helper
540 Traits::mark_empty (v
);
544 template<typename Type
, typename Traits
>
545 struct mark_empty_helper
<Type
*, Traits
, false>
550 v
= static_cast<Type
*> (HTAB_EMPTY_ENTRY
);
554 /* User-facing hash table type.
556 The table stores elements of type Descriptor::value_type.
558 It hashes values with the hash member function.
559 The table currently works with relatively weak hash functions.
560 Use typed_pointer_hash <Value> when hashing pointers instead of objects.
562 It compares elements with the equal member function.
563 Two elements with the same hash may not be equal.
564 Use typed_pointer_equal <Value> when hashing pointers instead of objects.
566 It removes elements with the remove member function.
567 This feature is useful for freeing memory.
568 Derive from typed_null_remove <Value> when not freeing objects.
569 Derive from typed_free_remove <Value> when doing a simple object free.
571 Specify the template Allocator to allocate and free memory.
572 The default is xcallocator.
574 Storage is an implementation detail and should not be used outside the
578 template <typename Descriptor
,
579 template<typename Type
> class Allocator
= xcallocator
>
582 typedef typename
Descriptor::value_type value_type
;
583 typedef typename
Descriptor::compare_type compare_type
;
586 explicit hash_table (size_t, bool ggc
= false CXX_MEM_STAT_INFO
);
589 /* Create a hash_table in gc memory. */
592 create_ggc (size_t n
)
594 hash_table
*table
= ggc_alloc
<hash_table
> ();
595 new (table
) hash_table (n
, true);
599 /* Current size (in entries) of the hash table. */
600 size_t size () const { return m_size
; }
602 /* Return the current number of elements in this hash table. */
603 size_t elements () const { return m_n_elements
- m_n_deleted
; }
605 /* Return the current number of elements in this hash table. */
606 size_t elements_with_deleted () const { return m_n_elements
; }
608 /* This function clears all entries in the given hash table. */
611 /* This function clears a specified SLOT in a hash table. It is
612 useful when you've already done the lookup and don't want to do it
615 void clear_slot (value_type
*);
617 /* This function searches for a hash table entry equal to the given
618 COMPARABLE element starting with the given HASH value. It cannot
619 be used to insert or delete an element. */
620 value_type
&find_with_hash (const compare_type
&, hashval_t
);
622 /* Like find_slot_with_hash, but compute the hash value from the element. */
623 value_type
&find (const value_type
&value
)
625 return find_with_hash (value
, Descriptor::hash (value
));
628 value_type
*find_slot (const value_type
&value
, insert_option insert
)
630 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
633 /* This function searches for a hash table slot containing an entry
634 equal to the given COMPARABLE element and starting with the given
635 HASH. To delete an entry, call this with insert=NO_INSERT, then
636 call clear_slot on the slot returned (possibly after doing some
637 checks). To insert an entry, call this with insert=INSERT, then
638 write the value you want into the returned slot. When inserting an
639 entry, NULL may be returned if memory allocation fails. */
640 value_type
*find_slot_with_hash (const compare_type
&comparable
,
641 hashval_t hash
, enum insert_option insert
);
643 /* This function deletes an element with the given COMPARABLE value
644 from hash table starting with the given HASH. If there is no
645 matching element in the hash table, this function does nothing. */
646 void remove_elt_with_hash (const compare_type
&, hashval_t
);
648 /* Like remove_elt_with_hash, but compute the hash value from the element. */
649 void remove_elt (const value_type
&value
)
651 remove_elt_with_hash (value
, Descriptor::hash (value
));
654 /* This function scans over the entire hash table calling CALLBACK for
655 each live entry. If CALLBACK returns false, the iteration stops.
656 ARGUMENT is passed as CALLBACK's second argument. */
657 template <typename Argument
,
658 int (*Callback
) (value_type
*slot
, Argument argument
)>
659 void traverse_noresize (Argument argument
);
661 /* Like traverse_noresize, but does resize the table when it is too empty
662 to improve effectivity of subsequent calls. */
663 template <typename Argument
,
664 int (*Callback
) (value_type
*slot
, Argument argument
)>
665 void traverse (Argument argument
);
670 iterator () : m_slot (NULL
), m_limit (NULL
) {}
672 iterator (value_type
*slot
, value_type
*limit
) :
673 m_slot (slot
), m_limit (limit
) {}
675 inline value_type
&operator * () { return *m_slot
; }
677 inline iterator
&operator ++ ();
678 bool operator != (const iterator
&other
) const
680 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
688 iterator
begin () const
690 iterator
iter (m_entries
, m_entries
+ m_size
);
695 iterator
end () const { return iterator (); }
697 double collisions () const
699 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
703 template<typename T
> friend void gt_ggc_mx (hash_table
<T
> *);
704 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *);
705 template<typename T
> friend void
706 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator
, void *);
707 template<typename T
, typename U
, typename V
> friend void
708 gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
709 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *,
712 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *,
713 gt_pointer_operator
, void *);
715 value_type
*alloc_entries (size_t n CXX_MEM_STAT_INFO
) const;
716 value_type
*find_empty_slot_for_expand (hashval_t
);
718 static bool is_deleted (value_type
&v
)
720 return is_deleted_helper
<value_type
, Descriptor
>::call (v
);
722 static bool is_empty (value_type
&v
)
724 return is_empty_helper
<value_type
, Descriptor
>::call (v
);
727 static void mark_deleted (value_type
&v
)
729 return mark_deleted_helper
<value_type
, Descriptor
>::call (v
);
732 static void mark_empty (value_type
&v
)
734 return mark_empty_helper
<value_type
, Descriptor
>::call (v
);
738 typename
Descriptor::value_type
*m_entries
;
742 /* Current number of elements including also deleted elements. */
745 /* Current number of deleted elements in the table. */
748 /* The following member is used for debugging. Its value is number
749 of all calls of `htab_find_slot' for the hash table. */
750 unsigned int m_searches
;
752 /* The following member is used for debugging. Its value is number
753 of collisions fixed for time of work with the hash table. */
754 unsigned int m_collisions
;
756 /* Current size (in entries) of the hash table, as an index into the
758 unsigned int m_size_prime_index
;
760 /* if m_entries is stored in ggc memory. */
764 template<typename Descriptor
, template<typename Type
> class Allocator
>
765 hash_table
<Descriptor
, Allocator
>::hash_table (size_t size
, bool ggc
767 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
770 unsigned int size_prime_index
;
772 size_prime_index
= hash_table_higher_prime_index (size
);
773 size
= prime_tab
[size_prime_index
].prime
;
775 m_entries
= alloc_entries (size PASS_MEM_STAT
);
777 m_size_prime_index
= size_prime_index
;
780 template<typename Descriptor
, template<typename Type
> class Allocator
>
781 hash_table
<Descriptor
, Allocator
>::~hash_table ()
783 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
784 if (!is_empty (m_entries
[i
]) && !is_deleted (m_entries
[i
]))
785 Descriptor::remove (m_entries
[i
]);
788 Allocator
<value_type
> ::data_free (m_entries
);
790 ggc_free (m_entries
);
793 /* This function returns an array of empty hash table elements. */
795 template<typename Descriptor
, template<typename Type
> class Allocator
>
796 inline typename hash_table
<Descriptor
, Allocator
>::value_type
*
797 hash_table
<Descriptor
, Allocator
>::alloc_entries (size_t n MEM_STAT_DECL
) const
799 value_type
*nentries
;
802 nentries
= Allocator
<value_type
> ::data_alloc (n
);
804 nentries
= ::ggc_cleared_vec_alloc
<value_type
> (n PASS_MEM_STAT
);
806 gcc_assert (nentries
!= NULL
);
807 for (size_t i
= 0; i
< n
; i
++)
808 mark_empty (nentries
[i
]);
813 /* Similar to find_slot, but without several unwanted side effects:
814 - Does not call equal when it finds an existing entry.
815 - Does not change the count of elements/searches/collisions in the
817 This function also assumes there are no deleted entries in the table.
818 HASH is the hash value for the element to be inserted. */
820 template<typename Descriptor
, template<typename Type
> class Allocator
>
821 typename hash_table
<Descriptor
, Allocator
>::value_type
*
822 hash_table
<Descriptor
, Allocator
>::find_empty_slot_for_expand (hashval_t hash
)
824 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
825 size_t size
= m_size
;
826 value_type
*slot
= m_entries
+ index
;
829 if (is_empty (*slot
))
831 #ifdef ENABLE_CHECKING
832 gcc_checking_assert (!is_deleted (*slot
));
835 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
842 slot
= m_entries
+ index
;
843 if (is_empty (*slot
))
845 #ifdef ENABLE_CHECKING
846 gcc_checking_assert (!is_deleted (*slot
));
851 /* The following function changes size of memory allocated for the
852 entries and repeatedly inserts the table elements. The occupancy
853 of the table after the call will be about 50%. Naturally the hash
854 table must already exist. Remember also that the place of the
855 table entries is changed. If memory allocation fails, this function
858 template<typename Descriptor
, template<typename Type
> class Allocator
>
860 hash_table
<Descriptor
, Allocator
>::expand ()
862 value_type
*oentries
= m_entries
;
863 unsigned int oindex
= m_size_prime_index
;
864 size_t osize
= size ();
865 value_type
*olimit
= oentries
+ osize
;
866 size_t elts
= elements ();
868 /* Resize only when table after removal of unused elements is either
869 too full or too empty. */
872 if (elts
* 2 > osize
|| (elts
* 8 < osize
&& osize
> 32))
874 nindex
= hash_table_higher_prime_index (elts
* 2);
875 nsize
= prime_tab
[nindex
].prime
;
883 value_type
*nentries
= alloc_entries (nsize
);
884 m_entries
= nentries
;
886 m_size_prime_index
= nindex
;
887 m_n_elements
-= m_n_deleted
;
890 value_type
*p
= oentries
;
895 if (!is_empty (x
) && !is_deleted (x
))
897 value_type
*q
= find_empty_slot_for_expand (Descriptor::hash (x
));
907 Allocator
<value_type
> ::data_free (oentries
);
912 template<typename Descriptor
, template<typename Type
> class Allocator
>
914 hash_table
<Descriptor
, Allocator
>::empty ()
916 size_t size
= m_size
;
917 value_type
*entries
= m_entries
;
920 for (i
= size
- 1; i
>= 0; i
--)
921 if (!is_empty (entries
[i
]) && !is_deleted (entries
[i
]))
922 Descriptor::remove (entries
[i
]);
924 /* Instead of clearing megabyte, downsize the table. */
925 if (size
> 1024*1024 / sizeof (PTR
))
927 int nindex
= hash_table_higher_prime_index (1024 / sizeof (PTR
));
928 int nsize
= prime_tab
[nindex
].prime
;
931 Allocator
<value_type
> ::data_free (m_entries
);
933 ggc_free (m_entries
);
935 m_entries
= alloc_entries (nsize
);
937 m_size_prime_index
= nindex
;
940 memset (entries
, 0, size
* sizeof (value_type
));
945 /* This function clears a specified SLOT in a hash table. It is
946 useful when you've already done the lookup and don't want to do it
949 template<typename Descriptor
, template<typename Type
> class Allocator
>
951 hash_table
<Descriptor
, Allocator
>::clear_slot (value_type
*slot
)
953 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
954 || is_empty (*slot
) || is_deleted (*slot
)));
956 Descriptor::remove (*slot
);
958 mark_deleted (*slot
);
962 /* This function searches for a hash table entry equal to the given
963 COMPARABLE element starting with the given HASH value. It cannot
964 be used to insert or delete an element. */
966 template<typename Descriptor
, template<typename Type
> class Allocator
>
967 typename hash_table
<Descriptor
, Allocator
>::value_type
&
968 hash_table
<Descriptor
, Allocator
>
969 ::find_with_hash (const compare_type
&comparable
, hashval_t hash
)
972 size_t size
= m_size
;
973 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
975 value_type
*entry
= &m_entries
[index
];
976 if (is_empty (*entry
)
977 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
980 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
988 entry
= &m_entries
[index
];
989 if (is_empty (*entry
)
990 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
995 /* This function searches for a hash table slot containing an entry
996 equal to the given COMPARABLE element and starting with the given
997 HASH. To delete an entry, call this with insert=NO_INSERT, then
998 call clear_slot on the slot returned (possibly after doing some
999 checks). To insert an entry, call this with insert=INSERT, then
1000 write the value you want into the returned slot. When inserting an
1001 entry, NULL may be returned if memory allocation fails. */
1003 template<typename Descriptor
, template<typename Type
> class Allocator
>
1004 typename hash_table
<Descriptor
, Allocator
>::value_type
*
1005 hash_table
<Descriptor
, Allocator
>
1006 ::find_slot_with_hash (const compare_type
&comparable
, hashval_t hash
,
1007 enum insert_option insert
)
1009 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
1014 value_type
*first_deleted_slot
= NULL
;
1015 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
1016 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
1017 value_type
*entry
= &m_entries
[index
];
1018 size_t size
= m_size
;
1019 if (is_empty (*entry
))
1021 else if (is_deleted (*entry
))
1022 first_deleted_slot
= &m_entries
[index
];
1023 else if (Descriptor::equal (*entry
, comparable
))
1024 return &m_entries
[index
];
1033 entry
= &m_entries
[index
];
1034 if (is_empty (*entry
))
1036 else if (is_deleted (*entry
))
1038 if (!first_deleted_slot
)
1039 first_deleted_slot
= &m_entries
[index
];
1041 else if (Descriptor::equal (*entry
, comparable
))
1042 return &m_entries
[index
];
1046 if (insert
== NO_INSERT
)
1049 if (first_deleted_slot
)
1052 mark_empty (*first_deleted_slot
);
1053 return first_deleted_slot
;
1057 return &m_entries
[index
];
1060 /* This function deletes an element with the given COMPARABLE value
1061 from hash table starting with the given HASH. If there is no
1062 matching element in the hash table, this function does nothing. */
1064 template<typename Descriptor
, template<typename Type
> class Allocator
>
1066 hash_table
<Descriptor
, Allocator
>
1067 ::remove_elt_with_hash (const compare_type
&comparable
, hashval_t hash
)
1069 value_type
*slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
1070 if (is_empty (*slot
))
1073 Descriptor::remove (*slot
);
1075 mark_deleted (*slot
);
1079 /* This function scans over the entire hash table calling CALLBACK for
1080 each live entry. If CALLBACK returns false, the iteration stops.
1081 ARGUMENT is passed as CALLBACK's second argument. */
1083 template<typename Descriptor
,
1084 template<typename Type
> class Allocator
>
1085 template<typename Argument
,
1087 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
1090 hash_table
<Descriptor
, Allocator
>::traverse_noresize (Argument argument
)
1092 value_type
*slot
= m_entries
;
1093 value_type
*limit
= slot
+ size ();
1097 value_type
&x
= *slot
;
1099 if (!is_empty (x
) && !is_deleted (x
))
1100 if (! Callback (slot
, argument
))
1103 while (++slot
< limit
);
1106 /* Like traverse_noresize, but does resize the table when it is too empty
1107 to improve effectivity of subsequent calls. */
1109 template <typename Descriptor
,
1110 template <typename Type
> class Allocator
>
1111 template <typename Argument
,
1113 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
1116 hash_table
<Descriptor
, Allocator
>::traverse (Argument argument
)
1118 size_t size
= m_size
;
1119 if (elements () * 8 < size
&& size
> 32)
1122 traverse_noresize
<Argument
, Callback
> (argument
);
1125 /* Slide down the iterator slots until an active entry is found. */
1127 template<typename Descriptor
, template<typename Type
> class Allocator
>
1129 hash_table
<Descriptor
, Allocator
>::iterator::slide ()
1131 for ( ; m_slot
< m_limit
; ++m_slot
)
1133 value_type
&x
= *m_slot
;
1134 if (!is_empty (x
) && !is_deleted (x
))
1141 /* Bump the iterator. */
1143 template<typename Descriptor
, template<typename Type
> class Allocator
>
1144 inline typename hash_table
<Descriptor
, Allocator
>::iterator
&
1145 hash_table
<Descriptor
, Allocator
>::iterator::operator ++ ()
1153 /* Iterate through the elements of hash_table HTAB,
1154 using hash_table <....>::iterator ITER,
1155 storing each element in RESULT, which is of type TYPE. */
1157 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1158 for ((ITER) = (HTAB).begin (); \
1159 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1162 /* ggc walking routines. */
1164 template<typename E
>
1166 gt_ggc_mx (hash_table
<E
> *h
)
1168 typedef hash_table
<E
> table
;
1170 if (!ggc_test_and_set_mark (h
->m_entries
))
1173 for (size_t i
= 0; i
< h
->m_size
; i
++)
1175 if (table::is_empty (h
->m_entries
[i
])
1176 || table::is_deleted (h
->m_entries
[i
]))
1179 E::ggc_mx (h
->m_entries
[i
]);
1183 template<typename D
>
1185 hashtab_entry_note_pointers (void *obj
, void *h
, gt_pointer_operator op
,
1188 hash_table
<D
> *map
= static_cast<hash_table
<D
> *> (h
);
1189 gcc_checking_assert (map
->m_entries
== obj
);
1190 for (size_t i
= 0; i
< map
->m_size
; i
++)
1192 typedef hash_table
<D
> table
;
1193 if (table::is_empty (map
->m_entries
[i
])
1194 || table::is_deleted (map
->m_entries
[i
]))
1197 D::pch_nx (map
->m_entries
[i
], op
, cookie
);
1201 template<typename D
>
1203 gt_pch_nx (hash_table
<D
> *h
)
1206 = gt_pch_note_object (h
->m_entries
, h
, hashtab_entry_note_pointers
<D
>);
1207 gcc_checking_assert (success
);
1208 for (size_t i
= 0; i
< h
->m_size
; i
++)
1210 if (hash_table
<D
>::is_empty (h
->m_entries
[i
])
1211 || hash_table
<D
>::is_deleted (h
->m_entries
[i
]))
1214 D::pch_nx (h
->m_entries
[i
]);
1218 template<typename D
>
1220 gt_pch_nx (hash_table
<D
> *h
, gt_pointer_operator op
, void *cookie
)
1222 op (&h
->m_entries
, cookie
);
1225 template<typename H
>
1227 gt_cleare_cache (hash_table
<H
> *h
)
1232 for (typename hash_table
<H
>::iterator iter
= h
->begin (); iter
!= h
->end ();
1234 H::handle_cache_entry (*iter
);
1237 #endif /* TYPED_HASHTAB_H */