/home/arjun/llvm-project/llvm/include/llvm/ADT/SmallPtrSet.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer 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 SmallPtrSet class. See the doxygen comment for |
10 | | // SmallPtrSetImplBase for more details on the algorithm used. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_ADT_SMALLPTRSET_H |
15 | | #define LLVM_ADT_SMALLPTRSET_H |
16 | | |
17 | | #include "llvm/ADT/EpochTracker.h" |
18 | | #include "llvm/Support/Compiler.h" |
19 | | #include "llvm/Support/ReverseIteration.h" |
20 | | #include "llvm/Support/type_traits.h" |
21 | | #include <cassert> |
22 | | #include <cstddef> |
23 | | #include <cstdlib> |
24 | | #include <cstring> |
25 | | #include <initializer_list> |
26 | | #include <iterator> |
27 | | #include <utility> |
28 | | |
29 | | namespace llvm { |
30 | | |
31 | | /// SmallPtrSetImplBase - This is the common code shared among all the |
32 | | /// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one |
33 | | /// for small and one for large sets. |
34 | | /// |
35 | | /// Small sets use an array of pointers allocated in the SmallPtrSet object, |
36 | | /// which is treated as a simple array of pointers. When a pointer is added to |
37 | | /// the set, the array is scanned to see if the element already exists, if not |
38 | | /// the element is 'pushed back' onto the array. If we run out of space in the |
39 | | /// array, we grow into the 'large set' case. SmallSet should be used when the |
40 | | /// sets are often small. In this case, no memory allocation is used, and only |
41 | | /// light-weight and cache-efficient scanning is used. |
42 | | /// |
43 | | /// Large sets use a classic exponentially-probed hash table. Empty buckets are |
44 | | /// represented with an illegal pointer value (-1) to allow null pointers to be |
45 | | /// inserted. Tombstones are represented with another illegal pointer value |
46 | | /// (-2), to allow deletion. The hash table is resized when the table is 3/4 or |
47 | | /// more. When this happens, the table is doubled in size. |
48 | | /// |
49 | | class SmallPtrSetImplBase : public DebugEpochBase { |
50 | | friend class SmallPtrSetIteratorImpl; |
51 | | |
52 | | protected: |
53 | | /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'. |
54 | | const void **SmallArray; |
55 | | /// CurArray - This is the current set of buckets. If equal to SmallArray, |
56 | | /// then the set is in 'small mode'. |
57 | | const void **CurArray; |
58 | | /// CurArraySize - The allocated size of CurArray, always a power of two. |
59 | | unsigned CurArraySize; |
60 | | |
61 | | /// Number of elements in CurArray that contain a value or are a tombstone. |
62 | | /// If small, all these elements are at the beginning of CurArray and the rest |
63 | | /// is uninitialized. |
64 | | unsigned NumNonEmpty; |
65 | | /// Number of tombstones in CurArray. |
66 | | unsigned NumTombstones; |
67 | | |
68 | | // Helpers to copy and move construct a SmallPtrSet. |
69 | | SmallPtrSetImplBase(const void **SmallStorage, |
70 | | const SmallPtrSetImplBase &that); |
71 | | SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize, |
72 | | SmallPtrSetImplBase &&that); |
73 | | |
74 | | explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) |
75 | | : SmallArray(SmallStorage), CurArray(SmallStorage), |
76 | 30 | CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) { |
77 | 30 | assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && |
78 | 30 | "Initial size must be a power of two!"); |
79 | 30 | } |
80 | | |
81 | 0 | ~SmallPtrSetImplBase() { |
82 | 0 | if (!isSmall()) |
83 | 0 | free(CurArray); |
84 | 0 | } |
85 | | |
86 | | public: |
87 | | using size_type = unsigned; |
88 | | |
89 | | SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete; |
90 | | |
91 | 28 | LLVM_NODISCARD bool empty() const { return size() == 0; } |
92 | 28 | size_type size() const { return NumNonEmpty - NumTombstones; } |
93 | | |
94 | 0 | void clear() { |
95 | 0 | incrementEpoch(); |
96 | 0 | // If the capacity of the array is huge, and the # elements used is small, |
97 | 0 | // shrink the array. |
98 | 0 | if (!isSmall()) { |
99 | 0 | if (size() * 4 < CurArraySize && CurArraySize > 32) |
100 | 0 | return shrink_and_clear(); |
101 | 0 | // Fill the array with empty markers. |
102 | 0 | memset(CurArray, -1, CurArraySize * sizeof(void *)); |
103 | 0 | } |
104 | 0 |
|
105 | 0 | NumNonEmpty = 0; |
106 | 0 | NumTombstones = 0; |
107 | 0 | } |
108 | | |
109 | | protected: |
110 | 82 | static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); } |
111 | | |
112 | 74 | static void *getEmptyMarker() { |
113 | 74 | // Note that -1 is chosen to make clear() efficiently implementable with |
114 | 74 | // memset and because it's not a valid pointer value. |
115 | 74 | return reinterpret_cast<void*>(-1); |
116 | 74 | } |
117 | | |
118 | 144 | const void **EndPointer() const { |
119 | 144 | return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize; |
120 | 144 | } |
121 | | |
122 | | /// insert_imp - This returns true if the pointer was new to the set, false if |
123 | | /// it was already in the set. This is hidden from the client so that the |
124 | | /// derived class can check that the right type of pointer is passed in. |
125 | 22 | std::pair<const void *const *, bool> insert_imp(const void *Ptr) { |
126 | 22 | if (isSmall()) { |
127 | 22 | // Check to see if it is already in the set. |
128 | 22 | const void **LastTombstone = nullptr; |
129 | 22 | for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty; |
130 | 30 | APtr != E; ++APtr) { |
131 | 8 | const void *Value = *APtr; |
132 | 8 | if (Value == Ptr) |
133 | 0 | return std::make_pair(APtr, false); |
134 | 8 | if (Value == getTombstoneMarker()) |
135 | 0 | LastTombstone = APtr; |
136 | 8 | } |
137 | 22 | |
138 | 22 | // Did we find any tombstone marker? |
139 | 22 | if (LastTombstone != nullptr) { |
140 | 0 | *LastTombstone = Ptr; |
141 | 0 | --NumTombstones; |
142 | 0 | incrementEpoch(); |
143 | 0 | return std::make_pair(LastTombstone, true); |
144 | 0 | } |
145 | 22 | |
146 | 22 | // Nope, there isn't. If we stay small, just 'pushback' now. |
147 | 22 | if (NumNonEmpty < CurArraySize) { |
148 | 22 | SmallArray[NumNonEmpty++] = Ptr; |
149 | 22 | incrementEpoch(); |
150 | 22 | return std::make_pair(SmallArray + (NumNonEmpty - 1), true); |
151 | 22 | } |
152 | 0 | // Otherwise, hit the big set case, which will call grow. |
153 | 0 | } |
154 | 0 | return insert_imp_big(Ptr); |
155 | 0 | } |
156 | | |
157 | | /// erase_imp - If the set contains the specified pointer, remove it and |
158 | | /// return true, otherwise return false. This is hidden from the client so |
159 | | /// that the derived class can check that the right type of pointer is passed |
160 | | /// in. |
161 | 0 | bool erase_imp(const void * Ptr) { |
162 | 0 | const void *const *P = find_imp(Ptr); |
163 | 0 | if (P == EndPointer()) |
164 | 0 | return false; |
165 | 0 | |
166 | 0 | const void **Loc = const_cast<const void **>(P); |
167 | 0 | assert(*Loc == Ptr && "broken find!"); |
168 | 0 | *Loc = getTombstoneMarker(); |
169 | 0 | NumTombstones++; |
170 | 0 | return true; |
171 | 0 | } |
172 | | |
173 | | /// Returns the raw pointer needed to construct an iterator. If element not |
174 | | /// found, this will be EndPointer. Otherwise, it will be a pointer to the |
175 | | /// slot which stores Ptr; |
176 | 0 | const void *const * find_imp(const void * Ptr) const { |
177 | 0 | if (isSmall()) { |
178 | 0 | // Linear search for the item. |
179 | 0 | for (const void *const *APtr = SmallArray, |
180 | 0 | *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr) |
181 | 0 | if (*APtr == Ptr) |
182 | 0 | return APtr; |
183 | 0 | return EndPointer(); |
184 | 0 | } |
185 | 0 | |
186 | 0 | // Big set case. |
187 | 0 | auto *Bucket = FindBucketFor(Ptr); |
188 | 0 | if (*Bucket == Ptr) |
189 | 0 | return Bucket; |
190 | 0 | return EndPointer(); |
191 | 0 | } |
192 | | |
193 | | private: |
194 | 174 | bool isSmall() const { return CurArray == SmallArray; } |
195 | | |
196 | | std::pair<const void *const *, bool> insert_imp_big(const void *Ptr); |
197 | | |
198 | | const void * const *FindBucketFor(const void *Ptr) const; |
199 | | void shrink_and_clear(); |
200 | | |
201 | | /// Grow - Allocate a larger backing store for the buckets and move it over. |
202 | | void Grow(unsigned NewSize); |
203 | | |
204 | | protected: |
205 | | /// swap - Swaps the elements of two sets. |
206 | | /// Note: This method assumes that both sets have the same small size. |
207 | | void swap(SmallPtrSetImplBase &RHS); |
208 | | |
209 | | void CopyFrom(const SmallPtrSetImplBase &RHS); |
210 | | void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS); |
211 | | |
212 | | private: |
213 | | /// Code shared by MoveFrom() and move constructor. |
214 | | void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS); |
215 | | /// Code shared by CopyFrom() and copy constructor. |
216 | | void CopyHelper(const SmallPtrSetImplBase &RHS); |
217 | | }; |
218 | | |
219 | | /// SmallPtrSetIteratorImpl - This is the common base class shared between all |
220 | | /// instances of SmallPtrSetIterator. |
221 | | class SmallPtrSetIteratorImpl { |
222 | | protected: |
223 | | const void *const *Bucket; |
224 | | const void *const *End; |
225 | | |
226 | | public: |
227 | | explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) |
228 | 102 | : Bucket(BP), End(E) { |
229 | 102 | if (shouldReverseIterate()) { |
230 | 0 | RetreatIfNotValid(); |
231 | 0 | return; |
232 | 0 | } |
233 | 102 | AdvanceIfNotValid(); |
234 | 102 | } |
235 | | |
236 | 0 | bool operator==(const SmallPtrSetIteratorImpl &RHS) const { |
237 | 0 | return Bucket == RHS.Bucket; |
238 | 0 | } |
239 | 90 | bool operator!=(const SmallPtrSetIteratorImpl &RHS) const { |
240 | 90 | return Bucket != RHS.Bucket; |
241 | 90 | } |
242 | | |
243 | | protected: |
244 | | /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket |
245 | | /// that is. This is guaranteed to stop because the end() bucket is marked |
246 | | /// valid. |
247 | 152 | void AdvanceIfNotValid() { |
248 | 152 | assert(Bucket <= End); |
249 | 152 | while (Bucket != End && |
250 | 152 | (*Bucket == SmallPtrSetImplBase::getEmptyMarker() || |
251 | 74 | *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) |
252 | 0 | ++Bucket; |
253 | 152 | } |
254 | 0 | void RetreatIfNotValid() { |
255 | 0 | assert(Bucket >= End); |
256 | 0 | while (Bucket != End && |
257 | 0 | (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() || |
258 | 0 | Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) { |
259 | 0 | --Bucket; |
260 | 0 | } |
261 | 0 | } |
262 | | }; |
263 | | |
264 | | /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. |
265 | | template <typename PtrTy> |
266 | | class SmallPtrSetIterator : public SmallPtrSetIteratorImpl, |
267 | | DebugEpochBase::HandleBase { |
268 | | using PtrTraits = PointerLikeTypeTraits<PtrTy>; |
269 | | |
270 | | public: |
271 | | using value_type = PtrTy; |
272 | | using reference = PtrTy; |
273 | | using pointer = PtrTy; |
274 | | using difference_type = std::ptrdiff_t; |
275 | | using iterator_category = std::forward_iterator_tag; |
276 | | |
277 | | explicit SmallPtrSetIterator(const void *const *BP, const void *const *E, |
278 | | const DebugEpochBase &Epoch) |
279 | 102 | : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {} _ZN4llvm19SmallPtrSetIteratorIPNS_2cl10SubCommandEEC2EPKPKvS8_RKNS_14DebugEpochBaseE Line | Count | Source | 279 | 84 | : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {} |
_ZN4llvm19SmallPtrSetIteratorIPNS_2cl14OptionCategoryEEC2EPKPKvS8_RKNS_14DebugEpochBaseE Line | Count | Source | 279 | 18 | : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {} |
Unexecuted instantiation: _ZN4llvm19SmallPtrSetIteratorIPNS_2cl6OptionEEC2EPKPKvS8_RKNS_14DebugEpochBaseE Unexecuted instantiation: _ZN4llvm19SmallPtrSetIteratorIN4mlir5ValueEEC2EPKPKvS7_RKNS_14DebugEpochBaseE Unexecuted instantiation: _ZN4llvm19SmallPtrSetIteratorIPN4mlir9OperationEEC2EPKPKvS8_RKNS_14DebugEpochBaseE |
280 | | |
281 | | // Most methods are provided by the base class. |
282 | | |
283 | 52 | const PtrTy operator*() const { |
284 | 52 | assert(isHandleInSync() && "invalid iterator access!"); |
285 | 52 | if (shouldReverseIterate()) { |
286 | 0 | assert(Bucket > End); |
287 | 0 | return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1])); |
288 | 0 | } |
289 | 52 | assert(Bucket < End); |
290 | 52 | return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket)); |
291 | 52 | } _ZNK4llvm19SmallPtrSetIteratorIPNS_2cl10SubCommandEEdeEv Line | Count | Source | 283 | 46 | const PtrTy operator*() const { | 284 | 46 | assert(isHandleInSync() && "invalid iterator access!"); | 285 | 46 | if (shouldReverseIterate()) { | 286 | 0 | assert(Bucket > End); | 287 | 0 | return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1])); | 288 | 0 | } | 289 | 46 | assert(Bucket < End); | 290 | 46 | return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket)); | 291 | 46 | } |
_ZNK4llvm19SmallPtrSetIteratorIPNS_2cl14OptionCategoryEEdeEv Line | Count | Source | 283 | 6 | const PtrTy operator*() const { | 284 | 6 | assert(isHandleInSync() && "invalid iterator access!"); | 285 | 6 | if (shouldReverseIterate()) { | 286 | 0 | assert(Bucket > End); | 287 | 0 | return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1])); | 288 | 0 | } | 289 | 6 | assert(Bucket < End); | 290 | 6 | return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket)); | 291 | 6 | } |
|
292 | | |
293 | 50 | inline SmallPtrSetIterator& operator++() { // Preincrement |
294 | 50 | assert(isHandleInSync() && "invalid iterator access!"); |
295 | 50 | if (shouldReverseIterate()) { |
296 | 0 | --Bucket; |
297 | 0 | RetreatIfNotValid(); |
298 | 0 | return *this; |
299 | 0 | } |
300 | 50 | ++Bucket; |
301 | 50 | AdvanceIfNotValid(); |
302 | 50 | return *this; |
303 | 50 | } _ZN4llvm19SmallPtrSetIteratorIPNS_2cl10SubCommandEEppEv Line | Count | Source | 293 | 44 | inline SmallPtrSetIterator& operator++() { // Preincrement | 294 | 44 | assert(isHandleInSync() && "invalid iterator access!"); | 295 | 44 | if (shouldReverseIterate()) { | 296 | 0 | --Bucket; | 297 | 0 | RetreatIfNotValid(); | 298 | 0 | return *this; | 299 | 0 | } | 300 | 44 | ++Bucket; | 301 | 44 | AdvanceIfNotValid(); | 302 | 44 | return *this; | 303 | 44 | } |
_ZN4llvm19SmallPtrSetIteratorIPNS_2cl14OptionCategoryEEppEv Line | Count | Source | 293 | 6 | inline SmallPtrSetIterator& operator++() { // Preincrement | 294 | 6 | assert(isHandleInSync() && "invalid iterator access!"); | 295 | 6 | if (shouldReverseIterate()) { | 296 | 0 | --Bucket; | 297 | 0 | RetreatIfNotValid(); | 298 | 0 | return *this; | 299 | 0 | } | 300 | 6 | ++Bucket; | 301 | 6 | AdvanceIfNotValid(); | 302 | 6 | return *this; | 303 | 6 | } |
|
304 | | |
305 | | SmallPtrSetIterator operator++(int) { // Postincrement |
306 | | SmallPtrSetIterator tmp = *this; |
307 | | ++*this; |
308 | | return tmp; |
309 | | } |
310 | | }; |
311 | | |
312 | | /// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next |
313 | | /// power of two (which means N itself if N is already a power of two). |
314 | | template<unsigned N> |
315 | | struct RoundUpToPowerOfTwo; |
316 | | |
317 | | /// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a |
318 | | /// helper template used to implement RoundUpToPowerOfTwo. |
319 | | template<unsigned N, bool isPowerTwo> |
320 | | struct RoundUpToPowerOfTwoH { |
321 | | enum { Val = N }; |
322 | | }; |
323 | | template<unsigned N> |
324 | | struct RoundUpToPowerOfTwoH<N, false> { |
325 | | enum { |
326 | | // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets |
327 | | // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111. |
328 | | Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val |
329 | | }; |
330 | | }; |
331 | | |
332 | | template<unsigned N> |
333 | | struct RoundUpToPowerOfTwo { |
334 | | enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val }; |
335 | | }; |
336 | | |
337 | | /// A templated base class for \c SmallPtrSet which provides the |
338 | | /// typesafe interface that is common across all small sizes. |
339 | | /// |
340 | | /// This is particularly useful for passing around between interface boundaries |
341 | | /// to avoid encoding a particular small size in the interface boundary. |
342 | | template <typename PtrType> |
343 | | class SmallPtrSetImpl : public SmallPtrSetImplBase { |
344 | | using ConstPtrType = typename add_const_past_pointer<PtrType>::type; |
345 | | using PtrTraits = PointerLikeTypeTraits<PtrType>; |
346 | | using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>; |
347 | | |
348 | | protected: |
349 | | // Forward constructors to the base. |
350 | | using SmallPtrSetImplBase::SmallPtrSetImplBase; |
351 | | |
352 | | public: |
353 | | using iterator = SmallPtrSetIterator<PtrType>; |
354 | | using const_iterator = SmallPtrSetIterator<PtrType>; |
355 | | using key_type = ConstPtrType; |
356 | | using value_type = PtrType; |
357 | | |
358 | | SmallPtrSetImpl(const SmallPtrSetImpl &) = delete; |
359 | | |
360 | | /// Inserts Ptr if and only if there is no element in the container equal to |
361 | | /// Ptr. The bool component of the returned pair is true if and only if the |
362 | | /// insertion takes place, and the iterator component of the pair points to |
363 | | /// the element equal to Ptr. |
364 | 22 | std::pair<iterator, bool> insert(PtrType Ptr) { |
365 | 22 | auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); |
366 | 22 | return std::make_pair(makeIterator(p.first), p.second); |
367 | 22 | } _ZN4llvm15SmallPtrSetImplIPNS_2cl10SubCommandEE6insertES3_ Line | Count | Source | 364 | 16 | std::pair<iterator, bool> insert(PtrType Ptr) { | 365 | 16 | auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); | 366 | 16 | return std::make_pair(makeIterator(p.first), p.second); | 367 | 16 | } |
_ZN4llvm15SmallPtrSetImplIPNS_2cl14OptionCategoryEE6insertES3_ Line | Count | Source | 364 | 6 | std::pair<iterator, bool> insert(PtrType Ptr) { | 365 | 6 | auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); | 366 | 6 | return std::make_pair(makeIterator(p.first), p.second); | 367 | 6 | } |
Unexecuted instantiation: _ZN4llvm15SmallPtrSetImplIPNS_2cl6OptionEE6insertES3_ Unexecuted instantiation: _ZN4llvm15SmallPtrSetImplIN4mlir5ValueEE6insertES2_ Unexecuted instantiation: _ZN4llvm15SmallPtrSetImplIPN4mlir9OperationEE6insertES3_ |
368 | | |
369 | | /// erase - If the set contains the specified pointer, remove it and return |
370 | | /// true, otherwise return false. |
371 | 0 | bool erase(PtrType Ptr) { |
372 | 0 | return erase_imp(PtrTraits::getAsVoidPointer(Ptr)); |
373 | 0 | } |
374 | | /// count - Return 1 if the specified pointer is in the set, 0 otherwise. |
375 | 0 | size_type count(ConstPtrType Ptr) const { return find(Ptr) != end() ? 1 : 0; } |
376 | 0 | iterator find(ConstPtrType Ptr) const { |
377 | 0 | return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr))); |
378 | 0 | } |
379 | | |
380 | | template <typename IterT> |
381 | | void insert(IterT I, IterT E) { |
382 | | for (; I != E; ++I) |
383 | | insert(*I); |
384 | | } |
385 | | |
386 | | void insert(std::initializer_list<PtrType> IL) { |
387 | | insert(IL.begin(), IL.end()); |
388 | | } |
389 | | |
390 | 40 | iterator begin() const { |
391 | 40 | if (shouldReverseIterate()) |
392 | 0 | return makeIterator(EndPointer() - 1); |
393 | 40 | return makeIterator(CurArray); |
394 | 40 | } _ZNK4llvm15SmallPtrSetImplIPNS_2cl10SubCommandEE5beginEv Line | Count | Source | 390 | 34 | iterator begin() const { | 391 | 34 | if (shouldReverseIterate()) | 392 | 0 | return makeIterator(EndPointer() - 1); | 393 | 34 | return makeIterator(CurArray); | 394 | 34 | } |
_ZNK4llvm15SmallPtrSetImplIPNS_2cl14OptionCategoryEE5beginEv Line | Count | Source | 390 | 6 | iterator begin() const { | 391 | 6 | if (shouldReverseIterate()) | 392 | 0 | return makeIterator(EndPointer() - 1); | 393 | 6 | return makeIterator(CurArray); | 394 | 6 | } |
|
395 | 40 | iterator end() const { return makeIterator(EndPointer()); } _ZNK4llvm15SmallPtrSetImplIPNS_2cl10SubCommandEE3endEv Line | Count | Source | 395 | 34 | iterator end() const { return makeIterator(EndPointer()); } |
_ZNK4llvm15SmallPtrSetImplIPNS_2cl14OptionCategoryEE3endEv Line | Count | Source | 395 | 6 | iterator end() const { return makeIterator(EndPointer()); } |
Unexecuted instantiation: _ZNK4llvm15SmallPtrSetImplIPN4mlir9OperationEE3endEv |
396 | | |
397 | | private: |
398 | | /// Create an iterator that dereferences to same place as the given pointer. |
399 | 102 | iterator makeIterator(const void *const *P) const { |
400 | 102 | if (shouldReverseIterate()) |
401 | 0 | return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this); |
402 | 102 | return iterator(P, EndPointer(), *this); |
403 | 102 | } _ZNK4llvm15SmallPtrSetImplIPNS_2cl10SubCommandEE12makeIteratorEPKPKv Line | Count | Source | 399 | 84 | iterator makeIterator(const void *const *P) const { | 400 | 84 | if (shouldReverseIterate()) | 401 | 0 | return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this); | 402 | 84 | return iterator(P, EndPointer(), *this); | 403 | 84 | } |
_ZNK4llvm15SmallPtrSetImplIPNS_2cl14OptionCategoryEE12makeIteratorEPKPKv Line | Count | Source | 399 | 18 | iterator makeIterator(const void *const *P) const { | 400 | 18 | if (shouldReverseIterate()) | 401 | 0 | return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this); | 402 | 18 | return iterator(P, EndPointer(), *this); | 403 | 18 | } |
Unexecuted instantiation: _ZNK4llvm15SmallPtrSetImplIPNS_2cl6OptionEE12makeIteratorEPKPKv Unexecuted instantiation: _ZNK4llvm15SmallPtrSetImplIN4mlir5ValueEE12makeIteratorEPKPKv Unexecuted instantiation: _ZNK4llvm15SmallPtrSetImplIPN4mlir9OperationEE12makeIteratorEPKPKv |
404 | | }; |
405 | | |
406 | | /// Equality comparison for SmallPtrSet. |
407 | | /// |
408 | | /// Iterates over elements of LHS confirming that each value from LHS is also in |
409 | | /// RHS, and that no additional values are in RHS. |
410 | | template <typename PtrType> |
411 | | bool operator==(const SmallPtrSetImpl<PtrType> &LHS, |
412 | | const SmallPtrSetImpl<PtrType> &RHS) { |
413 | | if (LHS.size() != RHS.size()) |
414 | | return false; |
415 | | |
416 | | for (const auto *KV : LHS) |
417 | | if (!RHS.count(KV)) |
418 | | return false; |
419 | | |
420 | | return true; |
421 | | } |
422 | | |
423 | | /// Inequality comparison for SmallPtrSet. |
424 | | /// |
425 | | /// Equivalent to !(LHS == RHS). |
426 | | template <typename PtrType> |
427 | | bool operator!=(const SmallPtrSetImpl<PtrType> &LHS, |
428 | | const SmallPtrSetImpl<PtrType> &RHS) { |
429 | | return !(LHS == RHS); |
430 | | } |
431 | | |
432 | | /// SmallPtrSet - This class implements a set which is optimized for holding |
433 | | /// SmallSize or less elements. This internally rounds up SmallSize to the next |
434 | | /// power of two if it is not already a power of two. See the comments above |
435 | | /// SmallPtrSetImplBase for details of the algorithm. |
436 | | template<class PtrType, unsigned SmallSize> |
437 | | class SmallPtrSet : public SmallPtrSetImpl<PtrType> { |
438 | | // In small mode SmallPtrSet uses linear search for the elements, so it is |
439 | | // not a good idea to choose this value too high. You may consider using a |
440 | | // DenseSet<> instead if you expect many elements in the set. |
441 | | static_assert(SmallSize <= 32, "SmallSize should be small"); |
442 | | |
443 | | using BaseT = SmallPtrSetImpl<PtrType>; |
444 | | |
445 | | // Make sure that SmallSize is a power of two, round up if not. |
446 | | enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val }; |
447 | | /// SmallStorage - Fixed size storage used in 'small mode'. |
448 | | const void *SmallStorage[SmallSizePowTwo]; |
449 | | |
450 | | public: |
451 | 30 | SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {} _ZN4llvm11SmallPtrSetIPNS_2cl10SubCommandELj1EEC2Ev Line | Count | Source | 451 | 26 | SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {} |
Unexecuted instantiation: _ZN4llvm11SmallPtrSetIPNS_2cl6OptionELj32EEC2Ev _ZN4llvm11SmallPtrSetIPNS_2cl14OptionCategoryELj16EEC2Ev Line | Count | Source | 451 | 2 | SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {} |
_ZN4llvm11SmallPtrSetIPNS_2cl10SubCommandELj4EEC2Ev Line | Count | Source | 451 | 2 | SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {} |
Unexecuted instantiation: _ZN4llvm11SmallPtrSetIN4mlir5ValueELj8EEC2Ev Unexecuted instantiation: _ZN4llvm11SmallPtrSetIPN4mlir9OperationELj4EEC2Ev |
452 | | SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {} |
453 | | SmallPtrSet(SmallPtrSet &&that) |
454 | | : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {} |
455 | | |
456 | | template<typename It> |
457 | | SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) { |
458 | | this->insert(I, E); |
459 | | } |
460 | | |
461 | | SmallPtrSet(std::initializer_list<PtrType> IL) |
462 | | : BaseT(SmallStorage, SmallSizePowTwo) { |
463 | | this->insert(IL.begin(), IL.end()); |
464 | | } |
465 | | |
466 | | SmallPtrSet<PtrType, SmallSize> & |
467 | 2 | operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) { |
468 | 2 | if (&RHS != this) |
469 | 2 | this->CopyFrom(RHS); |
470 | 2 | return *this; |
471 | 2 | } |
472 | | |
473 | | SmallPtrSet<PtrType, SmallSize> & |
474 | | operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) { |
475 | | if (&RHS != this) |
476 | | this->MoveFrom(SmallSizePowTwo, std::move(RHS)); |
477 | | return *this; |
478 | | } |
479 | | |
480 | | SmallPtrSet<PtrType, SmallSize> & |
481 | | operator=(std::initializer_list<PtrType> IL) { |
482 | | this->clear(); |
483 | | this->insert(IL.begin(), IL.end()); |
484 | | return *this; |
485 | | } |
486 | | |
487 | | /// swap - Swaps the elements of two sets. |
488 | | void swap(SmallPtrSet<PtrType, SmallSize> &RHS) { |
489 | | SmallPtrSetImplBase::swap(RHS); |
490 | | } |
491 | | }; |
492 | | |
493 | | } // end namespace llvm |
494 | | |
495 | | namespace std { |
496 | | |
497 | | /// Implement std::swap in terms of SmallPtrSet swap. |
498 | | template<class T, unsigned N> |
499 | | inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) { |
500 | | LHS.swap(RHS); |
501 | | } |
502 | | |
503 | | } // end namespace std |
504 | | |
505 | | #endif // LLVM_ADT_SMALLPTRSET_H |