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/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:
  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;
  65   using size_type = unsigned;
  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;
 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;
 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;
 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) {
 188     detail::DenseSetEmpty Empty;
 189     return TheMap.try_emplace(V, Empty);
 190   }
 191
 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>
 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>>
 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