Introduce a SmallDenseMap container that re-uses the existing DenseMap
implementation.

This type includes an inline bucket array which is used initially. Once
it is exceeded, an array of 64 buckets

Introduce a SmallDenseMap container that re-uses the existing DenseMap
implementation.

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
implementation:

- 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. =]

llvm-svn: 158638

show more ...

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

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.

llvm-svn: 158593

show more ...

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. Thi

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.

llvm-svn: 158589

show more ...

DenseMap::find_as() and unit tests.

llvm-svn: 149229

Fix DenseMap iterator constness.

This patch forbids implicit conversion of DenseMap::const_iterator to
DenseMap::iterator which was possible because DenseMapIterator inherited
(publicly) from DenseM

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
DenseMapIterator.

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
later.

Patch by Victor Zverovich!

llvm-svn: 86636

show more ...

Minor cleanup for unittest:
* Fixed {copy,assignment} constructor test names
* s/EXPECT_EQ(true, ...)/ASSERT_TRUE(...)/

Patch by Talin.

llvm-svn: 61883

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

llvm-svn: 615

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

llvm-svn: 61541

show more ...