GCC Middle and Back End API Reference
hash-set.h
Go to the documentation of this file.
1/* A type-safe hash set.
2 Copyright (C) 2014-2024 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20
21#ifndef hash_set_h
22#define hash_set_h
23
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. */
33
34template<typename KeyId, bool Lazy = false,
35 typename Traits = default_hash_traits<KeyId> >
37{
38public:
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) {}
42
43 /* Create a hash_set in gc memory with space for at least n elements. */
44
45 static hash_set *
46 create_ggc (size_t n)
47 {
49 new (set) hash_set (n, true);
50 return set;
51 }
52
53 /* If key k isn't already in the map add it to the map, and
54 return false. Otherwise return true. */
55
56 bool add (const Key &k)
57 {
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 {
62 new (e) Key (k);
63 // Catch attempts to insert e.g. a NULL pointer.
64 gcc_checking_assert (!Traits::is_empty (*e)
65 && !Traits::is_deleted (*e));
66 }
67
68 return existed;
69 }
70
71 /* if the passed in key is in the map return its value otherwise NULL. */
72
73 bool contains (const Key &k)
74 {
75 if (Lazy)
76 return (m_table.find_slot_with_hash (k, Traits::hash (k), NO_INSERT)
77 != NULL);
78 Key &e = m_table.find_with_hash (k, Traits::hash (k));
79 return !Traits::is_empty (e);
80 }
81
82 void remove (const Key &k)
83 {
84 m_table.remove_elt_with_hash (k, Traits::hash (k));
85 }
86
87 /* Call the call back on each pair of key and value with the passed in
88 arg. */
89
90 template<typename Arg, bool (*f)(const typename Traits::value_type &, Arg)>
91 void traverse (Arg a) const
92 {
93 for (typename hash_table<Traits, Lazy>::iterator iter = m_table.begin ();
94 iter != m_table.end (); ++iter)
95 f (*iter, a);
96 }
97
98 /* Return the number of elements in the set. */
99
100 size_t elements () const { return m_table.elements (); }
101
102 /* Clear the hash table. */
103
104 void empty () { m_table.empty (); }
105
106 /* Return true when there are no elements in this hash set. */
107 bool is_empty () const { return m_table.is_empty (); }
108
110 {
111 public:
112 explicit iterator (const typename hash_table<Traits,
113 Lazy>::iterator &iter) :
114 m_iter (iter) {}
115
117 {
118 ++m_iter;
119 return *this;
120 }
121
122 Key
124 {
125 return *m_iter;
126 }
127
128 bool
129 operator != (const iterator &other) const
130 {
131 return m_iter != other.m_iter;
132 }
133
134 private:
136 };
137
138 /* Standard iterator retrieval methods. */
139
140 iterator begin () const { return iterator (m_table.begin ()); }
141 iterator end () const { return iterator (m_table.end ()); }
142
143
144private:
145
146 template<typename T, typename U>
148 template<typename T, typename U>
150 template<typename T, typename U>
152
154};
155
156/* Generic hash_set<TYPE> debug helper.
157
158 This needs to be instantiated for each hash_set<TYPE> used throughout
159 the compiler like this:
160
161 DEFINE_DEBUG_HASH_SET (TYPE)
162
163 The reason we have a debug_helper() is because GDB can't
164 disambiguate a plain call to debug(some_hash), and it must be called
165 like debug<TYPE>(some_hash). */
166template<typename T>
167void
169{
170 for (typename hash_set<T>::iterator it = ref.begin ();
171 it != ref.end (); ++it)
172 {
173 debug_slim (*it);
174 fputc ('\n', stderr);
175 }
176}
177
178#define DEFINE_DEBUG_HASH_SET(T) \
179 template void debug_helper (hash_set<T> &); \
180 DEBUG_FUNCTION void \
181 debug (hash_set<T> &ref) \
182 { \
183 debug_helper <T> (ref); \
184 } \
185 DEBUG_FUNCTION void \
186 debug (hash_set<T> *ptr) \
187 { \
188 if (ptr) \
189 debug (*ptr); \
190 else \
191 fprintf (stderr, "<nil>\n"); \
192 }
193
194/* ggc marking routines. */
195
196template<typename K, typename H>
197inline void
202
203template<typename K, typename H>
204inline void
209
210template<typename K, typename H>
211inline void
213{
214 op (&h->m_table.m_entries, NULL, cookie);
215}
216
217#endif
static void debug_slim(edge e)
Definition cfg.cc:584
Definition hash-set.h:110
bool operator!=(const iterator &other) const
Definition hash-set.h:129
iterator & operator++()
Definition hash-set.h:116
iterator(const typename hash_table< Traits, Lazy >::iterator &iter)
Definition hash-set.h:112
hash_table< Traits, Lazy >::iterator m_iter
Definition hash-set.h:135
Key operator*()
Definition hash-set.h:123
Definition hash-set.h:37
void traverse(Arg a) const
Definition hash-set.h:91
iterator begin() const
Definition hash-set.h:140
iterator end() const
Definition hash-set.h:141
bool contains(const Key &k)
Definition hash-set.h:73
Traits::value_type Key
Definition hash-set.h:39
hash_table< Traits, Lazy > m_table
Definition hash-set.h:153
friend void gt_ggc_mx(hash_set< T, false, U > *)
hash_set(size_t n=13, bool ggc=false CXX_MEM_STAT_INFO)
Definition hash-set.h:40
bool add(const Key &k)
Definition hash-set.h:56
bool is_empty() const
Definition hash-set.h:107
static hash_set * create_ggc(size_t n)
Definition hash-set.h:46
void remove(const Key &k)
Definition hash-set.h:82
void empty()
Definition hash-set.h:104
friend void gt_pch_nx(hash_set< T, false, U > *, gt_pointer_operator, void *)
friend void gt_pch_nx(hash_set< T, false, U > *)
size_t elements() const
Definition hash-set.h:100
Definition hash-table.h:474
Definition hash-table.h:375
void remove_elt_with_hash(const compare_type &, hashval_t)
Definition hash-table.h:1133
void empty()
Definition hash-table.h:412
value_type & find_with_hash(const compare_type &, hashval_t)
Definition hash-table.h:981
value_type * find_slot_with_hash(const compare_type &comparable, hashval_t hash, enum insert_option insert)
Definition hash-table.h:1029
iterator end() const
Definition hash-table.h:504
bool is_empty() const
Definition hash-table.h:415
iterator begin() const
Definition hash-table.h:494
size_t elements() const
Definition hash-table.h:406
value_type * m_entries
Definition hash-table.h:597
void(* gt_pointer_operator)(void *, void *, void *)
Definition coretypes.h:463
T * ggc_alloc(ALONE_CXX_MEM_STAT_INFO)
Definition ggc.h:184
void gt_ggc_mx(hash_set< K, false, H > *h)
Definition hash-set.h:198
void gt_pch_nx(hash_set< K, false, H > *h)
Definition hash-set.h:205
void debug_helper(hash_set< T > &ref)
Definition hash-set.h:168
@ HASH_SET_ORIGIN
Definition mem-stats-traits.h:29
Ca & a
Definition poly-int.h:766
fputc('\n', stderr)
#define PASS_MEM_STAT
Definition statistics.h:54
#define CXX_MEM_STAT_INFO
Definition statistics.h:58
Definition hash-traits.h:466
Definition cse.cc:4118
#define NULL
Definition system.h:50
#define true
Definition system.h:894
#define gcc_checking_assert(EXPR)
Definition system.h:828