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() {
93 TheMap.clear();
94 }
95
96 /// Return 1 if the specified key is in the set, 0 otherwise.
97 size_type count(const_arg_type_t<ValueT> V) const {
98 return TheMap.count(V);
99 }
100
101 bool erase(const ValueT &V) {
102 return TheMap.erase(V);
103 }
104
105 void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
106
107 // Iterators.
108
109 class ConstIterator;
110
111 class Iterator {
112 typename MapTy::iterator I;
113 friend class DenseSetImpl;
114 friend class ConstIterator;
115
116 public:
117 using difference_type = typename MapTy::iterator::difference_type;
118 using value_type = ValueT;
119 using pointer = value_type *;
120 using reference = value_type &;
121 using iterator_category = std::forward_iterator_tag;
122
123 Iterator() = default;
124 Iterator(const typename MapTy::iterator &i) : I(i) {}
125
126 ValueT &operator*() { return I->getFirst(); }
127 const ValueT &operator*() const { return I->getFirst(); }
128 ValueT *operator->() { return &I->getFirst(); }
129 const ValueT *operator->() const { return &I->getFirst(); }
130
131 Iterator& operator++() { ++I; return *this; }
132 Iterator operator++(int) { auto T = *this; ++I; return T; }
133 friend bool operator==(const Iterator &X, const Iterator &Y) {
134 return X.I == Y.I;
135 }
136 friend bool operator!=(const Iterator &X, const Iterator &Y) {
137 return X.I != Y.I;
138 }
139 };
140
141 class ConstIterator {
142 typename MapTy::const_iterator I;
143 friend class DenseSetImpl;
144 friend class Iterator;
145
146 public:
147 using difference_type = typename MapTy::const_iterator::difference_type;
148 using value_type = ValueT;
149 using pointer = const value_type *;
150 using reference = const value_type &;
151 using iterator_category = std::forward_iterator_tag;
152
153 ConstIterator() = default;
154 ConstIterator(const Iterator &B) : I(B.I) {}
155 ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
156
157 const ValueT &operator*() const { return I->getFirst(); }
158 const ValueT *operator->() const { return &I->getFirst(); }
159
160 ConstIterator& operator++() { ++I; return *this; }
161 ConstIterator operator++(int) { auto T = *this; ++I; return T; }
162 friend bool operator==(const ConstIterator &X, const ConstIterator &Y) {
163 return X.I == Y.I;
164 }
165 friend bool operator!=(const ConstIterator &X, const ConstIterator &Y) {
166 return X.I != Y.I;
167 }
168 };
169
170 using iterator = Iterator;
171 using const_iterator = ConstIterator;
172
173 iterator begin() { return Iterator(TheMap.begin()); }
174 iterator end() { return Iterator(TheMap.end()); }
175
176 const_iterator begin() const { return ConstIterator(TheMap.begin()); }
177 const_iterator end() const { return ConstIterator(TheMap.end()); }
178
179 iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
180 const_iterator find(const_arg_type_t<ValueT> V) const {
181 return ConstIterator(TheMap.find(V));
182 }
183
184 /// Check if the set contains the given element.
185 bool contains(const_arg_type_t<ValueT> V) const {
186 return TheMap.find(V) != TheMap.end();
187 }
188
189 /// Alternative version of find() which allows a different, and possibly less
190 /// expensive, key type.
191 /// The DenseMapInfo is responsible for supplying methods
192 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
193 /// used.
194 template <class LookupKeyT>
195 iterator find_as(const LookupKeyT &Val) {
196 return Iterator(TheMap.find_as(Val));
197 }
198 template <class LookupKeyT>
199 const_iterator find_as(const LookupKeyT &Val) const {
200 return ConstIterator(TheMap.find_as(Val));
201 }
202
203 void erase(Iterator I) { return TheMap.erase(I.I); }
204 void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
205
206 std::pair<iterator, bool> insert(const ValueT &V) {
207 detail::DenseSetEmpty Empty;
208 return TheMap.try_emplace(V, Empty);
209 }
210
211 std::pair<iterator, bool> insert(ValueT &&V) {
212 detail::DenseSetEmpty Empty;
213 return TheMap.try_emplace(std::move(V), Empty);
214 }
215
216 /// Alternative version of insert that uses a different (and possibly less
217 /// expensive) key type.
218 template <typename LookupKeyT>
219 std::pair<iterator, bool> insert_as(const ValueT &V,
220 const LookupKeyT &LookupKey) {
221 return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
222 }
223 template <typename LookupKeyT>
224 std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
225 return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
226 }
227
228 // Range insertion of values.
229 template<typename InputIt>
230 void insert(InputIt I, InputIt E) {
231 for (; I != E; ++I)
232 insert(*I);
233 }
234};
235
236/// Equality comparison for DenseSet.
237///
238/// Iterates over elements of LHS confirming that each element is also a member
239/// of RHS, and that RHS contains no additional values.
240/// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
241/// case is O(N^2) (if every hash collides).
242template <typename ValueT, typename MapTy, typename ValueInfoT>
243bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
244 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
245 if (LHS.size() != RHS.size())
246 return false;
247
248 for (auto &E : LHS)
249 if (!RHS.count(E))
250 return false;
251
252 return true;
253}
254
255/// Inequality comparison for DenseSet.
256///
257/// Equivalent to !(LHS == RHS). See operator== for performance notes.
258template <typename ValueT, typename MapTy, typename ValueInfoT>
259bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
260 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
261 return !(LHS == RHS);
262}
263
264} // end namespace detail
265
266/// Implements a dense probed hash-table based set.
267template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
268class DenseSet : public detail::DenseSetImpl<
269 ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
270 detail::DenseSetPair<ValueT>>,
271 ValueInfoT> {
272 using BaseT =
273 detail::DenseSetImpl<ValueT,
274 DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
275 detail::DenseSetPair<ValueT>>,
276 ValueInfoT>;
277
278public:
279 using BaseT::BaseT;
280};
281
282/// Implements a dense probed hash-table based set with some number of buckets
283/// stored inline.
284template <typename ValueT, unsigned InlineBuckets = 4,
285 typename ValueInfoT = DenseMapInfo<ValueT>>
286class SmallDenseSet
287 : public detail::DenseSetImpl<
288 ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
289 ValueInfoT, detail::DenseSetPair<ValueT>>,
290 ValueInfoT> {
291 using BaseT = detail::DenseSetImpl<
292 ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
293 ValueInfoT, detail::DenseSetPair<ValueT>>,
294 ValueInfoT>;
295
296public:
297 using BaseT::BaseT;
298};
299
300} // end namespace llvm
301
302#endif // LLVM_ADT_DENSESET_H
303

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