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 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 void mark_empty (hash_entry
&e
) { Traits::mark_empty (e
); }
70 static bool is_empty (const hash_entry
&e
) { return Traits::is_empty (e
); }
72 static void ggc_mx (hash_entry
&e
)
75 gt_ggc_mx (e
.m_value
);
78 static void ggc_maybe_mx (hash_entry
&e
)
84 static void pch_nx (hash_entry
&e
)
87 gt_pch_nx (e
.m_value
);
90 static void pch_nx (hash_entry
&e
, gt_pointer_operator op
, void *c
)
92 pch_nx_helper (e
.m_key
, op
, c
);
93 pch_nx_helper (e
.m_value
, op
, c
);
96 static int keep_cache_entry (hash_entry
&e
)
98 return ggc_marked_p (e
.m_key
);
104 pch_nx_helper (T
&x
, gt_pointer_operator op
, void *cookie
)
106 gt_pch_nx (&x
, op
, cookie
);
110 pch_nx_helper (int, gt_pointer_operator
, void *)
115 pch_nx_helper (unsigned int, gt_pointer_operator
, void *)
120 pch_nx_helper (bool, gt_pointer_operator
, void *)
126 pch_nx_helper (T
*&x
, gt_pointer_operator op
, void *cookie
)
133 explicit hash_map (size_t n
= default_hash_map_size
, bool ggc
= false,
134 bool sanitize_eq_and_hash
= true,
135 bool gather_mem_stats
= GATHER_STATISTICS
137 : m_table (n
, ggc
, sanitize_eq_and_hash
, gather_mem_stats
,
138 HASH_MAP_ORIGIN PASS_MEM_STAT
)
142 explicit hash_map (const hash_map
&h
, bool ggc
= false,
143 bool sanitize_eq_and_hash
= true,
144 bool gather_mem_stats
= GATHER_STATISTICS
146 : m_table (h
.m_table
, ggc
, sanitize_eq_and_hash
, gather_mem_stats
,
147 HASH_MAP_ORIGIN PASS_MEM_STAT
) {}
149 /* Create a hash_map in ggc memory. */
150 static hash_map
*create_ggc (size_t size
= default_hash_map_size
,
151 bool gather_mem_stats
= GATHER_STATISTICS
154 hash_map
*map
= ggc_alloc
<hash_map
> ();
155 new (map
) hash_map (size
, true, true, gather_mem_stats PASS_MEM_STAT
);
159 /* If key k isn't already in the map add key k with value v to the map, and
160 return false. Otherwise set the value of the entry for key k to be v and
163 bool put (const Key
&k
, const Value
&v
)
165 hash_entry
*e
= m_table
.find_slot_with_hash (k
, Traits::hash (k
),
167 bool ins
= hash_entry::is_empty (*e
);
171 new ((void *) &e
->m_value
) Value (v
);
179 /* if the passed in key is in the map return its value otherwise NULL. */
181 Value
*get (const Key
&k
)
183 hash_entry
&e
= m_table
.find_with_hash (k
, Traits::hash (k
));
184 return Traits::is_empty (e
) ? NULL
: &e
.m_value
;
187 /* Return a reference to the value for the passed in key, creating the entry
188 if it doesn't already exist. If existed is not NULL then it is set to
189 false if the key was not previously in the map, and true otherwise. */
191 Value
&get_or_insert (const Key
&k
, bool *existed
= NULL
)
193 hash_entry
*e
= m_table
.find_slot_with_hash (k
, Traits::hash (k
),
195 bool ins
= Traits::is_empty (*e
);
199 new ((void *)&e
->m_value
) Value ();
208 void remove (const Key
&k
)
210 m_table
.remove_elt_with_hash (k
, Traits::hash (k
));
213 /* Call the call back on each pair of key and value with the passed in
216 template<typename Arg
, bool (*f
)(const typename
Traits::key_type
&,
218 void traverse (Arg a
) const
220 for (typename hash_table
<hash_entry
>::iterator iter
= m_table
.begin ();
221 iter
!= m_table
.end (); ++iter
)
222 f ((*iter
).m_key
, (*iter
).m_value
, a
);
225 template<typename Arg
, bool (*f
)(const typename
Traits::key_type
&,
227 void traverse (Arg a
) const
229 for (typename hash_table
<hash_entry
>::iterator iter
= m_table
.begin ();
230 iter
!= m_table
.end (); ++iter
)
231 if (!f ((*iter
).m_key
, &(*iter
).m_value
, a
))
235 size_t elements () const { return m_table
.elements (); }
237 void empty () { m_table
.empty(); }
239 /* Return true when there are no elements in this hash map. */
240 bool is_empty () const { return m_table
.is_empty (); }
245 explicit iterator (const typename hash_table
<hash_entry
>::iterator
&iter
) :
248 iterator
&operator++ ()
254 /* Can't use std::pair here, because GCC before 4.3 don't handle
255 std::pair where template parameters are references well.
257 class reference_pair
{
262 reference_pair (const Key
&key
, Value
&value
) : first (key
), second (value
) {}
264 template <typename K
, typename V
>
265 operator std::pair
<K
, V
> () const { return std::pair
<K
, V
> (first
, second
); }
268 reference_pair
operator* ()
270 hash_entry
&e
= *m_iter
;
271 return reference_pair (e
.m_key
, e
.m_value
);
275 operator != (const iterator
&other
) const
277 return m_iter
!= other
.m_iter
;
281 typename hash_table
<hash_entry
>::iterator m_iter
;
284 /* Standard iterator retrieval methods. */
286 iterator
begin () const { return iterator (m_table
.begin ()); }
287 iterator
end () const { return iterator (m_table
.end ()); }
291 template<typename T
, typename U
, typename V
> friend void gt_ggc_mx (hash_map
<T
, U
, V
> *);
292 template<typename T
, typename U
, typename V
> friend void gt_pch_nx (hash_map
<T
, U
, V
> *);
293 template<typename T
, typename U
, typename V
> friend void gt_pch_nx (hash_map
<T
, U
, V
> *, gt_pointer_operator
, void *);
294 template<typename T
, typename U
, typename V
> friend void gt_cleare_cache (hash_map
<T
, U
, V
> *);
296 hash_table
<hash_entry
> m_table
;
299 /* ggc marking routines. */
301 template<typename K
, typename V
, typename H
>
303 gt_ggc_mx (hash_map
<K
, V
, H
> *h
)
305 gt_ggc_mx (&h
->m_table
);
308 template<typename K
, typename V
, typename H
>
310 gt_pch_nx (hash_map
<K
, V
, H
> *h
)
312 gt_pch_nx (&h
->m_table
);
315 template<typename K
, typename V
, typename H
>
317 gt_cleare_cache (hash_map
<K
, V
, H
> *h
)
320 gt_cleare_cache (&h
->m_table
);
323 template<typename K
, typename V
, typename H
>
325 gt_pch_nx (hash_map
<K
, V
, H
> *h
, gt_pointer_operator op
, void *cookie
)
327 op (&h
->m_table
.m_entries
, cookie
);
330 enum hm_alloc
{ hm_heap
= false, hm_ggc
= true };
331 template<bool ggc
, typename K
, typename V
, typename H
>
332 inline hash_map
<K
,V
,H
> *
333 hash_map_maybe_create (hash_map
<K
,V
,H
> *&h
,
334 size_t size
= default_hash_map_size
)
339 h
= hash_map
<K
,V
,H
>::create_ggc (size
);
341 h
= new hash_map
<K
,V
,H
> (size
);
346 /* Like h->get, but handles null h. */
347 template<typename K
, typename V
, typename H
>
349 hash_map_safe_get (hash_map
<K
,V
,H
> *h
, const K
& k
)
351 return h
? h
->get (k
) : NULL
;
354 /* Like h->get, but handles null h. */
355 template<bool ggc
, typename K
, typename V
, typename H
>
357 hash_map_safe_get_or_insert (hash_map
<K
,V
,H
> *&h
, const K
& k
, bool *e
= NULL
,
358 size_t size
= default_hash_map_size
)
360 return hash_map_maybe_create
<ggc
> (h
, size
)->get_or_insert (k
, e
);
363 /* Like h->put, but handles null h. */
364 template<bool ggc
, typename K
, typename V
, typename H
>
366 hash_map_safe_put (hash_map
<K
,V
,H
> *&h
, const K
& k
, const V
& v
,
367 size_t size
= default_hash_map_size
)
369 return hash_map_maybe_create
<ggc
> (h
, size
)->put (k
, v
);