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

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