1 /* A type-safe hash map.
2 Copyright (C) 2014-2020 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 const size_t default_hash_map_size
= 13;
36 template<typename KeyId
, typename Value
,
37 typename Traits
/* = simple_hashmap_traits<default_hash_traits<Key>,
39 class GTY((user
)) hash_map
41 typedef typename
Traits::key_type Key
;
47 typedef hash_entry value_type
;
48 typedef Key compare_type
;
50 static hashval_t
hash (const hash_entry
&e
)
52 return Traits::hash (e
.m_key
);
55 static bool equal (const hash_entry
&a
, const Key
&b
)
57 return Traits::equal_keys (a
.m_key
, b
);
60 static void remove (hash_entry
&e
) { Traits::remove (e
); }
62 static void mark_deleted (hash_entry
&e
) { Traits::mark_deleted (e
); }
64 static bool is_deleted (const hash_entry
&e
)
66 return Traits::is_deleted (e
);
69 static const bool empty_zero_p
= Traits::empty_zero_p
;
70 static void mark_empty (hash_entry
&e
) { Traits::mark_empty (e
); }
71 static bool is_empty (const hash_entry
&e
) { return Traits::is_empty (e
); }
73 static void ggc_mx (hash_entry
&e
)
76 gt_ggc_mx (e
.m_value
);
79 static void ggc_maybe_mx (hash_entry
&e
)
85 static void pch_nx (hash_entry
&e
)
88 gt_pch_nx (e
.m_value
);
91 static void pch_nx (hash_entry
&e
, gt_pointer_operator op
, void *c
)
93 pch_nx_helper (e
.m_key
, op
, c
);
94 pch_nx_helper (e
.m_value
, op
, c
);
97 static int keep_cache_entry (hash_entry
&e
)
99 return ggc_marked_p (e
.m_key
);
105 pch_nx_helper (T
&x
, gt_pointer_operator op
, void *cookie
)
107 gt_pch_nx (&x
, op
, cookie
);
111 pch_nx_helper (int, gt_pointer_operator
, void *)
116 pch_nx_helper (unsigned int, gt_pointer_operator
, void *)
121 pch_nx_helper (bool, gt_pointer_operator
, void *)
127 pch_nx_helper (T
*&x
, gt_pointer_operator op
, void *cookie
)
134 explicit hash_map (size_t n
= default_hash_map_size
, bool ggc
= false,
135 bool sanitize_eq_and_hash
= true,
136 bool gather_mem_stats
= GATHER_STATISTICS
138 : m_table (n
, ggc
, sanitize_eq_and_hash
, gather_mem_stats
,
139 HASH_MAP_ORIGIN PASS_MEM_STAT
)
143 explicit hash_map (const hash_map
&h
, bool ggc
= false,
144 bool sanitize_eq_and_hash
= true,
145 bool gather_mem_stats
= GATHER_STATISTICS
147 : m_table (h
.m_table
, ggc
, sanitize_eq_and_hash
, gather_mem_stats
,
148 HASH_MAP_ORIGIN PASS_MEM_STAT
) {}
150 /* Create a hash_map in ggc memory. */
151 static hash_map
*create_ggc (size_t size
= default_hash_map_size
,
152 bool gather_mem_stats
= GATHER_STATISTICS
155 hash_map
*map
= ggc_alloc
<hash_map
> ();
156 new (map
) hash_map (size
, true, true, gather_mem_stats PASS_MEM_STAT
);
160 /* If key k isn't already in the map add key k with value v to the map, and
161 return false. Otherwise set the value of the entry for key k to be v and
164 bool put (const Key
&k
, const Value
&v
)
166 hash_entry
*e
= m_table
.find_slot_with_hash (k
, Traits::hash (k
),
168 bool ins
= hash_entry::is_empty (*e
);
172 new ((void *) &e
->m_value
) Value (v
);
180 /* If the passed in key is in the map return pointer to its value
183 Value
*get (const Key
&k
)
185 hash_entry
&e
= m_table
.find_with_hash (k
, Traits::hash (k
));
186 return Traits::is_empty (e
) ? NULL
: &e
.m_value
;
189 /* Return a reference to the value for the passed in key, creating the entry
190 if it doesn't already exist. If existed is not NULL then it is set to
191 false if the key was not previously in the map, and true otherwise. */
193 Value
&get_or_insert (const Key
&k
, bool *existed
= NULL
)
195 hash_entry
*e
= m_table
.find_slot_with_hash (k
, Traits::hash (k
),
197 bool ins
= Traits::is_empty (*e
);
201 new ((void *)&e
->m_value
) Value ();
210 void remove (const Key
&k
)
212 m_table
.remove_elt_with_hash (k
, Traits::hash (k
));
215 /* Call the call back on each pair of key and value with the passed in
218 template<typename Arg
, bool (*f
)(const typename
Traits::key_type
&,
220 void traverse (Arg a
) const
222 for (typename hash_table
<hash_entry
>::iterator iter
= m_table
.begin ();
223 iter
!= m_table
.end (); ++iter
)
224 f ((*iter
).m_key
, (*iter
).m_value
, a
);
227 template<typename Arg
, bool (*f
)(const typename
Traits::key_type
&,
229 void traverse (Arg a
) const
231 for (typename hash_table
<hash_entry
>::iterator iter
= m_table
.begin ();
232 iter
!= m_table
.end (); ++iter
)
233 if (!f ((*iter
).m_key
, &(*iter
).m_value
, a
))
237 size_t elements () const { return m_table
.elements (); }
239 void empty () { m_table
.empty(); }
241 /* Return true when there are no elements in this hash map. */
242 bool is_empty () const { return m_table
.is_empty (); }
247 explicit iterator (const typename hash_table
<hash_entry
>::iterator
&iter
) :
250 iterator
&operator++ ()
256 /* Can't use std::pair here, because GCC before 4.3 don't handle
257 std::pair where template parameters are references well.
259 class reference_pair
{
264 reference_pair (const Key
&key
, Value
&value
) : first (key
), second (value
) {}
266 template <typename K
, typename V
>
267 operator std::pair
<K
, V
> () const { return std::pair
<K
, V
> (first
, second
); }
270 reference_pair
operator* ()
272 hash_entry
&e
= *m_iter
;
273 return reference_pair (e
.m_key
, e
.m_value
);
277 operator != (const iterator
&other
) const
279 return m_iter
!= other
.m_iter
;
283 typename hash_table
<hash_entry
>::iterator m_iter
;
286 /* Standard iterator retrieval methods. */
288 iterator
begin () const { return iterator (m_table
.begin ()); }
289 iterator
end () const { return iterator (m_table
.end ()); }
293 template<typename T
, typename U
, typename V
> friend void gt_ggc_mx (hash_map
<T
, U
, V
> *);
294 template<typename T
, typename U
, typename V
> friend void gt_pch_nx (hash_map
<T
, U
, V
> *);
295 template<typename T
, typename U
, typename V
> friend void gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
296 template<typename T
, typename U
, typename V
> friend void gt_cleare_cache (hash_map
<T
, U
, V
> *);
298 hash_table
<hash_entry
> m_table
;
301 /* ggc marking routines. */
303 template<typename K
, typename V
, typename H
>
305 gt_ggc_mx (hash_map
<K
, V
, H
> *h
)
307 gt_ggc_mx (&h
->m_table
);
310 template<typename K
, typename V
, typename H
>
312 gt_pch_nx (hash_map
<K
, V
, H
> *h
)
314 gt_pch_nx (&h
->m_table
);
317 template<typename K
, typename V
, typename H
>
319 gt_cleare_cache (hash_map
<K
, V
, H
> *h
)
322 gt_cleare_cache (&h
->m_table
);
325 template<typename K
, typename V
, typename H
>
327 gt_pch_nx (hash_map
<K
, V
, H
> *h
, gt_pointer_operator op
, void *cookie
)
329 op (&h
->m_table
.m_entries
, cookie
);
332 enum hm_alloc
{ hm_heap
= false, hm_ggc
= true };
333 template<bool ggc
, typename K
, typename V
, typename H
>
334 inline hash_map
<K
,V
,H
> *
335 hash_map_maybe_create (hash_map
<K
,V
,H
> *&h
,
336 size_t size
= default_hash_map_size
)
341 h
= hash_map
<K
,V
,H
>::create_ggc (size
);
343 h
= new hash_map
<K
,V
,H
> (size
);
348 /* Like h->get, but handles null h. */
349 template<typename K
, typename V
, typename H
>
351 hash_map_safe_get (hash_map
<K
,V
,H
> *h
, const K
& k
)
353 return h
? h
->get (k
) : NULL
;
356 /* Like h->get, but handles null h. */
357 template<bool ggc
, typename K
, typename V
, typename H
>
359 hash_map_safe_get_or_insert (hash_map
<K
,V
,H
> *&h
, const K
& k
, bool *e
= NULL
,
360 size_t size
= default_hash_map_size
)
362 return hash_map_maybe_create
<ggc
> (h
, size
)->get_or_insert (k
, e
);
365 /* Like h->put, but handles null h. */
366 template<bool ggc
, typename K
, typename V
, typename H
>
368 hash_map_safe_put (hash_map
<K
,V
,H
> *&h
, const K
& k
, const V
& v
,
369 size_t size
= default_hash_map_size
)
371 return hash_map_maybe_create
<ggc
> (h
, size
)->put (k
, v
);