1 /* A type-safe hash set.
2 Copyright (C) 2014-2015 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 #include "hash-table.h"
26 /* implement default behavior for traits when types allow it. */
28 struct default_hashset_traits
30 /* Hashes the passed in key. */
36 return uintptr_t(p
) >> 3;
39 template<typename T
> static hashval_t
hash(const T
&v
) { return v
; }
41 /* Return true if the two keys passed as arguments are equal. */
45 equal (const T
&a
, const T
&b
)
50 /* Called to dispose of the key before marking the entry as deleted. */
52 template<typename T
> static void remove (T
&v
) { v
.~T (); }
54 /* Mark the passed in entry as being deleted. */
60 e
= reinterpret_cast<void *> (1);
63 /* Mark the passed in entry as being empty. */
72 /* Return true if the passed in entry is marked as deleted. */
78 return e
== reinterpret_cast<void *> (1);
81 /* Return true if the passed in entry is marked as empty. */
83 template<typename T
> static bool is_empty (T
*e
) { return e
== NULL
; }
85 /* ggc walking routine, mark all objects refered to by this one. */
91 extern void gt_ggc_mx (T
&);
95 /* pch walking routine, note all objects refered to by this element. */
101 extern void gt_pch_nx (T
&);
106 template<typename Key
, typename Traits
= default_hashset_traits
>
113 typedef hash_entry value_type
;
114 typedef Key compare_type
;
116 static hashval_t
hash (const hash_entry
&e
)
118 return Traits::hash (e
.m_key
);
121 static bool equal (const hash_entry
&a
, const Key
&b
)
123 return Traits::equal (a
.m_key
, b
);
126 static void remove (hash_entry
&e
) { Traits::remove (e
.m_key
); }
129 mark_deleted (hash_entry
&e
)
131 Traits::mark_deleted (e
.m_key
);
134 static bool is_deleted (const hash_entry
&e
)
136 return Traits::is_deleted (e
.m_key
);
140 mark_empty (hash_entry
&e
)
142 Traits::mark_empty (e
.m_key
);
146 is_empty (const hash_entry
&e
)
148 return Traits::is_empty (e
.m_key
);
151 static void ggc_mx (hash_entry
&e
)
153 Traits::ggc_mx (e
.m_key
);
156 static void pch_nx (hash_entry
&e
)
158 Traits::pch_nx (e
.m_key
);
161 static void pch_nx (hash_entry
&e
, gt_pointer_operator op
, void *c
)
163 pch_nx_helper (e
.m_key
, op
, c
);
169 pch_nx_helper (T
&x
, gt_pointer_operator op
, void *cookie
)
171 gt_pch_nx (&x
, op
, cookie
);
176 pch_nx_helper (T
*&x
, gt_pointer_operator op
, void *cookie
)
183 explicit hash_set (size_t n
= 13, bool ggc
= false) : m_table (n
, ggc
) {}
185 /* Create a hash_set in gc memory with space for at least n elements. */
188 create_ggc (size_t n
)
190 hash_set
*set
= ggc_alloc
<hash_set
> ();
191 new (set
) hash_set (n
, true);
195 /* If key k isn't already in the map add it to the map, and
196 return false. Otherwise return true. */
198 bool add (const Key
&k
)
200 hash_entry
*e
= m_table
.find_slot_with_hash (k
, Traits::hash (k
),
202 bool existed
= !hash_entry::is_empty (*e
);
209 /* if the passed in key is in the map return its value otherwise NULL. */
211 bool contains (const Key
&k
)
213 hash_entry
&e
= m_table
.find_with_hash (k
, Traits::hash (k
));
214 return !Traits::is_empty (e
.m_key
);
217 /* Call the call back on each pair of key and value with the passed in
220 template<typename Arg
, bool (*f
)(const Key
&, Arg
)>
221 void traverse (Arg a
) const
223 for (typename hash_table
<hash_entry
>::iterator iter
= m_table
.begin ();
224 iter
!= m_table
.end (); ++iter
)
225 f ((*iter
).m_key
, a
);
228 /* Return the number of elements in the set. */
230 size_t elements () const { return m_table
.elements (); }
234 template<typename T
, typename U
> friend void gt_ggc_mx (hash_set
<T
, U
> *);
235 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *);
236 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *, gt_pointer_operator
, void *);
238 hash_table
<hash_entry
> m_table
;
241 /* ggc marking routines. */
243 template<typename K
, typename H
>
245 gt_ggc_mx (hash_set
<K
, H
> *h
)
247 gt_ggc_mx (&h
->m_table
);
250 template<typename K
, typename H
>
252 gt_pch_nx (hash_set
<K
, H
> *h
)
254 gt_pch_nx (&h
->m_table
);
257 template<typename K
, typename H
>
259 gt_pch_nx (hash_set
<K
, H
> *h
, gt_pointer_operator op
, void *cookie
)
261 op (&h
->m_table
.m_entries
, cookie
);