Page MenuHomePhabricator

[SmallSet] Add SmallSetIterator.

Authored by fhahn on Jun 8 2018, 6:16 AM.



This patch adds a simple const_iterator implementation for SmallSet by
delegating to either a SmallVector::const_iterator or
std::set::const_iterator, depending on which storage is used by the

The motivation for adding this is D46827, where it is helpful to iterate
over a SmallSet.

Diff Detail

Event Timeline

fhahn created this revision.Jun 8 2018, 6:16 AM
dblaikie added inline comments.Jun 8 2018, 11:11 AM

Any chance using iterator_facade (in include/llvm/ADT/iterator.h) would help simplify this implementation?


Might make sense to put isSmall after the union for packing reasons (eg: if the iterators are 24 bits long and require 32 bit alignment - the existing ordering would create a 64 bit total size, but swapping it around would allow a 32 bit size, I think?)?


Does this test both the small and non-small cases?

fhahn updated this revision to Diff 151350.Jun 14 2018, 7:49 AM

Thanks for having a look. I've updated the patch to use iterator_facade_base and changed the test to test both the big and small case.

dblaikie added inline comments.Jun 14 2018, 12:17 PM

I imagine this type needs user-defined special members (copy/move ctors and copy/move assignment operators) - the usual "rule of 5" (the user-defined dtor being an indicator here)


I'd probably put a blank line between these two lines - can look a bit confusing otherwise (similarly below).

And/or maybe skip the explicit scopes here - could move the std::vector declaration up to the s1 declaration, and replace the iter+iter ctor with v.assign(iter, iter) instead.

fhahn added inline comments.Jun 14 2018, 2:40 PM

It looks like both the set and SmallVector iterators have trivial ctors/dtors and move/assignment operators. So it seems like the destructor is not needed either, at least the compiler does not complain about any missing functions. Would it be safe to get rid of the dtor instead in this case?

dblaikie added inline comments.Jun 14 2018, 2:42 PM

Might be OK to remove them if you add in some static_asserts that all the relevant members (all 5) are trivial?

fhahn updated this revision to Diff 151463.Jun 15 2018, 1:05 AM

Replace unneeded destructor with static assertion making sure everything required by the rule of five is trivial. I also updated the test as suggested and added another test with a type with non-trivial ctors/dtor.

dblaikie accepted this revision.Jun 15 2018, 1:31 PM

Seems good to me (:

This revision is now accepted and ready to land.Jun 15 2018, 1:31 PM
Closed by commit rL334887: [SmallSet] Add SmallSetIterator. (authored by fhahn, committed by ). · Explain WhyJun 16 2018, 5:40 AM
This revision was automatically updated to reflect the committed changes.
fhahn added a comment.Jun 16 2018, 9:01 AM

I had to revert this, as libstdc++ 4.8 does not have the is_trivially_XXX<T> helpers :(

fhahn added a comment.Jul 11 2018, 9:28 AM

Recommitted as rL336805, with only the subset of is_trivially_XXX provided by GCC 4.8 and llvm/Support/type_traits.h

fhahn added a comment.Jul 13 2018, 9:21 AM

The windows bots have surfaced another problem: set<T>::const_iterator is not trivially copy constructible... Not sure how to best work around that yet.

fhahn added a comment.Jul 13 2018, 9:22 AM

err, hit send too soon: not trivially copy constructible in MSVC's STL.

It might worth updating the Programmer's Manual, it still states that SmallSet has no support for iteration.