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// This file defines the DenseSet and SmallDenseSet classes.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_DENSESET_H
14#define LLVM_ADT_DENSESET_H
15
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseMapInfo.h"
18#include "llvm/Support/MathExtras.h"
19#include "llvm/Support/type_traits.h"
20#include <algorithm>
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 DenseSetImpl(std::initializer_list<ValueT> Elems)
70 : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
71 insert(Elems.begin(), Elems.end());
72 }
73
74 bool empty() const { return TheMap.empty(); }
75 size_type size() const { return TheMap.size(); }
76 size_t getMemorySize() const { return TheMap.getMemorySize(); }
77
78 /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
79 /// the Size of the set.
80 void resize(size_t Size) { TheMap.resize(Size); }
81
82 /// Grow the DenseSet so that it can contain at least \p NumEntries items
83 /// before resizing again.
84 void reserve(size_t Size) { TheMap.reserve(Size); }
85
86 void clear() {
87 TheMap.clear();
88 }
89
90 /// Return 1 if the specified key is in the set, 0 otherwise.
91 size_type count(const_arg_type_t<ValueT> V) const {
92 return TheMap.count(V);
93 }
94
95 bool erase(const ValueT &V) {
96 return TheMap.erase(V);
97 }
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++() { ++I; return *this; }
126 Iterator operator++(int) { auto T = *this; ++I; return T; }
127 bool operator==(const ConstIterator& X) const { return I == X.I; }
128 bool operator!=(const ConstIterator& X) const { return I != X.I; }
129 };
130
131 class ConstIterator {
132 typename MapTy::const_iterator I;
133 friend class DenseSet;
134 friend class Iterator;
135
136 public:
137 using difference_type = typename MapTy::const_iterator::difference_type;
138 using value_type = ValueT;
139 using pointer = const value_type *;
140 using reference = const value_type &;
141 using iterator_category = std::forward_iterator_tag;
142
143 ConstIterator() = default;
144 ConstIterator(const Iterator &B) : I(B.I) {}
145 ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
146
147 const ValueT &operator*() const { return I->getFirst(); }
148 const ValueT *operator->() const { return &I->getFirst(); }
149
150 ConstIterator& operator++() { ++I; return *this; }
151 ConstIterator operator++(int) { auto T = *this; ++I; return T; }
152 bool operator==(const ConstIterator& X) const { return I == X.I; }
153 bool operator!=(const ConstIterator& X) const { return I != X.I; }
154 };
155
156 using iterator = Iterator;
157 using const_iterator = ConstIterator;
158
159 iterator begin() { return Iterator(TheMap.begin()); }
160 iterator end() { return Iterator(TheMap.end()); }
161
162 const_iterator begin() const { return ConstIterator(TheMap.begin()); }
163 const_iterator end() const { return ConstIterator(TheMap.end()); }
164
165 iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
166 const_iterator find(const_arg_type_t<ValueT> V) const {
167 return ConstIterator(TheMap.find(V));
168 }
169
170 /// Alternative version of find() which allows a different, and possibly less
171 /// expensive, key type.
172 /// The DenseMapInfo is responsible for supplying methods
173 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
174 /// used.
175 template <class LookupKeyT>
176 iterator find_as(const LookupKeyT &Val) {
177 return Iterator(TheMap.find_as(Val));
178 }
179 template <class LookupKeyT>
180 const_iterator find_as(const LookupKeyT &Val) const {
181 return ConstIterator(TheMap.find_as(Val));
182 }
183
184 void erase(Iterator I) { return TheMap.erase(I.I); }
185 void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
186
187 std::pair<iterator, bool> insert(const ValueT &V) {
188 detail::DenseSetEmpty Empty;
189 return TheMap.try_emplace(V, Empty);
190 }
191
192 std::pair<iterator, bool> insert(ValueT &&V) {
193 detail::DenseSetEmpty Empty;
194 return TheMap.try_emplace(std::move(V), Empty);
195 }
196
197 /// Alternative version of insert that uses a different (and possibly less
198 /// expensive) key type.
199 template <typename LookupKeyT>
200 std::pair<iterator, bool> insert_as(const ValueT &V,
201 const LookupKeyT &LookupKey) {
202 return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
203 }
204 template <typename LookupKeyT>
205 std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
206 return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
207 }
208
209 // Range insertion of values.
210 template<typename InputIt>
211 void insert(InputIt I, InputIt E) {
212 for (; I != E; ++I)
213 insert(*I);
214 }
215};
216
217/// Equality comparison for DenseSet.
218///
219/// Iterates over elements of LHS confirming that each element is also a member
220/// of RHS, and that RHS contains no additional values.
221/// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
222/// case is O(N^2) (if every hash collides).
223template <typename ValueT, typename MapTy, typename ValueInfoT>
224bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
225 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
226 if (LHS.size() != RHS.size())
227 return false;
228
229 for (auto &E : LHS)
230 if (!RHS.count(E))
231 return false;
232
233 return true;
234}
235
236/// Inequality comparison for DenseSet.
237///
238/// Equivalent to !(LHS == RHS). See operator== for performance notes.
239template <typename ValueT, typename MapTy, typename ValueInfoT>
240bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
241 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
242 return !(LHS == RHS);
243}
244
245} // end namespace detail
246
247/// Implements a dense probed hash-table based set.
248template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
249class DenseSet : public detail::DenseSetImpl<
250 ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
251 detail::DenseSetPair<ValueT>>,
252 ValueInfoT> {
253 using BaseT =
254 detail::DenseSetImpl<ValueT,
255 DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
256 detail::DenseSetPair<ValueT>>,
257 ValueInfoT>;
258
259public:
260 using BaseT::BaseT;
261};
262
263/// Implements a dense probed hash-table based set with some number of buckets
264/// stored inline.
265template <typename ValueT, unsigned InlineBuckets = 4,
266 typename ValueInfoT = DenseMapInfo<ValueT>>
267class SmallDenseSet
268 : public detail::DenseSetImpl<
269 ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
270 ValueInfoT, detail::DenseSetPair<ValueT>>,
271 ValueInfoT> {
272 using BaseT = detail::DenseSetImpl<
273 ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
274 ValueInfoT, detail::DenseSetPair<ValueT>>,
275 ValueInfoT>;
276
277public:
278 using BaseT::BaseT;
279};
280
281} // end namespace llvm
282
283#endif // LLVM_ADT_DENSESET_H
284