1 /* A type-safe hash table template.
2 Copyright (C) 2012-2016 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* This file implements a typed hash table.
23 The implementation borrows from libiberty's htab_t in hashtab.h.
28 Users of the hash table generally need to be aware of three types.
30 1. The type being placed into the hash table. This type is called
33 2. The type used to describe how to handle the value type within
34 the hash table. This descriptor type provides the hash table with
37 - A typedef named 'value_type' to the value type (from above).
39 - A static member function named 'hash' that takes a value_type
40 (or 'const value_type &') and returns a hashval_t value.
42 - A typedef named 'compare_type' that is used to test when a value
43 is found. This type is the comparison type. Usually, it will be the
44 same as value_type. If it is not the same type, you must generally
45 explicitly compute hash values and pass them to the hash table.
47 - A static member function named 'equal' that takes a value_type
48 and a compare_type, and returns a bool. Both arguments can be
51 - A static function named 'remove' that takes an value_type pointer
52 and frees the memory allocated by it. This function is used when
53 individual elements of the table need to be disposed of (e.g.,
54 when deleting a hash table, removing elements from the table, etc).
56 - An optional static function named 'keep_cache_entry'. This
57 function is provided only for garbage-collected elements that
58 are not marked by the normal gc mark pass. It describes what
59 what should happen to the element at the end of the gc mark phase.
60 The return value should be:
61 - 0 if the element should be deleted
62 - 1 if the element should be kept and needs to be marked
63 - -1 if the element should be kept and is already marked.
64 Returning -1 rather than 1 is purely an optimization.
66 3. The type of the hash table itself. (More later.)
68 In very special circumstances, users may need to know about a fourth type.
70 4. The template type used to describe how hash table memory
71 is allocated. This type is called the allocator type. It is
72 parameterized on the value type. It provides two functions:
74 - A static member function named 'data_alloc'. This function
75 allocates the data elements in the table.
77 - A static member function named 'data_free'. This function
78 deallocates the data elements in the table.
80 Hash table are instantiated with two type arguments.
82 * The descriptor type, (2) above.
84 * The allocator type, (4) above. In general, you will not need to
85 provide your own allocator type. By default, hash tables will use
86 the class template xcallocator, which uses malloc/free for allocation.
89 DEFINING A DESCRIPTOR TYPE
91 The first task in using the hash table is to describe the element type.
92 We compose this into a few steps.
94 1. Decide on a removal policy for values stored in the table.
95 hash-traits.h provides class templates for the four most common
98 * typed_free_remove implements the static 'remove' member function
101 * typed_noop_remove implements the static 'remove' member function
104 * ggc_remove implements the static 'remove' member by doing nothing,
105 but instead provides routines for gc marking and for PCH streaming.
106 Use this for garbage-collected data that needs to be preserved across
109 * ggc_cache_remove is like ggc_remove, except that it does not
110 mark the entries during the normal gc mark phase. Instead it
111 uses 'keep_cache_entry' (described above) to keep elements that
112 were not collected and delete those that were. Use this for
113 garbage-collected caches that should not in themselves stop
114 the data from being collected.
116 You can use these policies by simply deriving the descriptor type
117 from one of those class template, with the appropriate argument.
119 Otherwise, you need to write the static 'remove' member function
120 in the descriptor class.
122 2. Choose a hash function. Write the static 'hash' member function.
124 3. Decide whether the lookup function should take as input an object
125 of type value_type or something more restricted. Define compare_type
128 4. Choose an equality testing function 'equal' that compares a value_type
131 If your elements are pointers, it is usually easiest to start with one
132 of the generic pointer descriptors described below and override the bits
135 AN EXAMPLE DESCRIPTOR TYPE
137 Suppose you want to put some_type into the hash table. You could define
138 the descriptor type as follows.
140 struct some_type_hasher : nofree_ptr_hash <some_type>
141 // Deriving from nofree_ptr_hash means that we get a 'remove' that does
142 // nothing. This choice is good for raw values.
144 static inline hashval_t hash (const value_type *);
145 static inline bool equal (const value_type *, const compare_type *);
149 some_type_hasher::hash (const value_type *e)
150 { ... compute and return a hash value for E ... }
153 some_type_hasher::equal (const value_type *p1, const compare_type *p2)
154 { ... compare P1 vs P2. Return true if they are the 'same' ... }
157 AN EXAMPLE HASH_TABLE DECLARATION
159 To instantiate a hash table for some_type:
161 hash_table <some_type_hasher> some_type_hash_table;
163 There is no need to mention some_type directly, as the hash table will
164 obtain it using some_type_hasher::value_type.
166 You can then use any of the functions in hash_table's public interface.
167 See hash_table for details. The interface is very similar to libiberty's
171 EASY DESCRIPTORS FOR POINTERS
173 There are four descriptors for pointer elements, one for each of
174 the removal policies above:
176 * nofree_ptr_hash (based on typed_noop_remove)
177 * free_ptr_hash (based on typed_free_remove)
178 * ggc_ptr_hash (based on ggc_remove)
179 * ggc_cache_ptr_hash (based on ggc_cache_remove)
181 These descriptors hash and compare elements by their pointer value,
182 rather than what they point to. So, to instantiate a hash table over
183 pointers to whatever_type, without freeing the whatever_types, use:
185 hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
190 The hash table provides standard C++ iterators. For example, consider a
191 hash table of some_info. We wish to consume each element of the table:
193 extern void consume (some_info *);
195 We define a convenience typedef and the hash table:
197 typedef hash_table <some_info_hasher> info_table_type;
198 info_table_type info_table;
200 Then we write the loop in typical C++ style:
202 for (info_table_type::iterator iter = info_table.begin ();
203 iter != info_table.end ();
205 if ((*iter).status == INFO_READY)
208 Or with common sub-expression elimination:
210 for (info_table_type::iterator iter = info_table.begin ();
211 iter != info_table.end ();
214 some_info &elem = *iter;
215 if (elem.status == INFO_READY)
219 One can also use a more typical GCC style:
221 typedef some_info *some_info_p;
223 info_table_type::iterator iter;
224 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
225 if (elem_ptr->status == INFO_READY)
231 #ifndef TYPED_HASHTAB_H
232 #define TYPED_HASHTAB_H
234 #include "statistics.h"
239 #include "mem-stats-traits.h"
240 #include "hash-traits.h"
241 #include "hash-map-traits.h"
243 template<typename
, typename
, typename
> class hash_map
;
244 template<typename
, typename
> class hash_set
;
246 /* The ordinary memory allocator. */
247 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
249 template <typename Type
>
252 static Type
*data_alloc (size_t count
);
253 static void data_free (Type
*memory
);
257 /* Allocate memory for COUNT data blocks. */
259 template <typename Type
>
261 xcallocator
<Type
>::data_alloc (size_t count
)
263 return static_cast <Type
*> (xcalloc (count
, sizeof (Type
)));
267 /* Free memory for data blocks. */
269 template <typename Type
>
271 xcallocator
<Type
>::data_free (Type
*memory
)
273 return ::free (memory
);
277 /* Table of primes and their inversion information. */
283 hashval_t inv_m2
; /* inverse of prime-2 */
287 extern struct prime_ent
const prime_tab
[];
290 /* Functions for computing hash table indexes. */
292 extern unsigned int hash_table_higher_prime_index (unsigned long n
)
295 /* Return X % Y using multiplicative inverse values INV and SHIFT.
297 The multiplicative inverses computed above are for 32-bit types,
298 and requires that we be able to compute a highpart multiply.
300 FIX: I am not at all convinced that
301 3 loads, 2 multiplications, 3 shifts, and 3 additions
304 on modern systems running a compiler. */
307 mul_mod (hashval_t x
, hashval_t y
, hashval_t inv
, int shift
)
309 hashval_t t1
, t2
, t3
, t4
, q
, r
;
311 t1
= ((uint64_t)x
* inv
) >> 32;
321 /* Compute the primary table index for HASH given current prime index. */
324 hash_table_mod1 (hashval_t hash
, unsigned int index
)
326 const struct prime_ent
*p
= &prime_tab
[index
];
327 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
328 return mul_mod (hash
, p
->prime
, p
->inv
, p
->shift
);
331 /* Compute the secondary table index for HASH given current prime index. */
334 hash_table_mod2 (hashval_t hash
, unsigned int index
)
336 const struct prime_ent
*p
= &prime_tab
[index
];
337 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
338 return 1 + mul_mod (hash
, p
->prime
- 2, p
->inv_m2
, p
->shift
);
343 /* User-facing hash table type.
345 The table stores elements of type Descriptor::value_type and uses
346 the static descriptor functions described at the top of the file
347 to hash, compare and remove elements.
349 Specify the template Allocator to allocate and free memory.
350 The default is xcallocator.
352 Storage is an implementation detail and should not be used outside the
356 template <typename Descriptor
,
357 template<typename Type
> class Allocator
= xcallocator
>
360 typedef typename
Descriptor::value_type value_type
;
361 typedef typename
Descriptor::compare_type compare_type
;
364 explicit hash_table (size_t, bool ggc
= false,
365 bool gather_mem_stats
= GATHER_STATISTICS
,
366 mem_alloc_origin origin
= HASH_TABLE_ORIGIN
368 explicit hash_table (const hash_table
&, bool ggc
= false,
369 bool gather_mem_stats
= GATHER_STATISTICS
,
370 mem_alloc_origin origin
= HASH_TABLE_ORIGIN
374 /* Create a hash_table in gc memory. */
376 create_ggc (size_t n CXX_MEM_STAT_INFO
)
378 hash_table
*table
= ggc_alloc
<hash_table
> ();
379 new (table
) hash_table (n
, true, GATHER_STATISTICS
,
380 HASH_TABLE_ORIGIN PASS_MEM_STAT
);
384 /* Current size (in entries) of the hash table. */
385 size_t size () const { return m_size
; }
387 /* Return the current number of elements in this hash table. */
388 size_t elements () const { return m_n_elements
- m_n_deleted
; }
390 /* Return the current number of elements in this hash table. */
391 size_t elements_with_deleted () const { return m_n_elements
; }
393 /* This function clears all entries in the given hash table. */
396 /* This function clears a specified SLOT in a hash table. It is
397 useful when you've already done the lookup and don't want to do it
399 void clear_slot (value_type
*);
401 /* This function searches for a hash table entry equal to the given
402 COMPARABLE element starting with the given HASH value. It cannot
403 be used to insert or delete an element. */
404 value_type
&find_with_hash (const compare_type
&, hashval_t
);
406 /* Like find_slot_with_hash, but compute the hash value from the element. */
407 value_type
&find (const value_type
&value
)
409 return find_with_hash (value
, Descriptor::hash (value
));
412 value_type
*find_slot (const value_type
&value
, insert_option insert
)
414 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
417 /* This function searches for a hash table slot containing an entry
418 equal to the given COMPARABLE element and starting with the given
419 HASH. To delete an entry, call this with insert=NO_INSERT, then
420 call clear_slot on the slot returned (possibly after doing some
421 checks). To insert an entry, call this with insert=INSERT, then
422 write the value you want into the returned slot. When inserting an
423 entry, NULL may be returned if memory allocation fails. */
424 value_type
*find_slot_with_hash (const compare_type
&comparable
,
425 hashval_t hash
, enum insert_option insert
);
427 /* This function deletes an element with the given COMPARABLE value
428 from hash table starting with the given HASH. If there is no
429 matching element in the hash table, this function does nothing. */
430 void remove_elt_with_hash (const compare_type
&, hashval_t
);
432 /* Like remove_elt_with_hash, but compute the hash value from the
434 void remove_elt (const value_type
&value
)
436 remove_elt_with_hash (value
, Descriptor::hash (value
));
439 /* This function scans over the entire hash table calling CALLBACK for
440 each live entry. If CALLBACK returns false, the iteration stops.
441 ARGUMENT is passed as CALLBACK's second argument. */
442 template <typename Argument
,
443 int (*Callback
) (value_type
*slot
, Argument argument
)>
444 void traverse_noresize (Argument argument
);
446 /* Like traverse_noresize, but does resize the table when it is too empty
447 to improve effectivity of subsequent calls. */
448 template <typename Argument
,
449 int (*Callback
) (value_type
*slot
, Argument argument
)>
450 void traverse (Argument argument
);
455 iterator () : m_slot (NULL
), m_limit (NULL
) {}
457 iterator (value_type
*slot
, value_type
*limit
) :
458 m_slot (slot
), m_limit (limit
) {}
460 inline value_type
&operator * () { return *m_slot
; }
462 inline iterator
&operator ++ ();
463 bool operator != (const iterator
&other
) const
465 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
473 iterator
begin () const
475 iterator
iter (m_entries
, m_entries
+ m_size
);
480 iterator
end () const { return iterator (); }
482 double collisions () const
484 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
488 template<typename T
> friend void gt_ggc_mx (hash_table
<T
> *);
489 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *);
490 template<typename T
> friend void
491 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator
, void *);
492 template<typename T
, typename U
, typename V
> friend void
493 gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
494 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *,
497 template<typename T
> friend void gt_pch_nx (hash_table
<T
> *,
498 gt_pointer_operator
, void *);
500 template<typename T
> friend void gt_cleare_cache (hash_table
<T
> *);
502 value_type
*alloc_entries (size_t n CXX_MEM_STAT_INFO
) const;
503 value_type
*find_empty_slot_for_expand (hashval_t
);
505 static bool is_deleted (value_type
&v
)
507 return Descriptor::is_deleted (v
);
510 static bool is_empty (value_type
&v
)
512 return Descriptor::is_empty (v
);
515 static void mark_deleted (value_type
&v
)
517 Descriptor::mark_deleted (v
);
520 static void mark_empty (value_type
&v
)
522 Descriptor::mark_empty (v
);
526 typename
Descriptor::value_type
*m_entries
;
530 /* Current number of elements including also deleted elements. */
533 /* Current number of deleted elements in the table. */
536 /* The following member is used for debugging. Its value is number
537 of all calls of `htab_find_slot' for the hash table. */
538 unsigned int m_searches
;
540 /* The following member is used for debugging. Its value is number
541 of collisions fixed for time of work with the hash table. */
542 unsigned int m_collisions
;
544 /* Current size (in entries) of the hash table, as an index into the
546 unsigned int m_size_prime_index
;
548 /* if m_entries is stored in ggc memory. */
551 /* If we should gather memory statistics for the table. */
552 bool m_gather_mem_stats
;
555 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
556 mem-stats.h after hash_table declaration. */
558 #include "mem-stats.h"
559 #include "hash-map.h"
561 extern mem_alloc_description
<mem_usage
> hash_table_usage
;
563 /* Support function for statistics. */
564 extern void dump_hash_table_loc_statistics (void);
566 template<typename Descriptor
, template<typename Type
> class Allocator
>
567 hash_table
<Descriptor
, Allocator
>::hash_table (size_t size
, bool ggc
, bool
569 mem_alloc_origin origin
571 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
572 m_ggc (ggc
), m_gather_mem_stats (gather_mem_stats
)
574 unsigned int size_prime_index
;
576 size_prime_index
= hash_table_higher_prime_index (size
);
577 size
= prime_tab
[size_prime_index
].prime
;
579 if (m_gather_mem_stats
)
580 hash_table_usage
.register_descriptor (this, origin
, ggc
581 FINAL_PASS_MEM_STAT
);
583 m_entries
= alloc_entries (size PASS_MEM_STAT
);
585 m_size_prime_index
= size_prime_index
;
588 template<typename Descriptor
, template<typename Type
> class Allocator
>
589 hash_table
<Descriptor
, Allocator
>::hash_table (const hash_table
&h
, bool ggc
,
590 bool gather_mem_stats
,
591 mem_alloc_origin origin
593 m_n_elements (h
.m_n_elements
), m_n_deleted (h
.m_n_deleted
),
594 m_searches (0), m_collisions (0), m_ggc (ggc
),
595 m_gather_mem_stats (gather_mem_stats
)
597 size_t size
= h
.m_size
;
599 if (m_gather_mem_stats
)
600 hash_table_usage
.register_descriptor (this, origin
, ggc
601 FINAL_PASS_MEM_STAT
);
603 value_type
*nentries
= alloc_entries (size PASS_MEM_STAT
);
604 for (size_t i
= 0; i
< size
; ++i
)
606 value_type
&entry
= h
.m_entries
[i
];
607 if (is_deleted (entry
))
608 mark_deleted (nentries
[i
]);
609 else if (!is_empty (entry
))
612 m_entries
= nentries
;
614 m_size_prime_index
= h
.m_size_prime_index
;
617 template<typename Descriptor
, template<typename Type
> class Allocator
>
618 hash_table
<Descriptor
, Allocator
>::~hash_table ()
620 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
621 if (!is_empty (m_entries
[i
]) && !is_deleted (m_entries
[i
]))
622 Descriptor::remove (m_entries
[i
]);
625 Allocator
<value_type
> ::data_free (m_entries
);
627 ggc_free (m_entries
);
629 if (m_gather_mem_stats
)
630 hash_table_usage
.release_instance_overhead (this,
631 sizeof (value_type
) * m_size
,
635 /* This function returns an array of empty hash table elements. */
637 template<typename Descriptor
, template<typename Type
> class Allocator
>
638 inline typename hash_table
<Descriptor
, Allocator
>::value_type
*
639 hash_table
<Descriptor
, Allocator
>::alloc_entries (size_t n MEM_STAT_DECL
) const
641 value_type
*nentries
;
643 if (m_gather_mem_stats
)
644 hash_table_usage
.register_instance_overhead (sizeof (value_type
) * n
, this);
647 nentries
= Allocator
<value_type
> ::data_alloc (n
);
649 nentries
= ::ggc_cleared_vec_alloc
<value_type
> (n PASS_MEM_STAT
);
651 gcc_assert (nentries
!= NULL
);
652 for (size_t i
= 0; i
< n
; i
++)
653 mark_empty (nentries
[i
]);
658 /* Similar to find_slot, but without several unwanted side effects:
659 - Does not call equal when it finds an existing entry.
660 - Does not change the count of elements/searches/collisions in the
662 This function also assumes there are no deleted entries in the table.
663 HASH is the hash value for the element to be inserted. */
665 template<typename Descriptor
, template<typename Type
> class Allocator
>
666 typename hash_table
<Descriptor
, Allocator
>::value_type
*
667 hash_table
<Descriptor
, Allocator
>::find_empty_slot_for_expand (hashval_t hash
)
669 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
670 size_t size
= m_size
;
671 value_type
*slot
= m_entries
+ index
;
674 if (is_empty (*slot
))
676 gcc_checking_assert (!is_deleted (*slot
));
678 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
685 slot
= m_entries
+ index
;
686 if (is_empty (*slot
))
688 gcc_checking_assert (!is_deleted (*slot
));
692 /* The following function changes size of memory allocated for the
693 entries and repeatedly inserts the table elements. The occupancy
694 of the table after the call will be about 50%. Naturally the hash
695 table must already exist. Remember also that the place of the
696 table entries is changed. If memory allocation fails, this function
699 template<typename Descriptor
, template<typename Type
> class Allocator
>
701 hash_table
<Descriptor
, Allocator
>::expand ()
703 value_type
*oentries
= m_entries
;
704 unsigned int oindex
= m_size_prime_index
;
705 size_t osize
= size ();
706 value_type
*olimit
= oentries
+ osize
;
707 size_t elts
= elements ();
709 /* Resize only when table after removal of unused elements is either
710 too full or too empty. */
713 if (elts
* 2 > osize
|| (elts
* 8 < osize
&& osize
> 32))
715 nindex
= hash_table_higher_prime_index (elts
* 2);
716 nsize
= prime_tab
[nindex
].prime
;
724 value_type
*nentries
= alloc_entries (nsize
);
726 if (m_gather_mem_stats
)
727 hash_table_usage
.release_instance_overhead (this, sizeof (value_type
)
730 m_entries
= nentries
;
732 m_size_prime_index
= nindex
;
733 m_n_elements
-= m_n_deleted
;
736 value_type
*p
= oentries
;
741 if (!is_empty (x
) && !is_deleted (x
))
743 value_type
*q
= find_empty_slot_for_expand (Descriptor::hash (x
));
753 Allocator
<value_type
> ::data_free (oentries
);
758 template<typename Descriptor
, template<typename Type
> class Allocator
>
760 hash_table
<Descriptor
, Allocator
>::empty ()
762 size_t size
= m_size
;
763 value_type
*entries
= m_entries
;
766 for (i
= size
- 1; i
>= 0; i
--)
767 if (!is_empty (entries
[i
]) && !is_deleted (entries
[i
]))
768 Descriptor::remove (entries
[i
]);
770 /* Instead of clearing megabyte, downsize the table. */
771 if (size
> 1024*1024 / sizeof (PTR
))
773 int nindex
= hash_table_higher_prime_index (1024 / sizeof (PTR
));
774 int nsize
= prime_tab
[nindex
].prime
;
777 Allocator
<value_type
> ::data_free (m_entries
);
779 ggc_free (m_entries
);
781 m_entries
= alloc_entries (nsize
);
783 m_size_prime_index
= nindex
;
786 memset (entries
, 0, size
* sizeof (value_type
));
791 /* This function clears a specified SLOT in a hash table. It is
792 useful when you've already done the lookup and don't want to do it
795 template<typename Descriptor
, template<typename Type
> class Allocator
>
797 hash_table
<Descriptor
, Allocator
>::clear_slot (value_type
*slot
)
799 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
800 || is_empty (*slot
) || is_deleted (*slot
)));
802 Descriptor::remove (*slot
);
804 mark_deleted (*slot
);
808 /* This function searches for a hash table entry equal to the given
809 COMPARABLE element starting with the given HASH value. It cannot
810 be used to insert or delete an element. */
812 template<typename Descriptor
, template<typename Type
> class Allocator
>
813 typename hash_table
<Descriptor
, Allocator
>::value_type
&
814 hash_table
<Descriptor
, Allocator
>
815 ::find_with_hash (const compare_type
&comparable
, hashval_t hash
)
818 size_t size
= m_size
;
819 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
821 value_type
*entry
= &m_entries
[index
];
822 if (is_empty (*entry
)
823 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
826 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
834 entry
= &m_entries
[index
];
835 if (is_empty (*entry
)
836 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
841 /* This function searches for a hash table slot containing an entry
842 equal to the given COMPARABLE element and starting with the given
843 HASH. To delete an entry, call this with insert=NO_INSERT, then
844 call clear_slot on the slot returned (possibly after doing some
845 checks). To insert an entry, call this with insert=INSERT, then
846 write the value you want into the returned slot. When inserting an
847 entry, NULL may be returned if memory allocation fails. */
849 template<typename Descriptor
, template<typename Type
> class Allocator
>
850 typename hash_table
<Descriptor
, Allocator
>::value_type
*
851 hash_table
<Descriptor
, Allocator
>
852 ::find_slot_with_hash (const compare_type
&comparable
, hashval_t hash
,
853 enum insert_option insert
)
855 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
860 value_type
*first_deleted_slot
= NULL
;
861 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
862 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
863 value_type
*entry
= &m_entries
[index
];
864 size_t size
= m_size
;
865 if (is_empty (*entry
))
867 else if (is_deleted (*entry
))
868 first_deleted_slot
= &m_entries
[index
];
869 else if (Descriptor::equal (*entry
, comparable
))
870 return &m_entries
[index
];
879 entry
= &m_entries
[index
];
880 if (is_empty (*entry
))
882 else if (is_deleted (*entry
))
884 if (!first_deleted_slot
)
885 first_deleted_slot
= &m_entries
[index
];
887 else if (Descriptor::equal (*entry
, comparable
))
888 return &m_entries
[index
];
892 if (insert
== NO_INSERT
)
895 if (first_deleted_slot
)
898 mark_empty (*first_deleted_slot
);
899 return first_deleted_slot
;
903 return &m_entries
[index
];
906 /* This function deletes an element with the given COMPARABLE value
907 from hash table starting with the given HASH. If there is no
908 matching element in the hash table, this function does nothing. */
910 template<typename Descriptor
, template<typename Type
> class Allocator
>
912 hash_table
<Descriptor
, Allocator
>
913 ::remove_elt_with_hash (const compare_type
&comparable
, hashval_t hash
)
915 value_type
*slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
916 if (is_empty (*slot
))
919 Descriptor::remove (*slot
);
921 mark_deleted (*slot
);
925 /* This function scans over the entire hash table calling CALLBACK for
926 each live entry. If CALLBACK returns false, the iteration stops.
927 ARGUMENT is passed as CALLBACK's second argument. */
929 template<typename Descriptor
,
930 template<typename Type
> class Allocator
>
931 template<typename Argument
,
933 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
936 hash_table
<Descriptor
, Allocator
>::traverse_noresize (Argument argument
)
938 value_type
*slot
= m_entries
;
939 value_type
*limit
= slot
+ size ();
943 value_type
&x
= *slot
;
945 if (!is_empty (x
) && !is_deleted (x
))
946 if (! Callback (slot
, argument
))
949 while (++slot
< limit
);
952 /* Like traverse_noresize, but does resize the table when it is too empty
953 to improve effectivity of subsequent calls. */
955 template <typename Descriptor
,
956 template <typename Type
> class Allocator
>
957 template <typename Argument
,
959 (typename hash_table
<Descriptor
, Allocator
>::value_type
*slot
,
962 hash_table
<Descriptor
, Allocator
>::traverse (Argument argument
)
964 size_t size
= m_size
;
965 if (elements () * 8 < size
&& size
> 32)
968 traverse_noresize
<Argument
, Callback
> (argument
);
971 /* Slide down the iterator slots until an active entry is found. */
973 template<typename Descriptor
, template<typename Type
> class Allocator
>
975 hash_table
<Descriptor
, Allocator
>::iterator::slide ()
977 for ( ; m_slot
< m_limit
; ++m_slot
)
979 value_type
&x
= *m_slot
;
980 if (!is_empty (x
) && !is_deleted (x
))
987 /* Bump the iterator. */
989 template<typename Descriptor
, template<typename Type
> class Allocator
>
990 inline typename hash_table
<Descriptor
, Allocator
>::iterator
&
991 hash_table
<Descriptor
, Allocator
>::iterator::operator ++ ()
999 /* Iterate through the elements of hash_table HTAB,
1000 using hash_table <....>::iterator ITER,
1001 storing each element in RESULT, which is of type TYPE. */
1003 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1004 for ((ITER) = (HTAB).begin (); \
1005 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1008 /* ggc walking routines. */
1010 template<typename E
>
1012 gt_ggc_mx (hash_table
<E
> *h
)
1014 typedef hash_table
<E
> table
;
1016 if (!ggc_test_and_set_mark (h
->m_entries
))
1019 for (size_t i
= 0; i
< h
->m_size
; i
++)
1021 if (table::is_empty (h
->m_entries
[i
])
1022 || table::is_deleted (h
->m_entries
[i
]))
1025 E::ggc_mx (h
->m_entries
[i
]);
1029 template<typename D
>
1031 hashtab_entry_note_pointers (void *obj
, void *h
, gt_pointer_operator op
,
1034 hash_table
<D
> *map
= static_cast<hash_table
<D
> *> (h
);
1035 gcc_checking_assert (map
->m_entries
== obj
);
1036 for (size_t i
= 0; i
< map
->m_size
; i
++)
1038 typedef hash_table
<D
> table
;
1039 if (table::is_empty (map
->m_entries
[i
])
1040 || table::is_deleted (map
->m_entries
[i
]))
1043 D::pch_nx (map
->m_entries
[i
], op
, cookie
);
1047 template<typename D
>
1049 gt_pch_nx (hash_table
<D
> *h
)
1052 = gt_pch_note_object (h
->m_entries
, h
, hashtab_entry_note_pointers
<D
>);
1053 gcc_checking_assert (success
);
1054 for (size_t i
= 0; i
< h
->m_size
; i
++)
1056 if (hash_table
<D
>::is_empty (h
->m_entries
[i
])
1057 || hash_table
<D
>::is_deleted (h
->m_entries
[i
]))
1060 D::pch_nx (h
->m_entries
[i
]);
1064 template<typename D
>
1066 gt_pch_nx (hash_table
<D
> *h
, gt_pointer_operator op
, void *cookie
)
1068 op (&h
->m_entries
, cookie
);
1071 template<typename H
>
1073 gt_cleare_cache (hash_table
<H
> *h
)
1075 extern void gt_ggc_mx (typename
H::value_type
&t
);
1076 typedef hash_table
<H
> table
;
1080 for (typename
table::iterator iter
= h
->begin (); iter
!= h
->end (); ++iter
)
1081 if (!table::is_empty (*iter
) && !table::is_deleted (*iter
))
1083 int res
= H::keep_cache_entry (*iter
);
1085 h
->clear_slot (&*iter
);
1091 #endif /* TYPED_HASHTAB_H */