1234285Sdim//===--- llvm/ADT/SparseSet.h - Sparse set ----------------------*- C++ -*-===// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This file defines the SparseSet class derived from the version described in 11234285Sdim// Briggs, Torczon, "An efficient representation for sparse sets", ACM Letters 12234285Sdim// on Programming Languages and Systems, Volume 2 Issue 1-4, March-Dec. 1993. 13234285Sdim// 14234285Sdim// A sparse set holds a small number of objects identified by integer keys from 15234285Sdim// a moderately sized universe. The sparse set uses more memory than other 16234285Sdim// containers in order to provide faster operations. 17234285Sdim// 18234285Sdim//===----------------------------------------------------------------------===// 19234285Sdim 20234285Sdim#ifndef LLVM_ADT_SPARSESET_H 21234285Sdim#define LLVM_ADT_SPARSESET_H 22234285Sdim 23249423Sdim#include "llvm/ADT/STLExtras.h" 24234285Sdim#include "llvm/ADT/SmallVector.h" 25234285Sdim#include "llvm/Support/DataTypes.h" 26234285Sdim#include <limits> 27234285Sdim 28234285Sdimnamespace llvm { 29234285Sdim 30239462Sdim/// SparseSetValTraits - Objects in a SparseSet are identified by keys that can 31239462Sdim/// be uniquely converted to a small integer less than the set's universe. This 32239462Sdim/// class allows the set to hold values that differ from the set's key type as 33239462Sdim/// long as an index can still be derived from the value. SparseSet never 34239462Sdim/// directly compares ValueT, only their indices, so it can map keys to 35239462Sdim/// arbitrary values. SparseSetValTraits computes the index from the value 36239462Sdim/// object. To compute the index from a key, SparseSet uses a separate 37239462Sdim/// KeyFunctorT template argument. 38234285Sdim/// 39239462Sdim/// A simple type declaration, SparseSet<Type>, handles these cases: 40239462Sdim/// - unsigned key, identity index, identity value 41239462Sdim/// - unsigned key, identity index, fat value providing getSparseSetIndex() 42234285Sdim/// 43239462Sdim/// The type declaration SparseSet<Type, UnaryFunction> handles: 44239462Sdim/// - unsigned key, remapped index, identity value (virtual registers) 45239462Sdim/// - pointer key, pointer-derived index, identity value (node+ID) 46239462Sdim/// - pointer key, pointer-derived index, fat value with getSparseSetIndex() 47239462Sdim/// 48239462Sdim/// Only other, unexpected cases require specializing SparseSetValTraits. 49239462Sdim/// 50239462Sdim/// For best results, ValueT should not require a destructor. 51239462Sdim/// 52234285Sdimtemplate<typename ValueT> 53239462Sdimstruct SparseSetValTraits { 54239462Sdim static unsigned getValIndex(const ValueT &Val) { 55239462Sdim return Val.getSparseSetIndex(); 56234285Sdim } 57234285Sdim}; 58234285Sdim 59239462Sdim/// SparseSetValFunctor - Helper class for selecting SparseSetValTraits. The 60239462Sdim/// generic implementation handles ValueT classes which either provide 61239462Sdim/// getSparseSetIndex() or specialize SparseSetValTraits<>. 62234285Sdim/// 63239462Sdimtemplate<typename KeyT, typename ValueT, typename KeyFunctorT> 64239462Sdimstruct SparseSetValFunctor { 65239462Sdim unsigned operator()(const ValueT &Val) const { 66239462Sdim return SparseSetValTraits<ValueT>::getValIndex(Val); 67239462Sdim } 68234285Sdim}; 69234285Sdim 70239462Sdim/// SparseSetValFunctor<KeyT, KeyT> - Helper class for the common case of 71239462Sdim/// identity key/value sets. 72239462Sdimtemplate<typename KeyT, typename KeyFunctorT> 73239462Sdimstruct SparseSetValFunctor<KeyT, KeyT, KeyFunctorT> { 74239462Sdim unsigned operator()(const KeyT &Key) const { 75239462Sdim return KeyFunctorT()(Key); 76239462Sdim } 77239462Sdim}; 78239462Sdim 79239462Sdim/// SparseSet - Fast set implmentation for objects that can be identified by 80234285Sdim/// small unsigned keys. 81234285Sdim/// 82234285Sdim/// SparseSet allocates memory proportional to the size of the key universe, so 83234285Sdim/// it is not recommended for building composite data structures. It is useful 84234285Sdim/// for algorithms that require a single set with fast operations. 85234285Sdim/// 86234285Sdim/// Compared to DenseSet and DenseMap, SparseSet provides constant-time fast 87234285Sdim/// clear() and iteration as fast as a vector. The find(), insert(), and 88234285Sdim/// erase() operations are all constant time, and typically faster than a hash 89234285Sdim/// table. The iteration order doesn't depend on numerical key values, it only 90234285Sdim/// depends on the order of insert() and erase() operations. When no elements 91234285Sdim/// have been erased, the iteration order is the insertion order. 92234285Sdim/// 93234285Sdim/// Compared to BitVector, SparseSet<unsigned> uses 8x-40x more memory, but 94234285Sdim/// offers constant-time clear() and size() operations as well as fast 95234285Sdim/// iteration independent on the size of the universe. 96234285Sdim/// 97234285Sdim/// SparseSet contains a dense vector holding all the objects and a sparse 98234285Sdim/// array holding indexes into the dense vector. Most of the memory is used by 99234285Sdim/// the sparse array which is the size of the key universe. The SparseT 100234285Sdim/// template parameter provides a space/speed tradeoff for sets holding many 101234285Sdim/// elements. 102234285Sdim/// 103234285Sdim/// When SparseT is uint32_t, find() only touches 2 cache lines, but the sparse 104234285Sdim/// array uses 4 x Universe bytes. 105234285Sdim/// 106234285Sdim/// When SparseT is uint8_t (the default), find() touches up to 2+[N/256] cache 107234285Sdim/// lines, but the sparse array is 4x smaller. N is the number of elements in 108234285Sdim/// the set. 109234285Sdim/// 110234285Sdim/// For sets that may grow to thousands of elements, SparseT should be set to 111234285Sdim/// uint16_t or uint32_t. 112234285Sdim/// 113243830Sdim/// @tparam ValueT The type of objects in the set. 114243830Sdim/// @tparam KeyFunctorT A functor that computes an unsigned index from KeyT. 115243830Sdim/// @tparam SparseT An unsigned integer type. See above. 116234285Sdim/// 117234285Sdimtemplate<typename ValueT, 118239462Sdim typename KeyFunctorT = llvm::identity<unsigned>, 119239462Sdim typename SparseT = uint8_t> 120234285Sdimclass SparseSet { 121239462Sdim typedef typename KeyFunctorT::argument_type KeyT; 122234285Sdim typedef SmallVector<ValueT, 8> DenseT; 123234285Sdim DenseT Dense; 124234285Sdim SparseT *Sparse; 125234285Sdim unsigned Universe; 126239462Sdim KeyFunctorT KeyIndexOf; 127239462Sdim SparseSetValFunctor<KeyT, ValueT, KeyFunctorT> ValIndexOf; 128234285Sdim 129234285Sdim // Disable copy construction and assignment. 130234285Sdim // This data structure is not meant to be used that way. 131243830Sdim SparseSet(const SparseSet&) LLVM_DELETED_FUNCTION; 132243830Sdim SparseSet &operator=(const SparseSet&) LLVM_DELETED_FUNCTION; 133234285Sdim 134234285Sdimpublic: 135234285Sdim typedef ValueT value_type; 136234285Sdim typedef ValueT &reference; 137234285Sdim typedef const ValueT &const_reference; 138234285Sdim typedef ValueT *pointer; 139234285Sdim typedef const ValueT *const_pointer; 140234285Sdim 141234285Sdim SparseSet() : Sparse(0), Universe(0) {} 142234285Sdim ~SparseSet() { free(Sparse); } 143234285Sdim 144234285Sdim /// setUniverse - Set the universe size which determines the largest key the 145234285Sdim /// set can hold. The universe must be sized before any elements can be 146234285Sdim /// added. 147234285Sdim /// 148234285Sdim /// @param U Universe size. All object keys must be less than U. 149234285Sdim /// 150234285Sdim void setUniverse(unsigned U) { 151234285Sdim // It's not hard to resize the universe on a non-empty set, but it doesn't 152234285Sdim // seem like a likely use case, so we can add that code when we need it. 153234285Sdim assert(empty() && "Can only resize universe on an empty map"); 154234285Sdim // Hysteresis prevents needless reallocations. 155234285Sdim if (U >= Universe/4 && U <= Universe) 156234285Sdim return; 157234285Sdim free(Sparse); 158234285Sdim // The Sparse array doesn't actually need to be initialized, so malloc 159234285Sdim // would be enough here, but that will cause tools like valgrind to 160234285Sdim // complain about branching on uninitialized data. 161234285Sdim Sparse = reinterpret_cast<SparseT*>(calloc(U, sizeof(SparseT))); 162234285Sdim Universe = U; 163234285Sdim } 164234285Sdim 165234285Sdim // Import trivial vector stuff from DenseT. 166234285Sdim typedef typename DenseT::iterator iterator; 167234285Sdim typedef typename DenseT::const_iterator const_iterator; 168234285Sdim 169234285Sdim const_iterator begin() const { return Dense.begin(); } 170234285Sdim const_iterator end() const { return Dense.end(); } 171234285Sdim iterator begin() { return Dense.begin(); } 172234285Sdim iterator end() { return Dense.end(); } 173234285Sdim 174234285Sdim /// empty - Returns true if the set is empty. 175234285Sdim /// 176234285Sdim /// This is not the same as BitVector::empty(). 177234285Sdim /// 178234285Sdim bool empty() const { return Dense.empty(); } 179234285Sdim 180234285Sdim /// size - Returns the number of elements in the set. 181234285Sdim /// 182234285Sdim /// This is not the same as BitVector::size() which returns the size of the 183234285Sdim /// universe. 184234285Sdim /// 185234285Sdim unsigned size() const { return Dense.size(); } 186234285Sdim 187234285Sdim /// clear - Clears the set. This is a very fast constant time operation. 188234285Sdim /// 189234285Sdim void clear() { 190234285Sdim // Sparse does not need to be cleared, see find(). 191234285Sdim Dense.clear(); 192234285Sdim } 193234285Sdim 194239462Sdim /// findIndex - Find an element by its index. 195234285Sdim /// 196239462Sdim /// @param Idx A valid index to find. 197234285Sdim /// @returns An iterator to the element identified by key, or end(). 198234285Sdim /// 199239462Sdim iterator findIndex(unsigned Idx) { 200239462Sdim assert(Idx < Universe && "Key out of range"); 201234285Sdim assert(std::numeric_limits<SparseT>::is_integer && 202234285Sdim !std::numeric_limits<SparseT>::is_signed && 203234285Sdim "SparseT must be an unsigned integer type"); 204234285Sdim const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; 205239462Sdim for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride) { 206239462Sdim const unsigned FoundIdx = ValIndexOf(Dense[i]); 207239462Sdim assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); 208239462Sdim if (Idx == FoundIdx) 209234285Sdim return begin() + i; 210234285Sdim // Stride is 0 when SparseT >= unsigned. We don't need to loop. 211234285Sdim if (!Stride) 212234285Sdim break; 213234285Sdim } 214234285Sdim return end(); 215234285Sdim } 216234285Sdim 217239462Sdim /// find - Find an element by its key. 218239462Sdim /// 219239462Sdim /// @param Key A valid key to find. 220239462Sdim /// @returns An iterator to the element identified by key, or end(). 221239462Sdim /// 222239462Sdim iterator find(const KeyT &Key) { 223239462Sdim return findIndex(KeyIndexOf(Key)); 224234285Sdim } 225234285Sdim 226239462Sdim const_iterator find(const KeyT &Key) const { 227239462Sdim return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key)); 228239462Sdim } 229239462Sdim 230234285Sdim /// count - Returns true if this set contains an element identified by Key. 231234285Sdim /// 232239462Sdim bool count(const KeyT &Key) const { 233234285Sdim return find(Key) != end(); 234234285Sdim } 235234285Sdim 236234285Sdim /// insert - Attempts to insert a new element. 237234285Sdim /// 238234285Sdim /// If Val is successfully inserted, return (I, true), where I is an iterator 239234285Sdim /// pointing to the newly inserted element. 240234285Sdim /// 241234285Sdim /// If the set already contains an element with the same key as Val, return 242234285Sdim /// (I, false), where I is an iterator pointing to the existing element. 243234285Sdim /// 244234285Sdim /// Insertion invalidates all iterators. 245234285Sdim /// 246234285Sdim std::pair<iterator, bool> insert(const ValueT &Val) { 247239462Sdim unsigned Idx = ValIndexOf(Val); 248239462Sdim iterator I = findIndex(Idx); 249234285Sdim if (I != end()) 250234285Sdim return std::make_pair(I, false); 251239462Sdim Sparse[Idx] = size(); 252234285Sdim Dense.push_back(Val); 253234285Sdim return std::make_pair(end() - 1, true); 254234285Sdim } 255234285Sdim 256234285Sdim /// array subscript - If an element already exists with this key, return it. 257234285Sdim /// Otherwise, automatically construct a new value from Key, insert it, 258234285Sdim /// and return the newly inserted element. 259239462Sdim ValueT &operator[](const KeyT &Key) { 260234285Sdim return *insert(ValueT(Key)).first; 261234285Sdim } 262234285Sdim 263234285Sdim /// erase - Erases an existing element identified by a valid iterator. 264234285Sdim /// 265234285Sdim /// This invalidates all iterators, but erase() returns an iterator pointing 266234285Sdim /// to the next element. This makes it possible to erase selected elements 267234285Sdim /// while iterating over the set: 268234285Sdim /// 269234285Sdim /// for (SparseSet::iterator I = Set.begin(); I != Set.end();) 270234285Sdim /// if (test(*I)) 271234285Sdim /// I = Set.erase(I); 272234285Sdim /// else 273234285Sdim /// ++I; 274234285Sdim /// 275234285Sdim /// Note that end() changes when elements are erased, unlike std::list. 276234285Sdim /// 277234285Sdim iterator erase(iterator I) { 278234285Sdim assert(unsigned(I - begin()) < size() && "Invalid iterator"); 279234285Sdim if (I != end() - 1) { 280234285Sdim *I = Dense.back(); 281239462Sdim unsigned BackIdx = ValIndexOf(Dense.back()); 282239462Sdim assert(BackIdx < Universe && "Invalid key in set. Did object mutate?"); 283239462Sdim Sparse[BackIdx] = I - begin(); 284234285Sdim } 285234285Sdim // This depends on SmallVector::pop_back() not invalidating iterators. 286234285Sdim // std::vector::pop_back() doesn't give that guarantee. 287234285Sdim Dense.pop_back(); 288234285Sdim return I; 289234285Sdim } 290234285Sdim 291234285Sdim /// erase - Erases an element identified by Key, if it exists. 292234285Sdim /// 293234285Sdim /// @param Key The key identifying the element to erase. 294234285Sdim /// @returns True when an element was erased, false if no element was found. 295234285Sdim /// 296239462Sdim bool erase(const KeyT &Key) { 297234285Sdim iterator I = find(Key); 298234285Sdim if (I == end()) 299234285Sdim return false; 300234285Sdim erase(I); 301234285Sdim return true; 302234285Sdim } 303234285Sdim 304234285Sdim}; 305234285Sdim 306234285Sdim} // end namespace llvm 307234285Sdim 308234285Sdim#endif 309