History log of /external/llvm/include/llvm/ADT/DenseMap.h
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
/external/llvm/include/llvm/ADT/DenseMap.h
dce4a407a24b04eebc6a376f8e62b41aaa7b071f 29-May-2014 Stephen Hines <srhines@google.com> Update LLVM for 3.5 rebase (r209712).

Change-Id: I149556c940fb7dc92d075273c87ff584f400941f
/external/llvm/include/llvm/ADT/DenseMap.h
36b56886974eae4f9c5ebc96befd3e7bfe5de338 24-Apr-2014 Stephen Hines <srhines@google.com> Update to LLVM 3.5a.

Change-Id: Ifadecab779f128e62e430c2b4f6ddd84953ed617
/external/llvm/include/llvm/ADT/DenseMap.h
2aaa47f396f185d28aa7855d345f7385681098e2 30-Oct-2013 Howard Hinnant <hhinnant@apple.com> Rehash but don't grow when full of tombstones.

This problem was found and fixed by José Fonseca in March 2011 for
SmallPtrSet, committed r128566. But as far as I can tell, all other
llvm hash tables retain the same problem: the bucket count can grow
without bound while size() remains near constant by repeated
insert/erase cycles that tend to fill the container with tombstones.
Here is a demo that has been reduced to a trivial case:

int
main()
{
llvm::DenseSet<unsigned> d;
for (unsigned i = 0; i < 0xFFFFFFF; ++i)
{
d.insert(i);
d.erase(i);
}
}

While the container size() never grows above 1, the bucket count grows
like this:

nb = 64
nb = 128
nb = 256
nb = 512
nb = 1024
nb = 2048
nb = 4096
nb = 8192
nb = 16384
nb = 32768
nb = 65536
nb = 131072
nb = 262144
nb = 524288
nb = 1048576
nb = 2097152
nb = 4194304
nb = 8388608
nb = 16777216
nb = 33554432
nb = 67108864
nb = 134217728
nb = 268435456

The above program currently consumes a few GB ram. This patch brings
the memory consumption down by several orders of magnitude, and keeps
the bucket count at 64 for the above test.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193689 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
cbe40cfe96a6bb3f2da56445269c2c71e55e0e56 13-Sep-2013 Benjamin Kramer <benny.kra@googlemail.com> Add warn_unused_result to empty() on various containers.

empty() doesn't actually empty out the container, making this a common typo.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190708 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
4e31acb558a7f157244a11ae382c0138ee12d60b 16-Aug-2013 Aaron Ballman <aaron@aaronballman.com> Calling the base class constructor from the derived class' initializer list. This matches DenseMap's behavior, and silences some warnings.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188528 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
6e52c6164d499fac983f720540e9a8345f36f691 07-Aug-2013 Dmitri Gribenko <gribozavr@gmail.com> Remove the assertion for now. This breaks lld.

lld has a hashtable with StringRef keys; it needs to iterate over the keys in
*insertion* order. This is currently implemented as std::vector<StringRef> +
DenseMap<StringRef, T>. This will probably need a proper
DenseMapInfo<StringRef> if we don't want to lose memory/performance by
migrating to a different data structure.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187868 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
9e8eafa0f0ad36c3e4397e97b67b8245b04ba618 07-Aug-2013 Dmitri Gribenko <gribozavr@gmail.com> YAMLTraits.h: replace DenseMap that used a bad implementation of DenseMapInfo
for StringRef with a StringMap

The bug is that the empty key compares equal to the tombstone key.

Also added an assertion to DenseMap to catch similar bugs in future.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187866 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
da8b91a0731e34b97aadb0241ba6cefa4481cffa 01-Jun-2013 Benjamin Kramer <benny.kra@googlemail.com> DenseMap: Move the key into place when we use the move version of operator[].

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183074 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
711d324d50e5b335e98e576ce6725b056427e3f3 01-May-2013 Peng Cheng <gm4cheng@gmail.com> use static_cast to get rid of windows warning.

