contrib/llvm/include/llvm/ADT/SmallSet.h

   1 //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- 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 SmallSet class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_SMALLSET_H
  15 #define LLVM_ADT_SMALLSET_H
  16
  17 #include "llvm/ADT/None.h"
  18 #include "llvm/ADT/SmallPtrSet.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/ADT/iterator.h"
  21 #include "llvm/Support/Compiler.h"
  22 #include "llvm/Support/type_traits.h"
  23 #include <cstddef>
  24 #include <functional>
  25 #include <set>
  26 #include <type_traits>
  27 #include <utility>
  28
  29 namespace llvm {
  30
  31 /// SmallSetIterator - This class implements a const_iterator for SmallSet by
  32 /// delegating to the underlying SmallVector or Set iterators.
  33 template <typename T, unsigned N, typename C>
  34 class SmallSetIterator
  35     : public iterator_facade_base<SmallSetIterator<T, N, C>,
  36                                   std::forward_iterator_tag, T> {
  37 private:
  38   using SetIterTy = typename std::set<T, C>::const_iterator;
  39   using VecIterTy = typename SmallVector<T, N>::const_iterator;
  40   using SelfTy = SmallSetIterator<T, N, C>;
  41
  42   /// Iterators to the parts of the SmallSet containing the data. They are set
  43   /// depending on isSmall.
  44   union {
  45     SetIterTy SetIter;
  46     VecIterTy VecIter;
  47   };
  48
  49   bool isSmall;
  50
  51 public:
  52   SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {}
  53
  54   SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), isSmall(true) {}
  55
  56   // Spell out destructor, copy/move constructor and assignment operators for
  57   // MSVC STL, where set<T>::const_iterator is not trivially copy constructible.
  58   ~SmallSetIterator() {
  59     if (isSmall)
  60       VecIter.~VecIterTy();
  61     else
  62       SetIter.~SetIterTy();
  63   }
  64
  65   SmallSetIterator(const SmallSetIterator &Other) : isSmall(Other.isSmall) {
  66     if (isSmall)
  67       VecIter = Other.VecIter;
  68     else
  69       // Use placement new, to make sure SetIter is properly constructed, even
  70       // if it is not trivially copy-able (e.g. in MSVC).
  71       new (&SetIter) SetIterTy(Other.SetIter);
  72   }
  73
  74   SmallSetIterator(SmallSetIterator &&Other) : isSmall(Other.isSmall) {
  75     if (isSmall)
  76       VecIter = std::move(Other.VecIter);
  77     else
  78       // Use placement new, to make sure SetIter is properly constructed, even
  79       // if it is not trivially copy-able (e.g. in MSVC).
  80       new (&SetIter) SetIterTy(std::move(Other.SetIter));
  81   }
  82
  83   SmallSetIterator& operator=(const SmallSetIterator& Other) {
  84     // Call destructor for SetIter, so it gets properly destroyed if it is
  85     // not trivially destructible in case we are setting VecIter.
  86     if (!isSmall)
  87       SetIter.~SetIterTy();
  88
  89     isSmall = Other.isSmall;
  90     if (isSmall)
  91       VecIter = Other.VecIter;
  92     else
  93       new (&SetIter) SetIterTy(Other.SetIter);
  94     return *this;
  95   }
  96
  97   SmallSetIterator& operator=(SmallSetIterator&& Other) {
  98     // Call destructor for SetIter, so it gets properly destroyed if it is
  99     // not trivially destructible in case we are setting VecIter.
 100     if (!isSmall)
 101       SetIter.~SetIterTy();
 102
 103     isSmall = Other.isSmall;
 104     if (isSmall)
 105       VecIter = std::move(Other.VecIter);
 106     else
 107       new (&SetIter) SetIterTy(std::move(Other.SetIter));
 108     return *this;
 109   }
 110
 111   bool operator==(const SmallSetIterator &RHS) const {
 112     if (isSmall != RHS.isSmall)
 113       return false;
 114     if (isSmall)
 115       return VecIter == RHS.VecIter;
 116     return SetIter == RHS.SetIter;
 117   }
 118
 119   SmallSetIterator &operator++() { // Preincrement
 120     if (isSmall)
 121       VecIter++;
 122     else
 123       SetIter++;
 124     return *this;
 125   }
 126
 127   const T &operator*() const { return isSmall ? *VecIter : *SetIter; }
 128 };
 129
 130 /// SmallSet - This maintains a set of unique values, optimizing for the case
 131 /// when the set is small (less than N).  In this case, the set can be
 132 /// maintained with no mallocs.  If the set gets large, we expand to using an
 133 /// std::set to maintain reasonable lookup times.
 134 template <typename T, unsigned N, typename C = std::less<T>>
 135 class SmallSet {
 136   /// Use a SmallVector to hold the elements here (even though it will never
 137   /// reach its 'large' stage) to avoid calling the default ctors of elements
 138   /// we will never use.
 139   SmallVector<T, N> Vector;
 140   std::set<T, C> Set;
 141
 142   using VIterator = typename SmallVector<T, N>::const_iterator;
 143   using mutable_iterator = typename SmallVector<T, N>::iterator;
 144
 145   // In small mode SmallPtrSet uses linear search for the elements, so it is
 146   // not a good idea to choose this value too high. You may consider using a
 147   // DenseSet<> instead if you expect many elements in the set.
 148   static_assert(N <= 32, "N should be small");
 149
 150 public:
 151   using size_type = size_t;
 152   using const_iterator = SmallSetIterator<T, N, C>;
 153
 154   SmallSet() = default;
 155
 156   LLVM_NODISCARD bool empty() const {
 157     return Vector.empty() && Set.empty();
 158   }
 159
 160   size_type size() const {
 161     return isSmall() ? Vector.size() : Set.size();
 162   }
 163
 164   /// count - Return 1 if the element is in the set, 0 otherwise.
 165   size_type count(const T &V) const {
 166     if (isSmall()) {
 167       // Since the collection is small, just do a linear search.
 168       return vfind(V) == Vector.end() ? 0 : 1;
 169     } else {
 170       return Set.count(V);
 171     }
 172   }
 173
 174   /// insert - Insert an element into the set if it isn't already there.
 175   /// Returns true if the element is inserted (it was not in the set before).
 176   /// The first value of the returned pair is unused and provided for
 177   /// partial compatibility with the standard library self-associative container
 178   /// concept.
 179   // FIXME: Add iterators that abstract over the small and large form, and then
 180   // return those here.
 181   std::pair<NoneType, bool> insert(const T &V) {
 182     if (!isSmall())
 183       return std::make_pair(None, Set.insert(V).second);
 184
 185     VIterator I = vfind(V);
 186     if (I != Vector.end())    // Don't reinsert if it already exists.
 187       return std::make_pair(None, false);
 188     if (Vector.size() < N) {
 189       Vector.push_back(V);
 190       return std::make_pair(None, true);
 191     }
 192
 193     // Otherwise, grow from vector to set.
 194     while (!Vector.empty()) {
 195       Set.insert(Vector.back());
 196       Vector.pop_back();
 197     }
 198     Set.insert(V);
 199     return std::make_pair(None, true);
 200   }
 201
 202   template <typename IterT>
 203   void insert(IterT I, IterT E) {
 204     for (; I != E; ++I)
 205       insert(*I);
 206   }
 207
 208   bool erase(const T &V) {
 209     if (!isSmall())
 210       return Set.erase(V);
 211     for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
 212       if (*I == V) {
 213         Vector.erase(I);
 214         return true;
 215       }
 216     return false;
 217   }
 218
 219   void clear() {
 220     Vector.clear();
 221     Set.clear();
 222   }
 223
 224   const_iterator begin() const {
 225     if (isSmall())
 226       return {Vector.begin()};
 227     return {Set.begin()};
 228   }
 229
 230   const_iterator end() const {
 231     if (isSmall())
 232       return {Vector.end()};
 233     return {Set.end()};
 234   }
 235
 236 private:
 237   bool isSmall() const { return Set.empty(); }
 238
 239   VIterator vfind(const T &V) const {
 240     for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
 241       if (*I == V)
 242         return I;
 243     return Vector.end();
 244   }
 245 };
 246
 247 /// If this set is of pointer values, transparently switch over to using
 248 /// SmallPtrSet for performance.
 249 template <typename PointeeType, unsigned N>
 250 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
 251
 252 } // end namespace llvm
 253
 254 #endif // LLVM_ADT_SMALLSET_H