1551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 34bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer// The LLVM Compiler Infrastructure 44bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 84bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer//===----------------------------------------------------------------------===// 94bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer// 109769ab22265b313171d201b5928688524a01bd87Misha Brukman// This file implements a set that has insertion order iteration 114bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer// characteristics. This is useful for keeping a set of things that need to be 124bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer// visited later but in a deterministic order (insertion order). The interface 134bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer// is purposefully minimal. 144bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer// 15337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner// This file defines SetVector and SmallSetVector, which performs no allocations 16337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner// if the SetVector has less than a certain number of elements. 17337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner// 184bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer//===----------------------------------------------------------------------===// 194bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 20551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#ifndef LLVM_ADT_SETVECTOR_H 21551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#define LLVM_ADT_SETVECTOR_H 224bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 23f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/ADT/DenseSet.h" 24337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner#include "llvm/ADT/SmallSet.h" 250bdc620c16963908d74db498f79676e558f09e82Reid Spencer#include <algorithm> 26a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman#include <cassert> 27de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include <utility> 28a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman#include <vector> 294bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 304bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencernamespace llvm { 314bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 325d37976090df34f003e5128e39593b763be0ca71Chandler Carruth/// \brief A vector that has set insertion semantics. 335d37976090df34f003e5128e39593b763be0ca71Chandler Carruth/// 34337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner/// This adapter class provides a way to keep a set of things that also has the 354bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer/// property of a deterministic iteration order. The order of iteration is the 364bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer/// order of insertion. 37337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattnertemplate <typename T, typename Vector = std::vector<T>, 38f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typename Set = DenseSet<T>> 394bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencerclass SetVector { 404bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencerpublic: 414bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer typedef T value_type; 424bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer typedef T key_type; 434bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer typedef T& reference; 444bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer typedef const T& const_reference; 45337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner typedef Set set_type; 46337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner typedef Vector vector_type; 47cf48cab945f1cbdf637d7d970398cbe6d89135eeReid Spencer typedef typename vector_type::const_iterator iterator; 484bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer typedef typename vector_type::const_iterator const_iterator; 49f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef typename vector_type::const_reverse_iterator reverse_iterator; 50f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef typename vector_type::const_reverse_iterator const_reverse_iterator; 514bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer typedef typename vector_type::size_type size_type; 524bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 535d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Construct an empty SetVector 545e8775425063e7067dde18e893977bb9cef0558eChris Lattner SetVector() {} 555e8775425063e7067dde18e893977bb9cef0558eChris Lattner 565d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Initialize a SetVector with a range of elements 575e8775425063e7067dde18e893977bb9cef0558eChris Lattner template<typename It> 58f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner SetVector(It Start, It End) { 595e8775425063e7067dde18e893977bb9cef0558eChris Lattner insert(Start, End); 605e8775425063e7067dde18e893977bb9cef0558eChris Lattner } 615e8775425063e7067dde18e893977bb9cef0558eChris Lattner 62f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ArrayRef<T> getArrayRef() const { return vector_; } 63f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 645d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Determine if the SetVector is empty or not. 654bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer bool empty() const { 664bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer return vector_.empty(); 674bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer } 684bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 695d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Determine the number of elements in the SetVector. 704bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer size_type size() const { 714bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer return vector_.size(); 724bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer } 734bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 745d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Get an iterator to the beginning of the SetVector. 754bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer iterator begin() { 764bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer return vector_.begin(); 774bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer } 784bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 795d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Get a const_iterator to the beginning of the SetVector. 804bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer const_iterator begin() const { 814bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer return vector_.begin(); 824bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer } 834bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 845d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Get an iterator to the end of the SetVector. 854bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer iterator end() { 864bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer return vector_.end(); 874bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer } 884bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 895d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Get a const_iterator to the end of the SetVector. 904bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer const_iterator end() const { 914bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer return vector_.end(); 924bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer } 934bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 94f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// \brief Get an reverse_iterator to the end of the SetVector. 95f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar reverse_iterator rbegin() { 96f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return vector_.rbegin(); 97f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 98f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 99f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// \brief Get a const_reverse_iterator to the end of the SetVector. 100f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const_reverse_iterator rbegin() const { 101f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return vector_.rbegin(); 102f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 103f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 104f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// \brief Get a reverse_iterator to the beginning of the SetVector. 105f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar reverse_iterator rend() { 106f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return vector_.rend(); 107f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 108f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 109f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// \brief Get a const_reverse_iterator to the beginning of the SetVector. 110f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const_reverse_iterator rend() const { 111f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return vector_.rend(); 112f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 113f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1145d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Return the last element of the SetVector. 115f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner const T &back() const { 116f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner assert(!empty() && "Cannot call back() on empty SetVector!"); 117f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner return vector_.back(); 118f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner } 119f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner 1205d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Index into the SetVector. 1214bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer const_reference operator[](size_type n) const { 122f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner assert(n < vector_.size() && "SetVector access out of range!"); 123f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner return vector_[n]; 1244bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer } 1254bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 1265d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Insert a new element into the SetVector. 127de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \returns true if the element was inserted into the SetVector. 128f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner bool insert(const value_type &X) { 12937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool result = set_.insert(X).second; 130f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner if (result) 1314bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer vector_.push_back(X); 132800473c8df8f0c9b566c9216bf124495451cb573Reid Spencer return result; 1334bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer } 1344bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 1355d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Insert a range of elements into the SetVector. 1365e8775425063e7067dde18e893977bb9cef0558eChris Lattner template<typename It> 137f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner void insert(It Start, It End) { 1385e8775425063e7067dde18e893977bb9cef0558eChris Lattner for (; Start != End; ++Start) 13937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (set_.insert(*Start).second) 1405e8775425063e7067dde18e893977bb9cef0558eChris Lattner vector_.push_back(*Start); 1415e8775425063e7067dde18e893977bb9cef0558eChris Lattner } 1425e8775425063e7067dde18e893977bb9cef0558eChris Lattner 1435d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Remove an item from the set vector. 144df046f078e95417f0ece761c92b8cc549f7ab105Dan Gohman bool remove(const value_type& X) { 1455fcaf3ed141a3f0246e41f45077dbb7d7d0b11d3Chris Lattner if (set_.erase(X)) { 146cf48cab945f1cbdf637d7d970398cbe6d89135eeReid Spencer typename vector_type::iterator I = 147cf48cab945f1cbdf637d7d970398cbe6d89135eeReid Spencer std::find(vector_.begin(), vector_.end(), X); 14870e2d38361b675ed8c3d874d091636c470795550Reid Spencer assert(I != vector_.end() && "Corrupted SetVector instances!"); 14970e2d38361b675ed8c3d874d091636c470795550Reid Spencer vector_.erase(I); 150df046f078e95417f0ece761c92b8cc549f7ab105Dan Gohman return true; 1510bdc620c16963908d74db498f79676e558f09e82Reid Spencer } 152df046f078e95417f0ece761c92b8cc549f7ab105Dan Gohman return false; 1530bdc620c16963908d74db498f79676e558f09e82Reid Spencer } 1540bdc620c16963908d74db498f79676e558f09e82Reid Spencer 155de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Erase a single element from the set vector. 156de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \returns an iterator pointing to the next element that followed the 157de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// element erased. This is the end of the SetVector if the last element is 158de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// erased. 159de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar iterator erase(iterator I) { 160de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const key_type &V = *I; 161de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(set_.count(V) && "Corrupted SetVector instances!"); 162de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar set_.erase(V); 163de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 164de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // FIXME: No need to use the non-const iterator when built with 165de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // std:vector.erase(const_iterator) as defined in C++11. This is for 166de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9). 167de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto NI = vector_.begin(); 168de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::advance(NI, std::distance<iterator>(NI, I)); 169de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 170de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return vector_.erase(NI); 171de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 172de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 1735c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// \brief Remove items from the set vector based on a predicate function. 1745c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// 1755c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// This is intended to be equivalent to the following code, if we could 1765c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// write it: 1775c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// 1785c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// \code 1795c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// V.erase(std::remove_if(V.begin(), V.end(), P), V.end()); 1805c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// \endcode 1815c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// 1825c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// However, SetVector doesn't expose non-const iterators, making any 1835c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// algorithm like remove_if impossible to use. 1845c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// 1855c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth /// \returns true if any element is removed. 1865c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth template <typename UnaryPredicate> 1875c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth bool remove_if(UnaryPredicate P) { 188de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth typename vector_type::iterator I 189de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth = std::remove_if(vector_.begin(), vector_.end(), 190de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth TestAndEraseFromSet<UnaryPredicate>(P, set_)); 191de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth if (I == vector_.end()) 1925c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth return false; 193de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth vector_.erase(I, vector_.end()); 1945c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth return true; 1955c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth } 1965c5b3cf5b8af06b8e9347f3f45e8c67438ffd446Chandler Carruth 1975d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Count the number of elements of a given key in the SetVector. 1985d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \returns 0 if the element is not in the SetVector, 1 if it is. 199f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner size_type count(const key_type &key) const { 2004bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer return set_.count(key); 2014bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer } 2024bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 2035d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Completely clear the SetVector 204f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner void clear() { 205f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner set_.clear(); 206f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner vector_.clear(); 207f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner } 208f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner 2095d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Remove the last element of the SetVector. 210f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner void pop_back() { 211f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner assert(!empty() && "Cannot remove an element from an empty SetVector!"); 212f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner set_.erase(back()); 213f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner vector_.pop_back(); 214f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner } 215f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 216b937c55e93e9d52fa618b3488da04ff73182f3f9Jakub Staszak T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() { 217f5c9bd07bca0a14afc37b7c28409736e001de96dChris Lattner T Ret = back(); 218f5c9bd07bca0a14afc37b7c28409736e001de96dChris Lattner pop_back(); 219f5c9bd07bca0a14afc37b7c28409736e001de96dChris Lattner return Ret; 220f5c9bd07bca0a14afc37b7c28409736e001de96dChris Lattner } 221f90fcaf5729f2987c9f4e91ca4e6ee4397ba0a8dChris Lattner 222f2aac4db4ec4eb0f8b070a4f525801798157dfcfDan Gohman bool operator==(const SetVector &that) const { 223f2aac4db4ec4eb0f8b070a4f525801798157dfcfDan Gohman return vector_ == that.vector_; 224f2aac4db4ec4eb0f8b070a4f525801798157dfcfDan Gohman } 225f2aac4db4ec4eb0f8b070a4f525801798157dfcfDan Gohman 226f2aac4db4ec4eb0f8b070a4f525801798157dfcfDan Gohman bool operator!=(const SetVector &that) const { 227f2aac4db4ec4eb0f8b070a4f525801798157dfcfDan Gohman return vector_ != that.vector_; 228f2aac4db4ec4eb0f8b070a4f525801798157dfcfDan Gohman } 229de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 230de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief Compute This := This u S, return whether 'This' changed. 231de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// TODO: We should be able to use set_union from SetOperations.h, but 232de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// SetVector interface is inconsistent with DenseSet. 233de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar template <class STy> 234de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool set_union(const STy &S) { 235de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Changed = false; 236de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 237de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 238de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++SI) 239de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (insert(*SI)) 240de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Changed = true; 241de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 242de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Changed; 243de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 244de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 245de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief Compute This := This - B 246de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// TODO: We should be able to use set_subtract from SetOperations.h, but 247de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// SetVector interface is inconsistent with DenseSet. 248de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar template <class STy> 249de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void set_subtract(const STy &S) { 250de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 251de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++SI) 252de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar remove(*SI); 253de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 254f2aac4db4ec4eb0f8b070a4f525801798157dfcfDan Gohman 2554bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencerprivate: 256de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth /// \brief A wrapper predicate designed for use with std::remove_if. 257de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth /// 258de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth /// This predicate wraps a predicate suitable for use with std::remove_if to 259de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth /// call set_.erase(x) on each element which is slated for removal. 260de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth template <typename UnaryPredicate> 261de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth class TestAndEraseFromSet { 262de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth UnaryPredicate P; 263de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth set_type &set_; 264de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth 265de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth public: 266de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TestAndEraseFromSet(UnaryPredicate P, set_type &set_) 267de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : P(std::move(P)), set_(set_) {} 268de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines template <typename ArgumentT> 27036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool operator()(const ArgumentT &Arg) { 271de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth if (P(Arg)) { 272de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth set_.erase(Arg); 273de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth return true; 274de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth } 275de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth return false; 276de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth } 277de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth }; 278de2fae4c7bfaedb95705b272015592895e05fd9cChandler Carruth 2794bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer set_type set_; ///< The set. 2804bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer vector_type vector_; ///< The vector. 2814bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer}; 2824bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 2835d37976090df34f003e5128e39593b763be0ca71Chandler Carruth/// \brief A SetVector that performs no allocations if smaller than 284337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner/// a certain size. 285337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattnertemplate <typename T, unsigned N> 286337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattnerclass SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > { 2875fcaf3ed141a3f0246e41f45077dbb7d7d0b11d3Chris Lattnerpublic: 288337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner SmallSetVector() {} 2893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2905d37976090df34f003e5128e39593b763be0ca71Chandler Carruth /// \brief Initialize a SmallSetVector with a range of elements 291337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner template<typename It> 292337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner SmallSetVector(It Start, It End) { 293337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner this->insert(Start, End); 294337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner } 295337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner}; 296337cde0d5ac8c28793b305d17c1ccfb5228eab11Chris Lattner 2974bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer} // End llvm namespace 2984bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer 2994bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer// vim: sw=2 ai 3004bb2867bc1faa2eedafc39b37bbf481ff4dcb725Reid Spencer#endif 301