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 
26 namespace llvm {
27 
28 namespace detail {
29 
30 struct DenseSetEmpty {};
31 
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 {
35   KeyT key;
36 
37 public:
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".
53 template <typename ValueT, typename MapTy, typename ValueInfoT>
54 class 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 
62 public:
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 DenseSetImpl;
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).
223 template <typename ValueT, typename MapTy, typename ValueInfoT>
224 bool 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.
239 template <typename ValueT, typename MapTy, typename ValueInfoT>
240 bool 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.
248 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
249 class 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 
259 public:
260   using BaseT::BaseT;
261 };
262 
263 /// Implements a dense probed hash-table based set with some number of buckets
264 /// stored inline.
265 template <typename ValueT, unsigned InlineBuckets = 4,
266           typename ValueInfoT = DenseMapInfo<ValueT>>
267 class 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 
277 public:
278   using BaseT::BaseT;
279 };
280 
281 } // end namespace llvm
282 
283 #endif // LLVM_ADT_DENSESET_H
284