llvm/ADT/SmallSet.h

0001 //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines the SmallSet class.
0011 ///
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ADT_SMALLSET_H
0015 #define LLVM_ADT_SMALLSET_H
0016
0017 #include "llvm/ADT/SmallPtrSet.h"
0018 #include "llvm/ADT/SmallVector.h"
0019 #include "llvm/ADT/iterator.h"
0020 #include <cstddef>
0021 #include <functional>
0022 #include <initializer_list>
0023 #include <set>
0024 #include <utility>
0025
0026 namespace llvm {
0027
0028 /// SmallSetIterator - This class implements a const_iterator for SmallSet by
0029 /// delegating to the underlying SmallVector or Set iterators.
0030 template <typename T, unsigned N, typename C>
0031 class SmallSetIterator
0032     : public iterator_facade_base<SmallSetIterator<T, N, C>,
0033                                   std::forward_iterator_tag, T> {
0034 private:
0035   using SetIterTy = typename std::set<T, C>::const_iterator;
0036   using VecIterTy = typename SmallVector<T, N>::const_iterator;
0037   using SelfTy = SmallSetIterator<T, N, C>;
0038
0039   /// Iterators to the parts of the SmallSet containing the data. They are set
0040   /// depending on isSmall.
0041   union {
0042     SetIterTy SetIter;
0043     VecIterTy VecIter;
0044   };
0045
0046   bool IsSmall;
0047
0048 public:
0049   SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), IsSmall(false) {}
0050
0051   SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), IsSmall(true) {}
0052
0053   // Spell out destructor, copy/move constructor and assignment operators for
0054   // MSVC STL, where set<T>::const_iterator is not trivially copy constructible.
0055   ~SmallSetIterator() {
0056     if (IsSmall)
0057       VecIter.~VecIterTy();
0058     else
0059       SetIter.~SetIterTy();
0060   }
0061
0062   SmallSetIterator(const SmallSetIterator &Other) : IsSmall(Other.IsSmall) {
0063     if (IsSmall)
0064       VecIter = Other.VecIter;
0065     else
0066       // Use placement new, to make sure SetIter is properly constructed, even
0067       // if it is not trivially copy-able (e.g. in MSVC).
0068       new (&SetIter) SetIterTy(Other.SetIter);
0069   }
0070
0071   SmallSetIterator(SmallSetIterator &&Other) : IsSmall(Other.IsSmall) {
0072     if (IsSmall)
0073       VecIter = std::move(Other.VecIter);
0074     else
0075       // Use placement new, to make sure SetIter is properly constructed, even
0076       // if it is not trivially copy-able (e.g. in MSVC).
0077       new (&SetIter) SetIterTy(std::move(Other.SetIter));
0078   }
0079
0080   SmallSetIterator& operator=(const SmallSetIterator& Other) {
0081     // Call destructor for SetIter, so it gets properly destroyed if it is
0082     // not trivially destructible in case we are setting VecIter.
0083     if (!IsSmall)
0084       SetIter.~SetIterTy();
0085
0086     IsSmall = Other.IsSmall;
0087     if (IsSmall)
0088       VecIter = Other.VecIter;
0089     else
0090       new (&SetIter) SetIterTy(Other.SetIter);
0091     return *this;
0092   }
0093
0094   SmallSetIterator& operator=(SmallSetIterator&& Other) {
0095     // Call destructor for SetIter, so it gets properly destroyed if it is
0096     // not trivially destructible in case we are setting VecIter.
0097     if (!IsSmall)
0098       SetIter.~SetIterTy();
0099
0100     IsSmall = Other.IsSmall;
0101     if (IsSmall)
0102       VecIter = std::move(Other.VecIter);
0103     else
0104       new (&SetIter) SetIterTy(std::move(Other.SetIter));
0105     return *this;
0106   }
0107
0108   bool operator==(const SmallSetIterator &RHS) const {
0109     if (IsSmall != RHS.IsSmall)
0110       return false;
0111     if (IsSmall)
0112       return VecIter == RHS.VecIter;
0113     return SetIter == RHS.SetIter;
0114   }
0115
0116   SmallSetIterator &operator++() { // Preincrement
0117     if (IsSmall)
0118       ++VecIter;
0119     else
0120       ++SetIter;
0121     return *this;
0122   }
0123
0124   const T &operator*() const { return IsSmall ? *VecIter : *SetIter; }
0125 };
0126
0127 /// SmallSet - This maintains a set of unique values, optimizing for the case
0128 /// when the set is small (less than N).  In this case, the set can be
0129 /// maintained with no mallocs.  If the set gets large, we expand to using an
0130 /// std::set to maintain reasonable lookup times.
0131 template <typename T, unsigned N, typename C = std::less<T>>
0132 class SmallSet {
0133   /// Use a SmallVector to hold the elements here (even though it will never
0134   /// reach its 'large' stage) to avoid calling the default ctors of elements
0135   /// we will never use.
0136   SmallVector<T, N> Vector;
0137   std::set<T, C> Set;
0138
0139   // In small mode SmallPtrSet uses linear search for the elements, so it is
0140   // not a good idea to choose this value too high. You may consider using a
0141   // DenseSet<> instead if you expect many elements in the set.
0142   static_assert(N <= 32, "N should be small");
0143
0144 public:
0145   using key_type = T;
0146   using size_type = size_t;
0147   using value_type = T;
0148   using const_iterator = SmallSetIterator<T, N, C>;
0149
0150   SmallSet() = default;
0151   SmallSet(const SmallSet &) = default;
0152   SmallSet(SmallSet &&) = default;
0153
0154   template <typename IterT> SmallSet(IterT Begin, IterT End) {
0155     insert(Begin, End);
0156   }
0157
0158   template <typename RangeT>
0159   explicit SmallSet(const iterator_range<RangeT> &R) {
0160     insert(R.begin(), R.end());
0161   }
0162
0163   SmallSet(std::initializer_list<T> L) { insert(L.begin(), L.end()); }
0164
0165   SmallSet &operator=(const SmallSet &) = default;
0166   SmallSet &operator=(SmallSet &&) = default;
0167
0168   [[nodiscard]] bool empty() const { return Vector.empty() && Set.empty(); }
0169
0170   size_type size() const {
0171     return isSmall() ? Vector.size() : Set.size();
0172   }
0173
0174   /// count - Return 1 if the element is in the set, 0 otherwise.
0175   size_type count(const T &V) const { return contains(V) ? 1 : 0; }
0176
0177   /// insert - Insert an element into the set if it isn't already there.
0178   /// Returns a pair. The first value of it is an iterator to the inserted
0179   /// element or the existing element in the set. The second value is true
0180   /// if the element is inserted (it was not in the set before).
0181   std::pair<const_iterator, bool> insert(const T &V) { return insertImpl(V); }
0182
0183   std::pair<const_iterator, bool> insert(T &&V) {
0184     return insertImpl(std::move(V));
0185   }
0186
0187   template <typename IterT>
0188   void insert(IterT I, IterT E) {
0189     for (; I != E; ++I)
0190       insert(*I);
0191   }
0192
0193   bool erase(const T &V) {
0194     if (!isSmall())
0195       return Set.erase(V);
0196     auto I = vfind(V);
0197     if (I != Vector.end()) {
0198       Vector.erase(I);
0199       return true;
0200     }
0201     return false;
0202   }
0203
0204   void clear() {
0205     Vector.clear();
0206     Set.clear();
0207   }
0208
0209   const_iterator begin() const {
0210     if (isSmall())
0211       return {Vector.begin()};
0212     return {Set.begin()};
0213   }
0214
0215   const_iterator end() const {
0216     if (isSmall())
0217       return {Vector.end()};
0218     return {Set.end()};
0219   }
0220
0221   /// Check if the SmallSet contains the given element.
0222   bool contains(const T &V) const {
0223     if (isSmall())
0224       return vfind(V) != Vector.end();
0225     return Set.find(V) != Set.end();
0226   }
0227
0228 private:
0229   bool isSmall() const { return Set.empty(); }
0230
0231   template <typename ArgType>
0232   std::pair<const_iterator, bool> insertImpl(ArgType &&V) {
0233     static_assert(std::is_convertible_v<ArgType, T>,
0234                   "ArgType must be convertible to T!");
0235     if (!isSmall()) {
0236       auto [I, Inserted] = Set.insert(std::forward<ArgType>(V));
0237       return {const_iterator(I), Inserted};
0238     }
0239
0240     auto I = vfind(V);
0241     if (I != Vector.end()) // Don't reinsert if it already exists.
0242       return {const_iterator(I), false};
0243     if (Vector.size() < N) {
0244       Vector.push_back(std::forward<ArgType>(V));
0245       return {const_iterator(std::prev(Vector.end())), true};
0246     }
0247     // Otherwise, grow from vector to set.
0248     Set.insert(std::make_move_iterator(Vector.begin()),
0249                std::make_move_iterator(Vector.end()));
0250     Vector.clear();
0251     return {const_iterator(Set.insert(std::forward<ArgType>(V)).first), true};
0252   }
0253
0254   // Handwritten linear search. The use of std::find might hurt performance as
0255   // its implementation may be optimized for larger containers.
0256   typename SmallVector<T, N>::const_iterator vfind(const T &V) const {
0257     for (auto I = Vector.begin(), E = Vector.end(); I != E; ++I)
0258       if (*I == V)
0259         return I;
0260     return Vector.end();
0261   }
0262 };
0263
0264 /// If this set is of pointer values, transparently switch over to using
0265 /// SmallPtrSet for performance.
0266 template <typename PointeeType, unsigned N>
0267 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
0268
0269 /// Equality comparison for SmallSet.
0270 ///
0271 /// Iterates over elements of LHS confirming that each element is also a member
0272 /// of RHS, and that RHS contains no additional values.
0273 /// Equivalent to N calls to RHS.count.
0274 /// For small-set mode amortized complexity is O(N^2)
0275 /// For large-set mode amortized complexity is linear, worst case is O(N^2) (if
0276 /// every hash collides).
0277 template <typename T, unsigned LN, unsigned RN, typename C>
0278 bool operator==(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) {
0279   if (LHS.size() != RHS.size())
0280     return false;
0281
0282   // All elements in LHS must also be in RHS
0283   return all_of(LHS, [&RHS](const T &E) { return RHS.count(E); });
0284 }
0285
0286 /// Inequality comparison for SmallSet.
0287 ///
0288 /// Equivalent to !(LHS == RHS). See operator== for performance notes.
0289 template <typename T, unsigned LN, unsigned RN, typename C>
0290 bool operator!=(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) {
0291   return !(LHS == RHS);
0292 }
0293
0294 } // end namespace llvm
0295
0296 #endif // LLVM_ADT_SMALLSET_H