runtime/llvm-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 // Taken from clang-1100.247.11.10.9
  15
  16 #ifndef LLVM_ADT_DENSESET_H
  17 #define LLVM_ADT_DENSESET_H
  18
  19 #include "llvm-DenseMap.h"
  20 #include "llvm-DenseMapInfo.h"
  21 #include "llvm-type_traits.h"
  22 #include <algorithm>
  23 #include <cstddef>
  24 #include <initializer_list>
  25 #include <iterator>
  26 #include <utility>
  27 #include <TargetConditionals.h>
  28
  29 #include "objc-private.h"
  30
  31 namespace objc {
  32
  33 namespace detail {
  34
  35 struct DenseSetEmpty {};
  36
  37 // Use the empty base class trick so we can create a DenseMap where the buckets
  38 // contain only a single item.
  39 template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
  40   KeyT key;
  41
  42 public:
  43   KeyT &getFirst() { return key; }
  44   const KeyT &getFirst() const { return key; }
  45   DenseSetEmpty &getSecond() { return *this; }
  46   const DenseSetEmpty &getSecond() const { return *this; }
  47 };
  48
  49 /// Base class for DenseSet and DenseSmallSet.
  50 ///
  51 /// MapTy should be either
  52 ///
  53 ///   DenseMap<ValueT, detail::DenseSetEmpty,
  54 ///            DenseMapValueInfo<detail::DenseSetEmpty>,
  55 ///            ValueInfoT, detail::DenseSetPair<ValueT>>
  56 ///
  57 /// or the equivalent SmallDenseMap type.  ValueInfoT must implement the
  58 /// DenseMapInfo "concept".
  59 template <typename ValueT, typename MapTy, typename ValueInfoT>
  60 class DenseSetImpl {
  61   static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
  62                 "DenseMap buckets unexpectedly large!");
  63   MapTy TheMap;
  64
  65   template <typename T>
  66   using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
  67
  68 public:
  69   using key_type = ValueT;
  70   using value_type = ValueT;
  71   using size_type = unsigned;
  72
  73   explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
  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     bool operator==(const ConstIterator& X) const { return I == X.I; }
 134     bool operator!=(const ConstIterator& X) const { return I != X.I; }
 135   };
 136
 137   class ConstIterator {
 138     typename MapTy::const_iterator I;
 139     friend class DenseSet;
 140     friend class Iterator;
 141
 142   public:
 143     using difference_type = typename MapTy::const_iterator::difference_type;
 144     using value_type = ValueT;
 145     using pointer = const value_type *;
 146     using reference = const value_type &;
 147     using iterator_category = std::forward_iterator_tag;
 148
 149     ConstIterator() = default;
 150     ConstIterator(const Iterator &B) : I(B.I) {}
 151     ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
 152
 153     const ValueT &operator*() const { return I->getFirst(); }
 154     const ValueT *operator->() const { return &I->getFirst(); }
 155
 156     ConstIterator& operator++() { ++I; return *this; }
 157     ConstIterator operator++(int) { auto T = *this; ++I; return T; }
 158     bool operator==(const ConstIterator& X) const { return I == X.I; }
 159     bool operator!=(const ConstIterator& X) const { return I != X.I; }
 160   };
 161
 162   using iterator = Iterator;
 163   using const_iterator = ConstIterator;
 164
 165   iterator begin() { return Iterator(TheMap.begin()); }
 166   iterator end() { return Iterator(TheMap.end()); }
 167
 168   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
 169   const_iterator end() const { return ConstIterator(TheMap.end()); }
 170
 171   iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
 172   const_iterator find(const_arg_type_t<ValueT> V) const {
 173     return ConstIterator(TheMap.find(V));
 174   }
 175
 176   /// Alternative version of find() which allows a different, and possibly less
 177   /// expensive, key type.
 178   /// The DenseMapInfo is responsible for supplying methods
 179   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
 180   /// used.
 181   template <class LookupKeyT>
 182   iterator find_as(const LookupKeyT &Val) {
 183     return Iterator(TheMap.find_as(Val));
 184   }
 185   template <class LookupKeyT>
 186   const_iterator find_as(const LookupKeyT &Val) const {
 187     return ConstIterator(TheMap.find_as(Val));
 188   }
 189
 190   void erase(Iterator I) { return TheMap.erase(I.I); }
 191   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
 192
 193   std::pair<iterator, bool> insert(const ValueT &V) {
 194     detail::DenseSetEmpty Empty;
 195     return TheMap.try_emplace(V, Empty);
 196   }
 197
 198   std::pair<iterator, bool> insert(ValueT &&V) {
 199     detail::DenseSetEmpty Empty;
 200     return TheMap.try_emplace(std::move(V), Empty);
 201   }
 202
 203   /// Alternative version of insert that uses a different (and possibly less
 204   /// expensive) key type.
 205   template <typename LookupKeyT>
 206   std::pair<iterator, bool> insert_as(const ValueT &V,
 207                                       const LookupKeyT &LookupKey) {
 208     return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
 209   }
 210   template <typename LookupKeyT>
 211   std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
 212     return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
 213   }
 214
 215   // Range insertion of values.
 216   template<typename InputIt>
 217   void insert(InputIt I, InputIt E) {
 218     for (; I != E; ++I)
 219       insert(*I);
 220   }
 221 };
 222
 223 /// Equality comparison for DenseSet.
 224 ///
 225 /// Iterates over elements of LHS confirming that each element is also a member
 226 /// of RHS, and that RHS contains no additional values.
 227 /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
 228 /// case is O(N^2) (if every hash collides).
 229 template <typename ValueT, typename MapTy, typename ValueInfoT>
 230 bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
 231                 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
 232   if (LHS.size() != RHS.size())
 233     return false;
 234
 235   for (auto &E : LHS)
 236     if (!RHS.count(E))
 237       return false;
 238
 239   return true;
 240 }
 241
 242 /// Inequality comparison for DenseSet.
 243 ///
 244 /// Equivalent to !(LHS == RHS). See operator== for performance notes.
 245 template <typename ValueT, typename MapTy, typename ValueInfoT>
 246 bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
 247                 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
 248   return !(LHS == RHS);
 249 }
 250
 251 } // end namespace detail
 252
 253 /// Implements a dense probed hash-table based set.
 254 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
 255 class DenseSet : public detail::DenseSetImpl<
 256                      ValueT, DenseMap<ValueT, detail::DenseSetEmpty,
 257                                       DenseMapValueInfo<detail::DenseSetEmpty>,
 258                                       ValueInfoT, detail::DenseSetPair<ValueT>>,
 259                      ValueInfoT> {
 260   using BaseT =
 261       detail::DenseSetImpl<ValueT,
 262                            DenseMap<ValueT, detail::DenseSetEmpty,
 263                                     DenseMapValueInfo<detail::DenseSetEmpty>,
 264                                     ValueInfoT, detail::DenseSetPair<ValueT>>,
 265                            ValueInfoT>;
 266
 267 public:
 268   using BaseT::BaseT;
 269 };
 270
 271 /// Implements a dense probed hash-table based set with some number of buckets
 272 /// stored inline.
 273 template <typename ValueT, unsigned InlineBuckets = 4,
 274           typename ValueInfoT = DenseMapInfo<ValueT>>
 275 class SmallDenseSet
 276     : public detail::DenseSetImpl<
 277           ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
 278                                 DenseMapValueInfo<detail::DenseSetEmpty>,
 279                                 ValueInfoT, detail::DenseSetPair<ValueT>>,
 280           ValueInfoT> {
 281   using BaseT = detail::DenseSetImpl<
 282       ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
 283                             DenseMapValueInfo<detail::DenseSetEmpty>,
 284                             ValueInfoT, detail::DenseSetPair<ValueT>>,
 285       ValueInfoT>;
 286
 287 public:
 288   using BaseT::BaseT;
 289 };
 290
 291 } // end namespace objc
 292
 293 #endif // LLVM_ADT_DENSESET_H