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