LLVM  6.0.0svn
DenseSet.h
Go to the documentation of this file.
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"
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;
66 
67  explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
68 
69  DenseSetImpl(std::initializer_list<ValueT> Elems)
70  : DenseSetImpl(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;
113  using pointer = 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 
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;
139  using pointer = 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) {
189  return TheMap.try_emplace(V, Empty);
190  }
191 
192  std::pair<iterator, bool> insert(ValueT &&V) {
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 } // end namespace detail
218 
219 /// Implements a dense probed hash-table based set.
220 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
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,
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>>
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
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool operator!=(const ConstIterator &X) const
Definition: DenseSet.h:153
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
const KeyT & getFirst() const
Definition: DenseSet.h:39
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
bool erase(const ValueT &V)
Definition: DenseSet.h:95
std::pair< iterator, bool > insert_as(ValueT &&V, const LookupKeyT &LookupKey)
Definition: DenseSet.h:205
bool operator==(const ConstIterator &X) const
Definition: DenseSet.h:152
bool operator==(const ConstIterator &X) const
Definition: DenseSet.h:127
#define T
DenseSetEmpty & getSecond()
Definition: DenseSet.h:40
Iterator(const typename MapTy::iterator &i)
Definition: DenseSet.h:118
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
std::pair< iterator, bool > insert_as(const ValueT &V, const LookupKeyT &LookupKey)
Alternative version of insert that uses a different (and possibly less expensive) key type...
Definition: DenseSet.h:200
bool operator!=(const ConstIterator &X) const
Definition: DenseSet.h:128
const ValueT & operator*() const
Definition: DenseSet.h:121
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
const_iterator begin() const
Definition: DenseSet.h:162
iterator find_as(const LookupKeyT &Val)
Alternative version of find() which allows a different, and possibly less expensive, key type.
Definition: DenseSet.h:176
std::pair< iterator, bool > insert(ValueT &&V)
Definition: DenseSet.h:192
void erase(Iterator I)
Definition: DenseSet.h:184
void insert(InputIt I, InputIt E)
Definition: DenseSet.h:211
std::forward_iterator_tag iterator_category
Definition: DenseSet.h:141
void swap(DenseSetImpl &RHS)
Definition: DenseSet.h:99
DenseSetImpl(std::initializer_list< ValueT > Elems)
Definition: DenseSet.h:69
DenseSetImpl(unsigned InitialReserve=0)
Definition: DenseSet.h:67
size_type size() const
Definition: DenseSet.h:75
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:239
typename MapTy::const_iterator::difference_type difference_type
Definition: DenseSet.h:137
const ValueT * operator->() const
Definition: DenseSet.h:123
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
void erase(ConstIterator CI)
Definition: DenseSet.h:185
void resize(size_t Size)
Grow the DenseSet so that it has at least Size buckets.
Definition: DenseSet.h:80
ConstIterator(const typename MapTy::const_iterator &i)
Definition: DenseSet.h:145
#define I(x, y, z)
Definition: MD5.cpp:58
iterator find(const_arg_type_t< ValueT > V)
Definition: DenseSet.h:165
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again...
Definition: DenseSet.h:84
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
const ValueT & operator*() const
Definition: DenseSet.h:147
const ValueT * operator->() const
Definition: DenseSet.h:148
std::forward_iterator_tag iterator_category
Definition: DenseSet.h:115
typename MapTy::iterator::difference_type difference_type
Definition: DenseSet.h:111
const_iterator find_as(const LookupKeyT &Val) const
Definition: DenseSet.h:180
const_iterator find(const_arg_type_t< ValueT > V) const
Definition: DenseSet.h:166
size_t getMemorySize() const
Definition: DenseSet.h:76
const DenseSetEmpty & getSecond() const
Definition: DenseSet.h:41
const_iterator end() const
Definition: DenseSet.h:163
Base class for DenseSet and DenseSmallSet.
Definition: DenseSet.h:54