contrib/llvm/include/llvm/ADT/DenseSet.h

   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:
  39   KeyT &getFirst() { return key; }
  40   const KeyT &getFirst() const { return key; }
  41   DenseSetEmpty &getSecond() { return *this; }
  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
  68   explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
  69
  70   DenseSetImpl(std::initializer_list<ValueT> Elems)
  71       : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
  72     insert(Elems.begin(), Elems.end());
  73   }
  74
  75   bool empty() const { return TheMap.empty(); }
  76   size_type size() const { return TheMap.size(); }
  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.
  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.
  85   void reserve(size_t Size) { TheMap.reserve(Size); }
  86
  87   void clear() {
  88     TheMap.clear();
  89   }
  90
  91   /// Return 1 if the specified key is in the set, 0 otherwise.
  92   size_type count(const_arg_type_t<ValueT> V) const {
  93     return TheMap.count(V);
  94   }
  95
  96   bool erase(const ValueT &V) {
  97     return TheMap.erase(V);
  98   }
  99
 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;
 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;
 145     ConstIterator(const Iterator &B) : I(B.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
 160   iterator begin() { return Iterator(TheMap.begin()); }
 161   iterator end() { return Iterator(TheMap.end()); }
 162
 163   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
 164   const_iterator end() const { return ConstIterator(TheMap.end()); }
 165
 166   iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(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>
 177   iterator find_as(const LookupKeyT &Val) {
 178     return Iterator(TheMap.find_as(Val));
 179   }
 180   template <class LookupKeyT>
 181   const_iterator find_as(const LookupKeyT &Val) const {
 182     return ConstIterator(TheMap.find_as(Val));
 183   }
 184
 185   void erase(Iterator I) { return TheMap.erase(I.I); }
 186   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
 187
 188   std::pair<iterator, bool> insert(const ValueT &V) {
 189     detail::DenseSetEmpty Empty;
 190     return TheMap.try_emplace(V, Empty);
 191   }
 192
 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>
 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>
 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>
 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