warning C4244: 'argument' : conversion from 'uint64_t' to 'const unsigned int', possible loss of data

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180846 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
cef6cfe4a67af030754b4151cd63076c4aab7467 13-Feb-2013 Craig Topper <craig.topper@gmail.com> Remove unnecessary condtional assignment. The next line ignores the result of the assignment with the same condition.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175042 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
289148afcb68b28e155ee87aa5a9efcf75adb444 14-Jan-2013 Joe Groff <arcata@gmail.com> Fix DenseMap when LLVM_HAS_RVALUE_REFERENCES is defined but equals 0.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172454 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
a662a9862501fc86904e90054f7c1519101d9126 14-Jan-2013 Joe Groff <arcata@gmail.com> Add DenseMap::insert(value_type&&) method.
Use the existing move implementation of the internal DenseMap::InsertIntoBucket
method to provide a user-facing move insert method.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172453 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
255cd6f317f3a0bad6e7939ca5ce49b33c6676f9 05-Jan-2013 NAKAMURA Takumi <geek4civic@gmail.com> Whitespace.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171601 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
5d295b41a3f4194778b6bc01a828b2115bd3a3f1 05-Jan-2013 NAKAMURA Takumi <geek4civic@gmail.com> DenseMap: Appease -fstrict-aliasing on g++-4.4.

With DenseMapInfo<Enum>, it is miscompiled on g++-4.4.

static inline Enum getEmptyKey() { return Enum(<arbitrary int/unsigned value>); }

isEauql(getEmptyKey(), ...)

The compiler mis-assumes the return value is not aliased to Enum.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171600 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
319120f6229dcf37f288be2719bc095a2f454d55 05-Jan-2013 Alex Rosenberg <alexr@leftfield.org> Fix warnings from llvm-gcc as seen on darwin10 (10.6).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171567 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
255f89faee13dc491cb64fbeae3c763e7e2ea4e6 03-Dec-2012 Chandler Carruth <chandlerc@gmail.com> Sort the #include lines for the include/... tree with the script.

AKA: Recompile *ALL* the source code!

This one went much better. No manual edits here. I spot-checked for
silliness and grep-checked for really broken edits and everything seemed
good. It all still compiles. Yell if you see something that looks goofy.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169133 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
4334dd96a9e622fdcf2825a8f73a2d941d67be72 30-Nov-2012 Chandler Carruth <chandlerc@gmail.com> Switch LLVM_USE_RVALUE_REFERENCES to LLVM_HAS_RVALUE_REFERENCES.

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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168996 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
99112c6b193c54409e2a3a5ea76c3759d5c1244c 24-Oct-2012 Pete Cooper <peter_cooper@apple.com> Improve DenseMap checks for power of 2 growth. Thanks for the tip Jakob

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166609 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
2430973fb657eb84dfbacb1e8886d3a29190e0b5 23-Oct-2012 Pete Cooper <peter_cooper@apple.com> Change DenseMap to use a power of 2 growth if one is given instead of the next power of 2. This was causing DenseMaps to grow 4x instead of 2x. I'll keep an eye on the buildbots as this could impact performance

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166493 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
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
/external/llvm/include/llvm/ADT/DenseMap.h
3bbdddf527c762085802544665d6e77471ea035b 22-Sep-2012 Jordan Rose <jordan_rose@apple.com> DenseMap: assert that we have found a bucket before we try to insert into it.

