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 template<typename KeyId
, typename Traits
= default_hash_traits
<KeyId
> >
28 typedef typename
Traits::value_type Key
;
29 explicit hash_set (size_t n
= 13, bool ggc
= false CXX_MEM_STAT_INFO
)
30 : m_table (n
, ggc
, GATHER_STATISTICS
, HASH_SET_ORIGIN PASS_MEM_STAT
) {}
32 /* Create a hash_set in gc memory with space for at least n elements. */
37 hash_set
*set
= ggc_alloc
<hash_set
> ();
38 new (set
) hash_set (n
, true);
42 /* If key k isn't already in the map add it to the map, and
43 return false. Otherwise return true. */
45 bool add (const Key
&k
)
47 Key
*e
= m_table
.find_slot_with_hash (k
, Traits::hash (k
), INSERT
);
48 bool existed
= !Traits::is_empty (*e
);
55 /* if the passed in key is in the map return its value otherwise NULL. */
57 bool contains (const Key
&k
)
59 Key
&e
= m_table
.find_with_hash (k
, Traits::hash (k
));
60 return !Traits::is_empty (e
);
63 void remove (const Key
&k
)
65 m_table
.remove_elt_with_hash (k
, Traits::hash (k
));
68 /* Call the call back on each pair of key and value with the passed in
71 template<typename Arg
, bool (*f
)(const typename
Traits::value_type
&, Arg
)>
72 void traverse (Arg a
) const
74 for (typename hash_table
<Traits
>::iterator iter
= m_table
.begin ();
75 iter
!= m_table
.end (); ++iter
)
79 /* Return the number of elements in the set. */
81 size_t elements () const { return m_table
.elements (); }
86 explicit iterator (const typename hash_table
<Traits
>::iterator
&iter
) :
89 iterator
&operator++ ()
102 operator != (const iterator
&other
) const
104 return m_iter
!= other
.m_iter
;
108 typename hash_table
<Traits
>::iterator m_iter
;
111 /* Standard iterator retrieval methods. */
113 iterator
begin () const { return iterator (m_table
.begin ()); }
114 iterator
end () const { return iterator (m_table
.end ()); }
119 template<typename T
, typename U
> friend void gt_ggc_mx (hash_set
<T
, U
> *);
120 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *);
121 template<typename T
, typename U
> friend void gt_pch_nx (hash_set
<T
, U
> *, gt_pointer_operator
, void *);
123 hash_table
<Traits
> m_table
;
126 /* ggc marking routines. */
128 template<typename K
, typename H
>
130 gt_ggc_mx (hash_set
<K
, H
> *h
)
132 gt_ggc_mx (&h
->m_table
);
135 template<typename K
, typename H
>
137 gt_pch_nx (hash_set
<K
, H
> *h
)
139 gt_pch_nx (&h
->m_table
);
142 template<typename K
, typename H
>
144 gt_pch_nx (hash_set
<K
, H
> *h
, gt_pointer_operator op
, void *cookie
)
146 op (&h
->m_table
.m_entries
, cookie
);