1193323Sed//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file implements a set that has insertion order iteration 10193323Sed// characteristics. This is useful for keeping a set of things that need to be 11193323Sed// visited later but in a deterministic order (insertion order). The interface 12193323Sed// is purposefully minimal. 13193323Sed// 14193323Sed// This file defines SetVector and SmallSetVector, which performs no allocations 15193323Sed// if the SetVector has less than a certain number of elements. 16193323Sed// 17193323Sed//===----------------------------------------------------------------------===// 18193323Sed 19193323Sed#ifndef LLVM_ADT_SETVECTOR_H 20193323Sed#define LLVM_ADT_SETVECTOR_H 21193323Sed 22314564Sdim#include "llvm/ADT/ArrayRef.h" 23296417Sdim#include "llvm/ADT/DenseSet.h" 24314564Sdim#include "llvm/ADT/STLExtras.h" 25314564Sdim#include "llvm/Support/Compiler.h" 26193323Sed#include <algorithm> 27193323Sed#include <cassert> 28314564Sdim#include <iterator> 29193323Sed#include <vector> 30193323Sed 31193323Sednamespace llvm { 32193323Sed 33341825Sdim/// A vector that has set insertion semantics. 34243830Sdim/// 35193323Sed/// This adapter class provides a way to keep a set of things that also has the 36193323Sed/// property of a deterministic iteration order. The order of iteration is the 37193323Sed/// order of insertion. 38193323Sedtemplate <typename T, typename Vector = std::vector<T>, 39296417Sdim typename Set = DenseSet<T>> 40193323Sedclass SetVector { 41193323Sedpublic: 42321369Sdim using value_type = T; 43321369Sdim using key_type = T; 44321369Sdim using reference = T&; 45321369Sdim using const_reference = const T&; 46321369Sdim using set_type = Set; 47321369Sdim using vector_type = Vector; 48321369Sdim using iterator = typename vector_type::const_iterator; 49321369Sdim using const_iterator = typename vector_type::const_iterator; 50321369Sdim using reverse_iterator = typename vector_type::const_reverse_iterator; 51321369Sdim using const_reverse_iterator = typename vector_type::const_reverse_iterator; 52321369Sdim using size_type = typename vector_type::size_type; 53193323Sed 54341825Sdim /// Construct an empty SetVector 55314564Sdim SetVector() = default; 56193323Sed 57341825Sdim /// Initialize a SetVector with a range of elements 58193323Sed template<typename It> 59193323Sed SetVector(It Start, It End) { 60193323Sed insert(Start, End); 61193323Sed } 62193323Sed 63296417Sdim ArrayRef<T> getArrayRef() const { return vector_; } 64296417Sdim 65314564Sdim /// Clear the SetVector and return the underlying vector. 66314564Sdim Vector takeVector() { 67314564Sdim set_.clear(); 68314564Sdim return std::move(vector_); 69314564Sdim } 70314564Sdim 71341825Sdim /// Determine if the SetVector is empty or not. 72193323Sed bool empty() const { 73193323Sed return vector_.empty(); 74193323Sed } 75193323Sed 76341825Sdim /// Determine the number of elements in the SetVector. 77193323Sed size_type size() const { 78193323Sed return vector_.size(); 79193323Sed } 80193323Sed 81341825Sdim /// Get an iterator to the beginning of the SetVector. 82193323Sed iterator begin() { 83193323Sed return vector_.begin(); 84193323Sed } 85193323Sed 86341825Sdim /// Get a const_iterator to the beginning of the SetVector. 87193323Sed const_iterator begin() const { 88193323Sed return vector_.begin(); 89193323Sed } 90193323Sed 91341825Sdim /// Get an iterator to the end of the SetVector. 92193323Sed iterator end() { 93193323Sed return vector_.end(); 94193323Sed } 95193323Sed 96341825Sdim /// Get a const_iterator to the end of the SetVector. 97193323Sed const_iterator end() const { 98193323Sed return vector_.end(); 99193323Sed } 100193323Sed 101341825Sdim /// Get an reverse_iterator to the end of the SetVector. 102296417Sdim reverse_iterator rbegin() { 103296417Sdim return vector_.rbegin(); 104296417Sdim } 105296417Sdim 106341825Sdim /// Get a const_reverse_iterator to the end of the SetVector. 107296417Sdim const_reverse_iterator rbegin() const { 108296417Sdim return vector_.rbegin(); 109296417Sdim } 110296417Sdim 111341825Sdim /// Get a reverse_iterator to the beginning of the SetVector. 112296417Sdim reverse_iterator rend() { 113296417Sdim return vector_.rend(); 114296417Sdim } 115296417Sdim 116341825Sdim /// Get a const_reverse_iterator to the beginning of the SetVector. 117296417Sdim const_reverse_iterator rend() const { 118296417Sdim return vector_.rend(); 119296417Sdim } 120296417Sdim 121341825Sdim /// Return the first element of the SetVector. 122321369Sdim const T &front() const { 123321369Sdim assert(!empty() && "Cannot call front() on empty SetVector!"); 124321369Sdim return vector_.front(); 125321369Sdim } 126321369Sdim 127341825Sdim /// Return the last element of the SetVector. 128193323Sed const T &back() const { 129193323Sed assert(!empty() && "Cannot call back() on empty SetVector!"); 130193323Sed return vector_.back(); 131193323Sed } 132193323Sed 133341825Sdim /// Index into the SetVector. 134193323Sed const_reference operator[](size_type n) const { 135193323Sed assert(n < vector_.size() && "SetVector access out of range!"); 136193323Sed return vector_[n]; 137193323Sed } 138193323Sed 139341825Sdim /// Insert a new element into the SetVector. 140309124Sdim /// \returns true if the element was inserted into the SetVector. 141193323Sed bool insert(const value_type &X) { 142280031Sdim bool result = set_.insert(X).second; 143193323Sed if (result) 144193323Sed vector_.push_back(X); 145193323Sed return result; 146193323Sed } 147193323Sed 148341825Sdim /// Insert a range of elements into the SetVector. 149193323Sed template<typename It> 150193323Sed void insert(It Start, It End) { 151193323Sed for (; Start != End; ++Start) 152280031Sdim if (set_.insert(*Start).second) 153193323Sed vector_.push_back(*Start); 154193323Sed } 155193323Sed 156341825Sdim /// Remove an item from the set vector. 157218893Sdim bool remove(const value_type& X) { 158193323Sed if (set_.erase(X)) { 159314564Sdim typename vector_type::iterator I = find(vector_, X); 160193323Sed assert(I != vector_.end() && "Corrupted SetVector instances!"); 161193323Sed vector_.erase(I); 162218893Sdim return true; 163193323Sed } 164218893Sdim return false; 165193323Sed } 166193323Sed 167309124Sdim /// Erase a single element from the set vector. 168309124Sdim /// \returns an iterator pointing to the next element that followed the 169309124Sdim /// element erased. This is the end of the SetVector if the last element is 170309124Sdim /// erased. 171309124Sdim iterator erase(iterator I) { 172309124Sdim const key_type &V = *I; 173309124Sdim assert(set_.count(V) && "Corrupted SetVector instances!"); 174309124Sdim set_.erase(V); 175309124Sdim 176309124Sdim // FIXME: No need to use the non-const iterator when built with 177309124Sdim // std:vector.erase(const_iterator) as defined in C++11. This is for 178309124Sdim // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9). 179309124Sdim auto NI = vector_.begin(); 180309124Sdim std::advance(NI, std::distance<iterator>(NI, I)); 181309124Sdim 182309124Sdim return vector_.erase(NI); 183309124Sdim } 184309124Sdim 185341825Sdim /// Remove items from the set vector based on a predicate function. 186243830Sdim /// 187243830Sdim /// This is intended to be equivalent to the following code, if we could 188243830Sdim /// write it: 189243830Sdim /// 190243830Sdim /// \code 191314564Sdim /// V.erase(remove_if(V, P), V.end()); 192243830Sdim /// \endcode 193243830Sdim /// 194243830Sdim /// However, SetVector doesn't expose non-const iterators, making any 195243830Sdim /// algorithm like remove_if impossible to use. 196243830Sdim /// 197243830Sdim /// \returns true if any element is removed. 198243830Sdim template <typename UnaryPredicate> 199243830Sdim bool remove_if(UnaryPredicate P) { 200314564Sdim typename vector_type::iterator I = 201314564Sdim llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_)); 202243830Sdim if (I == vector_.end()) 203243830Sdim return false; 204243830Sdim vector_.erase(I, vector_.end()); 205243830Sdim return true; 206243830Sdim } 207193323Sed 208341825Sdim /// Count the number of elements of a given key in the SetVector. 209243830Sdim /// \returns 0 if the element is not in the SetVector, 1 if it is. 210193323Sed size_type count(const key_type &key) const { 211193323Sed return set_.count(key); 212193323Sed } 213193323Sed 214341825Sdim /// Completely clear the SetVector 215193323Sed void clear() { 216193323Sed set_.clear(); 217193323Sed vector_.clear(); 218193323Sed } 219193323Sed 220341825Sdim /// Remove the last element of the SetVector. 221193323Sed void pop_back() { 222193323Sed assert(!empty() && "Cannot remove an element from an empty SetVector!"); 223193323Sed set_.erase(back()); 224193323Sed vector_.pop_back(); 225193323Sed } 226296417Sdim 227314564Sdim LLVM_NODISCARD T pop_back_val() { 228234353Sdim T Ret = back(); 229234353Sdim pop_back(); 230234353Sdim return Ret; 231234353Sdim } 232193323Sed 233210299Sed bool operator==(const SetVector &that) const { 234210299Sed return vector_ == that.vector_; 235210299Sed } 236210299Sed 237210299Sed bool operator!=(const SetVector &that) const { 238210299Sed return vector_ != that.vector_; 239210299Sed } 240321369Sdim 241341825Sdim /// Compute This := This u S, return whether 'This' changed. 242309124Sdim /// TODO: We should be able to use set_union from SetOperations.h, but 243309124Sdim /// SetVector interface is inconsistent with DenseSet. 244309124Sdim template <class STy> 245309124Sdim bool set_union(const STy &S) { 246309124Sdim bool Changed = false; 247210299Sed 248309124Sdim for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 249309124Sdim ++SI) 250309124Sdim if (insert(*SI)) 251309124Sdim Changed = true; 252309124Sdim 253309124Sdim return Changed; 254309124Sdim } 255309124Sdim 256341825Sdim /// Compute This := This - B 257309124Sdim /// TODO: We should be able to use set_subtract from SetOperations.h, but 258309124Sdim /// SetVector interface is inconsistent with DenseSet. 259309124Sdim template <class STy> 260309124Sdim void set_subtract(const STy &S) { 261309124Sdim for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 262309124Sdim ++SI) 263309124Sdim remove(*SI); 264309124Sdim } 265309124Sdim 266193323Sedprivate: 267341825Sdim /// A wrapper predicate designed for use with std::remove_if. 268243830Sdim /// 269243830Sdim /// This predicate wraps a predicate suitable for use with std::remove_if to 270243830Sdim /// call set_.erase(x) on each element which is slated for removal. 271243830Sdim template <typename UnaryPredicate> 272243830Sdim class TestAndEraseFromSet { 273243830Sdim UnaryPredicate P; 274243830Sdim set_type &set_; 275243830Sdim 276243830Sdim public: 277309124Sdim TestAndEraseFromSet(UnaryPredicate P, set_type &set_) 278309124Sdim : P(std::move(P)), set_(set_) {} 279243830Sdim 280276479Sdim template <typename ArgumentT> 281276479Sdim bool operator()(const ArgumentT &Arg) { 282243830Sdim if (P(Arg)) { 283243830Sdim set_.erase(Arg); 284243830Sdim return true; 285243830Sdim } 286243830Sdim return false; 287243830Sdim } 288243830Sdim }; 289243830Sdim 290193323Sed set_type set_; ///< The set. 291193323Sed vector_type vector_; ///< The vector. 292193323Sed}; 293193323Sed 294341825Sdim/// A SetVector that performs no allocations if smaller than 295193323Sed/// a certain size. 296193323Sedtemplate <typename T, unsigned N> 297314564Sdimclass SmallSetVector 298314564Sdim : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> { 299193323Sedpublic: 300314564Sdim SmallSetVector() = default; 301193323Sed 302341825Sdim /// Initialize a SmallSetVector with a range of elements 303193323Sed template<typename It> 304193323Sed SmallSetVector(It Start, It End) { 305193323Sed this->insert(Start, End); 306193323Sed } 307193323Sed}; 308193323Sed 309314564Sdim} // end namespace llvm 310193323Sed 311314564Sdim#endif // LLVM_ADT_SETVECTOR_H 312