This silences literally dozens of analyzer warnings on LLVM (since DenseMap
is such a commonly-used class).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164438 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
cbeb8d9869aafec3c2c1ee0922f0a4d5bb4a916a 17-Aug-2012 Chandler Carruth <chandlerc@gmail.com> Flatten the aligned-char-array utility template to be a directly
templated union at the request of Richard Smith. This makes it
substantially easier to type. =]

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162072 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
b8ea08ca8c43016f5bc35e1a3b6557d414448fae 14-Aug-2012 Richard Smith <richard-llvm@metafoo.co.uk> Avoid undefined behavior in DenseMap::shrink_and_clear(). Log2_32_Ceil(0)
returns 32. This change mirrors the corresponding code in
SmallDenseMap::shrink_and_clear().


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161829 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
ce9a04132d1bf85967d6ad062d45dd75f148eef1 03-Jul-2012 Chandler Carruth <chandlerc@gmail.com> Micro-optimize this function a bit. This shrinks the generated code
some, and allows the routine to be inlined into common callers. The
various bits that hit this code in their hotpath seem slightly lower on
the profile, but I can't really measure a performance improvement as
everything seems to still be bottlenecked on likely cache misses. =/

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159648 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
ac24e251014de60a16558fc0a1f2340c334d2aa8 30-Jun-2012 Benjamin Kramer <benny.kra@googlemail.com> Avoid sign compare warning.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159481 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
90420105964371571ccacdf47771c6ca05db2e67 19-Jun-2012 David Blaikie <dblaikie@gmail.com> Don't copy a potentially-uninitialized variable.

Based on review discussion of r158638 with Chandler Carruth, Tobias von Koch, and Duncan Sands and a -Wmaybe-uninitialized warning from GCC.

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

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
/external/llvm/include/llvm/ADT/DenseMap.h
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
buffer.

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
/external/llvm/include/llvm/ADT/DenseMap.h
dd9d38d57bbd2161e04af90a9e03011afb039b16 17-Jun-2012 Chandler Carruth <chandlerc@gmail.com> 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. =]

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158638 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
48f4dcf0f7fd64df00839018d633944bc2464501 16-Jun-2012 Chandler Carruth <chandlerc@gmail.com> Lift the NumElements and NumTombstones members into the super class
rather than the base class. Add a pile of boilerplate to indirect around
this.

This is pretty ugly, but it allows the super class to change the
representation of these values, which will be key for doing
a SmallDenseMap.

Suggestions on better method structuring / naming are welcome, but keep
in mind that SmallDenseMap won't have an 'unsigned' member to expose
a reference to... =/

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158586 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
7f6c82a7e0fbf8ed012bc76471576c8cc42370a3 16-Jun-2012 Chandler Carruth <chandlerc@gmail.com> Factor DenseMap into a base class that implements the hashtable logic,
and a derived class that provides the allocation and growth strategy.

This is the first (and biggest) step toward building a SmallDenseMap
that actually behaves exactly the same as DenseMap, and supports all the
same types and interface points with the same semantics.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158585 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
14d81c416c72dc779dd31a81f68ebd6a6456f6f0 13-Jun-2012 Chandler Carruth <chandlerc@gmail.com> Group the 'unsigned' members after the pointer to avoid 4 bytes of
padding on x86-64.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158421 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
aad82963837af31c1e5b8b9c3ac282b0e826b18b 29-May-2012 Douglas Gregor <dgregor@apple.com> DenseMap's move assignment operator needs to return *this

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157644 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
8e337120133c746640246feb9383556d383a94be 28-May-2012 Benjamin Kramer <benny.kra@googlemail.com> DenseMap: Use an early exit when there is nothing to do in DestroyAll().

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157550 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ff 27-May-2012 Benjamin Kramer <benny.kra@googlemail.com> DenseMap: Provide a move ctor and move semantics for operator[] and FindAndConstruct.

The only missing part is insert(), which uses a pair of parameters and I haven't
figured out how to convert it to rvalue references. It's now possible to use a
DenseMap with std::unique_ptr values :)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157539 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
295d8ff007ef2c36a91141d7f7aa218f43c4c4b5 27-May-2012 Benjamin Kramer <benny.kra@googlemail.com> DenseMap: Factor destruction into a common helper method.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157538 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
ac5802bca0285eee49c1c372846552823d819181 19-May-2012 Benjamin Kramer <benny.kra@googlemail.com> Provide move semantics for TinyPtrVector and for DenseMap's rehash function.

