1 //===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines the DenseSet and SmallDenseSet classes.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_ADT_DENSESET_H
14 #define LLVM_ADT_DENSESET_H
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"
22 #include <initializer_list>
30 struct DenseSetEmpty {};
32 // Use the empty base class trick so we can create a DenseMap where the buckets
33 // contain only a single item.
34 template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
38 KeyT &getFirst() { return key; }
39 const KeyT &getFirst() const { return key; }
40 DenseSetEmpty &getSecond() { return *this; }
41 const DenseSetEmpty &getSecond() const { return *this; }
44 /// Base class for DenseSet and DenseSmallSet.
46 /// MapTy should be either
48 /// DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
49 /// detail::DenseSetPair<ValueT>>
51 /// or the equivalent SmallDenseMap type. ValueInfoT must implement the
52 /// DenseMapInfo "concept".
53 template <typename ValueT, typename MapTy, typename ValueInfoT>
55 static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
56 "DenseMap buckets unexpectedly large!");
60 using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
63 using key_type = ValueT;
64 using value_type = ValueT;
65 using size_type = unsigned;
67 explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
69 template <typename InputIt>
70 DenseSetImpl(const InputIt &I, const InputIt &E)
71 : DenseSetImpl(PowerOf2Ceil(std::distance(I, E))) {
75 DenseSetImpl(std::initializer_list<ValueT> Elems)
76 : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
77 insert(Elems.begin(), Elems.end());
80 bool empty() const { return TheMap.empty(); }
81 size_type size() const { return TheMap.size(); }
82 size_t getMemorySize() const { return TheMap.getMemorySize(); }
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); }
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); }
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);
101 bool erase(const ValueT &V) {
102 return TheMap.erase(V);
105 void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
112 typename MapTy::iterator I;
113 friend class DenseSetImpl;
114 friend class ConstIterator;
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;
123 Iterator() = default;
124 Iterator(const typename MapTy::iterator &i) : I(i) {}
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(); }
131 Iterator& operator++() { ++I; return *this; }
132 Iterator operator++(int) { auto T = *this; ++I; return T; }
133 bool operator==(const ConstIterator& X) const { return I == X.I; }
134 bool operator!=(const ConstIterator& X) const { return I != X.I; }
137 class ConstIterator {
138 typename MapTy::const_iterator I;
139 friend class DenseSetImpl;
140 friend class Iterator;
143 using difference_type = typename MapTy::const_iterator::difference_type;
144 using value_type = ValueT;
145 using pointer = const value_type *;
146 using reference = const value_type &;
147 using iterator_category = std::forward_iterator_tag;
149 ConstIterator() = default;
150 ConstIterator(const Iterator &B) : I(B.I) {}
151 ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
153 const ValueT &operator*() const { return I->getFirst(); }
154 const ValueT *operator->() const { return &I->getFirst(); }
156 ConstIterator& operator++() { ++I; return *this; }
157 ConstIterator operator++(int) { auto T = *this; ++I; return T; }
158 bool operator==(const ConstIterator& X) const { return I == X.I; }
159 bool operator!=(const ConstIterator& X) const { return I != X.I; }
162 using iterator = Iterator;
163 using const_iterator = ConstIterator;
165 iterator begin() { return Iterator(TheMap.begin()); }
166 iterator end() { return Iterator(TheMap.end()); }
168 const_iterator begin() const { return ConstIterator(TheMap.begin()); }
169 const_iterator end() const { return ConstIterator(TheMap.end()); }
171 iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
172 const_iterator find(const_arg_type_t<ValueT> V) const {
173 return ConstIterator(TheMap.find(V));
176 /// Alternative version of find() which allows a different, and possibly less
177 /// expensive, key type.
178 /// The DenseMapInfo is responsible for supplying methods
179 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
181 template <class LookupKeyT>
182 iterator find_as(const LookupKeyT &Val) {
183 return Iterator(TheMap.find_as(Val));
185 template <class LookupKeyT>
186 const_iterator find_as(const LookupKeyT &Val) const {
187 return ConstIterator(TheMap.find_as(Val));
190 void erase(Iterator I) { return TheMap.erase(I.I); }
191 void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
193 std::pair<iterator, bool> insert(const ValueT &V) {
194 detail::DenseSetEmpty Empty;
195 return TheMap.try_emplace(V, Empty);
198 std::pair<iterator, bool> insert(ValueT &&V) {
199 detail::DenseSetEmpty Empty;
200 return TheMap.try_emplace(std::move(V), Empty);
203 /// Alternative version of insert that uses a different (and possibly less
204 /// expensive) key type.
205 template <typename LookupKeyT>
206 std::pair<iterator, bool> insert_as(const ValueT &V,
207 const LookupKeyT &LookupKey) {
208 return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
210 template <typename LookupKeyT>
211 std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
212 return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
215 // Range insertion of values.
216 template<typename InputIt>
217 void insert(InputIt I, InputIt E) {
223 /// Equality comparison for DenseSet.
225 /// Iterates over elements of LHS confirming that each element is also a member
226 /// of RHS, and that RHS contains no additional values.
227 /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
228 /// case is O(N^2) (if every hash collides).
229 template <typename ValueT, typename MapTy, typename ValueInfoT>
230 bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
231 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
232 if (LHS.size() != RHS.size())
242 /// Inequality comparison for DenseSet.
244 /// Equivalent to !(LHS == RHS). See operator== for performance notes.
245 template <typename ValueT, typename MapTy, typename ValueInfoT>
246 bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
247 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
248 return !(LHS == RHS);
251 } // end namespace detail
253 /// Implements a dense probed hash-table based set.
254 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
255 class DenseSet : public detail::DenseSetImpl<
256 ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
257 detail::DenseSetPair<ValueT>>,
260 detail::DenseSetImpl<ValueT,
261 DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
262 detail::DenseSetPair<ValueT>>,
269 /// Implements a dense probed hash-table based set with some number of buckets
271 template <typename ValueT, unsigned InlineBuckets = 4,
272 typename ValueInfoT = DenseMapInfo<ValueT>>
274 : public detail::DenseSetImpl<
275 ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
276 ValueInfoT, detail::DenseSetPair<ValueT>>,
278 using BaseT = detail::DenseSetImpl<
279 ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
280 ValueInfoT, detail::DenseSetPair<ValueT>>,
287 } // end namespace llvm
289 #endif // LLVM_ADT_DENSESET_H