1//===- llvm/ADT/SparseSet.h - Sparse set ------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the SparseSet class derived from the version described in
10// Briggs, Torczon, "An efficient representation for sparse sets", ACM Letters
11// on Programming Languages and Systems, Volume 2 Issue 1-4, March-Dec. 1993.
12//
13// A sparse set holds a small number of objects identified by integer keys from
14// a moderately sized universe. The sparse set uses more memory than other
15// containers in order to provide faster operations.
16//
17//===----------------------------------------------------------------------===//
18
19#ifndef LLVM_ADT_SPARSESET_H
20#define LLVM_ADT_SPARSESET_H
21
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/Support/AllocatorBase.h"
25#include <cassert>
26#include <cstdint>
27#include <cstdlib>
28#include <limits>
29#include <utility>
30
31namespace llvm {
32
33/// SparseSetValTraits - Objects in a SparseSet are identified by keys that can
34/// be uniquely converted to a small integer less than the set's universe. This
35/// class allows the set to hold values that differ from the set's key type as
36/// long as an index can still be derived from the value. SparseSet never
37/// directly compares ValueT, only their indices, so it can map keys to
38/// arbitrary values. SparseSetValTraits computes the index from the value
39/// object. To compute the index from a key, SparseSet uses a separate
40/// KeyFunctorT template argument.
41///
42/// A simple type declaration, SparseSet<Type>, handles these cases:
43/// - unsigned key, identity index, identity value
44/// - unsigned key, identity index, fat value providing getSparseSetIndex()
45///
46/// The type declaration SparseSet<Type, UnaryFunction> handles:
47/// - unsigned key, remapped index, identity value (virtual registers)
48/// - pointer key, pointer-derived index, identity value (node+ID)
49/// - pointer key, pointer-derived index, fat value with getSparseSetIndex()
50///
51/// Only other, unexpected cases require specializing SparseSetValTraits.
52///
53/// For best results, ValueT should not require a destructor.
54///
55template<typename ValueT>
56struct SparseSetValTraits {
57 static unsigned getValIndex(const ValueT &Val) {
58 return Val.getSparseSetIndex();
59 }
60};
61
62/// SparseSetValFunctor - Helper class for selecting SparseSetValTraits. The
63/// generic implementation handles ValueT classes which either provide
64/// getSparseSetIndex() or specialize SparseSetValTraits<>.
65///
66template<typename KeyT, typename ValueT, typename KeyFunctorT>
67struct SparseSetValFunctor {
68 unsigned operator()(const ValueT &Val) const {
69 return SparseSetValTraits<ValueT>::getValIndex(Val);
70 }
71};
72
73/// SparseSetValFunctor<KeyT, KeyT> - Helper class for the common case of
74/// identity key/value sets.
75template<typename KeyT, typename KeyFunctorT>
76struct SparseSetValFunctor<KeyT, KeyT, KeyFunctorT> {
77 unsigned operator()(const KeyT &Key) const {
78 return KeyFunctorT()(Key);
79 }
80};
81
82/// SparseSet - Fast set implementation for objects that can be identified by
83/// small unsigned keys.
84///
85/// SparseSet allocates memory proportional to the size of the key universe, so
86/// it is not recommended for building composite data structures. It is useful
87/// for algorithms that require a single set with fast operations.
88///
89/// Compared to DenseSet and DenseMap, SparseSet provides constant-time fast
90/// clear() and iteration as fast as a vector. The find(), insert(), and
91/// erase() operations are all constant time, and typically faster than a hash
92/// table. The iteration order doesn't depend on numerical key values, it only
93/// depends on the order of insert() and erase() operations. When no elements
94/// have been erased, the iteration order is the insertion order.
95///
96/// Compared to BitVector, SparseSet<unsigned> uses 8x-40x more memory, but
97/// offers constant-time clear() and size() operations as well as fast
98/// iteration independent on the size of the universe.
99///
100/// SparseSet contains a dense vector holding all the objects and a sparse
101/// array holding indexes into the dense vector. Most of the memory is used by
102/// the sparse array which is the size of the key universe. The SparseT
103/// template parameter provides a space/speed tradeoff for sets holding many
104/// elements.
105///
106/// When SparseT is uint32_t, find() only touches 2 cache lines, but the sparse
107/// array uses 4 x Universe bytes.
108///
109/// When SparseT is uint8_t (the default), find() touches up to 2+[N/256] cache
110/// lines, but the sparse array is 4x smaller. N is the number of elements in
111/// the set.
112///
113/// For sets that may grow to thousands of elements, SparseT should be set to
114/// uint16_t or uint32_t.
115///
116/// @tparam ValueT The type of objects in the set.
117/// @tparam KeyFunctorT A functor that computes an unsigned index from KeyT.
118/// @tparam SparseT An unsigned integer type. See above.
119///
120template<typename ValueT,
121 typename KeyFunctorT = identity<unsigned>,
122 typename SparseT = uint8_t>
123class SparseSet {
124 static_assert(std::numeric_limits<SparseT>::is_integer &&
125 !std::numeric_limits<SparseT>::is_signed,
126 "SparseT must be an unsigned integer type");
127
128 using KeyT = typename KeyFunctorT::argument_type;
129 using DenseT = SmallVector<ValueT, 8>;
130 using size_type = unsigned;
131 DenseT Dense;
132 SparseT *Sparse = nullptr;
133 unsigned Universe = 0;
134 KeyFunctorT KeyIndexOf;
135 SparseSetValFunctor<KeyT, ValueT, KeyFunctorT> ValIndexOf;
136
137public:
138 using value_type = ValueT;
139 using reference = ValueT &;
140 using const_reference = const ValueT &;
141 using pointer = ValueT *;
142 using const_pointer = const ValueT *;
143
144 SparseSet() = default;
145 SparseSet(const SparseSet &) = delete;
146 SparseSet &operator=(const SparseSet &) = delete;
147 ~SparseSet() { free(Sparse); }
148
149 /// setUniverse - Set the universe size which determines the largest key the
150 /// set can hold. The universe must be sized before any elements can be
151 /// added.
152 ///
153 /// @param U Universe size. All object keys must be less than U.
154 ///
155 void setUniverse(unsigned U) {
156 // It's not hard to resize the universe on a non-empty set, but it doesn't
157 // seem like a likely use case, so we can add that code when we need it.
158 assert(empty() && "Can only resize universe on an empty map");
159 // Hysteresis prevents needless reallocations.
160 if (U >= Universe/4 && U <= Universe)
161 return;
162 free(Sparse);
163 // The Sparse array doesn't actually need to be initialized, so malloc
164 // would be enough here, but that will cause tools like valgrind to
165 // complain about branching on uninitialized data.
166 Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT)));
167 Universe = U;
168 }
169
170 // Import trivial vector stuff from DenseT.
171 using iterator = typename DenseT::iterator;
172 using const_iterator = typename DenseT::const_iterator;
173
174 const_iterator begin() const { return Dense.begin(); }
175 const_iterator end() const { return Dense.end(); }
176 iterator begin() { return Dense.begin(); }
177 iterator end() { return Dense.end(); }
178
179 /// empty - Returns true if the set is empty.
180 ///
181 /// This is not the same as BitVector::empty().
182 ///
183 bool empty() const { return Dense.empty(); }
184
185 /// size - Returns the number of elements in the set.
186 ///
187 /// This is not the same as BitVector::size() which returns the size of the
188 /// universe.
189 ///
190 size_type size() const { return Dense.size(); }
191
192 /// clear - Clears the set. This is a very fast constant time operation.
193 ///
194 void clear() {
195 // Sparse does not need to be cleared, see find().
196 Dense.clear();
197 }
198
199 /// findIndex - Find an element by its index.
200 ///
201 /// @param Idx A valid index to find.
202 /// @returns An iterator to the element identified by key, or end().
203 ///
204 iterator findIndex(unsigned Idx) {
205 assert(Idx < Universe && "Key out of range");
206 const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u;
207 for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride) {
208 const unsigned FoundIdx = ValIndexOf(Dense[i]);
209 assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?");
210 if (Idx == FoundIdx)
211 return begin() + i;
212 // Stride is 0 when SparseT >= unsigned. We don't need to loop.
213 if (!Stride)
214 break;
215 }
216 return end();
217 }
218
219 /// find - Find an element by its key.
220 ///
221 /// @param Key A valid key to find.
222 /// @returns An iterator to the element identified by key, or end().
223 ///
224 iterator find(const KeyT &Key) {
225 return findIndex(KeyIndexOf(Key));
226 }
227
228 const_iterator find(const KeyT &Key) const {
229 return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key));
230 }
231
232 /// Check if the set contains the given \c Key.
233 ///
234 /// @param Key A valid key to find.
235 bool contains(const KeyT &Key) const { return find(Key) == end() ? 0 : 1; }
236
237 /// count - Returns 1 if this set contains an element identified by Key,
238 /// 0 otherwise.
239 ///
240 size_type count(const KeyT &Key) const { return contains(Key) ? 1 : 0; }
241
242 /// insert - Attempts to insert a new element.
243 ///
244 /// If Val is successfully inserted, return (I, true), where I is an iterator
245 /// pointing to the newly inserted element.
246 ///
247 /// If the set already contains an element with the same key as Val, return
248 /// (I, false), where I is an iterator pointing to the existing element.
249 ///
250 /// Insertion invalidates all iterators.
251 ///
252 std::pair<iterator, bool> insert(const ValueT &Val) {
253 unsigned Idx = ValIndexOf(Val);
254 iterator I = findIndex(Idx);
255 if (I != end())
256 return std::make_pair(I, false);
257 Sparse[Idx] = size();
258 Dense.push_back(Val);
259 return std::make_pair(end() - 1, true);
260 }
261
262 /// array subscript - If an element already exists with this key, return it.
263 /// Otherwise, automatically construct a new value from Key, insert it,
264 /// and return the newly inserted element.
265 ValueT &operator[](const KeyT &Key) {
266 return *insert(ValueT(Key)).first;
267 }
268
269 ValueT pop_back_val() {
270 // Sparse does not need to be cleared, see find().
271 return Dense.pop_back_val();
272 }
273
274 /// erase - Erases an existing element identified by a valid iterator.
275 ///
276 /// This invalidates all iterators, but erase() returns an iterator pointing
277 /// to the next element. This makes it possible to erase selected elements
278 /// while iterating over the set:
279 ///
280 /// for (SparseSet::iterator I = Set.begin(); I != Set.end();)
281 /// if (test(*I))
282 /// I = Set.erase(I);
283 /// else
284 /// ++I;
285 ///
286 /// Note that end() changes when elements are erased, unlike std::list.
287 ///
288 iterator erase(iterator I) {
289 assert(unsigned(I - begin()) < size() && "Invalid iterator");
290 if (I != end() - 1) {
291 *I = Dense.back();
292 unsigned BackIdx = ValIndexOf(Dense.back());
293 assert(BackIdx < Universe && "Invalid key in set. Did object mutate?");
294 Sparse[BackIdx] = I - begin();
295 }
296 // This depends on SmallVector::pop_back() not invalidating iterators.
297 // std::vector::pop_back() doesn't give that guarantee.
298 Dense.pop_back();
299 return I;
300 }
301
302 /// erase - Erases an element identified by Key, if it exists.
303 ///
304 /// @param Key The key identifying the element to erase.
305 /// @returns True when an element was erased, false if no element was found.
306 ///
307 bool erase(const KeyT &Key) {
308 iterator I = find(Key);
309 if (I == end())
310 return false;
311 erase(I);
312 return true;
313 }
314};
315
316} // end namespace llvm
317
318#endif // LLVM_ADT_SPARSESET_H
319