This makes DenseMap<..., TinyPtrVector<...>> as cheap as it always should've been!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157113 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
4e58263459d7f9ae862b52adafe585b66411272f 06-Apr-2012 Benjamin Kramer <benny.kra@googlemail.com> DenseMap: Perform the pod-like object optimization when the value type is POD-like, not the DenseMapInfo for it.

Purge now unused template arguments. This has been broken since r91421. Patch by Lubos Lunak!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154170 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
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
/external/llvm/include/llvm/ADT/DenseMap.h
f0be7ca7e42915779175a9332c6baba18a2a840c 07-Jan-2012 Benjamin Kramer <benny.kra@googlemail.com> Port the trick to skip the check for empty buckets from StringMap to DenseMap.

This should fix the odd behavior that find() is slower than lookup().

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147731 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
18dceba0bb5e38250535401ecc9d9737943d0657 27-Jul-2011 Ted Kremenek <kremenek@apple.com> Add a generic 'capacity_in_bytes' function to allow inspection of memory usage of various data structures.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136233 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
776157ac926102de7a8e40e936dd9efcd7f9dd1b 28-Apr-2011 Chandler Carruth <chandlerc@gmail.com> Fix more -Wnon-pod-memset warnings.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130392 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
e6b693db8cc07be91229bef0d8577ce8b5caf34b 28-Apr-2011 Ted Kremenek <kremenek@apple.com> Add utility method to DenseMap to return the amount of memory used for its buckets.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130382 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
450ed1a05bd5e12c141629b0d0ba275958634980 28-Apr-2011 Chris Lattner <sabre@nondot.org> silence some -Wnon-pod-memset warnings, since std::pair is not POD.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130364 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
414fdbdb0104fdc8c570287f94df8bb697e7b7c1 30-Mar-2011 Jakob Stoklund Olesen <stoklund@2pi.dk> Prevent infinite growth of the DenseMap.

When the hash function uses object pointers all free entries eventually
become tombstones as they are used at least once, regardless of the size.

DenseMap cannot function with zero empty keys, so it double size to get
get ridof the tombstones.

However DenseMap never shrinks automatically unless it is cleared, so
the net result is that certain tables grow infinitely.

The solution is to make a fresh copy of the table without tombstones
instead of doubling size, by simply calling grow with the current size.

Patch by José Fonseca!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128564 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
d01f2633b9aab6281c936da04226b46a0dde7ba9 30-Mar-2011 Jay Foad <jay.foad@gmail.com> Fix more zero length memset warnings.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128543 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
e54f64899fbaaa95fc3241236aabfaa37003a658 07-Mar-2011 Duncan Sands <baldrick@free.fr> Often GCC can see that NumBuckets is zero here, resulting in a warning
about possibly swapped memset parameters. Avoid the warning.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127170 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
88b0c6a59a54a2d7b3763dfabb595ce0e09e658a 05-Mar-2011 Benjamin Kramer <benny.kra@googlemail.com> Avoid zero-sized allocations when copying a fresh DenseMap.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127110 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
49d443053bf6565f2420692b54f96abffa76f236 05-Mar-2011 Benjamin Kramer <benny.kra@googlemail.com> Lazily allocate DenseMaps.

This makes lookup slightly more expensive but it's worth it, unused
DenseMaps are common in LLVM code apparently.

