LLVM API Documentation

SparseSet.h
Go to the documentation of this file.
00001 //===--- llvm/ADT/SparseSet.h - Sparse set ----------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the SparseSet class derived from the version described in
00011 // Briggs, Torczon, "An efficient representation for sparse sets", ACM Letters
00012 // on Programming Languages and Systems, Volume 2 Issue 1-4, March-Dec.  1993.
00013 //
00014 // A sparse set holds a small number of objects identified by integer keys from
00015 // a moderately sized universe. The sparse set uses more memory than other
00016 // containers in order to provide faster operations.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #ifndef LLVM_ADT_SPARSESET_H
00021 #define LLVM_ADT_SPARSESET_H
00022 
00023 #include "llvm/ADT/STLExtras.h"
00024 #include "llvm/ADT/SmallVector.h"
00025 #include "llvm/Support/DataTypes.h"
00026 #include <limits>
00027 
00028 namespace llvm {
00029 
00030 /// SparseSetValTraits - Objects in a SparseSet are identified by keys that can
00031 /// be uniquely converted to a small integer less than the set's universe. This
00032 /// class allows the set to hold values that differ from the set's key type as
00033 /// long as an index can still be derived from the value. SparseSet never
00034 /// directly compares ValueT, only their indices, so it can map keys to
00035 /// arbitrary values. SparseSetValTraits computes the index from the value
00036 /// object. To compute the index from a key, SparseSet uses a separate
00037 /// KeyFunctorT template argument.
00038 ///
00039 /// A simple type declaration, SparseSet<Type>, handles these cases:
00040 /// - unsigned key, identity index, identity value
00041 /// - unsigned key, identity index, fat value providing getSparseSetIndex()
00042 ///
00043 /// The type declaration SparseSet<Type, UnaryFunction> handles:
00044 /// - unsigned key, remapped index, identity value (virtual registers)
00045 /// - pointer key, pointer-derived index, identity value (node+ID)
00046 /// - pointer key, pointer-derived index, fat value with getSparseSetIndex()
00047 ///
00048 /// Only other, unexpected cases require specializing SparseSetValTraits.
00049 ///
00050 /// For best results, ValueT should not require a destructor.
00051 ///
00052 template<typename ValueT>
00053 struct SparseSetValTraits {
00054   static unsigned getValIndex(const ValueT &Val) {
00055     return Val.getSparseSetIndex();
00056   }
00057 };
00058 
00059 /// SparseSetValFunctor - Helper class for selecting SparseSetValTraits. The
00060 /// generic implementation handles ValueT classes which either provide
00061 /// getSparseSetIndex() or specialize SparseSetValTraits<>.
00062 ///
00063 template<typename KeyT, typename ValueT, typename KeyFunctorT>
00064 struct SparseSetValFunctor {
00065   unsigned operator()(const ValueT &Val) const {
00066     return SparseSetValTraits<ValueT>::getValIndex(Val);
00067   }
00068 };
00069 
00070 /// SparseSetValFunctor<KeyT, KeyT> - Helper class for the common case of
00071 /// identity key/value sets.
00072 template<typename KeyT, typename KeyFunctorT>
00073 struct SparseSetValFunctor<KeyT, KeyT, KeyFunctorT> {
00074   unsigned operator()(const KeyT &Key) const {
00075     return KeyFunctorT()(Key);
00076   }
00077 };
00078 
00079 /// SparseSet - Fast set implmentation for objects that can be identified by
00080 /// small unsigned keys.
00081 ///
00082 /// SparseSet allocates memory proportional to the size of the key universe, so
00083 /// it is not recommended for building composite data structures.  It is useful
00084 /// for algorithms that require a single set with fast operations.
00085 ///
00086 /// Compared to DenseSet and DenseMap, SparseSet provides constant-time fast
00087 /// clear() and iteration as fast as a vector.  The find(), insert(), and
00088 /// erase() operations are all constant time, and typically faster than a hash
00089 /// table.  The iteration order doesn't depend on numerical key values, it only
00090 /// depends on the order of insert() and erase() operations.  When no elements
00091 /// have been erased, the iteration order is the insertion order.
00092 ///
00093 /// Compared to BitVector, SparseSet<unsigned> uses 8x-40x more memory, but
00094 /// offers constant-time clear() and size() operations as well as fast
00095 /// iteration independent on the size of the universe.
00096 ///
00097 /// SparseSet contains a dense vector holding all the objects and a sparse
00098 /// array holding indexes into the dense vector.  Most of the memory is used by
00099 /// the sparse array which is the size of the key universe.  The SparseT
00100 /// template parameter provides a space/speed tradeoff for sets holding many
00101 /// elements.
00102 ///
00103 /// When SparseT is uint32_t, find() only touches 2 cache lines, but the sparse
00104 /// array uses 4 x Universe bytes.
00105 ///
00106 /// When SparseT is uint8_t (the default), find() touches up to 2+[N/256] cache
00107 /// lines, but the sparse array is 4x smaller.  N is the number of elements in
00108 /// the set.
00109 ///
00110 /// For sets that may grow to thousands of elements, SparseT should be set to
00111 /// uint16_t or uint32_t.
00112 ///
00113 /// @tparam ValueT      The type of objects in the set.
00114 /// @tparam KeyFunctorT A functor that computes an unsigned index from KeyT.
00115 /// @tparam SparseT     An unsigned integer type. See above.
00116 ///
00117 template<typename ValueT,
00118          typename KeyFunctorT = llvm::identity<unsigned>,
00119          typename SparseT = uint8_t>
00120 class SparseSet {
00121   static_assert(std::numeric_limits<SparseT>::is_integer &&
00122                 !std::numeric_limits<SparseT>::is_signed,
00123                 "SparseT must be an unsigned integer type");
00124 
00125   typedef typename KeyFunctorT::argument_type KeyT;
00126   typedef SmallVector<ValueT, 8> DenseT;
00127   DenseT Dense;
00128   SparseT *Sparse;
00129   unsigned Universe;
00130   KeyFunctorT KeyIndexOf;
00131   SparseSetValFunctor<KeyT, ValueT, KeyFunctorT> ValIndexOf;
00132 
00133   // Disable copy construction and assignment.
00134   // This data structure is not meant to be used that way.
00135   SparseSet(const SparseSet&) LLVM_DELETED_FUNCTION;
00136   SparseSet &operator=(const SparseSet&) LLVM_DELETED_FUNCTION;
00137 
00138 public:
00139   typedef ValueT value_type;
00140   typedef ValueT &reference;
00141   typedef const ValueT &const_reference;
00142   typedef ValueT *pointer;
00143   typedef const ValueT *const_pointer;
00144 
00145   SparseSet() : Sparse(nullptr), Universe(0) {}
00146   ~SparseSet() { free(Sparse); }
00147 
00148   /// setUniverse - Set the universe size which determines the largest key the
00149   /// set can hold.  The universe must be sized before any elements can be
00150   /// added.
00151   ///
00152   /// @param U Universe size. All object keys must be less than U.
00153   ///
00154   void setUniverse(unsigned U) {
00155     // It's not hard to resize the universe on a non-empty set, but it doesn't
00156     // seem like a likely use case, so we can add that code when we need it.
00157     assert(empty() && "Can only resize universe on an empty map");
00158     // Hysteresis prevents needless reallocations.
00159     if (U >= Universe/4 && U <= Universe)
00160       return;
00161     free(Sparse);
00162     // The Sparse array doesn't actually need to be initialized, so malloc
00163     // would be enough here, but that will cause tools like valgrind to
00164     // complain about branching on uninitialized data.
00165     Sparse = reinterpret_cast<SparseT*>(calloc(U, sizeof(SparseT)));
00166     Universe = U;
00167   }
00168 
00169   // Import trivial vector stuff from DenseT.
00170   typedef typename DenseT::iterator iterator;
00171   typedef typename DenseT::const_iterator const_iterator;
00172 
00173   const_iterator begin() const { return Dense.begin(); }
00174   const_iterator end() const { return Dense.end(); }
00175   iterator begin() { return Dense.begin(); }
00176   iterator end() { return Dense.end(); }
00177 
00178   /// empty - Returns true if the set is empty.
00179   ///
00180   /// This is not the same as BitVector::empty().
00181   ///
00182   bool empty() const { return Dense.empty(); }
00183 
00184   /// size - Returns the number of elements in the set.
00185   ///
00186   /// This is not the same as BitVector::size() which returns the size of the
00187   /// universe.
00188   ///
00189   unsigned size() const { return Dense.size(); }
00190 
00191   /// clear - Clears the set.  This is a very fast constant time operation.
00192   ///
00193   void clear() {
00194     // Sparse does not need to be cleared, see find().
00195     Dense.clear();
00196   }
00197 
00198   /// findIndex - Find an element by its index.
00199   ///
00200   /// @param   Idx A valid index to find.
00201   /// @returns An iterator to the element identified by key, or end().
00202   ///
00203   iterator findIndex(unsigned Idx) {
00204     assert(Idx < Universe && "Key out of range");
00205     const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u;
00206     for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride) {
00207       const unsigned FoundIdx = ValIndexOf(Dense[i]);
00208       assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?");
00209       if (Idx == FoundIdx)
00210         return begin() + i;
00211       // Stride is 0 when SparseT >= unsigned.  We don't need to loop.
00212       if (!Stride)
00213         break;
00214     }
00215     return end();
00216   }
00217 
00218   /// find - Find an element by its key.
00219   ///
00220   /// @param   Key A valid key to find.
00221   /// @returns An iterator to the element identified by key, or end().
00222   ///
00223   iterator find(const KeyT &Key) {
00224     return findIndex(KeyIndexOf(Key));
00225   }
00226 
00227   const_iterator find(const KeyT &Key) const {
00228     return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key));
00229   }
00230 
00231   /// count - Returns 1 if this set contains an element identified by Key,
00232   /// 0 otherwise.
00233   ///
00234   unsigned count(const KeyT &Key) const {
00235     return find(Key) == end() ? 0 : 1;
00236   }
00237 
00238   /// insert - Attempts to insert a new element.
00239   ///
00240   /// If Val is successfully inserted, return (I, true), where I is an iterator
00241   /// pointing to the newly inserted element.
00242   ///
00243   /// If the set already contains an element with the same key as Val, return
00244   /// (I, false), where I is an iterator pointing to the existing element.
00245   ///
00246   /// Insertion invalidates all iterators.
00247   ///
00248   std::pair<iterator, bool> insert(const ValueT &Val) {
00249     unsigned Idx = ValIndexOf(Val);
00250     iterator I = findIndex(Idx);
00251     if (I != end())
00252       return std::make_pair(I, false);
00253     Sparse[Idx] = size();
00254     Dense.push_back(Val);
00255     return std::make_pair(end() - 1, true);
00256   }
00257 
00258   /// array subscript - If an element already exists with this key, return it.
00259   /// Otherwise, automatically construct a new value from Key, insert it,
00260   /// and return the newly inserted element.
00261   ValueT &operator[](const KeyT &Key) {
00262     return *insert(ValueT(Key)).first;
00263   }
00264 
00265   /// erase - Erases an existing element identified by a valid iterator.
00266   ///
00267   /// This invalidates all iterators, but erase() returns an iterator pointing
00268   /// to the next element.  This makes it possible to erase selected elements
00269   /// while iterating over the set:
00270   ///
00271   ///   for (SparseSet::iterator I = Set.begin(); I != Set.end();)
00272   ///     if (test(*I))
00273   ///       I = Set.erase(I);
00274   ///     else
00275   ///       ++I;
00276   ///
00277   /// Note that end() changes when elements are erased, unlike std::list.
00278   ///
00279   iterator erase(iterator I) {
00280     assert(unsigned(I - begin()) < size() && "Invalid iterator");
00281     if (I != end() - 1) {
00282       *I = Dense.back();
00283       unsigned BackIdx = ValIndexOf(Dense.back());
00284       assert(BackIdx < Universe && "Invalid key in set. Did object mutate?");
00285       Sparse[BackIdx] = I - begin();
00286     }
00287     // This depends on SmallVector::pop_back() not invalidating iterators.
00288     // std::vector::pop_back() doesn't give that guarantee.
00289     Dense.pop_back();
00290     return I;
00291   }
00292 
00293   /// erase - Erases an element identified by Key, if it exists.
00294   ///
00295   /// @param   Key The key identifying the element to erase.
00296   /// @returns True when an element was erased, false if no element was found.
00297   ///
00298   bool erase(const KeyT &Key) {
00299     iterator I = find(Key);
00300     if (I == end())
00301       return false;
00302     erase(I);
00303     return true;
00304   }
00305 
00306 };
00307 
00308 } // end namespace llvm
00309 
00310 #endif