X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSetVector.h;h=d2f7286c2596d66496ebc0018fc7e8865b9d61d8;hb=e19f11215d8fa29635b28317dd1cfd1915d048d4;hp=1b250ad670b8103f2cc7fb24531621e3faca1d5f;hpb=5e8775425063e7067dde18e893977bb9cef0558e;p=oota-llvm.git diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h index 1b250ad670b..d2f7286c259 100644 --- a/include/llvm/ADT/SetVector.h +++ b/include/llvm/ADT/SetVector.h @@ -1,123 +1,231 @@ -//===- 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 "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. -/// @breif 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 ) { + SetVector(It Start, It End) { insert(Start, End); } - /// @brief Completely clear the SetVector - void clear() { - set_.clear(); - vector_.clear(); - } - - /// @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 Index into 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. const_reference operator[](size_type n) const { - return vector_[n]; + 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. - bool insert( const value_type& X ) { - bool result = set_.insert(X).second; - if ( result ) { + /// \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); + 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 ) { + 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. - size_type count( const key_type& key ) const { + /// \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 + void clear() { + set_.clear(); + vector_.clear(); + } + + /// \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 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: + typedef typename UnaryPredicate::argument_type argument_type; + + TestAndEraseFromSet(UnaryPredicate P, set_type &set_) : P(P), set_(set_) {} + + bool operator()(argument_type 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