1% speedup on clang -O3 bzip2.c
4% speedup on clang -O3 oggenc.c (Release build of clang on i386/linux)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127088 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
9d38acb254108db0ee9e746bb3f7aa64168f7e36 19-Dec-2010 Nick Lewycky <nicholas@mxc.ca> Use the new way of silencing this warning.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122195 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
476b242fe7a61e5f9ac6214b0bc5c680d24f152e 19-Dec-2010 Nick Lewycky <nicholas@mxc.ca> Add missing standard headers. Patch by Joerg Sonnenberger!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122193 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
e3955df639ff9aff990f628ef6a219ff5efdbc81 01-Sep-2010 Dan Gohman <gohman@apple.com> Make the iterator form of erase return void, since it always succeeds,
and since this is what std::map and std::set do.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112701 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
345b378309eabd74a7a43f095dca9a4894bc371e 10-Jun-2010 Duncan Sands <baldrick@free.fr> Add includes to get ptrdiff_t. This is needed by gcc-4.6 which has
done some more header trimming, resulting in cstdef being included
by less header files.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@105786 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
b843d9f833aa474ae700363a445b7409665c4a6e 17-May-2010 Jakob Stoklund Olesen <stoklund@2pi.dk> Optimize empty DenseMap iteration.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103962 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
ccb4f2d813380d8cf139062b8c829e4b8b322c0d 08-Mar-2010 Andrew Lenharth <andrewl@lenharth.org> Iterator traits and swap. closes PR6548 and PR6549

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97974 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
fcb0ee8ffeae12aa866f4e7da12a4dd2a1d0dc35 29-Jan-2010 Junjie Gu <jgu222@gmail.com> Make sure the size is doubled (not 4x).


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94845 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
6a363782fe4ecba4f0a72c2edf03596004470c4a 21-Dec-2009 Chris Lattner <sabre@nondot.org> add a helper ctor.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91819 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
4bbf4ee1491637c247e195e19e3e4a8ee5ad72fa 15-Dec-2009 Chris Lattner <sabre@nondot.org> Remove isPod() from DenseMapInfo, splitting it out to its own
isPodLike type trait. This is a generally useful type trait for
more than just DenseMap, and we really care about whether something
acts like a pod, not whether it really is a pod.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91421 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
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
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!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86636 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
4ab74cdc124af6b4f57c2d2d09548e01d64a1f34 23-Oct-2009 Jeffrey Yasskin <jyasskin@google.com> Fix stylistic and documentation problems in ValueMap found by Nick Lewycky and
Evan Cheng.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84967 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
127445818efd810b138dd5362129ab3c7f8b9963 07-Oct-2009 Torok Edwin <edwintorok@gmail.com> Add a comment explaining how DenseMap::insert works, because it is not
intuitive.
It does NOT update the value if the key is already in the map,
it also returns false if the key is already in the map, regardless
if the value matched.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83458 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
724f6751442e2006856a9365ef3d3bc6f1b31c98 11-Sep-2009 Chris Lattner <sabre@nondot.org> give densemap iterators real iterator traits.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81538 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
32859c71d6ba9cd5e38662611a73d82335f4ba41 30-Aug-2009 Chris Lattner <sabre@nondot.org> make DenseMap::clear() early exit if there is nothing to do.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@80480 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
a9ad04191cb56c42944b17980b8b2bb2afe11ab2 13-Aug-2009 Dan Gohman <gohman@apple.com> This void is implicit in C++.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78848 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
fb3af88ba75898896714d49c608b8daa4f106636 31-Jul-2009 Dan Gohman <gohman@apple.com> Split DenseMapInfo into a separate header file, so that it can be
included separately.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77693 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
d06c59821a1ca0191ea8a326a18509808a02ed03 21-Jul-2009 Torok Edwin <edwintorok@gmail.com> Add freed memory poisoning in !NDEBUG mode for DenseMap.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76597 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
f0e4cac7ebdee07639bd1fc3eadf204f45868556 01-May-2009 Stuart Hastings <stuart@apple.com> Prevent looping when DenseSet is abused.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70572 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
11d8fb960963a1f8a7e2b2972bc560a5b24cf216 25-Apr-2009 Chris Lattner <sabre@nondot.org> DenseMap.h needs <new> because it explicitly calls operator new/delete.
Patch by John McCall!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70068 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
dd255a62474a2016702e2985710e6e8910b3c974 01-Apr-2009 Chris Lattner <sabre@nondot.org> Add range insert method for DenseSet and define DenseMapInfo for chars.
Patch by Kevin Fan!



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@68239 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
bdd376ccb25f251e115fff24b526b4e65e03a1d3 31-Mar-2009 Chris Lattner <sabre@nondot.org> add some accessors so I can play games with DenseMaps.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@68145 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
f341a47d10501bc69b5d4d2217992bb6e08668d8 29-Mar-2009 Chris Lattner <sabre@nondot.org> When forming sentinels for empty/tombstone, make sure to respect the
pointer's expected number of zero low-bits.

