being power-of-two sized.

llvm-svn: 178332

llvm-svn: 175730

Code review feedback for r175580 by Jordan Rose.

llvm-svn: 175729

llvm-svn: 175621

Code review feedback on r175580 from Jordan Rose.

llvm-svn: 175595

This generalizes Optional to require less from the T type by using aligned
storage for backing & placement new/deleting the T into it when necessary.

Also includes unit tests.

llvm-svn: 175580

llvm-svn: 175538

PR15138 was opened because of a segfault in the Bitcode writer.
The actual issue ended up being a bug in APInt where calls to
APInt::getActiveWords returns a bogus value when the APInt value
is 0.  This patch fixes the problem by ensuring that getActiveWords
returns 1 for 0 valued APInts.

llvm-svn: 174641

As a bonus I put in some extra checks to make sure that we are identifying the
machine word of various Mac OS X/iOS targets appropriately.

llvm-svn: 173994

llvm-svn: 173513

llvm-svn: 173505

Fixes PR15054.

llvm-svn: 173459

llvm-svn: 173144

llvm-svn: 173127

A SparseMultiSet adds multiset behavior to SparseSet, while retaining SparseSet's desirable properties. Essentially, SparseMultiSet provides multiset behavior by storing its dense data in doubly linked lists that are inlined into the dense vector. This allows it to provide good data locality as well as vector-like constant-time clear() and fast constant time find(), insert(), and erase(). It also allows SparseMultiSet to have a builtin recycler rather than keeping SparseSet's behavior of always swapping upon removal, which allows it to preserve more iterators. It's often a better alternative to a SparseSet of a growable container or vector-of-vector.

llvm-svn: 173064

llvm-svn: 171764

The iplist::clear() function can be quite expensive because it traverses
the entire list, calling deleteNode() and removeNodeFromList() on each
element. If node destruction and deallocation can be handled some other
way, clearAndLeakNodesUnsafely() can be used to jettison all nodes
without bringing them into cache.

The function name is meant to be ominous.

llvm-svn: 171540

llvm-svn: 171363

The single-element ilist::splice() function supports a noop move:

  List.splice(I, List, I);

The corresponding std::list function doesn't allow that, so add a unit
test to document that behavior.

This also means that

  List.splice(I, List, F);

is somewhat surprisingly not equivalent to

  List.splice(I, List, F, next(F));

This patch adds an assertion to catch the illegal case I == F above.
Alternatively, we could make I == F a legal noop, but that would make
ilist differ even more from std::list.

llvm-svn: 170443

llvm-svn: 169250

Rationale:
1) This was the name in the comment block. ;]
2) It matches Clang's __has_feature naming convention.
3) It matches other compiler-feature-test conventions.

Sorry for the noise. =]

I've also switch the comment block to use a \brief tag and not duplicate
the name.

llvm-svn: 168996

This is safe for x87 long doubles and ppc double doubles too.

llvm-svn: 167582

treating it as if it were an IEEE floating-point type with 106-bit
mantissa.

This makes compile-time arithmetic on "long double" for PowerPC
in clang (in particular parsing of floating point constants)
work, and fixes all "long double" related failures in the test
suite.

llvm-svn: 166951

Fixed bug in SmallDenseMap where it wouldn't leave enough space for an empty bucket if the number of values was exactly equal to the small capacity.  This led to an infinite loop when finding a non-existent element

llvm-svn: 166492

Fix a bug in the set(I,E)/reset(I,E) methods that I recently added.  The boundary condition for checking if I and E were in the same word were incorrect, and, beyond that, the mask computation was not using a wide enough constant.

llvm-svn: 166015

Add range-based set()/reset() to BitVector.  These allow fast setting/resetting of ranges of bits, particularly useful when dealing with very large BitVector's.

llvm-svn: 165984

llvm-svn: 165908

Add a basic unit test for ImmutableMap. Found by inspection.

llvm-svn: 165907

llvm-svn: 165792

llvm-svn: 165147

Don't call getAsUnsignedInteger directly, it fails to compile if uint64_t is not "unsigned long long".

while there add more test cases.

llvm-svn: 165140

llvm-svn: 165136

APFloat::roundToIntegral: Special values don't keep the exponent value up to date, don't rely on it.

Add a couple of unit tests for special floats. Fixes 13929, found by MemorySanitizer.

llvm-svn: 164698

llvm-svn: 163979

llvm-svn: 162918

Fix another roundToIntegral bug where very large values could become infinity.  Problem and solution identified by Steve Canon.

llvm-svn: 161969

Fix a problem with APFloat::roundToIntegral where it would return incorrect results for negative inputs to trunc.  Add unit tests to verify this behavior.

llvm-svn: 161929

TinyPtrVector. With these, it is sufficiently functional for my more
normal / pedestrian uses.

I've not included some r-value reference stuff here because the value
type for a TinyPtrVector is, necessarily, just a pointer.

I've added tests that cover the basic behavior of these routines, but
they aren't as comprehensive as I'd like. In particular, they don't
really test the iterator semantics as thoroughly as they should. Maybe
some brave soul will feel enterprising and flesh them out. ;]

llvm-svn: 161104

re-use allocated vectors as much as possible.

llvm-svn: 161041

for this class. These tests exercise most of the basic properties, but
the API for TinyPtrVector is very strange currently. My plan is to start
fleshing out the API to match that of SmallVector, but I wanted a test
for what is there first.

Sadly, it doesn't look reasonable to just re-use the SmallVector tests,
as this container can only ever store pointers, and much of the
SmallVector testing is to get construction and destruction right.

Just to get this basic test working, I had to add value_type to the
interface.

While here I found a subtle bug in the combination of 'erase', 'begin',
and 'end'. Both 'begin' and 'end' wanted to use a null pointer to
indicate the "end" iterator of an empty vector, regardless of whether
there is actually a vector allocated or the pointer union is null.
Everything else was fine with this except for erase. If you erase the
last element of a vector after it has held more than one element, we
return the end iterator of the underlying SmallVector which need not be
a null pointer. Instead, simply use the pointer, and poniter + size()
begin/end definitions in the tiny case, and delegate to the inner vector
whenever it is present.

llvm-svn: 161024