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 hash-traits.h 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
199 #include "statistics.h"
204 #include "mem-stats-traits.h"
205 #include "hash-traits.h"
206 #include "hash-map-traits.h"
208 template<typename
, typename
, typename
> class hash_map
;
209 template<typename
, typename
> class hash_set
;
211 /* The ordinary memory allocator. */
212 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
214 template <typename Type
>
217 static Type
*data_alloc (size_t count
);
218 static void data_free (Type
*memory
);
222 /* Allocate memory for COUNT data blocks. */
224 template <typename Type
>
226 xcallocator
<Type
>::data_alloc (size_t count
)
228 return static_cast <Type
*> (xcalloc (count
, sizeof (Type
)));
232 /* Free memory for data blocks. */
234 template <typename Type
>
236 xcallocator
<Type
>::data_free (Type
*memory
)
238 return ::free (memory
);
242 /* Table of primes and their inversion information. */
248 hashval_t inv_m2
; /* inverse of prime-2 */
252 extern struct prime_ent
const prime_tab
[];
255 /* Functions for computing hash table indexes. */
257 extern unsigned int hash_table_higher_prime_index (unsigned long n
)
260 /* Return X % Y using multiplicative inverse values INV and SHIFT.
262 The multiplicative inverses computed above are for 32-bit types,
263 and requires that we be able to compute a highpart multiply.
265 FIX: I am not at all convinced that
266 3 loads, 2 multiplications, 3 shifts, and 3 additions
269 on modern systems running a compiler. */
272 mul_mod (hashval_t x
, hashval_t y
, hashval_t inv
, int shift
)
274 hashval_t t1
, t2
, t3
, t4
, q
, r
;
276 t1
= ((uint64_t)x
* inv
) >> 32;
286 /* Compute the primary table index for HASH given current prime index. */
289 hash_table_mod1 (hashval_t hash
, unsigned int index
)
291 const struct prime_ent
*p
= &prime_tab
[index
];
292 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
293 return mul_mod (hash
, p
->prime
, p
->inv
, p
->shift
);
296 /* Compute the secondary table index for HASH given current prime index. */
299 hash_table_mod2 (hashval_t hash
, unsigned int index
)
301 const struct prime_ent
*p
= &prime_tab
[index
];
302 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
303 return 1 + mul_mod (hash
, p
->prime
- 2, p
->inv_m2
, p
->shift
);
306 template<typename Traits
>
307 struct has_is_deleted
309 template<typename U
, bool (*)(U
&)> struct helper
{};
310 template<typename U
> static char test (helper
<U
, U::is_deleted
> *);
311 template<typename U
> static int test (...);
312 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
315 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
316 struct is_deleted_helper
321 return Traits::is_deleted (v
);
325 template<typename Type
, typename Traits
>
326 struct is_deleted_helper
<Type
*, Traits
, false>
331 return v
== HTAB_DELETED_ENTRY
;
335 template<typename Traits
>
338 template<typename U
, bool (*)(U
&)> struct helper
{};
339 template<typename U
> static char test (helper
<U
, U::is_empty
> *);
340 template<typename U
> static int test (...);
341 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
344 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
345 struct is_empty_helper
350 return Traits::is_empty (v
);
354 template<typename Type
, typename Traits
>
355 struct is_empty_helper
<Type
*, Traits
, false>
360 return v
== HTAB_EMPTY_ENTRY
;
364 template<typename Traits
>
365 struct has_mark_deleted
367 template<typename U
, void (*)(U
&)> struct helper
{};
368 template<typename U
> static char test (helper
<U
, U::mark_deleted
> *);
369 template<typename U
> static int test (...);
370 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
373 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
374 struct mark_deleted_helper
379 Traits::mark_deleted (v
);
383 template<typename Type
, typename Traits
>
384 struct mark_deleted_helper
<Type
*, Traits
, false>
389 v
= static_cast<Type
*> (HTAB_DELETED_ENTRY
);
393 template<typename Traits
>
394 struct has_mark_empty
396 template<typename U
, void (*)(U
&)> struct helper
{};
397 template<typename U
> static char test (helper
<U
, U::mark_empty
> *);
398 template<typename U
> static int test (...);
399 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
402 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
403 struct mark_empty_helper
408 Traits::mark_empty (v
);
412 template<typename Type
, typename Traits
>
413 struct mark_empty_helper
<Type
*, Traits
, false>
418 v
= static_cast<Type
*> (HTAB_EMPTY_ENTRY
);
424 /* User-facing hash table type.
426 The table stores elements of type Descriptor::value_type.
428 It hashes values with the hash member function.
429 The table currently works with relatively weak hash functions.
430 Use typed_pointer_hash <Value> when hashing pointers instead of objects.
432 It compares elements with the equal member function.
433 Two elements with the same hash may not be equal.
434 Use typed_pointer_equal <Value> when hashing pointers instead of objects.
436 It removes elements with the remove member function.
437 This feature is useful for freeing memory.
438 Derive from typed_null_remove <Value> when not freeing objects.
439 Derive from typed_free_remove <Value> when doing a simple object free.
441 Specify the template Allocator to allocate and free memory.
442 The default is xcallocator.
444 Storage is an implementation detail and should not be used outside the
448 template <typename Descriptor
,
449 template<typename Type
> class Allocator
= xcallocator
>
452 typedef typename
Descriptor::value_type value_type
;
453 typedef typename
Descriptor::compare_type compare_type
;
456 explicit hash_table (size_t, bool ggc
= false, bool gather_mem_stats
= true,
457 mem_alloc_origin origin
= HASH_TABLE_ORIGIN
461 /* Create a hash_table in gc memory. */
464 create_ggc (size_t n CXX_MEM_STAT_INFO
)
466 hash_table
*table
= ggc_alloc
<hash_table
> ();
467 new (table
) hash_table (n
, true, true, HASH_TABLE_ORIGIN PASS_MEM_STAT
);
471 /* Current size (in entries) of the hash table. */
472 size_t size () const { return m_size
; }
474 /* Return the current number of elements in this hash table. */
475 size_t elements () const { return m_n_elements
- m_n_deleted
; }
477 /* Return the current number of elements in this hash table. */
478 size_t elements_with_deleted () const { return m_n_elements
; }
480 /* This function clears all entries in the given hash table. */
483 /* This function clears a specified SLOT in a hash table. It is
484 useful when you've already done the lookup and don't want to do it
487 void clear_slot (value_type
*);
489 /* This function searches for a hash table entry equal to the given
490 COMPARABLE element starting with the given HASH value. It cannot
491 be used to insert or delete an element. */
492 value_type
&find_with_hash (const compare_type
&, hashval_t
);
494 /* Like find_slot_with_hash, but compute the hash value from the element. */
495 value_type
&find (const value_type
&value
)
497 return find_with_hash (value
, Descriptor::hash (value
));
500 value_type
*find_slot (const value_type
&value
, insert_option insert
)
502 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
505 /* This function searches for a hash table slot containing an entry
506 equal to the given COMPARABLE element and starting with the given
507 HASH. To delete an entry, call this with insert=NO_INSERT, then
508 call clear_slot on the slot returned (possibly after doing some
509 checks). To insert an entry, call this with insert=INSERT, then
510 write the value you want into the returned slot. When inserting an
511 entry, NULL may be returned if memory allocation fails. */
512 value_type
*find_slot_with_hash (const compare_type
&comparable
,
513 hashval_t hash
, enum insert_option insert
);
515 /* This function deletes an element with the given COMPARABLE value
516 from hash table starting with the given HASH. If there is no
517 matching element in the hash table, this function does nothing. */
518 void remove_elt_with_hash (const compare_type
&, hashval_t
);
520 /* Like remove_elt_with_hash, but compute the hash value from the element. */
521 void remove_elt (const value_type
&value
)
523 remove_elt_with_hash (value
, Descriptor::hash (value
));
526 /* This function scans over the entire hash table calling CALLBACK for
527 each live entry. If CALLBACK returns false, the iteration stops.
528 ARGUMENT is passed as CALLBACK's second argument. */
529 template <typename Argument
,
530 int (*Callback
) (value_type
*slot
, Argument argument
)>
531 void traverse_noresize (Argument argument
);
533 /* Like traverse_noresize, but does resize the table when it is too empty
534 to improve effectivity of subsequent calls. */
535 template <typename Argument
,
536 int (*Callback
) (value_type
*slot
, Argument argument
)>
537 void traverse (Argument argument
);
542 iterator () : m_slot (NULL
), m_limit (NULL
) {}
544 iterator (value_type
*slot
, value_type
*limit
) :
545 m_slot (slot
), m_limit (limit
) {}
547 inline value_type
&operator * () { return *m_slot
; }
549 inline iterator
&operator ++ ();
550 bool operator != (const iterator
&other
) const
552 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
560 iterator
begin () const
562 iterator
iter (m_entries
, m_entries
+ m_size
);
567 iterator
end () const { return iterator (); }
569 double collisions () const
571 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
575 template<typename T
> friend void gt_ggc_mx (hash_table
<T
> *);
576 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *);
577 template<typename T
> friend void
578 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator
, void *);
579 template<typename T
, typename U
, typename V
> friend void
580 gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
581 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *,
584 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *,
585 gt_pointer_operator
, void *);
587 value_type
*alloc_entries (size_t n CXX_MEM_STAT_INFO
) const;
588 value_type
*find_empty_slot_for_expand (hashval_t
);
590 static bool is_deleted (value_type
&v
)
592 return is_deleted_helper
<value_type
, Descriptor
>::call (v
);
594 static bool is_empty (value_type
&v
)
596 return is_empty_helper
<value_type
, Descriptor
>::call (v
);
599 static void mark_deleted (value_type
&v
)
601 return mark_deleted_helper
<value_type
, Descriptor
>::call (v
);
604 static void mark_empty (value_type
&v
)
606 return mark_empty_helper
<value_type
, Descriptor
>::call (v
);
610 typename
Descriptor::value_type
*m_entries
;
614 /* Current number of elements including also deleted elements. */
617 /* Current number of deleted elements in the table. */
620 /* The following member is used for debugging. Its value is number
621 of all calls of `htab_find_slot' for the hash table. */
622 unsigned int m_searches
;
624 /* The following member is used for debugging. Its value is number
625 of collisions fixed for time of work with the hash table. */
626 unsigned int m_collisions
;
628 /* Current size (in entries) of the hash table, as an index into the
630 unsigned int m_size_prime_index
;
632 /* if m_entries is stored in ggc memory. */
635 /* If we should gather memory statistics for the table. */
636 bool m_gather_mem_stats
;
639 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
640 mem-stats.h after hash_table declaration. */
642 #include "mem-stats.h"
643 #include "hash-map.h"
645 extern mem_alloc_description
<mem_usage
> hash_table_usage
;
647 /* Support function for statistics. */
648 extern void dump_hash_table_loc_statistics (void);
650 template<typename Descriptor
, template<typename Type
> class Allocator
>
651 hash_table
<Descriptor
, Allocator
>::hash_table (size_t size
, bool ggc
, bool
653 mem_alloc_origin origin
655 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
656 m_ggc (ggc
), m_gather_mem_stats (gather_mem_stats
)
658 unsigned int size_prime_index
;
660 size_prime_index
= hash_table_higher_prime_index (size
);
661 size
= prime_tab
[size_prime_index
].prime
;
663 if (m_gather_mem_stats
)
664 hash_table_usage
.register_descriptor (this, origin
, ggc
665 FINAL_PASS_MEM_STAT
);
667 m_entries
= alloc_entries (size PASS_MEM_STAT
);
669 m_size_prime_index
= size_prime_index
;
672 template<typename Descriptor
, template<typename Type
> class Allocator
>
673 hash_table
<Descriptor
, Allocator
>::~hash_table ()
675 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
676 if (!is_empty (m_entries
[i
]) && !is_deleted (m_entries
[i
]))
677 Descriptor::remove (m_entries
[i
]);
680 Allocator
<value_type
> ::data_free (m_entries
);
682 ggc_free (m_entries
);
684 if (m_gather_mem_stats
)
685 hash_table_usage
.release_instance_overhead (this,
686 sizeof (value_type
) * m_size
,
690 /* This function returns an array of empty hash table elements. */
692 template<typename Descriptor
, template<typename Type
> class Allocator
>
693 inline typename hash_table
<Descriptor
, Allocator
>::value_type
*
694 hash_table
<Descriptor
, Allocator
>::alloc_entries (size_t n MEM_STAT_DECL
) const
696 value_type
*nentries
;
698 if (m_gather_mem_stats
)
699 hash_table_usage
.register_instance_overhead (sizeof (value_type
) * n
, this);
702 nentries
= Allocator
<value_type
> ::data_alloc (n
);
704 nentries
= ::ggc_cleared_vec_alloc
<value_type
> (n PASS_MEM_STAT
);
706 gcc_assert (nentries
!= NULL
);
707 for (size_t i
= 0; i
< n
; i
++)
708 mark_empty (nentries
[i
]);
713 /* Similar to find_slot, but without several unwanted side effects:
714 - Does not call equal when it finds an existing entry.
715 - Does not change the count of elements/searches/collisions in the
717 This function also assumes there are no deleted entries in the table.
718 HASH is the hash value for the element to be inserted. */
720 template<typename Descriptor
, template<typename Type
> class Allocator
>
721 typename hash_table
<Descriptor
, Allocator
>::value_type
*
722 hash_table
<Descriptor
, Allocator
>::find_empty_slot_for_expand (hashval_t hash
)
724 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
725 size_t size
= m_size
;
726 value_type
*slot
= m_entries
+ index
;
729 if (is_empty (*slot
))
731 #ifdef ENABLE_CHECKING
732 gcc_checking_assert (!is_deleted (*slot
));
735 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
742 slot
= m_entries
+ index
;
743 if (is_empty (*slot
))
745 #ifdef ENABLE_CHECKING
746 gcc_checking_assert (!is_deleted (*slot
));
751 /* The following function changes size of memory allocated for the
752 entries and repeatedly inserts the table elements. The occupancy
753 of the table after the call will be about 50%. Naturally the hash
754 table must already exist. Remember also that the place of the
755 table entries is changed. If memory allocation fails, this function
758 template<typename Descriptor
, template<typename Type
> class Allocator
>
760 hash_table
<Descriptor
, Allocator
>::expand ()
762 value_type
*oentries
= m_entries
;
763 unsigned int oindex
= m_size_prime_index
;
764 size_t osize
= size ();
765 value_type
*olimit
= oentries
+ osize
;
766 size_t elts
= elements ();
768 /* Resize only when table after removal of unused elements is either
769 too full or too empty. */
772 if (elts
* 2 > osize
|| (elts
* 8 < osize
&& osize
> 32))
774 nindex
= hash_table_higher_prime_index (elts
* 2);
775 nsize
= prime_tab
[nindex
].prime
;
783 value_type
*nentries
= alloc_entries (nsize
);
785 if (m_gather_mem_stats
)
786 hash_table_usage
.release_instance_overhead (this, sizeof (value_type
)
789 m_entries
= nentries
;
791 m_size_prime_index
= nindex
;
792 m_n_elements
-= m_n_deleted
;
795 value_type
*p
= oentries
;
800 if (!is_empty (x
) && !is_deleted (x
))
802 value_type
*q
= find_empty_slot_for_expand (Descriptor::hash (x
));
812 Allocator
<value_type
> ::data_free (oentries
);
817 template<typename Descriptor
, template<typename Type
> class Allocator
>
819 hash_table
<Descriptor
, Allocator
>::empty ()
821 size_t size
= m_size
;
822 value_type
*entries
= m_entries
;
825 for (i
= size
- 1; i
>= 0; i
--)
826 if (!is_empty (entries
[i
]) && !is_deleted (entries
[i
]))
827 Descriptor::remove (entries
[i
]);
829 /* Instead of clearing megabyte, downsize the table. */
830 if (size
> 1024*1024 / sizeof (PTR
))
832 int nindex
= hash_table_higher_prime_index (1024 / sizeof (PTR
));
833 int nsize
= prime_tab
[nindex
].prime
;
836 Allocator
<value_type
> ::data_free (m_entries
);
838 ggc_free (m_entries
);
840 m_entries
= alloc_entries (nsize
);
842 m_size_prime_index
= nindex
;
845 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
, template<typename Type
> class Allocator
>
856 hash_table
<Descriptor
, Allocator
>::clear_slot (value_type
*slot
)
858 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
859 || is_empty (*slot
) || is_deleted (*slot
)));
861 Descriptor::remove (*slot
);
863 mark_deleted (*slot
);
867 /* This function searches for a hash table entry equal to the given
868 COMPARABLE element starting with the given HASH value. It cannot
869 be used to insert or delete an element. */
871 template<typename Descriptor
, template<typename Type
> class Allocator
>
872 typename hash_table
<Descriptor
, Allocator
>::value_type
&
873 hash_table
<Descriptor
, Allocator
>
874 ::find_with_hash (const compare_type
&comparable
, hashval_t hash
)
877 size_t size
= m_size
;
878 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
880 value_type
*entry
= &m_entries
[index
];
881 if (is_empty (*entry
)
882 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
885 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
893 entry
= &m_entries
[index
];
894 if (is_empty (*entry
)
895 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
900 /* This function searches for a hash table slot containing an entry
901 equal to the given COMPARABLE element and starting with the given
902 HASH. To delete an entry, call this with insert=NO_INSERT, then
903 call clear_slot on the slot returned (possibly after doing some
904 checks). To insert an entry, call this with insert=INSERT, then
905 write the value you want into the returned slot. When inserting an
906 entry, NULL may be returned if memory allocation fails. */
908 template<typename Descriptor
, template<typename Type
> class Allocator
>
909 typename hash_table
<Descriptor
, Allocator
>::value_type
*
910 hash_table
<Descriptor
, Allocator
>
911 ::find_slot_with_hash (const compare_type
&comparable
, hashval_t hash
,
912 enum insert_option insert
)
914 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
919 value_type
*first_deleted_slot
= NULL
;
920 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
921 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
922 value_type
*entry
= &m_entries
[index
];
923 size_t size
= m_size
;
924 if (is_empty (*entry
))
926 else if (is_deleted (*entry
))
927 first_deleted_slot
= &m_entries
[index
];
928 else if (Descriptor::equal (*entry
, comparable
))
929 return &m_entries
[index
];
938 entry
= &m_entries
[index
];
939 if (is_empty (*entry
))
941 else if (is_deleted (*entry
))
943 if (!first_deleted_slot
)
944 first_deleted_slot
= &m_entries
[index
];
946 else if (Descriptor::equal (*entry
, comparable
))
947 return &m_entries
[index
];
951 if (insert
== NO_INSERT
)
954 if (first_deleted_slot
)
957 mark_empty (*first_deleted_slot
);
958 return first_deleted_slot
;
962 return &m_entries
[index
];
965 /* This function deletes an element with the given COMPARABLE value
966 from hash table starting with the given HASH. If there is no
967 matching element in the hash table, this function does nothing. */
969 template<typename Descriptor
, template<typename Type
> class Allocator
>
971 hash_table
<Descriptor
, Allocator
>
972 ::remove_elt_with_hash (const compare_type
&comparable
, hashval_t hash
)
974 value_type
*slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
975 if (is_empty (*slot
))
978 Descriptor::remove (*slot
);
980 mark_deleted (*slot
);
984 /* This function scans over the entire hash table calling CALLBACK for
985 each live entry. If CALLBACK returns false, the iteration stops.
986 ARGUMENT is passed as CALLBACK's second argument. */
988 template<typename Descriptor
,
989 template<typename Type
> class Allocator
>
990 template<typename Argument
,
992 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
995 hash_table
<Descriptor
, Allocator
>::traverse_noresize (Argument argument
)
997 value_type
*slot
= m_entries
;
998 value_type
*limit
= slot
+ size ();
1002 value_type
&x
= *slot
;
1004 if (!is_empty (x
) && !is_deleted (x
))
1005 if (! Callback (slot
, argument
))
1008 while (++slot
< limit
);
1011 /* Like traverse_noresize, but does resize the table when it is too empty
1012 to improve effectivity of subsequent calls. */
1014 template <typename Descriptor
,
1015 template <typename Type
> class Allocator
>
1016 template <typename Argument
,
1018 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
1021 hash_table
<Descriptor
, Allocator
>::traverse (Argument argument
)
1023 size_t size
= m_size
;
1024 if (elements () * 8 < size
&& size
> 32)
1027 traverse_noresize
<Argument
, Callback
> (argument
);
1030 /* Slide down the iterator slots until an active entry is found. */
1032 template<typename Descriptor
, template<typename Type
> class Allocator
>
1034 hash_table
<Descriptor
, Allocator
>::iterator::slide ()
1036 for ( ; m_slot
< m_limit
; ++m_slot
)
1038 value_type
&x
= *m_slot
;
1039 if (!is_empty (x
) && !is_deleted (x
))
1046 /* Bump the iterator. */
1048 template<typename Descriptor
, template<typename Type
> class Allocator
>
1049 inline typename hash_table
<Descriptor
, Allocator
>::iterator
&
1050 hash_table
<Descriptor
, Allocator
>::iterator::operator ++ ()
1058 /* Iterate through the elements of hash_table HTAB,
1059 using hash_table <....>::iterator ITER,
1060 storing each element in RESULT, which is of type TYPE. */
1062 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1063 for ((ITER) = (HTAB).begin (); \
1064 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1067 /* ggc walking routines. */
1069 template<typename E
>
1071 gt_ggc_mx (hash_table
<E
> *h
)
1073 typedef hash_table
<E
> table
;
1075 if (!ggc_test_and_set_mark (h
->m_entries
))
1078 for (size_t i
= 0; i
< h
->m_size
; i
++)
1080 if (table::is_empty (h
->m_entries
[i
])
1081 || table::is_deleted (h
->m_entries
[i
]))
1084 E::ggc_mx (h
->m_entries
[i
]);
1088 template<typename D
>
1090 hashtab_entry_note_pointers (void *obj
, void *h
, gt_pointer_operator op
,
1093 hash_table
<D
> *map
= static_cast<hash_table
<D
> *> (h
);
1094 gcc_checking_assert (map
->m_entries
== obj
);
1095 for (size_t i
= 0; i
< map
->m_size
; i
++)
1097 typedef hash_table
<D
> table
;
1098 if (table::is_empty (map
->m_entries
[i
])
1099 || table::is_deleted (map
->m_entries
[i
]))
1102 D::pch_nx (map
->m_entries
[i
], op
, cookie
);
1106 template<typename D
>
1108 gt_pch_nx (hash_table
<D
> *h
)
1111 = gt_pch_note_object (h
->m_entries
, h
, hashtab_entry_note_pointers
<D
>);
1112 gcc_checking_assert (success
);
1113 for (size_t i
= 0; i
< h
->m_size
; i
++)
1115 if (hash_table
<D
>::is_empty (h
->m_entries
[i
])
1116 || hash_table
<D
>::is_deleted (h
->m_entries
[i
]))
1119 D::pch_nx (h
->m_entries
[i
]);
1123 template<typename D
>
1125 gt_pch_nx (hash_table
<D
> *h
, gt_pointer_operator op
, void *cookie
)
1127 op (&h
->m_entries
, cookie
);
1130 template<typename H
>
1132 gt_cleare_cache (hash_table
<H
> *h
)
1137 for (typename hash_table
<H
>::iterator iter
= h
->begin (); iter
!= h
->end ();
1139 H::handle_cache_entry (*iter
);
1142 #endif /* TYPED_HASHTAB_H */