This should fix the breakage I introduced recently.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@67990 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
d10aacea5e2c8ea62e08956aa0a94fa2da60e148 22-Jan-2009 Bill Wendling <isanbard@gmail.com> Get rid of warning about implicit 64-to-32 bit conversions.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62741 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
2f39b29170e0f69491fc5b73952725266ac32fb8 19-Jan-2009 Chris Lattner <sabre@nondot.org> improve compatibility with cygwin, patch by Jay Foad!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62535 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
3a54b3dc87a581c203b18050b4f787b4ca28a12c 09-Jan-2009 Misha Brukman <brukman+llvm@gmail.com> Removed trailing whitespace.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62000 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
b6bbe6320b4a60b7399eea08426aec834701d514 02-Dec-2008 Chris Lattner <sabre@nondot.org> add densemap range insertion method.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60400 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
b9118246201592e7e6c1353a09f69e8a4d469d9d 30-Nov-2008 Chris Lattner <sabre@nondot.org> fix indentation. std::pair is "isPod" if the first/second are both isPod.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60262 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
13e781ebe7a39e008dd5e5de78983e095e8a1d02 27-Oct-2008 David Greene <greened@obbligato.org> Add STL-style typedefs and default constructors to make it possible to
use DenseMap in more contexts.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@58256 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
7b75fbf224c0a2d181c35708a27c514ae798c904 29-Aug-2008 Daniel Dunbar <daniel@zuster.org> Add DenseMap::lookup:
/// lookup - Return the entry for the specified key, or a default
/// constructed value if no such entry exists.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55523 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
2dba6a1bdb7d78b4d1e5e69b81989816193e6b70 22-Aug-2008 Chris Lattner <sabre@nondot.org> consolidate DenseMapInfo implementations, and add one for std::pair.
Patch contributed by m-s.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55167 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
6b345ee9b2833cf1b2f79dc16d06d4060bec36ef 07-Jul-2008 Dan Gohman <gohman@apple.com> Make DenseMap's insert return a pair, to more closely resemble std::map.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53177 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
08c09496c2fa7c1da027a52d8c410c2ae98481e1 03-Jul-2008 Dan Gohman <gohman@apple.com> Use operator new instead of new char[].


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53067 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
2b7470eb54880ce7f74469d6e09eaf7f0864f8ab 17-Jun-2008 Owen Anderson <resistor@mac.com> Fix use of placement new to actually use an address.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52423 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
ae9f3a3b7c915f725aef5a7250e88eaeddda03c6 20-Feb-2008 Anton Korobeynikov <asl@math.spbu.ru> Unbreak build with gcc 4.3: provide missed includes and silence most annoying warnings.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47367 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
7ed47a13356daed2a34cd2209a31f92552e3bdd8 29-Dec-2007 Chris Lattner <sabre@nondot.org> Don't attribute in file headers anymore. See llvmdev for the
discussion of this change. Boy are my fingers tired. ;-)



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45411 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
aef806e9cb021919be8f3a988af0478f3da75758 01-Nov-2007 Ted Kremenek <kremenek@apple.com> Added typedef "value_type" to DenseMap (similar typedef appears in std::map).

Added method FindAndConstruct() to DenseMap, which does the same thing as
operator[], except that it refers value_type& (a reference to both the
key and mapped data pair). This method is useful for clients that wish
to access the stored key value, as opposed to the key used to do the
actual lookup (these need not always be the same).

