1//===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file defines the DenseSet and SmallDenseSet classes.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_DENSESET_H
15#define LLVM_ADT_DENSESET_H
16
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/DenseMapInfo.h"
19#include "llvm/Support/MathExtras.h"
20#include "llvm/Support/type_traits.h"
21#include <cstddef>
22#include <initializer_list>
23#include <iterator>
24#include <utility>
25
26namespace llvm {
27
28namespace detail {
29
30struct DenseSetEmpty {};
31
32// Use the empty base class trick so we can create a DenseMap where the buckets
33// contain only a single item.
34template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
35 KeyT key;
36
37public:
38 KeyT &getFirst() { return key; }
39 const KeyT &getFirst() const { return key; }
40 DenseSetEmpty &getSecond() { return *this; }
41 const DenseSetEmpty &getSecond() const { return *this; }
42};
43
44/// Base class for DenseSet and DenseSmallSet.
45///
46/// MapTy should be either
47///
48/// DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
49/// detail::DenseSetPair<ValueT>>
50///
51/// or the equivalent SmallDenseMap type. ValueInfoT must implement the
52/// DenseMapInfo "concept".
53template <typename ValueT, typename MapTy, typename ValueInfoT>
54class DenseSetImpl {
55 static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
56 "DenseMap buckets unexpectedly large!");
57 MapTy TheMap;
58
59 template <typename T>
60 using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
61
62public:
63 using key_type = ValueT;
64 using value_type = ValueT;
65 using size_type = unsigned;
66
67 explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
68
69 template <typename InputIt>
70 DenseSetImpl(const InputIt &I, const InputIt &E)
71 : DenseSetImpl(PowerOf2Ceil(std::distance(I, E))) {
72 insert(I, E);
73 }
74
75 DenseSetImpl(std::initializer_list<ValueT> Elems)
76 : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
77 insert(Elems.begin(), Elems.end());
78 }
79
80 bool empty() const { return TheMap.empty(); }
81 size_type size() const { return TheMap.size(); }
82 size_t getMemorySize() const { return TheMap.getMemorySize(); }
83
84 /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
85 /// the Size of the set.
86 void resize(size_t Size) { TheMap.resize(Size); }
87
88 /// Grow the DenseSet so that it can contain at least \p NumEntries items
89 /// before resizing again.
90 void reserve(size_t Size) { TheMap.reserve(Size); }
91
92 void clear() { TheMap.clear(); }
93
94 /// Return 1 if the specified key is in the set, 0 otherwise.
95 size_type count(const_arg_type_t<ValueT> V) const { return TheMap.count(V); }
96
97 bool erase(const ValueT &V) { return TheMap.erase(V); }
98
99 void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
100
101 // Iterators.
102
103 class ConstIterator;
104
105 class Iterator {
106 typename MapTy::iterator I;
107 friend class DenseSetImpl;
108 friend class ConstIterator;
109
110 public:
111 using difference_type = typename MapTy::iterator::difference_type;
112 using value_type = ValueT;
113 using pointer = value_type *;
114 using reference = value_type &;
115 using iterator_category = std::forward_iterator_tag;
116
117 Iterator() = default;
118 Iterator(const typename MapTy::iterator &i) : I(i) {}
119
120 ValueT &operator*() { return I->getFirst(); }
121 const ValueT &operator*() const { return I->getFirst(); }
122 ValueT *operator->() { return &I->getFirst(); }
123 const ValueT *operator->() const { return &I->getFirst(); }
124
125 Iterator &operator++() {
126 ++I;
127 return *this;
128 }
129 Iterator operator++(int) {
130 auto T = *this;
131 ++I;
132 return T;
133 }
134 friend bool operator==(const Iterator &X, const Iterator &Y) {
135 return X.I == Y.I;
136 }
137 friend bool operator!=(const Iterator &X, const Iterator &Y) {
138 return X.I != Y.I;
139 }
140 };
141
142 class ConstIterator {
143 typename MapTy::const_iterator I;
144 friend class DenseSetImpl;
145 friend class Iterator;
146
147 public:
148 using difference_type = typename MapTy::const_iterator::difference_type;
149 using value_type = ValueT;
150 using pointer = const value_type *;
151 using reference = const value_type &;
152 using iterator_category = std::forward_iterator_tag;
153
154 ConstIterator() = default;
155 ConstIterator(const Iterator &B) : I(B.I) {}
156 ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
157
158 const ValueT &operator*() const { return I->getFirst(); }
159 const ValueT *operator->() const { return &I->getFirst(); }
160
161 ConstIterator &operator++() {
162 ++I;
163 return *this;
164 }
165 ConstIterator operator++(int) {
166 auto T = *this;
167 ++I;
168 return T;
169 }
170 friend bool operator==(const ConstIterator &X, const ConstIterator &Y) {
171 return X.I == Y.I;
172 }
173 friend bool operator!=(const ConstIterator &X, const ConstIterator &Y) {
174 return X.I != Y.I;
175 }
176 };
177
178 using iterator = Iterator;
179 using const_iterator = ConstIterator;
180
181 iterator begin() { return Iterator(TheMap.begin()); }
182 iterator end() { return Iterator(TheMap.end()); }
183
184 const_iterator begin() const { return ConstIterator(TheMap.begin()); }
185 const_iterator end() const { return ConstIterator(TheMap.end()); }
186
187 iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
188 const_iterator find(const_arg_type_t<ValueT> V) const {
189 return ConstIterator(TheMap.find(V));
190 }
191
192 /// Check if the set contains the given element.
193 bool contains(const_arg_type_t<ValueT> V) const {
194 return TheMap.find(V) != TheMap.end();
195 }
196
197 /// Alternative version of find() which allows a different, and possibly less
198 /// expensive, key type.
199 /// The DenseMapInfo is responsible for supplying methods
200 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
201 /// used.
202 template <class LookupKeyT> iterator find_as(const LookupKeyT &Val) {
203 return Iterator(TheMap.find_as(Val));
204 }
205 template <class LookupKeyT>
206 const_iterator find_as(const LookupKeyT &Val) const {
207 return ConstIterator(TheMap.find_as(Val));
208 }
209
210 void erase(Iterator I) { return TheMap.erase(I.I); }
211 void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
212
213 std::pair<iterator, bool> insert(const ValueT &V) {
214 detail::DenseSetEmpty Empty;
215 return TheMap.try_emplace(V, Empty);
216 }
217
218 std::pair<iterator, bool> insert(ValueT &&V) {
219 detail::DenseSetEmpty Empty;
220 return TheMap.try_emplace(std::move(V), Empty);
221 }
222
223 /// Alternative version of insert that uses a different (and possibly less
224 /// expensive) key type.
225 template <typename LookupKeyT>
226 std::pair<iterator, bool> insert_as(const ValueT &V,
227 const LookupKeyT &LookupKey) {
228 return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
229 }
230 template <typename LookupKeyT>
231 std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
232 return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
233 }
234
235 // Range insertion of values.
236 template <typename InputIt> void insert(InputIt I, InputIt E) {
237 for (; I != E; ++I)
238 insert(*I);
239 }
240};
241
242/// Equality comparison for DenseSet.
243///
244/// Iterates over elements of LHS confirming that each element is also a member
245/// of RHS, and that RHS contains no additional values.
246/// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
247/// case is O(N^2) (if every hash collides).
248template <typename ValueT, typename MapTy, typename ValueInfoT>
249bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
250 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
251 if (LHS.size() != RHS.size())
252 return false;
253
254 for (auto &E : LHS)
255 if (!RHS.count(E))
256 return false;
257
258 return true;
259}
260
261/// Inequality comparison for DenseSet.
262///
263/// Equivalent to !(LHS == RHS). See operator== for performance notes.
264template <typename ValueT, typename MapTy, typename ValueInfoT>
265bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
266 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
267 return !(LHS == RHS);
268}
269
270} // end namespace detail
271
272/// Implements a dense probed hash-table based set.
273template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
274class DenseSet : public detail::DenseSetImpl<
275 ValueT,
276 DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
277 detail::DenseSetPair<ValueT>>,
278 ValueInfoT> {
279 using BaseT =
280 detail::DenseSetImpl<ValueT,
281 DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
282 detail::DenseSetPair<ValueT>>,
283 ValueInfoT>;
284
285public:
286 using BaseT::BaseT;
287};
288
289/// Implements a dense probed hash-table based set with some number of buckets
290/// stored inline.
291template <typename ValueT, unsigned InlineBuckets = 4,
292 typename ValueInfoT = DenseMapInfo<ValueT>>
293class SmallDenseSet
294 : public detail::DenseSetImpl<
295 ValueT,
296 SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
297 ValueInfoT, detail::DenseSetPair<ValueT>>,
298 ValueInfoT> {
299 using BaseT = detail::DenseSetImpl<
300 ValueT,
301 SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets, ValueInfoT,
302 detail::DenseSetPair<ValueT>>,
303 ValueInfoT>;
304
305public:
306 using BaseT::BaseT;
307};
308
309} // end namespace llvm
310
311#endif // LLVM_ADT_DENSESET_H
312

source code of include/llvm-20/llvm/ADT/DenseSet.h