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