llvm/ADT/SetVector.h

0001 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- 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 implements a set that has insertion order iteration
0011 /// characteristics. This is useful for keeping a set of things that need to be
0012 /// visited later but in a deterministic order (insertion order). The interface
0013 /// is purposefully minimal.
0014 ///
0015 /// This file defines SetVector and SmallSetVector, which performs no
0016 /// allocations if the SetVector has less than a certain number of elements.
0017 ///
0018 //===----------------------------------------------------------------------===//
0019
0020 #ifndef LLVM_ADT_SETVECTOR_H
0021 #define LLVM_ADT_SETVECTOR_H
0022
0023 #include "llvm/ADT/ArrayRef.h"
0024 #include "llvm/ADT/DenseSet.h"
0025 #include "llvm/ADT/STLExtras.h"
0026 #include "llvm/ADT/SmallVector.h"
0027 #include "llvm/Support/Compiler.h"
0028 #include <cassert>
0029 #include <iterator>
0030
0031 namespace llvm {
0032
0033 /// A vector that has set insertion semantics.
0034 ///
0035 /// This adapter class provides a way to keep a set of things that also has the
0036 /// property of a deterministic iteration order. The order of iteration is the
0037 /// order of insertion.
0038 ///
0039 /// The key and value types are derived from the Set and Vector types
0040 /// respectively. This allows the vector-type operations and set-type operations
0041 /// to have different types. In particular, this is useful when storing pointers
0042 /// as "Foo *" values but looking them up as "const Foo *" keys.
0043 ///
0044 /// No constraint is placed on the key and value types, although it is assumed
0045 /// that value_type can be converted into key_type for insertion. Users must be
0046 /// aware of any loss of information in this conversion. For example, setting
0047 /// value_type to float and key_type to int can produce very surprising results,
0048 /// but it is not explicitly disallowed.
0049 ///
0050 /// The parameter N specifies the "small" size of the container, which is the
0051 /// number of elements upto which a linear scan over the Vector will be used
0052 /// when searching for elements instead of checking Set, due to it being better
0053 /// for performance. A value of 0 means that this mode of operation is not used,
0054 /// and is the default value.
0055 template <typename T, typename Vector = SmallVector<T, 0>,
0056           typename Set = DenseSet<T>, unsigned N = 0>
0057 class SetVector {
0058   // Much like in SmallPtrSet, this value should not be too high to prevent
0059   // excessively long linear scans from occuring.
0060   static_assert(N <= 32, "Small size should be less than or equal to 32!");
0061
0062 public:
0063   using value_type = typename Vector::value_type;
0064   using key_type = typename Set::key_type;
0065   using reference = value_type &;
0066   using const_reference = const value_type &;
0067   using set_type = Set;
0068   using vector_type = Vector;
0069   using iterator = typename vector_type::const_iterator;
0070   using const_iterator = typename vector_type::const_iterator;
0071   using reverse_iterator = typename vector_type::const_reverse_iterator;
0072   using const_reverse_iterator = typename vector_type::const_reverse_iterator;
0073   using size_type = typename vector_type::size_type;
0074
0075   /// Construct an empty SetVector
0076   SetVector() = default;
0077
0078   /// Initialize a SetVector with a range of elements
0079   template<typename It>
0080   SetVector(It Start, It End) {
0081     insert(Start, End);
0082   }
0083
0084   ArrayRef<value_type> getArrayRef() const { return vector_; }
0085
0086   /// Clear the SetVector and return the underlying vector.
0087   Vector takeVector() {
0088     set_.clear();
0089     return std::move(vector_);
0090   }
0091
0092   /// Determine if the SetVector is empty or not.
0093   bool empty() const {
0094     return vector_.empty();
0095   }
0096
0097   /// Determine the number of elements in the SetVector.
0098   size_type size() const {
0099     return vector_.size();
0100   }
0101
0102   /// Get an iterator to the beginning of the SetVector.
0103   iterator begin() {
0104     return vector_.begin();
0105   }
0106
0107   /// Get a const_iterator to the beginning of the SetVector.
0108   const_iterator begin() const {
0109     return vector_.begin();
0110   }
0111
0112   /// Get an iterator to the end of the SetVector.
0113   iterator end() {
0114     return vector_.end();
0115   }
0116
0117   /// Get a const_iterator to the end of the SetVector.
0118   const_iterator end() const {
0119     return vector_.end();
0120   }
0121
0122   /// Get an reverse_iterator to the end of the SetVector.
0123   reverse_iterator rbegin() {
0124     return vector_.rbegin();
0125   }
0126
0127   /// Get a const_reverse_iterator to the end of the SetVector.
0128   const_reverse_iterator rbegin() const {
0129     return vector_.rbegin();
0130   }
0131
0132   /// Get a reverse_iterator to the beginning of the SetVector.
0133   reverse_iterator rend() {
0134     return vector_.rend();
0135   }
0136
0137   /// Get a const_reverse_iterator to the beginning of the SetVector.
0138   const_reverse_iterator rend() const {
0139     return vector_.rend();
0140   }
0141
0142   /// Return the first element of the SetVector.
0143   const value_type &front() const {
0144     assert(!empty() && "Cannot call front() on empty SetVector!");
0145     return vector_.front();
0146   }
0147
0148   /// Return the last element of the SetVector.
0149   const value_type &back() const {
0150     assert(!empty() && "Cannot call back() on empty SetVector!");
0151     return vector_.back();
0152   }
0153
0154   /// Index into the SetVector.
0155   const_reference operator[](size_type n) const {
0156     assert(n < vector_.size() && "SetVector access out of range!");
0157     return vector_[n];
0158   }
0159
0160   /// Insert a new element into the SetVector.
0161   /// \returns true if the element was inserted into the SetVector.
0162   bool insert(const value_type &X) {
0163     if constexpr (canBeSmall())
0164       if (isSmall()) {
0165         if (!llvm::is_contained(vector_, X)) {
0166           vector_.push_back(X);
0167           if (vector_.size() > N)
0168             makeBig();
0169           return true;
0170         }
0171         return false;
0172       }
0173
0174     bool result = set_.insert(X).second;
0175     if (result)
0176       vector_.push_back(X);
0177     return result;
0178   }
0179
0180   /// Insert a range of elements into the SetVector.
0181   template<typename It>
0182   void insert(It Start, It End) {
0183     for (; Start != End; ++Start)
0184       insert(*Start);
0185   }
0186
0187   /// Remove an item from the set vector.
0188   bool remove(const value_type& X) {
0189     if constexpr (canBeSmall())
0190       if (isSmall()) {
0191         typename vector_type::iterator I = find(vector_, X);
0192         if (I != vector_.end()) {
0193           vector_.erase(I);
0194           return true;
0195         }
0196         return false;
0197       }
0198
0199     if (set_.erase(X)) {
0200       typename vector_type::iterator I = find(vector_, X);
0201       assert(I != vector_.end() && "Corrupted SetVector instances!");
0202       vector_.erase(I);
0203       return true;
0204     }
0205     return false;
0206   }
0207
0208   /// Erase a single element from the set vector.
0209   /// \returns an iterator pointing to the next element that followed the
0210   /// element erased. This is the end of the SetVector if the last element is
0211   /// erased.
0212   iterator erase(const_iterator I) {
0213     if constexpr (canBeSmall())
0214       if (isSmall())
0215         return vector_.erase(I);
0216
0217     const key_type &V = *I;
0218     assert(set_.count(V) && "Corrupted SetVector instances!");
0219     set_.erase(V);
0220     return vector_.erase(I);
0221   }
0222
0223   /// Remove items from the set vector based on a predicate function.
0224   ///
0225   /// This is intended to be equivalent to the following code, if we could
0226   /// write it:
0227   ///
0228   /// \code
0229   ///   V.erase(remove_if(V, P), V.end());
0230   /// \endcode
0231   ///
0232   /// However, SetVector doesn't expose non-const iterators, making any
0233   /// algorithm like remove_if impossible to use.
0234   ///
0235   /// \returns true if any element is removed.
0236   template <typename UnaryPredicate>
0237   bool remove_if(UnaryPredicate P) {
0238     typename vector_type::iterator I = [this, P] {
0239       if constexpr (canBeSmall())
0240         if (isSmall())
0241           return llvm::remove_if(vector_, P);
0242
0243       return llvm::remove_if(vector_,
0244                              TestAndEraseFromSet<UnaryPredicate>(P, set_));
0245     }();
0246
0247     if (I == vector_.end())
0248       return false;
0249     vector_.erase(I, vector_.end());
0250     return true;
0251   }
0252
0253   /// Check if the SetVector contains the given key.
0254   bool contains(const key_type &key) const {
0255     if constexpr (canBeSmall())
0256       if (isSmall())
0257         return is_contained(vector_, key);
0258
0259     return set_.find(key) != set_.end();
0260   }
0261
0262   /// Count the number of elements of a given key in the SetVector.
0263   /// \returns 0 if the element is not in the SetVector, 1 if it is.
0264   size_type count(const key_type &key) const {
0265     if constexpr (canBeSmall())
0266       if (isSmall())
0267         return is_contained(vector_, key);
0268
0269     return set_.count(key);
0270   }
0271
0272   /// Completely clear the SetVector
0273   void clear() {
0274     set_.clear();
0275     vector_.clear();
0276   }
0277
0278   /// Remove the last element of the SetVector.
0279   void pop_back() {
0280     assert(!empty() && "Cannot remove an element from an empty SetVector!");
0281     set_.erase(back());
0282     vector_.pop_back();
0283   }
0284
0285   [[nodiscard]] value_type pop_back_val() {
0286     value_type Ret = back();
0287     pop_back();
0288     return Ret;
0289   }
0290
0291   bool operator==(const SetVector &that) const {
0292     return vector_ == that.vector_;
0293   }
0294
0295   bool operator!=(const SetVector &that) const {
0296     return vector_ != that.vector_;
0297   }
0298
0299   /// Compute This := This u S, return whether 'This' changed.
0300   /// TODO: We should be able to use set_union from SetOperations.h, but
0301   ///       SetVector interface is inconsistent with DenseSet.
0302   template <class STy>
0303   bool set_union(const STy &S) {
0304     bool Changed = false;
0305
0306     for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
0307          ++SI)
0308       if (insert(*SI))
0309         Changed = true;
0310
0311     return Changed;
0312   }
0313
0314   /// Compute This := This - B
0315   /// TODO: We should be able to use set_subtract from SetOperations.h, but
0316   ///       SetVector interface is inconsistent with DenseSet.
0317   template <class STy>
0318   void set_subtract(const STy &S) {
0319     for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
0320          ++SI)
0321       remove(*SI);
0322   }
0323
0324   void swap(SetVector<T, Vector, Set, N> &RHS) {
0325     set_.swap(RHS.set_);
0326     vector_.swap(RHS.vector_);
0327   }
0328
0329 private:
0330   /// A wrapper predicate designed for use with std::remove_if.
0331   ///
0332   /// This predicate wraps a predicate suitable for use with std::remove_if to
0333   /// call set_.erase(x) on each element which is slated for removal.
0334   template <typename UnaryPredicate>
0335   class TestAndEraseFromSet {
0336     UnaryPredicate P;
0337     set_type &set_;
0338
0339   public:
0340     TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
0341         : P(std::move(P)), set_(set_) {}
0342
0343     template <typename ArgumentT>
0344     bool operator()(const ArgumentT &Arg) {
0345       if (P(Arg)) {
0346         set_.erase(Arg);
0347         return true;
0348       }
0349       return false;
0350     }
0351   };
0352
0353   [[nodiscard]] static constexpr bool canBeSmall() { return N != 0; }
0354
0355   [[nodiscard]] bool isSmall() const { return set_.empty(); }
0356
0357   void makeBig() {
0358     if constexpr (canBeSmall())
0359       for (const auto &entry : vector_)
0360         set_.insert(entry);
0361   }
0362
0363   set_type set_;         ///< The set.
0364   vector_type vector_;   ///< The vector.
0365 };
0366
0367 /// A SetVector that performs no allocations if smaller than
0368 /// a certain size.
0369 template <typename T, unsigned N>
0370 class SmallSetVector : public SetVector<T, SmallVector<T, N>, DenseSet<T>, N> {
0371 public:
0372   SmallSetVector() = default;
0373
0374   /// Initialize a SmallSetVector with a range of elements
0375   template<typename It>
0376   SmallSetVector(It Start, It End) {
0377     this->insert(Start, End);
0378   }
0379 };
0380
0381 } // end namespace llvm
0382
0383 namespace std {
0384
0385 /// Implement std::swap in terms of SetVector swap.
0386 template <typename T, typename V, typename S, unsigned N>
0387 inline void swap(llvm::SetVector<T, V, S, N> &LHS,
0388                  llvm::SetVector<T, V, S, N> &RHS) {
0389   LHS.swap(RHS);
0390 }
0391
0392 /// Implement std::swap in terms of SmallSetVector swap.
0393 template<typename T, unsigned N>
0394 inline void
0395 swap(llvm::SmallSetVector<T, N> &LHS, llvm::SmallSetVector<T, N> &RHS) {
0396   LHS.swap(RHS);
0397 }
0398
0399 } // end namespace std
0400
0401 #endif // LLVM_ADT_SETVECTOR_H