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/// \file
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 <cstddef>
22#include <initializer_list>
23#include <iterator>
24#include <utility>
25
26namespace llvm {
27
28namespace detail {
29
30struct DenseSetEmpty {};
31
32// Use the empty base class trick so we can create a DenseMap where the buckets
33// contain only a single item.
34template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
35  KeyT key;
36
37public:
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".
53template <typename ValueT, typename MapTy, typename ValueInfoT>
54class 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
62public:
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  template <typename InputIt>
70  DenseSetImpl(const InputIt &I, const InputIt &E)
71      : DenseSetImpl(PowerOf2Ceil(std::distance(I, E))) {
72    insert(I, E);
73  }
74
75  DenseSetImpl(std::initializer_list<ValueT> Elems)
76      : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
77    insert(Elems.begin(), Elems.end());
78  }
79
80  bool empty() const { return TheMap.empty(); }
81  size_type size() const { return TheMap.size(); }
82  size_t getMemorySize() const { return TheMap.getMemorySize(); }
83
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); }
87
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); }
91
92  void clear() {
93    TheMap.clear();
94  }
95
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);
99  }
100
101  bool erase(const ValueT &V) {
102    return TheMap.erase(V);
103  }
104
105  void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
106
107  // Iterators.
108
109  class ConstIterator;
110
111  class Iterator {
112    typename MapTy::iterator I;
113    friend class DenseSetImpl;
114    friend class ConstIterator;
115
116  public:
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;
122
123    Iterator() = default;
124    Iterator(const typename MapTy::iterator &i) : I(i) {}
125
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(); }
130
131    Iterator& operator++() { ++I; return *this; }
132    Iterator operator++(int) { auto T = *this; ++I; return T; }
133    friend bool operator==(const Iterator &X, const Iterator &Y) {
134      return X.I == Y.I;
135    }
136    friend bool operator!=(const Iterator &X, const Iterator &Y) {
137      return X.I != Y.I;
138    }
139  };
140
141  class ConstIterator {
142    typename MapTy::const_iterator I;
143    friend class DenseSetImpl;
144    friend class Iterator;
145
146  public:
147    using difference_type = typename MapTy::const_iterator::difference_type;
148    using value_type = ValueT;
149    using pointer = const value_type *;
150    using reference = const value_type &;
151    using iterator_category = std::forward_iterator_tag;
152
153    ConstIterator() = default;
154    ConstIterator(const Iterator &B) : I(B.I) {}
155    ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
156
157    const ValueT &operator*() const { return I->getFirst(); }
158    const ValueT *operator->() const { return &I->getFirst(); }
159
160    ConstIterator& operator++() { ++I; return *this; }
161    ConstIterator operator++(int) { auto T = *this; ++I; return T; }
162    friend bool operator==(const ConstIterator &X, const ConstIterator &Y) {
163      return X.I == Y.I;
164    }
165    friend bool operator!=(const ConstIterator &X, const ConstIterator &Y) {
166      return X.I != Y.I;
167    }
168  };
169
170  using iterator = Iterator;
171  using const_iterator = ConstIterator;
172
173  iterator begin() { return Iterator(TheMap.begin()); }
174  iterator end() { return Iterator(TheMap.end()); }
175
176  const_iterator begin() const { return ConstIterator(TheMap.begin()); }
177  const_iterator end() const { return ConstIterator(TheMap.end()); }
178
179  iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
180  const_iterator find(const_arg_type_t<ValueT> V) const {
181    return ConstIterator(TheMap.find(V));
182  }
183
184  /// Check if the set contains the given element.
185  bool contains(const_arg_type_t<ValueT> V) const {
186    return TheMap.find(V) != TheMap.end();
187  }
188
189  /// Alternative version of find() which allows a different, and possibly less
190  /// expensive, key type.
191  /// The DenseMapInfo is responsible for supplying methods
192  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
193  /// used.
194  template <class LookupKeyT>
195  iterator find_as(const LookupKeyT &Val) {
196    return Iterator(TheMap.find_as(Val));
197  }
198  template <class LookupKeyT>
199  const_iterator find_as(const LookupKeyT &Val) const {
200    return ConstIterator(TheMap.find_as(Val));
201  }
202
203  void erase(Iterator I) { return TheMap.erase(I.I); }
204  void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
205
206  std::pair<iterator, bool> insert(const ValueT &V) {
207    detail::DenseSetEmpty Empty;
208    return TheMap.try_emplace(V, Empty);
209  }
210
211  std::pair<iterator, bool> insert(ValueT &&V) {
212    detail::DenseSetEmpty Empty;
213    return TheMap.try_emplace(std::move(V), Empty);
214  }
215
216  /// Alternative version of insert that uses a different (and possibly less
217  /// expensive) key type.
218  template <typename LookupKeyT>
219  std::pair<iterator, bool> insert_as(const ValueT &V,
220                                      const LookupKeyT &LookupKey) {
221    return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
222  }
223  template <typename LookupKeyT>
224  std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
225    return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
226  }
227
228  // Range insertion of values.
229  template<typename InputIt>
230  void insert(InputIt I, InputIt E) {
231    for (; I != E; ++I)
232      insert(*I);
233  }
234};
235
236/// Equality comparison for DenseSet.
237///
238/// Iterates over elements of LHS confirming that each element is also a member
239/// of RHS, and that RHS contains no additional values.
240/// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
241/// case is O(N^2) (if every hash collides).
242template <typename ValueT, typename MapTy, typename ValueInfoT>
243bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
244                const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
245  if (LHS.size() != RHS.size())
246    return false;
247
248  for (auto &E : LHS)
249    if (!RHS.count(E))
250      return false;
251
252  return true;
253}
254
255/// Inequality comparison for DenseSet.
256///
257/// Equivalent to !(LHS == RHS). See operator== for performance notes.
258template <typename ValueT, typename MapTy, typename ValueInfoT>
259bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
260                const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
261  return !(LHS == RHS);
262}
263
264} // end namespace detail
265
266/// Implements a dense probed hash-table based set.
267template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
268class DenseSet : public detail::DenseSetImpl<
269                     ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
270                                      detail::DenseSetPair<ValueT>>,
271                     ValueInfoT> {
272  using BaseT =
273      detail::DenseSetImpl<ValueT,
274                           DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
275                                    detail::DenseSetPair<ValueT>>,
276                           ValueInfoT>;
277
278public:
279  using BaseT::BaseT;
280};
281
282/// Implements a dense probed hash-table based set with some number of buckets
283/// stored inline.
284template <typename ValueT, unsigned InlineBuckets = 4,
285          typename ValueInfoT = DenseMapInfo<ValueT>>
286class SmallDenseSet
287    : public detail::DenseSetImpl<
288          ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
289                                ValueInfoT, detail::DenseSetPair<ValueT>>,
290          ValueInfoT> {
291  using BaseT = detail::DenseSetImpl<
292      ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
293                            ValueInfoT, detail::DenseSetPair<ValueT>>,
294      ValueInfoT>;
295
296public:
297  using BaseT::BaseT;
298};
299
300} // end namespace llvm
301
302#endif // LLVM_ADT_DENSESET_H
303