include/llvm/ADT/SetVector.h

   1 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- 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 implements a set that has insertion order iteration
  10 // characteristics. This is useful for keeping a set of things that need to be
  11 // visited later but in a deterministic order (insertion order). The interface
  12 // is purposefully minimal.
  13 //
  14 // This file defines SetVector and SmallSetVector, which performs no allocations
  15 // if the SetVector has less than a certain number of elements.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #ifndef LLVM_ADT_SETVECTOR_H
  20 #define LLVM_ADT_SETVECTOR_H
  21
  22 #include "llvm/ADT/ArrayRef.h"
  23 #include "llvm/ADT/DenseSet.h"
  24 #include "llvm/ADT/STLExtras.h"
  25 #include "llvm/Support/Compiler.h"
  26 #include <algorithm>
  27 #include <cassert>
  28 #include <iterator>
  29 #include <vector>
  30
  31 namespace llvm {
  32
  33 /// A vector that has set insertion semantics.
  34 ///
  35 /// This adapter class provides a way to keep a set of things that also has the
  36 /// property of a deterministic iteration order. The order of iteration is the
  37 /// order of insertion.
  38 template <typename T, typename Vector = std::vector<T>,
  39           typename Set = DenseSet<T>>
  40 class SetVector {
  41 public:
  42   using value_type = T;
  43   using key_type = T;
  44   using reference = T&;
  45   using const_reference = const T&;
  46   using set_type = Set;
  47   using vector_type = Vector;
  48   using iterator = typename vector_type::const_iterator;
  49   using const_iterator = typename vector_type::const_iterator;
  50   using reverse_iterator = typename vector_type::const_reverse_iterator;
  51   using const_reverse_iterator = typename vector_type::const_reverse_iterator;
  52   using size_type = typename vector_type::size_type;
  53
  54   /// Construct an empty SetVector
  55   SetVector() = default;
  56
  57   /// Initialize a SetVector with a range of elements
  58   template<typename It>
  59   SetVector(It Start, It End) {
  60     insert(Start, End);
  61   }
  62
  63   ArrayRef<T> getArrayRef() const { return vector_; }
  64
  65   /// Clear the SetVector and return the underlying vector.
  66   Vector takeVector() {
  67     set_.clear();
  68     return std::move(vector_);
  69   }
  70
  71   /// Determine if the SetVector is empty or not.
  72   bool empty() const {
  73     return vector_.empty();
  74   }
  75
  76   /// Determine the number of elements in the SetVector.
  77   size_type size() const {
  78     return vector_.size();
  79   }
  80
  81   /// Get an iterator to the beginning of the SetVector.
  82   iterator begin() {
  83     return vector_.begin();
  84   }
  85
  86   /// Get a const_iterator to the beginning of the SetVector.
  87   const_iterator begin() const {
  88     return vector_.begin();
  89   }
  90
  91   /// Get an iterator to the end of the SetVector.
  92   iterator end() {
  93     return vector_.end();
  94   }
  95
  96   /// Get a const_iterator to the end of the SetVector.
  97   const_iterator end() const {
  98     return vector_.end();
  99   }
 100
 101   /// Get an reverse_iterator to the end of the SetVector.
 102   reverse_iterator rbegin() {
 103     return vector_.rbegin();
 104   }
 105
 106   /// Get a const_reverse_iterator to the end of the SetVector.
 107   const_reverse_iterator rbegin() const {
 108     return vector_.rbegin();
 109   }
 110
 111   /// Get a reverse_iterator to the beginning of the SetVector.
 112   reverse_iterator rend() {
 113     return vector_.rend();
 114   }
 115
 116   /// Get a const_reverse_iterator to the beginning of the SetVector.
 117   const_reverse_iterator rend() const {
 118     return vector_.rend();
 119   }
 120
 121   /// Return the first element of the SetVector.
 122   const T &front() const {
 123     assert(!empty() && "Cannot call front() on empty SetVector!");
 124     return vector_.front();
 125   }
 126
 127   /// Return the last element of the SetVector.
 128   const T &back() const {
 129     assert(!empty() && "Cannot call back() on empty SetVector!");
 130     return vector_.back();
 131   }
 132
 133   /// Index into the SetVector.
 134   const_reference operator[](size_type n) const {
 135     assert(n < vector_.size() && "SetVector access out of range!");
 136     return vector_[n];
 137   }
 138
 139   /// Insert a new element into the SetVector.
 140   /// \returns true if the element was inserted into the SetVector.
 141   bool insert(const value_type &X) {
 142     bool result = set_.insert(X).second;
 143     if (result)
 144       vector_.push_back(X);
 145     return result;
 146   }
 147
 148   /// Insert a range of elements into the SetVector.
 149   template<typename It>
 150   void insert(It Start, It End) {
 151     for (; Start != End; ++Start)
 152       if (set_.insert(*Start).second)
 153         vector_.push_back(*Start);
 154   }
 155
 156   /// Remove an item from the set vector.
 157   bool remove(const value_type& X) {
 158     if (set_.erase(X)) {
 159       typename vector_type::iterator I = find(vector_, X);
 160       assert(I != vector_.end() && "Corrupted SetVector instances!");
 161       vector_.erase(I);
 162       return true;
 163     }
 164     return false;
 165   }
 166
 167   /// Erase a single element from the set vector.
 168   /// \returns an iterator pointing to the next element that followed the
 169   /// element erased. This is the end of the SetVector if the last element is
 170   /// erased.
 171   iterator erase(iterator I) {
 172     const key_type &V = *I;
 173     assert(set_.count(V) && "Corrupted SetVector instances!");
 174     set_.erase(V);
 175
 176     // FIXME: No need to use the non-const iterator when built with
 177     // std:vector.erase(const_iterator) as defined in C++11. This is for
 178     // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
 179     auto NI = vector_.begin();
 180     std::advance(NI, std::distance<iterator>(NI, I));
 181
 182     return vector_.erase(NI);
 183   }
 184
 185   /// Remove items from the set vector based on a predicate function.
 186   ///
 187   /// This is intended to be equivalent to the following code, if we could
 188   /// write it:
 189   ///
 190   /// \code
 191   ///   V.erase(remove_if(V, P), V.end());
 192   /// \endcode
 193   ///
 194   /// However, SetVector doesn't expose non-const iterators, making any
 195   /// algorithm like remove_if impossible to use.
 196   ///
 197   /// \returns true if any element is removed.
 198   template <typename UnaryPredicate>
 199   bool remove_if(UnaryPredicate P) {
 200     typename vector_type::iterator I =
 201         llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
 202     if (I == vector_.end())
 203       return false;
 204     vector_.erase(I, vector_.end());
 205     return true;
 206   }
 207
 208   /// Count the number of elements of a given key in the SetVector.
 209   /// \returns 0 if the element is not in the SetVector, 1 if it is.
 210   size_type count(const key_type &key) const {
 211     return set_.count(key);
 212   }
 213
 214   /// Completely clear the SetVector
 215   void clear() {
 216     set_.clear();
 217     vector_.clear();
 218   }
 219
 220   /// Remove the last element of the SetVector.
 221   void pop_back() {
 222     assert(!empty() && "Cannot remove an element from an empty SetVector!");
 223     set_.erase(back());
 224     vector_.pop_back();
 225   }
 226
 227   LLVM_NODISCARD T pop_back_val() {
 228     T Ret = back();
 229     pop_back();
 230     return Ret;
 231   }
 232
 233   bool operator==(const SetVector &that) const {
 234     return vector_ == that.vector_;
 235   }
 236
 237   bool operator!=(const SetVector &that) const {
 238     return vector_ != that.vector_;
 239   }
 240
 241   /// Compute This := This u S, return whether 'This' changed.
 242   /// TODO: We should be able to use set_union from SetOperations.h, but
 243   ///       SetVector interface is inconsistent with DenseSet.
 244   template <class STy>
 245   bool set_union(const STy &S) {
 246     bool Changed = false;
 247
 248     for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
 249          ++SI)
 250       if (insert(*SI))
 251         Changed = true;
 252
 253     return Changed;
 254   }
 255
 256   /// Compute This := This - B
 257   /// TODO: We should be able to use set_subtract from SetOperations.h, but
 258   ///       SetVector interface is inconsistent with DenseSet.
 259   template <class STy>
 260   void set_subtract(const STy &S) {
 261     for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
 262          ++SI)
 263       remove(*SI);
 264   }
 265
 266 private:
 267   /// A wrapper predicate designed for use with std::remove_if.
 268   ///
 269   /// This predicate wraps a predicate suitable for use with std::remove_if to
 270   /// call set_.erase(x) on each element which is slated for removal.
 271   template <typename UnaryPredicate>
 272   class TestAndEraseFromSet {
 273     UnaryPredicate P;
 274     set_type &set_;
 275
 276   public:
 277     TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
 278         : P(std::move(P)), set_(set_) {}
 279
 280     template <typename ArgumentT>
 281     bool operator()(const ArgumentT &Arg) {
 282       if (P(Arg)) {
 283         set_.erase(Arg);
 284         return true;
 285       }
 286       return false;
 287     }
 288   };
 289
 290   set_type set_;         ///< The set.
 291   vector_type vector_;   ///< The vector.
 292 };
 293
 294 /// A SetVector that performs no allocations if smaller than
 295 /// a certain size.
 296 template <typename T, unsigned N>
 297 class SmallSetVector
 298     : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
 299 public:
 300   SmallSetVector() = default;
 301
 302   /// Initialize a SmallSetVector with a range of elements
 303   template<typename It>
 304   SmallSetVector(It Start, It End) {
 305     this->insert(Start, End);
 306   }
 307 };
 308
 309 } // end namespace llvm
 310
 311 #endif // LLVM_ADT_SETVECTOR_H