1 /* A type-safe hash map.
2 Copyright (C) 2014-2019 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
24 /* Class hash_map is a hash-value based container mapping objects of
25 KeyId type to those of the Value type.
26 Both KeyId and Value may be non-trivial (non-POD) types provided
27 a suitabe Traits class. A few default Traits specializations are
28 provided for basic types such as integers, pointers, and std::pair.
29 Inserted elements are value-initialized either to zero for POD types
30 or by invoking their default ctor. Removed elements are destroyed
31 by invoking their dtor. On hash_map destruction all elements are
32 removed. Objects of hash_map type are copy-constructible but not
35 template<typename KeyId
, typename Value
,
36 typename Traits
/* = simple_hashmap_traits<default_hash_traits<Key>,
38 class GTY((user
)) hash_map
40 typedef typename
Traits::key_type Key
;
46 typedef hash_entry value_type
;
47 typedef Key compare_type
;
49 static hashval_t
hash (const hash_entry
&e
)
51 return Traits::hash (e
.m_key
);
54 static bool equal (const hash_entry
&a
, const Key
&b
)
56 return Traits::equal_keys (a
.m_key
, b
);
59 static void remove (hash_entry
&e
) { Traits::remove (e
); }
61 static void mark_deleted (hash_entry
&e
) { Traits::mark_deleted (e
); }
63 static bool is_deleted (const hash_entry
&e
)
65 return Traits::is_deleted (e
);
68 static void mark_empty (hash_entry
&e
) { Traits::mark_empty (e
); }
69 static bool is_empty (const hash_entry
&e
) { return Traits::is_empty (e
); }
71 static void ggc_mx (hash_entry
&e
)
74 gt_ggc_mx (e
.m_value
);
77 static void ggc_maybe_mx (hash_entry
&e
)
83 static void pch_nx (hash_entry
&e
)
86 gt_pch_nx (e
.m_value
);
89 static void pch_nx (hash_entry
&e
, gt_pointer_operator op
, void *c
)
91 pch_nx_helper (e
.m_key
, op
, c
);
92 pch_nx_helper (e
.m_value
, op
, c
);
95 static int keep_cache_entry (hash_entry
&e
)
97 return ggc_marked_p (e
.m_key
);
103 pch_nx_helper (T
&x
, gt_pointer_operator op
, void *cookie
)
105 gt_pch_nx (&x
, op
, cookie
);
109 pch_nx_helper (int, gt_pointer_operator
, void *)
114 pch_nx_helper (unsigned int, gt_pointer_operator
, void *)
119 pch_nx_helper (bool, gt_pointer_operator
, void *)
125 pch_nx_helper (T
*&x
, gt_pointer_operator op
, void *cookie
)
132 explicit hash_map (size_t n
= 13, bool ggc
= false,
133 bool sanitize_eq_and_hash
= true,
134 bool gather_mem_stats
= GATHER_STATISTICS
136 : m_table (n
, ggc
, sanitize_eq_and_hash
, gather_mem_stats
,
137 HASH_MAP_ORIGIN PASS_MEM_STAT
)
141 explicit hash_map (const hash_map
&h
, bool ggc
= false,
142 bool sanitize_eq_and_hash
= true,
143 bool gather_mem_stats
= GATHER_STATISTICS
145 : m_table (h
.m_table
, ggc
, sanitize_eq_and_hash
, gather_mem_stats
,
146 HASH_MAP_ORIGIN PASS_MEM_STAT
) {}
148 /* Create a hash_map in ggc memory. */
149 static hash_map
*create_ggc (size_t size
,
150 bool gather_mem_stats
= GATHER_STATISTICS
153 hash_map
*map
= ggc_alloc
<hash_map
> ();
154 new (map
) hash_map (size
, true, true, gather_mem_stats PASS_MEM_STAT
);
158 /* If key k isn't already in the map add key k with value v to the map, and
159 return false. Otherwise set the value of the entry for key k to be v and
162 bool put (const Key
&k
, const Value
&v
)
164 hash_entry
*e
= m_table
.find_slot_with_hash (k
, Traits::hash (k
),
166 bool ins
= hash_entry::is_empty (*e
);
170 new ((void *) &e
->m_value
) Value (v
);
178 /* if the passed in key is in the map return its value otherwise NULL. */
180 Value
*get (const Key
&k
)
182 hash_entry
&e
= m_table
.find_with_hash (k
, Traits::hash (k
));
183 return Traits::is_empty (e
) ? NULL
: &e
.m_value
;
186 /* Return a reference to the value for the passed in key, creating the entry
187 if it doesn't already exist. If existed is not NULL then it is set to
188 false if the key was not previously in the map, and true otherwise. */
190 Value
&get_or_insert (const Key
&k
, bool *existed
= NULL
)
192 hash_entry
*e
= m_table
.find_slot_with_hash (k
, Traits::hash (k
),
194 bool ins
= Traits::is_empty (*e
);
198 new ((void *)&e
->m_value
) Value ();
207 void remove (const Key
&k
)
209 m_table
.remove_elt_with_hash (k
, Traits::hash (k
));
212 /* Call the call back on each pair of key and value with the passed in
215 template<typename Arg
, bool (*f
)(const typename
Traits::key_type
&,
217 void traverse (Arg a
) const
219 for (typename hash_table
<hash_entry
>::iterator iter
= m_table
.begin ();
220 iter
!= m_table
.end (); ++iter
)
221 f ((*iter
).m_key
, (*iter
).m_value
, a
);
224 template<typename Arg
, bool (*f
)(const typename
Traits::key_type
&,
226 void traverse (Arg a
) const
228 for (typename hash_table
<hash_entry
>::iterator iter
= m_table
.begin ();
229 iter
!= m_table
.end (); ++iter
)
230 if (!f ((*iter
).m_key
, &(*iter
).m_value
, a
))
234 size_t elements () const { return m_table
.elements (); }
236 void empty () { m_table
.empty(); }
238 /* Return true when there are no elements in this hash map. */
239 bool is_empty () const { return m_table
.is_empty (); }
244 explicit iterator (const typename hash_table
<hash_entry
>::iterator
&iter
) :
247 iterator
&operator++ ()
253 /* Can't use std::pair here, because GCC before 4.3 don't handle
254 std::pair where template parameters are references well.
256 class reference_pair
{
261 reference_pair (const Key
&key
, Value
&value
) : first (key
), second (value
) {}
263 template <typename K
, typename V
>
264 operator std::pair
<K
, V
> () const { return std::pair
<K
, V
> (first
, second
); }
267 reference_pair
operator* ()
269 hash_entry
&e
= *m_iter
;
270 return reference_pair (e
.m_key
, e
.m_value
);
274 operator != (const iterator
&other
) const
276 return m_iter
!= other
.m_iter
;
280 typename hash_table
<hash_entry
>::iterator m_iter
;
283 /* Standard iterator retrieval methods. */
285 iterator
begin () const { return iterator (m_table
.begin ()); }
286 iterator
end () const { return iterator (m_table
.end ()); }
290 template<typename T
, typename U
, typename V
> friend void gt_ggc_mx (hash_map
<T
, U
, V
> *);
291 template<typename T
, typename U
, typename V
> friend void gt_pch_nx (hash_map
<T
, U
, V
> *);
292 template<typename T
, typename U
, typename V
> friend void gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
293 template<typename T
, typename U
, typename V
> friend void gt_cleare_cache (hash_map
<T
, U
, V
> *);
295 hash_table
<hash_entry
> m_table
;
298 /* ggc marking routines. */
300 template<typename K
, typename V
, typename H
>
302 gt_ggc_mx (hash_map
<K
, V
, H
> *h
)
304 gt_ggc_mx (&h
->m_table
);
307 template<typename K
, typename V
, typename H
>
309 gt_pch_nx (hash_map
<K
, V
, H
> *h
)
311 gt_pch_nx (&h
->m_table
);
314 template<typename K
, typename V
, typename H
>
316 gt_cleare_cache (hash_map
<K
, V
, H
> *h
)
319 gt_cleare_cache (&h
->m_table
);
322 template<typename K
, typename V
, typename H
>
324 gt_pch_nx (hash_map
<K
, V
, H
> *h
, gt_pointer_operator op
, void *cookie
)
326 op (&h
->m_table
.m_entries
, cookie
);