Redefined operator[] to use FindAndConstruct() (same logic).


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43594 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
05831c073abbaacbf2fc21ef5ef160872056e075 09-Oct-2007 Chris Lattner <sabre@nondot.org> Fix problems where DenseMap used operator!= instead of correctly
calling the traits implementation of isEqual.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42782 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
f8a3ee1d637a747c87f72bc880445e6a82280ff0 07-Oct-2007 Chris Lattner <sabre@nondot.org> Finish off PR1723, by working around some strange compiler bug.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42737 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
d81ccc2806b2c8a498d16f1a547d0cc9c00d602d 24-Sep-2007 Daniel Berlin <dberlin@dberlin.org> Implement offline variable substitution in order to reduce memory
and time usage.
Fixup operator == to make this work, and add a resize method to DenseMap
so we can resize our hashtable once we know how big it should be.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42269 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
4938d347723d452786c1a7c1d1b9ec79121b0040 21-Sep-2007 Owen Anderson <resistor@mac.com> Fix CopyFrom for non-POD data types.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42208 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
76c1b97e4020faace8c95a127f1eab66c278fb58 17-Sep-2007 Chris Lattner <sabre@nondot.org> Merge DenseMapKeyInfo & DenseMapValueInfo into DenseMapInfo

Add a new DenseMapInfo::isEqual method to allow clients to redefine
the equality predicate used when probing the hash table.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42042 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
29ce95511f905df3a63e3b953a4a0179ead46865 11-Sep-2007 Owen Anderson <resistor@mac.com> Add a ValueInfoT template parameter to DenseMap so that it can properly make decisions
based on whether the key AND the value require ctors/dtors.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41837 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
98153ecbc1b29c576ff43a7718c3f657f81b8aac 11-Sep-2007 Owen Anderson <resistor@mac.com> Don't bother to initialize values corresponding to empty or tombstone
keys.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41834 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
9544dc294f63ce116fbab398a8874ebf834cf41e 11-Sep-2007 Owen Anderson <resistor@mac.com> Fix non-deterministic behavior in the DenseMap copy constructor.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41831 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
3d345631db71174ffc4997a88c09f21eb9ed052b 16-Aug-2007 Owen Anderson <resistor@mac.com> Forgot a line.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41115 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
67280e1dd22cf9fa452c335d1e2328d13f158da1 16-Aug-2007 Owen Anderson <resistor@mac.com> Add a copy constructor and an assignment operator to DenseMap.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41114 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
276222a5ae189ed5c6a2afb248d4c8f0335585b4 12-Aug-2007 Reid Spencer <rspencer@reidspencer.com> Change casts from old style to new style. This helps document the details
better, gives the compiler a chance to validate the cast and reduces warnings
if the user turns on -Wold-style-cast option.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41033 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
7b54452c84e478ab4d49ac08759ca4ec1badf2b2 05-Aug-2007 Chris Lattner <sabre@nondot.org> Fix a bug in DenseMap::clear, where we never reset a tombstone
to EmptyKey.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40839 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
42e4bdf2577946380ce1529d5716e48b33d4186d 05-Aug-2007 Chris Lattner <sabre@nondot.org> When clearing a SmallPtrSet, if the set had a huge capacity, but the
contents of the set were small, deallocate and shrink the set. This
avoids having us to memset as much data, significantly speeding up
some pathological cases. For example, this speeds up the verifier
from 0.3899s to 0.0763 (5.1x) on the testcase from PR1432 in a
release build.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40837 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
398b40671b13018f88371b74822fa8ee2638577e 20-Jul-2007 Owen Anderson <resistor@mac.com> Make the heuristic for shrinking DenseMap smarter.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40114 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
6ad5fde5d01e0c8c23b928583d2fb9489b1b5a36 20-Jul-2007 Owen Anderson <resistor@mac.com> Have DenseMap auto-shrink itself on clear(). This improves the time to optimize
403.gcc from 15.2s to 14.3s.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40100 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
569b935e6b23c4a0e4ebb2c96603974310ef0587 10-Feb-2007 Chris Lattner <sabre@nondot.org> Make find return the appropriate iterator/const_iterator


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34137 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
a76b1febd4fd258e8054395adedcbd477668d956 10-Feb-2007 Chris Lattner <sabre@nondot.org> Allow DenseMAp to take an explicit DenseMapKeyInfo


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34134 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
04a3115e619740245cbe34c8c7428b4bde7868f7 07-Feb-2007 Chris Lattner <sabre@nondot.org> Fix a really subtle bug where the entire hash table could fill with
tombstones, causing subsequent insertions to infinitely loop.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33972 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
28f72279f5aaf34ba62ae00ca3b8bb94d8b91f70 04-Feb-2007 Chris Lattner <sabre@nondot.org> add a version of insert that takes the key and value.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33856 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
5a5f6b6e38b7155200903816f22501cce4ca36a7 03-Feb-2007 Chris Lattner <sabre@nondot.org> 8 buckets is way too small to start out with. This was only for testing.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33835 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
137d4b253384adce88bfa2a1c37695d90f0a9d6c 02-Feb-2007 Chris Lattner <sabre@nondot.org> silence annoying warning in release-asserts build


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33797 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
70a76a633ed5101dbe472404efd989f4f1b3669c 02-Feb-2007 Chris Lattner <sabre@nondot.org> add find/erase, add const iterators, fix bugs in iterators.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33791 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
f6390f48e6324b0221d10a9c75ab625357d8a43a 02-Feb-2007 Chris Lattner <sabre@nondot.org> add iterators


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33790 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
6e94c00ab29e654125e845f3bce692a3764c1c11 01-Feb-2007 Chris Lattner <sabre@nondot.org> Add a new dense hash table implementation


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33751 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
94c002a190cd2e3a52b1510bc997e53d63af0b3b 01-Feb-2007 Chris Lattner <sabre@nondot.org> rename DenseMap to IndexedMap.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33749 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
30eed211c99246392edf49c1bc6e9fb2a8f7a0f6 30-Sep-2004 Alkis Evlogimenos <alkis@evlogimenos.com> Remove whitespace from the end of the line.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16624 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
8018a665b2fa8250f12e079b19459c662cdd27f0 09-Sep-2004 Chris Lattner <sabre@nondot.org> Add missing #include


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16256 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
df8d5e908fe83dafe98a05086956e7b0943af1e0 02-Sep-2004 Alkis Evlogimenos <alkis@evlogimenos.com> Pull in definition of std::unary_function.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16140 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
551ccae044b0ff658fe629dd67edd5ffe75d10e8 02-Sep-2004 Reid Spencer <rspencer@reidspencer.com> Changes For Bug 352
Move include/Config and include/Support into include/llvm/Config,
include/llvm/ADT and include/llvm/Support. From here on out, all LLVM
public header files must be under include/llvm/.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16137 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
fc093bd0810b6e726c02c2430f77618fd7255541 27-Aug-2004 Alkis Evlogimenos <alkis@evlogimenos.com> Add size member function.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16067 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
5501e568b396f3e58f3d642e77139c790eda9df9 26-Aug-2004 Alkis Evlogimenos <alkis@evlogimenos.com> Add default index functor (an identity functor). You could use a
vector directly to get the same functionality but using a DenseMap
makes the code more readable IMO.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16052 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
7c78afefe96669cc3eb886308291213415d9d7b0 26-Feb-2004 Chris Lattner <sabre@nondot.org> Fix a bug in the densemap that was killing the local allocator, and probably
other clients. The problem is that the nullVal member was left to the default
constructor to initialize, which for int's does nothing (ie, leaves it unspecified).

To get a zero value, we must use T(). It's C++ wonderful? :)


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11867 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
00fa65be8344944b080cd790678e027e10942ffd 26-Feb-2004 Chris Lattner <sabre@nondot.org> Fix typeo. grow() cannot shrink storage. clear() should really nuke storage


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11865 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h
4d0d864be3d9a698c4edfe36961a22126f041298 25-Feb-2004 Alkis Evlogimenos <alkis@evlogimenos.com> Add DenseMap template and actually use it for for mapping virtual regs
to objects.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11840 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/include/llvm/ADT/DenseMap.h