X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSetVector.h;h=1e7d237045aacb6f39621c024aa82931a89d4fae;hp=c72f49bce89ecc882e3b6163706d470fda46cb73;hb=63b14baf799b4c3ba8182596073ad5b3f37cd1cc;hpb=3638e9918c632ab517066d79790601d25de568c9 diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h index c72f49bce89..1e7d237045a 100644 --- a/include/llvm/ADT/SetVector.h +++ b/include/llvm/ADT/SetVector.h @@ -1,137 +1,230 @@ -//===- SetVector.h - A set with insertion order iteration -------*- C++ -*-===// -// +//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===// +// // The LLVM Compiler Infrastructure // -// This file was developed by Reid Spencer and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// //===----------------------------------------------------------------------===// // -// This file implements a set that has insertion order iteration +// This file implements a set that has insertion order iteration // characteristics. This is useful for keeping a set of things that need to be // visited later but in a deterministic order (insertion order). The interface // is purposefully minimal. // +// This file defines SetVector and SmallSetVector, which performs no allocations +// if the SetVector has less than a certain number of elements. +// //===----------------------------------------------------------------------===// -#ifndef SUPPORT_SETVECTOR_H -#define SUPPORT_SETVECTOR_H +#ifndef LLVM_ADT_SETVECTOR_H +#define LLVM_ADT_SETVECTOR_H -#include -#include +#include "llvm/ADT/SmallSet.h" +#include #include +#include namespace llvm { -/// This class provides a way to keep a set of things that also has the +/// \brief A vector that has set insertion semantics. +/// +/// This adapter class provides a way to keep a set of things that also has the /// property of a deterministic iteration order. The order of iteration is the /// order of insertion. -/// @brief A vector that has set insertion semantics. -template +template , + typename Set = SmallSet > class SetVector { public: typedef T value_type; typedef T key_type; typedef T& reference; typedef const T& const_reference; - typedef std::set set_type; - typedef std::vector vector_type; - typedef typename vector_type::iterator iterator; + typedef Set set_type; + typedef Vector vector_type; + typedef typename vector_type::const_iterator iterator; typedef typename vector_type::const_iterator const_iterator; typedef typename vector_type::size_type size_type; - /// @brief Construct an empty SetVector + /// \brief Construct an empty SetVector SetVector() {} - /// @brief Initialize a SetVector with a range of elements + /// \brief Initialize a SetVector with a range of elements template SetVector(It Start, It End) { insert(Start, End); } - /// @brief Determine if the SetVector is empty or not. + /// \brief Determine if the SetVector is empty or not. bool empty() const { return vector_.empty(); } - /// @brief Determine the number of elements in the SetVector. + /// \brief Determine the number of elements in the SetVector. size_type size() const { return vector_.size(); } - /// @brief Get an iterator to the beginning of the SetVector. + /// \brief Get an iterator to the beginning of the SetVector. iterator begin() { return vector_.begin(); } - /// @brief Get a const_iterator to the beginning of the SetVector. + /// \brief Get a const_iterator to the beginning of the SetVector. const_iterator begin() const { return vector_.begin(); } - /// @brief Get an iterator to the end of the SetVector. + /// \brief Get an iterator to the end of the SetVector. iterator end() { return vector_.end(); } - /// @brief Get a const_iterator to the end of the SetVector. + /// \brief Get a const_iterator to the end of the SetVector. const_iterator end() const { return vector_.end(); } - /// @brief Return the last element of the SetVector. + /// \brief Return the last element of the SetVector. const T &back() const { assert(!empty() && "Cannot call back() on empty SetVector!"); return vector_.back(); } - /// @brief Index into the SetVector. + /// \brief Index into the SetVector. const_reference operator[](size_type n) const { assert(n < vector_.size() && "SetVector access out of range!"); return vector_[n]; } - /// @returns true iff the element was inserted into the SetVector. - /// @brief Insert a new element into the SetVector. + /// \brief Insert a new element into the SetVector. + /// \returns true iff the element was inserted into the SetVector. bool insert(const value_type &X) { - bool result = set_.insert(X).second; + bool result = set_.insert(X); if (result) vector_.push_back(X); return result; } - /// @brief Insert a range of elements into the SetVector. + /// \brief Insert a range of elements into the SetVector. template void insert(It Start, It End) { for (; Start != End; ++Start) - if (set_.insert(*Start).second) + if (set_.insert(*Start)) vector_.push_back(*Start); } - /// @returns 0 if the element is not in the SetVector, 1 if it is. - /// @brief Count the number of elements of a given key in the SetVector. + /// \brief Remove an item from the set vector. + bool remove(const value_type& X) { + if (set_.erase(X)) { + typename vector_type::iterator I = + std::find(vector_.begin(), vector_.end(), X); + assert(I != vector_.end() && "Corrupted SetVector instances!"); + vector_.erase(I); + return true; + } + return false; + } + + /// \brief Remove items from the set vector based on a predicate function. + /// + /// This is intended to be equivalent to the following code, if we could + /// write it: + /// + /// \code + /// V.erase(std::remove_if(V.begin(), V.end(), P), V.end()); + /// \endcode + /// + /// However, SetVector doesn't expose non-const iterators, making any + /// algorithm like remove_if impossible to use. + /// + /// \returns true if any element is removed. + template + bool remove_if(UnaryPredicate P) { + typename vector_type::iterator I + = std::remove_if(vector_.begin(), vector_.end(), + TestAndEraseFromSet(P, set_)); + if (I == vector_.end()) + return false; + vector_.erase(I, vector_.end()); + return true; + } + + + /// \brief Count the number of elements of a given key in the SetVector. + /// \returns 0 if the element is not in the SetVector, 1 if it is. size_type count(const key_type &key) const { return set_.count(key); } - /// @brief Completely clear the SetVector + /// \brief Completely clear the SetVector void clear() { set_.clear(); vector_.clear(); } - /// @brief Remove the last element of the SetVector. + /// \brief Remove the last element of the SetVector. void pop_back() { assert(!empty() && "Cannot remove an element from an empty SetVector!"); set_.erase(back()); vector_.pop_back(); } + + T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() { + T Ret = back(); + pop_back(); + return Ret; + } + + bool operator==(const SetVector &that) const { + return vector_ == that.vector_; + } + + bool operator!=(const SetVector &that) const { + return vector_ != that.vector_; + } private: + /// \brief A wrapper predicate designed for use with std::remove_if. + /// + /// This predicate wraps a predicate suitable for use with std::remove_if to + /// call set_.erase(x) on each element which is slated for removal. + template + class TestAndEraseFromSet { + UnaryPredicate P; + set_type &set_; + + public: + TestAndEraseFromSet(UnaryPredicate P, set_type &set_) : P(P), set_(set_) {} + + template + bool operator()(const ArgumentT &Arg) { + if (P(Arg)) { + set_.erase(Arg); + return true; + } + return false; + } + }; + set_type set_; ///< The set. vector_type vector_; ///< The vector. }; +/// \brief A SetVector that performs no allocations if smaller than +/// a certain size. +template +class SmallSetVector : public SetVector, SmallSet > { +public: + SmallSetVector() {} + + /// \brief Initialize a SmallSetVector with a range of elements + template + SmallSetVector(It Start, It End) { + this->insert(Start, End); + } +}; + } // End llvm namespace // vim: sw=2 ai