Daily bump.
[official-gcc.git] / gcc / hash-set.h
blob85c31efd412bad83d796fa586a5e71a807abc034
1 /* A type-safe hash set.
2 Copyright (C) 2014-2021 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
9 version.
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
14 for more details.
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/>. */
21 #ifndef hash_set_h
22 #define hash_set_h
24 /* Class hash_set is a hash-value based container for objects of
25 KeyId type.
26 KeyId may be a non-trivial (non-POD) type provided a suitabe Traits
27 class. Default Traits specializations are provided for basic types
28 such as integers, pointers, and std::pair. Inserted elements are
29 value-initialized either to zero for POD types or by invoking their
30 default ctor. Removed elements are destroyed by invoking their dtor.
31 On hash_set destruction all elements are removed. Objects of
32 hash_set type are copy-constructible but not assignable. */
34 template<typename KeyId, bool Lazy = false,
35 typename Traits = default_hash_traits<KeyId> >
36 class hash_set
38 public:
39 typedef typename Traits::value_type Key;
40 explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO)
41 : m_table (n, ggc, true, GATHER_STATISTICS, HASH_SET_ORIGIN PASS_MEM_STAT) {}
43 /* Create a hash_set in gc memory with space for at least n elements. */
45 static hash_set *
46 create_ggc (size_t n)
48 hash_set *set = ggc_alloc<hash_set> ();
49 new (set) hash_set (n, true);
50 return set;
53 /* If key k isn't already in the map add it to the map, and
54 return false. Otherwise return true. */
56 bool add (const Key &k)
58 Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
59 bool existed = !Traits::is_empty (*e);
60 if (!existed)
61 new (e) Key (k);
63 return existed;
66 /* if the passed in key is in the map return its value otherwise NULL. */
68 bool contains (const Key &k)
70 if (Lazy)
71 return (m_table.find_slot_with_hash (k, Traits::hash (k), NO_INSERT)
72 != NULL);
73 Key &e = m_table.find_with_hash (k, Traits::hash (k));
74 return !Traits::is_empty (e);
77 void remove (const Key &k)
79 m_table.remove_elt_with_hash (k, Traits::hash (k));
82 /* Call the call back on each pair of key and value with the passed in
83 arg. */
85 template<typename Arg, bool (*f)(const typename Traits::value_type &, Arg)>
86 void traverse (Arg a) const
88 for (typename hash_table<Traits, Lazy>::iterator iter = m_table.begin ();
89 iter != m_table.end (); ++iter)
90 f (*iter, a);
93 /* Return the number of elements in the set. */
95 size_t elements () const { return m_table.elements (); }
97 /* Clear the hash table. */
99 void empty () { m_table.empty (); }
101 /* Return true when there are no elements in this hash set. */
102 bool is_empty () const { return m_table.is_empty (); }
104 class iterator
106 public:
107 explicit iterator (const typename hash_table<Traits,
108 Lazy>::iterator &iter) :
109 m_iter (iter) {}
111 iterator &operator++ ()
113 ++m_iter;
114 return *this;
118 operator* ()
120 return *m_iter;
123 bool
124 operator != (const iterator &other) const
126 return m_iter != other.m_iter;
129 private:
130 typename hash_table<Traits, Lazy>::iterator m_iter;
133 /* Standard iterator retrieval methods. */
135 iterator begin () const { return iterator (m_table.begin ()); }
136 iterator end () const { return iterator (m_table.end ()); }
139 private:
141 template<typename T, typename U>
142 friend void gt_ggc_mx (hash_set<T, false, U> *);
143 template<typename T, typename U>
144 friend void gt_pch_nx (hash_set<T, false, U> *);
145 template<typename T, typename U>
146 friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
148 hash_table<Traits, Lazy> m_table;
151 /* Generic hash_set<TYPE> debug helper.
153 This needs to be instantiated for each hash_set<TYPE> used throughout
154 the compiler like this:
156 DEFINE_DEBUG_HASH_SET (TYPE)
158 The reason we have a debug_helper() is because GDB can't
159 disambiguate a plain call to debug(some_hash), and it must be called
160 like debug<TYPE>(some_hash). */
161 template<typename T>
162 void
163 debug_helper (hash_set<T> &ref)
165 for (typename hash_set<T>::iterator it = ref.begin ();
166 it != ref.end (); ++it)
168 debug_slim (*it);
169 fputc ('\n', stderr);
173 #define DEFINE_DEBUG_HASH_SET(T) \
174 template void debug_helper (hash_set<T> &); \
175 DEBUG_FUNCTION void \
176 debug (hash_set<T> &ref) \
178 debug_helper <T> (ref); \
180 DEBUG_FUNCTION void \
181 debug (hash_set<T> *ptr) \
183 if (ptr) \
184 debug (*ptr); \
185 else \
186 fprintf (stderr, "<nil>\n"); \
189 /* ggc marking routines. */
191 template<typename K, typename H>
192 static inline void
193 gt_ggc_mx (hash_set<K, false, H> *h)
195 gt_ggc_mx (&h->m_table);
198 template<typename K, typename H>
199 static inline void
200 gt_pch_nx (hash_set<K, false, H> *h)
202 gt_pch_nx (&h->m_table);
205 template<typename K, typename H>
206 static inline void
207 gt_pch_nx (hash_set<K, false, H> *h, gt_pointer_operator op, void *cookie)
209 op (&h->m_table.m_entries, cookie);
212 #endif