History log of /external/llvm/unittests/ADT/DenseMapTest.cpp
Revision Date Author Comments (<<< Hide modified files) (Show modified files >>>)
cd81d94322a39503e4a3e87b6ee03d4fcb3465fb 21-Jul-2014 Stephen Hines <srhines@google.com> Update LLVM for rebase to r212749.

Includes a cherry-pick of:
r212948 - fixes a small issue with atomic calls

Change-Id: Ib97bd980b59f18142a69506400911a6009d9df18
36b56886974eae4f9c5ebc96befd3e7bfe5de338 24-Apr-2014 Stephen Hines <srhines@google.com> Update to LLVM 3.5a.

Change-Id: Ifadecab779f128e62e430c2b4f6ddd84953ed617
fbaf206f470b5a6a54811547641ee41368a2cccd 23-Oct-2012 Pete Cooper <peter_cooper@apple.com> 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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166492 91177308-0d34-0410-b5e6-96231b3b80d8
8dffa4a106b52d893388c94c24e365e14c468b7c 17-Jun-2012 Chandler Carruth <chandlerc@gmail.com> Add a unit test for 'swap', and fix a pile of bugs in

First, make it parse cleanly. Yay for uninstantiated methods.

Second, make the inline-buckets case work correctly. This is way
trickier than it should be due to the uninitialized values in empty and
tombstone buckets.

Finally fix a few typos that caused construction/destruction mismatches
in the counting unittest.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158641 91177308-0d34-0410-b5e6-96231b3b80d8
6446d7e6d641135bdf9dc315ed69d0b10067fbd6 17-Jun-2012 Chandler Carruth <chandlerc@gmail.com> Add tests for *DenesMap for both key and value types' construction and
destruction and fix a bug in SmallDenseMap they caught.

This is kind of a poor-man's version of the testing that just adds the
addresses to a set on construction and removes them on destruction. We
check that double construction and double destruction don't occur.
Amusingly enough, this is enough to catch a lot of SmallDenseMap issues
because we spend a lot of time with fixed stable addresses in the inline

The SmallDenseMap bug fix included makes grow() not double-destroy in
some cases. It also fixes a FIXME there, the code was pretty crappy. We
now don't have any wasted initialization, but we do move the entries in
inline bucket array an extra time. It's probably a better tradeoff, and
is much easier to get correct.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158639 91177308-0d34-0410-b5e6-96231b3b80d8
dd9d38d57bbd2161e04af90a9e03011afb039b16 17-Jun-2012 Chandler Carruth <chandlerc@gmail.com> Introduce a SmallDenseMap container that re-uses the existing DenseMap

This type includes an inline bucket array which is used initially. Once
it is exceeded, an array of 64 buckets is allocated on the heap. The
bucket count grows from there as needed. Some highlights of this

- The inline buffer is very carefully aligned, and so supports types
with alignment constraints.
- It works hard to avoid aliasing issues.
- Supports types with non-trivial constructors, destructors, copy
constructions, etc. It works reasonably hard to minimize copies and
unnecessary initialization. The most common initialization is to set
keys to the empty key, and so that should be fast if at all possible.

This class has a performance / space trade-off. It tries to optimize for
relatively small maps, and so packs the inline bucket array densely into
the object. It will be marginally slower than a normal DenseMap in a few
use patterns, so it isn't appropriate everywhere.

The unit tests for DenseMap have been generalized a bit to support
running over different map implementations in addition to different
key/value types. They've then been automatically extended to cover the
new container through the magic of GoogleTest's typed tests.

All of this is still a bit rough though. I'm going to be cleaning up
some aspects of the implementation, documenting things better, and
adding tests which include non-trivial types. As soon as I'm comfortable
with the correctness, I plan to switch existing users of SmallMap over
to this class as it is already more correct w.r.t. construction and
destruction of objects iin the map.

Thanks to Benjamin Kramer for all the reviews of this and the lead-up
patches. That said, more review on this would really be appreciated. As
I've noted a few times, I'm quite surprised how hard it is to get the
semantics for a hashtable-based map container with a small buffer
optimization correct. =]

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158638 91177308-0d34-0410-b5e6-96231b3b80d8
7027ba92dd7381188d3014d2ae1d9bedef9a218e 16-Jun-2012 Chandler Carruth <chandlerc@gmail.com> Work around a bug with MSVC 10 where it fails to recognize a valid use
of typename. GCC and Clang were fine with this, but MSVC won't accept
it. Fortunately, it also doesn't need it. Yuck.

Thanks to Nakamura for pointing this out in IRC.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158593 91177308-0d34-0410-b5e6-96231b3b80d8
e5c7bc65c30feabed5f05eecee1ff1433e35d381 16-Jun-2012 Chandler Carruth <chandlerc@gmail.com> Type parameterize the DenseMap unit tests.

These were already trying to be type parameterized over different
key/value pairs. I've realized this goal using GoogleTest's typed test
functionality. This allows us to easily replicate the tests across
different key/value combinations and soon different mapping templates.

I've fixed a few bugs in the tests and extended them a bit in the
process as many tests were only applying to the int->int mapping.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158589 91177308-0d34-0410-b5e6-96231b3b80d8
babd5980d8a8b4aad9814212a269f6197ebf1f2e 30-Jan-2012 Talin <viridia@gmail.com> DenseMap::find_as() and unit tests.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149229 91177308-0d34-0410-b5e6-96231b3b80d8
81cf4325698b48b02eddab921ac333c7f25005c3 10-Nov-2009 Jeffrey Yasskin <jyasskin@google.com> Fix DenseMap iterator constness.

This patch forbids implicit conversion of DenseMap::const_iterator to
DenseMap::iterator which was possible because DenseMapIterator inherited
(publicly) from DenseMapConstIterator. Conversion the other way around is now
allowed as one may expect.

The template DenseMapConstIterator is removed and the template parameter
IsConst which specifies whether the iterator is constant is added to

Actually IsConst parameter is not necessary since the constness can be
determined from KeyT but this is not relevant to the fix and can be addressed

Patch by Victor Zverovich!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86636 91177308-0d34-0410-b5e6-96231b3b80d8
c870bb5c96c14da387770685dc6f200442a7549d 07-Jan-2009 Misha Brukman <brukman+llvm@gmail.com> Minor cleanup for unittest:
* Fixed {copy,assignment} constructor test names
* s/EXPECT_EQ(true, ...)/ASSERT_TRUE(...)/

Patch by Talin.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61883 91177308-0d34-0410-b5e6-96231b3b80d8
8fb520eb4f06d4ef771abe9c22d85b2a275988ee 01-Jan-2009 Misha Brukman <brukman+llvm@gmail.com> Original patch by Talin.

* Added the first LLVM unittest -- DenseMap.
* Updated mkpatch utility to include llvm/unittests dir
* Added top-level target "unittests" to run all unittests

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61541 91177308-0d34-0410-b5e6-96231b3b80d8