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/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:
getFirst()38   KeyT &getFirst() { return key; }
getFirst()39   const KeyT &getFirst() const { return key; }
getSecond()40   DenseSetEmpty &getSecond() { return *this; }
getSecond()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 
TheMap(InitialReserve)67   explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
68 
DenseSetImpl(std::initializer_list<ValueT> Elems)69   DenseSetImpl(std::initializer_list<ValueT> Elems)
70       : DenseSetImpl(Elems.size()) {
71     insert(Elems.begin(), Elems.end());
72   }
73 
empty()74   bool empty() const { return TheMap.empty(); }
size()75   size_type size() const { return TheMap.size(); }
getMemorySize()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.
resize(size_t Size)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.
reserve(size_t Size)84   void reserve(size_t Size) { TheMap.reserve(Size); }
85 
clear()86   void clear() {
87     TheMap.clear();
88   }
89 
90   /// Return 1 if the specified key is in the set, 0 otherwise.
count(const_arg_type_t<ValueT> V)91   size_type count(const_arg_type_t<ValueT> V) const {
92     return TheMap.count(V);
93   }
94 
erase(const ValueT & V)95   bool erase(const ValueT &V) {
96     return TheMap.erase(V);
97   }
98 
swap(DenseSetImpl & RHS)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;
Iterator(const typename MapTy::iterator & i)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 = value_type *;
140     using reference = value_type &;
141     using iterator_category = std::forward_iterator_tag;
142 
143     ConstIterator() = default;
ConstIterator(const Iterator & B)144     ConstIterator(const Iterator &B) : I(B.I) {}
ConstIterator(const typename MapTy::const_iterator & 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 
begin()159   iterator begin() { return Iterator(TheMap.begin()); }
end()160   iterator end() { return Iterator(TheMap.end()); }
161 
begin()162   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
end()163   const_iterator end() const { return ConstIterator(TheMap.end()); }
164 
find(const_arg_type_t<ValueT> V)165   iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
find(const_arg_type_t<ValueT> 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>
find_as(const LookupKeyT & Val)176   iterator find_as(const LookupKeyT &Val) {
177     return Iterator(TheMap.find_as(Val));
178   }
179   template <class LookupKeyT>
find_as(const LookupKeyT & Val)180   const_iterator find_as(const LookupKeyT &Val) const {
181     return ConstIterator(TheMap.find_as(Val));
182   }
183 
erase(Iterator I)184   void erase(Iterator I) { return TheMap.erase(I.I); }
erase(ConstIterator CI)185   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
186 
insert(const ValueT & V)187   std::pair<iterator, bool> insert(const ValueT &V) {
188     detail::DenseSetEmpty Empty;
189     return TheMap.try_emplace(V, Empty);
190   }
191 
insert(ValueT && V)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>
insert_as(const ValueT & V,const LookupKeyT & LookupKey)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>
insert_as(ValueT && V,const LookupKeyT & LookupKey)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>
insert(InputIt I,InputIt E)211   void insert(InputIt I, InputIt E) {
212     for (; I != E; ++I)
213       insert(*I);
214   }
215 };
216 
217 } // end namespace detail
218 
219 /// Implements a dense probed hash-table based set.
220 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
221 class DenseSet : public detail::DenseSetImpl<
222                      ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
223                                       detail::DenseSetPair<ValueT>>,
224                      ValueInfoT> {
225   using BaseT =
226       detail::DenseSetImpl<ValueT,
227                            DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
228                                     detail::DenseSetPair<ValueT>>,
229                            ValueInfoT>;
230 
231 public:
232   using BaseT::BaseT;
233 };
234 
235 /// Implements a dense probed hash-table based set with some number of buckets
236 /// stored inline.
237 template <typename ValueT, unsigned InlineBuckets = 4,
238           typename ValueInfoT = DenseMapInfo<ValueT>>
239 class SmallDenseSet
240     : public detail::DenseSetImpl<
241           ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
242                                 ValueInfoT, detail::DenseSetPair<ValueT>>,
243           ValueInfoT> {
244   using BaseT = detail::DenseSetImpl<
245       ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
246                             ValueInfoT, detail::DenseSetPair<ValueT>>,
247       ValueInfoT>;
248 
249 public:
250   using BaseT::BaseT;
251 };
252 
253 } // end namespace llvm
254 
255 #endif // LLVM_ADT_DENSESET_H
256