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 : typed_noop_remove <some_type>
122 // Deriving from typed_noop_remove means that we get a 'remove' that does
123 // nothing. This choice is good for raw values.
125 typedef some_type value_type;
126 typedef some_type compare_type;
127 static inline hashval_t hash (const value_type *);
128 static inline bool equal (const value_type *, const compare_type *);
132 some_type_hasher::hash (const value_type *e)
133 { ... compute and return a hash value for E ... }
136 some_type_hasher::equal (const value_type *p1, const compare_type *p2)
137 { ... compare P1 vs P2. Return true if they are the 'same' ... }
140 AN EXAMPLE HASH_TABLE DECLARATION
142 To instantiate a hash table for some_type:
144 hash_table <some_type_hasher> some_type_hash_table;
146 There is no need to mention some_type directly, as the hash table will
147 obtain it using some_type_hasher::value_type.
149 You can then used any of the functions in hash_table's public interface.
150 See hash_table for details. The interface is very similar to libiberty's
154 EASY DESCRIPTORS FOR POINTERS
156 The class template pointer_hash provides everything you need to hash
157 pointers (as opposed to what they point to). So, to instantiate a hash
158 table over pointers to whatever_type,
160 hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
165 The hash table provides standard C++ iterators. For example, consider a
166 hash table of some_info. We wish to consume each element of the table:
168 extern void consume (some_info *);
170 We define a convenience typedef and the hash table:
172 typedef hash_table <some_info_hasher> info_table_type;
173 info_table_type info_table;
175 Then we write the loop in typical C++ style:
177 for (info_table_type::iterator iter = info_table.begin ();
178 iter != info_table.end ();
180 if ((*iter).status == INFO_READY)
183 Or with common sub-expression elimination:
185 for (info_table_type::iterator iter = info_table.begin ();
186 iter != info_table.end ();
189 some_info &elem = *iter;
190 if (elem.status == INFO_READY)
194 One can also use a more typical GCC style:
196 typedef some_info *some_info_p;
198 info_table_type::iterator iter;
199 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
200 if (elem_ptr->status == INFO_READY)
206 #ifndef TYPED_HASHTAB_H
207 #define TYPED_HASHTAB_H
209 #include "statistics.h"
214 #include "mem-stats-traits.h"
215 #include "hash-traits.h"
216 #include "hash-map-traits.h"
218 template<typename
, typename
, typename
> class hash_map
;
219 template<typename
, typename
> class hash_set
;
221 /* The ordinary memory allocator. */
222 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
224 template <typename Type
>
227 static Type
*data_alloc (size_t count
);
228 static void data_free (Type
*memory
);
232 /* Allocate memory for COUNT data blocks. */
234 template <typename Type
>
236 xcallocator
<Type
>::data_alloc (size_t count
)
238 return static_cast <Type
*> (xcalloc (count
, sizeof (Type
)));
242 /* Free memory for data blocks. */
244 template <typename Type
>
246 xcallocator
<Type
>::data_free (Type
*memory
)
248 return ::free (memory
);
252 /* Table of primes and their inversion information. */
258 hashval_t inv_m2
; /* inverse of prime-2 */
262 extern struct prime_ent
const prime_tab
[];
265 /* Functions for computing hash table indexes. */
267 extern unsigned int hash_table_higher_prime_index (unsigned long n
)
270 /* Return X % Y using multiplicative inverse values INV and SHIFT.
272 The multiplicative inverses computed above are for 32-bit types,
273 and requires that we be able to compute a highpart multiply.
275 FIX: I am not at all convinced that
276 3 loads, 2 multiplications, 3 shifts, and 3 additions
279 on modern systems running a compiler. */
282 mul_mod (hashval_t x
, hashval_t y
, hashval_t inv
, int shift
)
284 hashval_t t1
, t2
, t3
, t4
, q
, r
;
286 t1
= ((uint64_t)x
* inv
) >> 32;
296 /* Compute the primary table index for HASH given current prime index. */
299 hash_table_mod1 (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 mul_mod (hash
, p
->prime
, p
->inv
, p
->shift
);
306 /* Compute the secondary table index for HASH given current prime index. */
309 hash_table_mod2 (hashval_t hash
, unsigned int index
)
311 const struct prime_ent
*p
= &prime_tab
[index
];
312 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
313 return 1 + mul_mod (hash
, p
->prime
- 2, p
->inv_m2
, p
->shift
);
316 template<typename Traits
>
317 struct has_is_deleted
319 template<typename U
, bool (*)(U
&)> struct helper
{};
320 template<typename U
> static char test (helper
<U
, U::is_deleted
> *);
321 template<typename U
> static int test (...);
322 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
325 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
326 struct is_deleted_helper
331 return Traits::is_deleted (v
);
335 template<typename Type
, typename Traits
>
336 struct is_deleted_helper
<Type
*, Traits
, false>
341 return v
== HTAB_DELETED_ENTRY
;
345 template<typename Traits
>
348 template<typename U
, bool (*)(U
&)> struct helper
{};
349 template<typename U
> static char test (helper
<U
, U::is_empty
> *);
350 template<typename U
> static int test (...);
351 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
354 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
355 struct is_empty_helper
360 return Traits::is_empty (v
);
364 template<typename Type
, typename Traits
>
365 struct is_empty_helper
<Type
*, Traits
, false>
370 return v
== HTAB_EMPTY_ENTRY
;
374 template<typename Traits
>
375 struct has_mark_deleted
377 template<typename U
, void (*)(U
&)> struct helper
{};
378 template<typename U
> static char test (helper
<U
, U::mark_deleted
> *);
379 template<typename U
> static int test (...);
380 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
383 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
384 struct mark_deleted_helper
389 Traits::mark_deleted (v
);
393 template<typename Type
, typename Traits
>
394 struct mark_deleted_helper
<Type
*, Traits
, false>
399 v
= static_cast<Type
*> (HTAB_DELETED_ENTRY
);
403 template<typename Traits
>
404 struct has_mark_empty
406 template<typename U
, void (*)(U
&)> struct helper
{};
407 template<typename U
> static char test (helper
<U
, U::mark_empty
> *);
408 template<typename U
> static int test (...);
409 static const bool value
= sizeof (test
<Traits
> (0)) == sizeof (char);
412 template<typename Type
, typename Traits
, bool = has_is_deleted
<Traits
>::value
>
413 struct mark_empty_helper
418 Traits::mark_empty (v
);
422 template<typename Type
, typename Traits
>
423 struct mark_empty_helper
<Type
*, Traits
, false>
428 v
= static_cast<Type
*> (HTAB_EMPTY_ENTRY
);
434 /* User-facing hash table type.
436 The table stores elements of type Descriptor::value_type.
438 It hashes values with the hash member function.
439 The table currently works with relatively weak hash functions.
440 Use typed_pointer_hash <Value> when hashing pointers instead of objects.
442 It compares elements with the equal member function.
443 Two elements with the same hash may not be equal.
444 Use typed_pointer_equal <Value> when hashing pointers instead of objects.
446 It removes elements with the remove member function.
447 This feature is useful for freeing memory.
448 Derive from typed_null_remove <Value> when not freeing objects.
449 Derive from typed_free_remove <Value> when doing a simple object free.
451 Specify the template Allocator to allocate and free memory.
452 The default is xcallocator.
454 Storage is an implementation detail and should not be used outside the
458 template <typename Descriptor
,
459 template<typename Type
> class Allocator
= xcallocator
>
462 typedef typename
Descriptor::value_type value_type
;
463 typedef typename
Descriptor::compare_type compare_type
;
466 explicit hash_table (size_t, bool ggc
= false, bool gather_mem_stats
= true,
467 mem_alloc_origin origin
= HASH_TABLE_ORIGIN
471 /* Create a hash_table in gc memory. */
474 create_ggc (size_t n CXX_MEM_STAT_INFO
)
476 hash_table
*table
= ggc_alloc
<hash_table
> ();
477 new (table
) hash_table (n
, true, true, HASH_TABLE_ORIGIN PASS_MEM_STAT
);
481 /* Current size (in entries) of the hash table. */
482 size_t size () const { return m_size
; }
484 /* Return the current number of elements in this hash table. */
485 size_t elements () const { return m_n_elements
- m_n_deleted
; }
487 /* Return the current number of elements in this hash table. */
488 size_t elements_with_deleted () const { return m_n_elements
; }
490 /* This function clears all entries in the given hash table. */
493 /* This function clears a specified SLOT in a hash table. It is
494 useful when you've already done the lookup and don't want to do it
497 void clear_slot (value_type
*);
499 /* This function searches for a hash table entry equal to the given
500 COMPARABLE element starting with the given HASH value. It cannot
501 be used to insert or delete an element. */
502 value_type
&find_with_hash (const compare_type
&, hashval_t
);
504 /* Like find_slot_with_hash, but compute the hash value from the element. */
505 value_type
&find (const value_type
&value
)
507 return find_with_hash (value
, Descriptor::hash (value
));
510 value_type
*find_slot (const value_type
&value
, insert_option insert
)
512 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
515 /* This function searches for a hash table slot containing an entry
516 equal to the given COMPARABLE element and starting with the given
517 HASH. To delete an entry, call this with insert=NO_INSERT, then
518 call clear_slot on the slot returned (possibly after doing some
519 checks). To insert an entry, call this with insert=INSERT, then
520 write the value you want into the returned slot. When inserting an
521 entry, NULL may be returned if memory allocation fails. */
522 value_type
*find_slot_with_hash (const compare_type
&comparable
,
523 hashval_t hash
, enum insert_option insert
);
525 /* This function deletes an element with the given COMPARABLE value
526 from hash table starting with the given HASH. If there is no
527 matching element in the hash table, this function does nothing. */
528 void remove_elt_with_hash (const compare_type
&, hashval_t
);
530 /* Like remove_elt_with_hash, but compute the hash value from the element. */
531 void remove_elt (const value_type
&value
)
533 remove_elt_with_hash (value
, Descriptor::hash (value
));
536 /* This function scans over the entire hash table calling CALLBACK for
537 each live entry. If CALLBACK returns false, the iteration stops.
538 ARGUMENT is passed as CALLBACK's second argument. */
539 template <typename Argument
,
540 int (*Callback
) (value_type
*slot
, Argument argument
)>
541 void traverse_noresize (Argument argument
);
543 /* Like traverse_noresize, but does resize the table when it is too empty
544 to improve effectivity of subsequent calls. */
545 template <typename Argument
,
546 int (*Callback
) (value_type
*slot
, Argument argument
)>
547 void traverse (Argument argument
);
552 iterator () : m_slot (NULL
), m_limit (NULL
) {}
554 iterator (value_type
*slot
, value_type
*limit
) :
555 m_slot (slot
), m_limit (limit
) {}
557 inline value_type
&operator * () { return *m_slot
; }
559 inline iterator
&operator ++ ();
560 bool operator != (const iterator
&other
) const
562 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
570 iterator
begin () const
572 iterator
iter (m_entries
, m_entries
+ m_size
);
577 iterator
end () const { return iterator (); }
579 double collisions () const
581 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
585 template<typename T
> friend void gt_ggc_mx (hash_table
<T
> *);
586 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *);
587 template<typename T
> friend void
588 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator
, void *);
589 template<typename T
, typename U
, typename V
> friend void
590 gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
591 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *,
594 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *,
595 gt_pointer_operator
, void *);
597 template<typename T
> friend void gt_cleare_cache (hash_table
<T
> *);
599 value_type
*alloc_entries (size_t n CXX_MEM_STAT_INFO
) const;
600 value_type
*find_empty_slot_for_expand (hashval_t
);
602 static bool is_deleted (value_type
&v
)
604 return is_deleted_helper
<value_type
, Descriptor
>::call (v
);
606 static bool is_empty (value_type
&v
)
608 return is_empty_helper
<value_type
, Descriptor
>::call (v
);
611 static void mark_deleted (value_type
&v
)
613 return mark_deleted_helper
<value_type
, Descriptor
>::call (v
);
616 static void mark_empty (value_type
&v
)
618 return mark_empty_helper
<value_type
, Descriptor
>::call (v
);
622 typename
Descriptor::value_type
*m_entries
;
626 /* Current number of elements including also deleted elements. */
629 /* Current number of deleted elements in the table. */
632 /* The following member is used for debugging. Its value is number
633 of all calls of `htab_find_slot' for the hash table. */
634 unsigned int m_searches
;
636 /* The following member is used for debugging. Its value is number
637 of collisions fixed for time of work with the hash table. */
638 unsigned int m_collisions
;
640 /* Current size (in entries) of the hash table, as an index into the
642 unsigned int m_size_prime_index
;
644 /* if m_entries is stored in ggc memory. */
647 /* If we should gather memory statistics for the table. */
648 bool m_gather_mem_stats
;
651 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
652 mem-stats.h after hash_table declaration. */
654 #include "mem-stats.h"
655 #include "hash-map.h"
657 extern mem_alloc_description
<mem_usage
> hash_table_usage
;
659 /* Support function for statistics. */
660 extern void dump_hash_table_loc_statistics (void);
662 template<typename Descriptor
, template<typename Type
> class Allocator
>
663 hash_table
<Descriptor
, Allocator
>::hash_table (size_t size
, bool ggc
, bool
665 mem_alloc_origin origin
667 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
668 m_ggc (ggc
), m_gather_mem_stats (gather_mem_stats
)
670 unsigned int size_prime_index
;
672 size_prime_index
= hash_table_higher_prime_index (size
);
673 size
= prime_tab
[size_prime_index
].prime
;
675 if (m_gather_mem_stats
)
676 hash_table_usage
.register_descriptor (this, origin
, ggc
677 FINAL_PASS_MEM_STAT
);
679 m_entries
= alloc_entries (size PASS_MEM_STAT
);
681 m_size_prime_index
= size_prime_index
;
684 template<typename Descriptor
, template<typename Type
> class Allocator
>
685 hash_table
<Descriptor
, Allocator
>::~hash_table ()
687 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
688 if (!is_empty (m_entries
[i
]) && !is_deleted (m_entries
[i
]))
689 Descriptor::remove (m_entries
[i
]);
692 Allocator
<value_type
> ::data_free (m_entries
);
694 ggc_free (m_entries
);
696 if (m_gather_mem_stats
)
697 hash_table_usage
.release_instance_overhead (this,
698 sizeof (value_type
) * m_size
,
702 /* This function returns an array of empty hash table elements. */
704 template<typename Descriptor
, template<typename Type
> class Allocator
>
705 inline typename hash_table
<Descriptor
, Allocator
>::value_type
*
706 hash_table
<Descriptor
, Allocator
>::alloc_entries (size_t n MEM_STAT_DECL
) const
708 value_type
*nentries
;
710 if (m_gather_mem_stats
)
711 hash_table_usage
.register_instance_overhead (sizeof (value_type
) * n
, this);
714 nentries
= Allocator
<value_type
> ::data_alloc (n
);
716 nentries
= ::ggc_cleared_vec_alloc
<value_type
> (n PASS_MEM_STAT
);
718 gcc_assert (nentries
!= NULL
);
719 for (size_t i
= 0; i
< n
; i
++)
720 mark_empty (nentries
[i
]);
725 /* Similar to find_slot, but without several unwanted side effects:
726 - Does not call equal when it finds an existing entry.
727 - Does not change the count of elements/searches/collisions in the
729 This function also assumes there are no deleted entries in the table.
730 HASH is the hash value for the element to be inserted. */
732 template<typename Descriptor
, template<typename Type
> class Allocator
>
733 typename hash_table
<Descriptor
, Allocator
>::value_type
*
734 hash_table
<Descriptor
, Allocator
>::find_empty_slot_for_expand (hashval_t hash
)
736 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
737 size_t size
= m_size
;
738 value_type
*slot
= m_entries
+ index
;
741 if (is_empty (*slot
))
743 #ifdef ENABLE_CHECKING
744 gcc_checking_assert (!is_deleted (*slot
));
747 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
754 slot
= m_entries
+ index
;
755 if (is_empty (*slot
))
757 #ifdef ENABLE_CHECKING
758 gcc_checking_assert (!is_deleted (*slot
));
763 /* The following function changes size of memory allocated for the
764 entries and repeatedly inserts the table elements. The occupancy
765 of the table after the call will be about 50%. Naturally the hash
766 table must already exist. Remember also that the place of the
767 table entries is changed. If memory allocation fails, this function
770 template<typename Descriptor
, template<typename Type
> class Allocator
>
772 hash_table
<Descriptor
, Allocator
>::expand ()
774 value_type
*oentries
= m_entries
;
775 unsigned int oindex
= m_size_prime_index
;
776 size_t osize
= size ();
777 value_type
*olimit
= oentries
+ osize
;
778 size_t elts
= elements ();
780 /* Resize only when table after removal of unused elements is either
781 too full or too empty. */
784 if (elts
* 2 > osize
|| (elts
* 8 < osize
&& osize
> 32))
786 nindex
= hash_table_higher_prime_index (elts
* 2);
787 nsize
= prime_tab
[nindex
].prime
;
795 value_type
*nentries
= alloc_entries (nsize
);
797 if (m_gather_mem_stats
)
798 hash_table_usage
.release_instance_overhead (this, sizeof (value_type
)
801 m_entries
= nentries
;
803 m_size_prime_index
= nindex
;
804 m_n_elements
-= m_n_deleted
;
807 value_type
*p
= oentries
;
812 if (!is_empty (x
) && !is_deleted (x
))
814 value_type
*q
= find_empty_slot_for_expand (Descriptor::hash (x
));
824 Allocator
<value_type
> ::data_free (oentries
);
829 template<typename Descriptor
, template<typename Type
> class Allocator
>
831 hash_table
<Descriptor
, Allocator
>::empty ()
833 size_t size
= m_size
;
834 value_type
*entries
= m_entries
;
837 for (i
= size
- 1; i
>= 0; i
--)
838 if (!is_empty (entries
[i
]) && !is_deleted (entries
[i
]))
839 Descriptor::remove (entries
[i
]);
841 /* Instead of clearing megabyte, downsize the table. */
842 if (size
> 1024*1024 / sizeof (PTR
))
844 int nindex
= hash_table_higher_prime_index (1024 / sizeof (PTR
));
845 int nsize
= prime_tab
[nindex
].prime
;
848 Allocator
<value_type
> ::data_free (m_entries
);
850 ggc_free (m_entries
);
852 m_entries
= alloc_entries (nsize
);
854 m_size_prime_index
= nindex
;
857 memset (entries
, 0, size
* sizeof (value_type
));
862 /* This function clears a specified SLOT in a hash table. It is
863 useful when you've already done the lookup and don't want to do it
866 template<typename Descriptor
, template<typename Type
> class Allocator
>
868 hash_table
<Descriptor
, Allocator
>::clear_slot (value_type
*slot
)
870 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
871 || is_empty (*slot
) || is_deleted (*slot
)));
873 Descriptor::remove (*slot
);
875 mark_deleted (*slot
);
879 /* This function searches for a hash table entry equal to the given
880 COMPARABLE element starting with the given HASH value. It cannot
881 be used to insert or delete an element. */
883 template<typename Descriptor
, template<typename Type
> class Allocator
>
884 typename hash_table
<Descriptor
, Allocator
>::value_type
&
885 hash_table
<Descriptor
, Allocator
>
886 ::find_with_hash (const compare_type
&comparable
, hashval_t hash
)
889 size_t size
= m_size
;
890 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
892 value_type
*entry
= &m_entries
[index
];
893 if (is_empty (*entry
)
894 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
897 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
905 entry
= &m_entries
[index
];
906 if (is_empty (*entry
)
907 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
912 /* This function searches for a hash table slot containing an entry
913 equal to the given COMPARABLE element and starting with the given
914 HASH. To delete an entry, call this with insert=NO_INSERT, then
915 call clear_slot on the slot returned (possibly after doing some
916 checks). To insert an entry, call this with insert=INSERT, then
917 write the value you want into the returned slot. When inserting an
918 entry, NULL may be returned if memory allocation fails. */
920 template<typename Descriptor
, template<typename Type
> class Allocator
>
921 typename hash_table
<Descriptor
, Allocator
>::value_type
*
922 hash_table
<Descriptor
, Allocator
>
923 ::find_slot_with_hash (const compare_type
&comparable
, hashval_t hash
,
924 enum insert_option insert
)
926 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
931 value_type
*first_deleted_slot
= NULL
;
932 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
933 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
934 value_type
*entry
= &m_entries
[index
];
935 size_t size
= m_size
;
936 if (is_empty (*entry
))
938 else if (is_deleted (*entry
))
939 first_deleted_slot
= &m_entries
[index
];
940 else if (Descriptor::equal (*entry
, comparable
))
941 return &m_entries
[index
];
950 entry
= &m_entries
[index
];
951 if (is_empty (*entry
))
953 else if (is_deleted (*entry
))
955 if (!first_deleted_slot
)
956 first_deleted_slot
= &m_entries
[index
];
958 else if (Descriptor::equal (*entry
, comparable
))
959 return &m_entries
[index
];
963 if (insert
== NO_INSERT
)
966 if (first_deleted_slot
)
969 mark_empty (*first_deleted_slot
);
970 return first_deleted_slot
;
974 return &m_entries
[index
];
977 /* This function deletes an element with the given COMPARABLE value
978 from hash table starting with the given HASH. If there is no
979 matching element in the hash table, this function does nothing. */
981 template<typename Descriptor
, template<typename Type
> class Allocator
>
983 hash_table
<Descriptor
, Allocator
>
984 ::remove_elt_with_hash (const compare_type
&comparable
, hashval_t hash
)
986 value_type
*slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
987 if (is_empty (*slot
))
990 Descriptor::remove (*slot
);
992 mark_deleted (*slot
);
996 /* This function scans over the entire hash table calling CALLBACK for
997 each live entry. If CALLBACK returns false, the iteration stops.
998 ARGUMENT is passed as CALLBACK's second argument. */
1000 template<typename Descriptor
,
1001 template<typename Type
> class Allocator
>
1002 template<typename Argument
,
1004 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
1007 hash_table
<Descriptor
, Allocator
>::traverse_noresize (Argument argument
)
1009 value_type
*slot
= m_entries
;
1010 value_type
*limit
= slot
+ size ();
1014 value_type
&x
= *slot
;
1016 if (!is_empty (x
) && !is_deleted (x
))
1017 if (! Callback (slot
, argument
))
1020 while (++slot
< limit
);
1023 /* Like traverse_noresize, but does resize the table when it is too empty
1024 to improve effectivity of subsequent calls. */
1026 template <typename Descriptor
,
1027 template <typename Type
> class Allocator
>
1028 template <typename Argument
,
1030 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
1033 hash_table
<Descriptor
, Allocator
>::traverse (Argument argument
)
1035 size_t size
= m_size
;
1036 if (elements () * 8 < size
&& size
> 32)
1039 traverse_noresize
<Argument
, Callback
> (argument
);
1042 /* Slide down the iterator slots until an active entry is found. */
1044 template<typename Descriptor
, template<typename Type
> class Allocator
>
1046 hash_table
<Descriptor
, Allocator
>::iterator::slide ()
1048 for ( ; m_slot
< m_limit
; ++m_slot
)
1050 value_type
&x
= *m_slot
;
1051 if (!is_empty (x
) && !is_deleted (x
))
1058 /* Bump the iterator. */
1060 template<typename Descriptor
, template<typename Type
> class Allocator
>
1061 inline typename hash_table
<Descriptor
, Allocator
>::iterator
&
1062 hash_table
<Descriptor
, Allocator
>::iterator::operator ++ ()
1070 /* Iterate through the elements of hash_table HTAB,
1071 using hash_table <....>::iterator ITER,
1072 storing each element in RESULT, which is of type TYPE. */
1074 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1075 for ((ITER) = (HTAB).begin (); \
1076 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1079 /* ggc walking routines. */
1081 template<typename E
>
1083 gt_ggc_mx (hash_table
<E
> *h
)
1085 typedef hash_table
<E
> table
;
1087 if (!ggc_test_and_set_mark (h
->m_entries
))
1090 for (size_t i
= 0; i
< h
->m_size
; i
++)
1092 if (table::is_empty (h
->m_entries
[i
])
1093 || table::is_deleted (h
->m_entries
[i
]))
1096 E::ggc_mx (h
->m_entries
[i
]);
1100 template<typename D
>
1102 hashtab_entry_note_pointers (void *obj
, void *h
, gt_pointer_operator op
,
1105 hash_table
<D
> *map
= static_cast<hash_table
<D
> *> (h
);
1106 gcc_checking_assert (map
->m_entries
== obj
);
1107 for (size_t i
= 0; i
< map
->m_size
; i
++)
1109 typedef hash_table
<D
> table
;
1110 if (table::is_empty (map
->m_entries
[i
])
1111 || table::is_deleted (map
->m_entries
[i
]))
1114 D::pch_nx (map
->m_entries
[i
], op
, cookie
);
1118 template<typename D
>
1120 gt_pch_nx (hash_table
<D
> *h
)
1123 = gt_pch_note_object (h
->m_entries
, h
, hashtab_entry_note_pointers
<D
>);
1124 gcc_checking_assert (success
);
1125 for (size_t i
= 0; i
< h
->m_size
; i
++)
1127 if (hash_table
<D
>::is_empty (h
->m_entries
[i
])
1128 || hash_table
<D
>::is_deleted (h
->m_entries
[i
]))
1131 D::pch_nx (h
->m_entries
[i
]);
1135 template<typename D
>
1137 gt_pch_nx (hash_table
<D
> *h
, gt_pointer_operator op
, void *cookie
)
1139 op (&h
->m_entries
, cookie
);
1142 template<typename H
>
1144 gt_cleare_cache (hash_table
<H
> *h
)
1146 extern void gt_ggc_mx (typename
H::value_type
&t
);
1147 typedef hash_table
<H
> table
;
1151 for (typename
table::iterator iter
= h
->begin (); iter
!= h
->end (); ++iter
)
1152 if (!table::is_empty (*iter
) && !table::is_deleted (*iter
))
1154 int res
= H::keep_cache_entry (*iter
);
1156 h
->clear_slot (&*iter
);
1162 #endif /* TYPED_HASHTAB_H */