X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSparseSet.h;h=55696333489408b08f621e30358592232f253101;hb=b4c28fc93f5149a0bd7967af44c429412e751c56;hp=9b276d55331ad0aecfee0d44ec48fab5df961a4f;hpb=81a682a4c004b0f44452ef824637a1b6face178f;p=oota-llvm.git diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h index 9b276d55331..55696333489 100644 --- a/include/llvm/ADT/SparseSet.h +++ b/include/llvm/ADT/SparseSet.h @@ -21,33 +21,62 @@ #define LLVM_ADT_SPARSESET_H #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Support/DataTypes.h" #include namespace llvm { -/// SparseSetFunctor - Objects in a SparseSet are identified by small integer -/// keys. A functor object is used to compute the key of an object. The -/// functor's operator() must return an unsigned smaller than the universe. +/// SparseSetValTraits - Objects in a SparseSet are identified by keys that can +/// be uniquely converted to a small integer less than the set's universe. This +/// class allows the set to hold values that differ from the set's key type as +/// long as an index can still be derived from the value. SparseSet never +/// directly compares ValueT, only their indices, so it can map keys to +/// arbitrary values. SparseSetValTraits computes the index from the value +/// object. To compute the index from a key, SparseSet uses a separate +/// KeyFunctorT template argument. /// -/// The default functor implementation forwards to a getSparseSetKey() method -/// on the object. It is intended for sparse sets holding ad-hoc structs. +/// A simple type declaration, SparseSet, handles these cases: +/// - unsigned key, identity index, identity value +/// - unsigned key, identity index, fat value providing getSparseSetIndex() +/// +/// The type declaration SparseSet handles: +/// - unsigned key, remapped index, identity value (virtual registers) +/// - pointer key, pointer-derived index, identity value (node+ID) +/// - pointer key, pointer-derived index, fat value with getSparseSetIndex() +/// +/// Only other, unexpected cases require specializing SparseSetValTraits. +/// +/// For best results, ValueT should not require a destructor. /// template -struct SparseSetFunctor { - unsigned operator()(const ValueT &Val) { - return Val.getSparseSetKey(); +struct SparseSetValTraits { + static unsigned getValIndex(const ValueT &Val) { + return Val.getSparseSetIndex(); } }; -/// SparseSetFunctor - Provide a trivial identity functor for -/// SparseSet. +/// SparseSetValFunctor - Helper class for selecting SparseSetValTraits. The +/// generic implementation handles ValueT classes which either provide +/// getSparseSetIndex() or specialize SparseSetValTraits<>. /// -template<> struct SparseSetFunctor { - unsigned operator()(unsigned Val) { return Val; } +template +struct SparseSetValFunctor { + unsigned operator()(const ValueT &Val) const { + return SparseSetValTraits::getValIndex(Val); + } }; -/// SparseSet - Fast set implementation for objects that can be identified by +/// SparseSetValFunctor - Helper class for the common case of +/// identity key/value sets. +template +struct SparseSetValFunctor { + unsigned operator()(const KeyT &Key) const { + return KeyFunctorT()(Key); + } +}; + +/// SparseSet - Fast set implmentation for objects that can be identified by /// small unsigned keys. /// /// SparseSet allocates memory proportional to the size of the key universe, so @@ -82,18 +111,20 @@ template<> struct SparseSetFunctor { /// uint16_t or uint32_t. /// /// @param ValueT The type of objects in the set. +/// @param KeyFunctorT A functor that computes an unsigned index from KeyT. /// @param SparseT An unsigned integer type. See above. -/// @param KeyFunctorT A functor that computes the unsigned key of a ValueT. /// template > + typename KeyFunctorT = llvm::identity, + typename SparseT = uint8_t> class SparseSet { + typedef typename KeyFunctorT::argument_type KeyT; typedef SmallVector DenseT; DenseT Dense; SparseT *Sparse; unsigned Universe; - KeyFunctorT KeyOf; + KeyFunctorT KeyIndexOf; + SparseSetValFunctor ValIndexOf; // Disable copy construction and assignment. // This data structure is not meant to be used that way. @@ -160,21 +191,21 @@ public: Dense.clear(); } - /// find - Find an element by its key. + /// findIndex - Find an element by its index. /// - /// @param Key A valid key to find. + /// @param Idx A valid index to find. /// @returns An iterator to the element identified by key, or end(). /// - iterator find(unsigned Key) { - assert(Key < Universe && "Key out of range"); + iterator findIndex(unsigned Idx) { + assert(Idx < Universe && "Key out of range"); assert(std::numeric_limits::is_integer && !std::numeric_limits::is_signed && "SparseT must be an unsigned integer type"); const unsigned Stride = std::numeric_limits::max() + 1u; - for (unsigned i = Sparse[Key], e = size(); i < e; i += Stride) { - const unsigned FoundKey = KeyOf(Dense[i]); - assert(FoundKey < Universe && "Invalid key in set. Did object mutate?"); - if (Key == FoundKey) + for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride) { + const unsigned FoundIdx = ValIndexOf(Dense[i]); + assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); + if (Idx == FoundIdx) return begin() + i; // Stride is 0 when SparseT >= unsigned. We don't need to loop. if (!Stride) @@ -183,13 +214,22 @@ public: return end(); } - const_iterator find(unsigned Key) const { - return const_cast(this)->find(Key); + /// find - Find an element by its key. + /// + /// @param Key A valid key to find. + /// @returns An iterator to the element identified by key, or end(). + /// + iterator find(const KeyT &Key) { + return findIndex(KeyIndexOf(Key)); + } + + const_iterator find(const KeyT &Key) const { + return const_cast(this)->findIndex(KeyIndexOf(Key)); } /// count - Returns true if this set contains an element identified by Key. /// - bool count(unsigned Key) const { + bool count(const KeyT &Key) const { return find(Key) != end(); } @@ -204,11 +244,11 @@ public: /// Insertion invalidates all iterators. /// std::pair insert(const ValueT &Val) { - unsigned Key = KeyOf(Val); - iterator I = find(Key); + unsigned Idx = ValIndexOf(Val); + iterator I = findIndex(Idx); if (I != end()) return std::make_pair(I, false); - Sparse[Key] = size(); + Sparse[Idx] = size(); Dense.push_back(Val); return std::make_pair(end() - 1, true); } @@ -216,7 +256,7 @@ public: /// array subscript - If an element already exists with this key, return it. /// Otherwise, automatically construct a new value from Key, insert it, /// and return the newly inserted element. - ValueT &operator[](unsigned Key) { + ValueT &operator[](const KeyT &Key) { return *insert(ValueT(Key)).first; } @@ -235,12 +275,12 @@ public: /// Note that end() changes when elements are erased, unlike std::list. /// iterator erase(iterator I) { - assert(I - begin() < size() && "Invalid iterator"); + assert(unsigned(I - begin()) < size() && "Invalid iterator"); if (I != end() - 1) { *I = Dense.back(); - unsigned BackKey = KeyOf(Dense.back()); - assert(BackKey < Universe && "Invalid key in set. Did object mutate?"); - Sparse[BackKey] = I - begin(); + unsigned BackIdx = ValIndexOf(Dense.back()); + assert(BackIdx < Universe && "Invalid key in set. Did object mutate?"); + Sparse[BackIdx] = I - begin(); } // This depends on SmallVector::pop_back() not invalidating iterators. // std::vector::pop_back() doesn't give that guarantee. @@ -253,7 +293,7 @@ public: /// @param Key The key identifying the element to erase. /// @returns True when an element was erased, false if no element was found. /// - bool erase(unsigned Key) { + bool erase(const KeyT &Key) { iterator I = find(Key); if (I == end()) return false;