X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSparseSet.h;h=267a340a7581486ebfa72ba90bb13eb3e34e989d;hb=b02ed5b8eafd11500bbefb7206ecbf5bc3fc324a;hp=b9928b9bb6600be070dfb7bfa4b95e2a9cee1b1c;hpb=f3b06a93825402b2121ec8231f56cd75539fe3aa;p=oota-llvm.git diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h index b9928b9bb66..267a340a758 100644 --- a/include/llvm/ADT/SparseSet.h +++ b/include/llvm/ADT/SparseSet.h @@ -9,7 +9,7 @@ // // This file defines the SparseSet class derived from the version described in // Briggs, Torczon, "An efficient representation for sparse sets", ACM Letters -// on Programming Languages and Systems, Volume 2 Issue 1-4, March–Dec. 1993. +// on Programming Languages and Systems, Volume 2 Issue 1-4, March-Dec. 1993. // // A sparse set holds a small number of objects identified by integer keys from // a moderately sized universe. The sparse set uses more memory than other @@ -20,34 +20,63 @@ #ifndef LLVM_ADT_SPARSESET_H #define LLVM_ADT_SPARSESET_H +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.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); + } +}; + +/// 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 implementation for objects that can be identified by +/// 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 @@ -81,24 +110,26 @@ template<> struct SparseSetFunctor { /// For sets that may grow to thousands of elements, SparseT should be set to /// uint16_t or uint32_t. /// -/// @param ValueT The type of objects in the set. -/// @param SparseT An unsigned integer type. See above. -/// @param KeyFunctorT A functor that computes the unsigned key of a ValueT. +/// @tparam ValueT The type of objects in the set. +/// @tparam KeyFunctorT A functor that computes an unsigned index from KeyT. +/// @tparam SparseT An unsigned integer type. See above. /// 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. - SparseSet(const SparseSet&); // DO NOT IMPLEMENT. - SparseSet &operator=(const SparseSet&); // DO NOT IMPLEMENT. + SparseSet(const SparseSet&) LLVM_DELETED_FUNCTION; + SparseSet &operator=(const SparseSet&) LLVM_DELETED_FUNCTION; public: typedef ValueT value_type; @@ -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,15 +244,22 @@ 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); } + /// 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[](const KeyT &Key) { + return *insert(ValueT(Key)).first; + } + /// erase - Erases an existing element identified by a valid iterator. /// /// This invalidates all iterators, but erase() returns an iterator pointing @@ -228,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. @@ -246,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;