SparseSet.h (234353) | SparseSet.h (239462) |
---|---|
1//===--- llvm/ADT/SparseSet.h - Sparse set ----------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// --- 7 unchanged lines hidden (view full) --- 16// containers in order to provide faster operations. 17// 18//===----------------------------------------------------------------------===// 19 20#ifndef LLVM_ADT_SPARSESET_H 21#define LLVM_ADT_SPARSESET_H 22 23#include "llvm/ADT/SmallVector.h" | 1//===--- llvm/ADT/SparseSet.h - Sparse set ----------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// --- 7 unchanged lines hidden (view full) --- 16// containers in order to provide faster operations. 17// 18//===----------------------------------------------------------------------===// 19 20#ifndef LLVM_ADT_SPARSESET_H 21#define LLVM_ADT_SPARSESET_H 22 23#include "llvm/ADT/SmallVector.h" |
24#include "llvm/ADT/STLExtras.h" |
|
24#include "llvm/Support/DataTypes.h" 25#include <limits> 26 27namespace llvm { 28 | 25#include "llvm/Support/DataTypes.h" 26#include <limits> 27 28namespace llvm { 29 |
29/// SparseSetFunctor - Objects in a SparseSet are identified by small integer 30/// keys. A functor object is used to compute the key of an object. The 31/// functor's operator() must return an unsigned smaller than the universe. | 30/// SparseSetValTraits - Objects in a SparseSet are identified by keys that can 31/// be uniquely converted to a small integer less than the set's universe. This 32/// class allows the set to hold values that differ from the set's key type as 33/// long as an index can still be derived from the value. SparseSet never 34/// directly compares ValueT, only their indices, so it can map keys to 35/// arbitrary values. SparseSetValTraits computes the index from the value 36/// object. To compute the index from a key, SparseSet uses a separate 37/// KeyFunctorT template argument. |
32/// | 38/// |
33/// The default functor implementation forwards to a getSparseSetKey() method 34/// on the object. It is intended for sparse sets holding ad-hoc structs. | 39/// A simple type declaration, SparseSet<Type>, handles these cases: 40/// - unsigned key, identity index, identity value 41/// - unsigned key, identity index, fat value providing getSparseSetIndex() |
35/// | 42/// |
43/// The type declaration SparseSet<Type, UnaryFunction> handles: 44/// - unsigned key, remapped index, identity value (virtual registers) 45/// - pointer key, pointer-derived index, identity value (node+ID) 46/// - pointer key, pointer-derived index, fat value with getSparseSetIndex() 47/// 48/// Only other, unexpected cases require specializing SparseSetValTraits. 49/// 50/// For best results, ValueT should not require a destructor. 51/// |
|
36template<typename ValueT> | 52template<typename ValueT> |
37struct SparseSetFunctor { 38 unsigned operator()(const ValueT &Val) { 39 return Val.getSparseSetKey(); | 53struct SparseSetValTraits { 54 static unsigned getValIndex(const ValueT &Val) { 55 return Val.getSparseSetIndex(); |
40 } 41}; 42 | 56 } 57}; 58 |
43/// SparseSetFunctor<unsigned> - Provide a trivial identity functor for 44/// SparseSet<unsigned>. | 59/// SparseSetValFunctor - Helper class for selecting SparseSetValTraits. The 60/// generic implementation handles ValueT classes which either provide 61/// getSparseSetIndex() or specialize SparseSetValTraits<>. |
45/// | 62/// |
46template<> struct SparseSetFunctor<unsigned> { 47 unsigned operator()(unsigned Val) { return Val; } | 63template<typename KeyT, typename ValueT, typename KeyFunctorT> 64struct SparseSetValFunctor { 65 unsigned operator()(const ValueT &Val) const { 66 return SparseSetValTraits<ValueT>::getValIndex(Val); 67 } |
48}; 49 | 68}; 69 |
50/// SparseSet - Fast set implementation for objects that can be identified by | 70/// SparseSetValFunctor<KeyT, KeyT> - Helper class for the common case of 71/// identity key/value sets. 72template<typename KeyT, typename KeyFunctorT> 73struct SparseSetValFunctor<KeyT, KeyT, KeyFunctorT> { 74 unsigned operator()(const KeyT &Key) const { 75 return KeyFunctorT()(Key); 76 } 77}; 78 79/// SparseSet - Fast set implmentation for objects that can be identified by |
51/// small unsigned keys. 52/// 53/// SparseSet allocates memory proportional to the size of the key universe, so 54/// it is not recommended for building composite data structures. It is useful 55/// for algorithms that require a single set with fast operations. 56/// 57/// Compared to DenseSet and DenseMap, SparseSet provides constant-time fast 58/// clear() and iteration as fast as a vector. The find(), insert(), and --- 18 unchanged lines hidden (view full) --- 77/// When SparseT is uint8_t (the default), find() touches up to 2+[N/256] cache 78/// lines, but the sparse array is 4x smaller. N is the number of elements in 79/// the set. 80/// 81/// For sets that may grow to thousands of elements, SparseT should be set to 82/// uint16_t or uint32_t. 83/// 84/// @param ValueT The type of objects in the set. | 80/// small unsigned keys. 81/// 82/// SparseSet allocates memory proportional to the size of the key universe, so 83/// it is not recommended for building composite data structures. It is useful 84/// for algorithms that require a single set with fast operations. 85/// 86/// Compared to DenseSet and DenseMap, SparseSet provides constant-time fast 87/// clear() and iteration as fast as a vector. The find(), insert(), and --- 18 unchanged lines hidden (view full) --- 106/// When SparseT is uint8_t (the default), find() touches up to 2+[N/256] cache 107/// lines, but the sparse array is 4x smaller. N is the number of elements in 108/// the set. 109/// 110/// For sets that may grow to thousands of elements, SparseT should be set to 111/// uint16_t or uint32_t. 112/// 113/// @param ValueT The type of objects in the set. |
114/// @param KeyFunctorT A functor that computes an unsigned index from KeyT. |
|
85/// @param SparseT An unsigned integer type. See above. | 115/// @param SparseT An unsigned integer type. See above. |
86/// @param KeyFunctorT A functor that computes the unsigned key of a ValueT. | |
87/// 88template<typename ValueT, | 116/// 117template<typename ValueT, |
89 typename SparseT = uint8_t, 90 typename KeyFunctorT = SparseSetFunctor<ValueT> > | 118 typename KeyFunctorT = llvm::identity<unsigned>, 119 typename SparseT = uint8_t> |
91class SparseSet { | 120class SparseSet { |
121 typedef typename KeyFunctorT::argument_type KeyT; |
|
92 typedef SmallVector<ValueT, 8> DenseT; 93 DenseT Dense; 94 SparseT *Sparse; 95 unsigned Universe; | 122 typedef SmallVector<ValueT, 8> DenseT; 123 DenseT Dense; 124 SparseT *Sparse; 125 unsigned Universe; |
96 KeyFunctorT KeyOf; | 126 KeyFunctorT KeyIndexOf; 127 SparseSetValFunctor<KeyT, ValueT, KeyFunctorT> ValIndexOf; |
97 98 // Disable copy construction and assignment. 99 // This data structure is not meant to be used that way. 100 SparseSet(const SparseSet&); // DO NOT IMPLEMENT. 101 SparseSet &operator=(const SparseSet&); // DO NOT IMPLEMENT. 102 103public: 104 typedef ValueT value_type; --- 50 unchanged lines hidden (view full) --- 155 156 /// clear - Clears the set. This is a very fast constant time operation. 157 /// 158 void clear() { 159 // Sparse does not need to be cleared, see find(). 160 Dense.clear(); 161 } 162 | 128 129 // Disable copy construction and assignment. 130 // This data structure is not meant to be used that way. 131 SparseSet(const SparseSet&); // DO NOT IMPLEMENT. 132 SparseSet &operator=(const SparseSet&); // DO NOT IMPLEMENT. 133 134public: 135 typedef ValueT value_type; --- 50 unchanged lines hidden (view full) --- 186 187 /// clear - Clears the set. This is a very fast constant time operation. 188 /// 189 void clear() { 190 // Sparse does not need to be cleared, see find(). 191 Dense.clear(); 192 } 193 |
163 /// find - Find an element by its key. | 194 /// findIndex - Find an element by its index. |
164 /// | 195 /// |
165 /// @param Key A valid key to find. | 196 /// @param Idx A valid index to find. |
166 /// @returns An iterator to the element identified by key, or end(). 167 /// | 197 /// @returns An iterator to the element identified by key, or end(). 198 /// |
168 iterator find(unsigned Key) { 169 assert(Key < Universe && "Key out of range"); | 199 iterator findIndex(unsigned Idx) { 200 assert(Idx < Universe && "Key out of range"); |
170 assert(std::numeric_limits<SparseT>::is_integer && 171 !std::numeric_limits<SparseT>::is_signed && 172 "SparseT must be an unsigned integer type"); 173 const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; | 201 assert(std::numeric_limits<SparseT>::is_integer && 202 !std::numeric_limits<SparseT>::is_signed && 203 "SparseT must be an unsigned integer type"); 204 const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; |
174 for (unsigned i = Sparse[Key], e = size(); i < e; i += Stride) { 175 const unsigned FoundKey = KeyOf(Dense[i]); 176 assert(FoundKey < Universe && "Invalid key in set. Did object mutate?"); 177 if (Key == FoundKey) | 205 for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride) { 206 const unsigned FoundIdx = ValIndexOf(Dense[i]); 207 assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); 208 if (Idx == FoundIdx) |
178 return begin() + i; 179 // Stride is 0 when SparseT >= unsigned. We don't need to loop. 180 if (!Stride) 181 break; 182 } 183 return end(); 184 } 185 | 209 return begin() + i; 210 // Stride is 0 when SparseT >= unsigned. We don't need to loop. 211 if (!Stride) 212 break; 213 } 214 return end(); 215 } 216 |
186 const_iterator find(unsigned Key) const { 187 return const_cast<SparseSet*>(this)->find(Key); | 217 /// find - Find an element by its key. 218 /// 219 /// @param Key A valid key to find. 220 /// @returns An iterator to the element identified by key, or end(). 221 /// 222 iterator find(const KeyT &Key) { 223 return findIndex(KeyIndexOf(Key)); |
188 } 189 | 224 } 225 |
226 const_iterator find(const KeyT &Key) const { 227 return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key)); 228 } 229 |
|
190 /// count - Returns true if this set contains an element identified by Key. 191 /// | 230 /// count - Returns true if this set contains an element identified by Key. 231 /// |
192 bool count(unsigned Key) const { | 232 bool count(const KeyT &Key) const { |
193 return find(Key) != end(); 194 } 195 196 /// insert - Attempts to insert a new element. 197 /// 198 /// If Val is successfully inserted, return (I, true), where I is an iterator 199 /// pointing to the newly inserted element. 200 /// 201 /// If the set already contains an element with the same key as Val, return 202 /// (I, false), where I is an iterator pointing to the existing element. 203 /// 204 /// Insertion invalidates all iterators. 205 /// 206 std::pair<iterator, bool> insert(const ValueT &Val) { | 233 return find(Key) != end(); 234 } 235 236 /// insert - Attempts to insert a new element. 237 /// 238 /// If Val is successfully inserted, return (I, true), where I is an iterator 239 /// pointing to the newly inserted element. 240 /// 241 /// If the set already contains an element with the same key as Val, return 242 /// (I, false), where I is an iterator pointing to the existing element. 243 /// 244 /// Insertion invalidates all iterators. 245 /// 246 std::pair<iterator, bool> insert(const ValueT &Val) { |
207 unsigned Key = KeyOf(Val); 208 iterator I = find(Key); | 247 unsigned Idx = ValIndexOf(Val); 248 iterator I = findIndex(Idx); |
209 if (I != end()) 210 return std::make_pair(I, false); | 249 if (I != end()) 250 return std::make_pair(I, false); |
211 Sparse[Key] = size(); | 251 Sparse[Idx] = size(); |
212 Dense.push_back(Val); 213 return std::make_pair(end() - 1, true); 214 } 215 216 /// array subscript - If an element already exists with this key, return it. 217 /// Otherwise, automatically construct a new value from Key, insert it, 218 /// and return the newly inserted element. | 252 Dense.push_back(Val); 253 return std::make_pair(end() - 1, true); 254 } 255 256 /// array subscript - If an element already exists with this key, return it. 257 /// Otherwise, automatically construct a new value from Key, insert it, 258 /// and return the newly inserted element. |
219 ValueT &operator[](unsigned Key) { | 259 ValueT &operator[](const KeyT &Key) { |
220 return *insert(ValueT(Key)).first; 221 } 222 223 /// erase - Erases an existing element identified by a valid iterator. 224 /// 225 /// This invalidates all iterators, but erase() returns an iterator pointing 226 /// to the next element. This makes it possible to erase selected elements 227 /// while iterating over the set: --- 5 unchanged lines hidden (view full) --- 233 /// ++I; 234 /// 235 /// Note that end() changes when elements are erased, unlike std::list. 236 /// 237 iterator erase(iterator I) { 238 assert(unsigned(I - begin()) < size() && "Invalid iterator"); 239 if (I != end() - 1) { 240 *I = Dense.back(); | 260 return *insert(ValueT(Key)).first; 261 } 262 263 /// erase - Erases an existing element identified by a valid iterator. 264 /// 265 /// This invalidates all iterators, but erase() returns an iterator pointing 266 /// to the next element. This makes it possible to erase selected elements 267 /// while iterating over the set: --- 5 unchanged lines hidden (view full) --- 273 /// ++I; 274 /// 275 /// Note that end() changes when elements are erased, unlike std::list. 276 /// 277 iterator erase(iterator I) { 278 assert(unsigned(I - begin()) < size() && "Invalid iterator"); 279 if (I != end() - 1) { 280 *I = Dense.back(); |
241 unsigned BackKey = KeyOf(Dense.back()); 242 assert(BackKey < Universe && "Invalid key in set. Did object mutate?"); 243 Sparse[BackKey] = I - begin(); | 281 unsigned BackIdx = ValIndexOf(Dense.back()); 282 assert(BackIdx < Universe && "Invalid key in set. Did object mutate?"); 283 Sparse[BackIdx] = I - begin(); |
244 } 245 // This depends on SmallVector::pop_back() not invalidating iterators. 246 // std::vector::pop_back() doesn't give that guarantee. 247 Dense.pop_back(); 248 return I; 249 } 250 251 /// erase - Erases an element identified by Key, if it exists. 252 /// 253 /// @param Key The key identifying the element to erase. 254 /// @returns True when an element was erased, false if no element was found. 255 /// | 284 } 285 // This depends on SmallVector::pop_back() not invalidating iterators. 286 // std::vector::pop_back() doesn't give that guarantee. 287 Dense.pop_back(); 288 return I; 289 } 290 291 /// erase - Erases an element identified by Key, if it exists. 292 /// 293 /// @param Key The key identifying the element to erase. 294 /// @returns True when an element was erased, false if no element was found. 295 /// |
256 bool erase(unsigned Key) { | 296 bool erase(const KeyT &Key) { |
257 iterator I = find(Key); 258 if (I == end()) 259 return false; 260 erase(I); 261 return true; 262 } 263 264}; 265 266} // end namespace llvm 267 268#endif | 297 iterator I = find(Key); 298 if (I == end()) 299 return false; 300 erase(I); 301 return true; 302 } 303 304}; 305 306} // end namespace llvm 307 308#endif |