1 //===- llvm/unittest/ADT/DenseMapMap.cpp - DenseMap unit tests --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/ADT/DenseMap.h"
11 #include "gtest/gtest.h"
19 uint32_t getTestKey(int i
, uint32_t *) { return i
; }
20 uint32_t getTestValue(int i
, uint32_t *) { return 42 + i
; }
22 uint32_t *getTestKey(int i
, uint32_t **) {
23 static uint32_t dummy_arr1
[8192];
24 assert(i
< 8192 && "Only support 8192 dummy keys.");
25 return &dummy_arr1
[i
];
27 uint32_t *getTestValue(int i
, uint32_t **) {
28 static uint32_t dummy_arr1
[8192];
29 assert(i
< 8192 && "Only support 8192 dummy keys.");
30 return &dummy_arr1
[i
];
33 /// A test class that tries to check that construction and destruction
36 static std::set
<CtorTester
*> Constructed
;
40 explicit CtorTester(int Value
= 0) : Value(Value
) {
41 EXPECT_TRUE(Constructed
.insert(this).second
);
43 CtorTester(uint32_t Value
) : Value(Value
) {
44 EXPECT_TRUE(Constructed
.insert(this).second
);
46 CtorTester(const CtorTester
&Arg
) : Value(Arg
.Value
) {
47 EXPECT_TRUE(Constructed
.insert(this).second
);
49 CtorTester
&operator=(const CtorTester
&) = default;
51 EXPECT_EQ(1u, Constructed
.erase(this));
53 operator uint32_t() const { return Value
; }
55 int getValue() const { return Value
; }
56 bool operator==(const CtorTester
&RHS
) const { return Value
== RHS
.Value
; }
59 std::set
<CtorTester
*> CtorTester::Constructed
;
61 struct CtorTesterMapInfo
{
62 static inline CtorTester
getEmptyKey() { return CtorTester(-1); }
63 static inline CtorTester
getTombstoneKey() { return CtorTester(-2); }
64 static unsigned getHashValue(const CtorTester
&Val
) {
65 return Val
.getValue() * 37u;
67 static bool isEqual(const CtorTester
&LHS
, const CtorTester
&RHS
) {
72 CtorTester
getTestKey(int i
, CtorTester
*) { return CtorTester(i
); }
73 CtorTester
getTestValue(int i
, CtorTester
*) { return CtorTester(42 + i
); }
75 // Test fixture, with helper functions implemented by forwarding to global
76 // function overloads selected by component types of the type parameter. This
77 // allows all of the map implementations to be tested with shared
78 // implementations of helper routines.
80 class DenseMapTest
: public ::testing::Test
{
84 static typename
T::key_type
*const dummy_key_ptr
;
85 static typename
T::mapped_type
*const dummy_value_ptr
;
87 typename
T::key_type
getKey(int i
= 0) {
88 return getTestKey(i
, dummy_key_ptr
);
90 typename
T::mapped_type
getValue(int i
= 0) {
91 return getTestValue(i
, dummy_value_ptr
);
96 typename
T::key_type
*const DenseMapTest
<T
>::dummy_key_ptr
= nullptr;
98 typename
T::mapped_type
*const DenseMapTest
<T
>::dummy_value_ptr
= nullptr;
100 // Register these types for testing.
101 typedef ::testing::Types
<DenseMap
<uint32_t, uint32_t>,
102 DenseMap
<uint32_t *, uint32_t *>,
103 DenseMap
<CtorTester
, CtorTester
, CtorTesterMapInfo
>,
104 SmallDenseMap
<uint32_t, uint32_t>,
105 SmallDenseMap
<uint32_t *, uint32_t *>,
106 SmallDenseMap
<CtorTester
, CtorTester
, 4,
109 TYPED_TEST_CASE(DenseMapTest
, DenseMapTestTypes
);
112 TYPED_TEST(DenseMapTest
, EmptyIntMapTest
) {
114 EXPECT_EQ(0u, this->Map
.size());
115 EXPECT_TRUE(this->Map
.empty());
118 EXPECT_TRUE(this->Map
.begin() == this->Map
.end());
121 EXPECT_FALSE(this->Map
.count(this->getKey()));
122 EXPECT_TRUE(this->Map
.find(this->getKey()) == this->Map
.end());
123 #if !defined(_MSC_VER) || defined(__clang__)
124 EXPECT_EQ(typename
TypeParam::mapped_type(),
125 this->Map
.lookup(this->getKey()));
127 // MSVC, at least old versions, cannot parse the typename to disambiguate
128 // TypeParam::mapped_type as a type. However, because MSVC doesn't implement
129 // two-phase name lookup, it also doesn't require the typename. Deal with
130 // this mutual incompatibility through specialized code.
131 EXPECT_EQ(TypeParam::mapped_type(),
132 this->Map
.lookup(this->getKey()));
136 // Constant map tests
137 TYPED_TEST(DenseMapTest
, ConstEmptyMapTest
) {
138 const TypeParam
&ConstMap
= this->Map
;
139 EXPECT_EQ(0u, ConstMap
.size());
140 EXPECT_TRUE(ConstMap
.empty());
141 EXPECT_TRUE(ConstMap
.begin() == ConstMap
.end());
144 // A map with a single entry
145 TYPED_TEST(DenseMapTest
, SingleEntryMapTest
) {
146 this->Map
[this->getKey()] = this->getValue();
149 EXPECT_EQ(1u, this->Map
.size());
150 EXPECT_FALSE(this->Map
.begin() == this->Map
.end());
151 EXPECT_FALSE(this->Map
.empty());
154 typename
TypeParam::iterator it
= this->Map
.begin();
155 EXPECT_EQ(this->getKey(), it
->first
);
156 EXPECT_EQ(this->getValue(), it
->second
);
158 EXPECT_TRUE(it
== this->Map
.end());
161 EXPECT_TRUE(this->Map
.count(this->getKey()));
162 EXPECT_TRUE(this->Map
.find(this->getKey()) == this->Map
.begin());
163 EXPECT_EQ(this->getValue(), this->Map
.lookup(this->getKey()));
164 EXPECT_EQ(this->getValue(), this->Map
[this->getKey()]);
167 // Test clear() method
168 TYPED_TEST(DenseMapTest
, ClearTest
) {
169 this->Map
[this->getKey()] = this->getValue();
172 EXPECT_EQ(0u, this->Map
.size());
173 EXPECT_TRUE(this->Map
.empty());
174 EXPECT_TRUE(this->Map
.begin() == this->Map
.end());
177 // Test erase(iterator) method
178 TYPED_TEST(DenseMapTest
, EraseTest
) {
179 this->Map
[this->getKey()] = this->getValue();
180 this->Map
.erase(this->Map
.begin());
182 EXPECT_EQ(0u, this->Map
.size());
183 EXPECT_TRUE(this->Map
.empty());
184 EXPECT_TRUE(this->Map
.begin() == this->Map
.end());
187 // Test erase(value) method
188 TYPED_TEST(DenseMapTest
, EraseTest2
) {
189 this->Map
[this->getKey()] = this->getValue();
190 this->Map
.erase(this->getKey());
192 EXPECT_EQ(0u, this->Map
.size());
193 EXPECT_TRUE(this->Map
.empty());
194 EXPECT_TRUE(this->Map
.begin() == this->Map
.end());
197 // Test insert() method
198 TYPED_TEST(DenseMapTest
, InsertTest
) {
199 this->Map
.insert(std::make_pair(this->getKey(), this->getValue()));
200 EXPECT_EQ(1u, this->Map
.size());
201 EXPECT_EQ(this->getValue(), this->Map
[this->getKey()]);
204 // Test copy constructor method
205 TYPED_TEST(DenseMapTest
, CopyConstructorTest
) {
206 this->Map
[this->getKey()] = this->getValue();
207 TypeParam
copyMap(this->Map
);
209 EXPECT_EQ(1u, copyMap
.size());
210 EXPECT_EQ(this->getValue(), copyMap
[this->getKey()]);
213 // Test copy constructor method where SmallDenseMap isn't small.
214 TYPED_TEST(DenseMapTest
, CopyConstructorNotSmallTest
) {
215 for (int Key
= 0; Key
< 5; ++Key
)
216 this->Map
[this->getKey(Key
)] = this->getValue(Key
);
217 TypeParam
copyMap(this->Map
);
219 EXPECT_EQ(5u, copyMap
.size());
220 for (int Key
= 0; Key
< 5; ++Key
)
221 EXPECT_EQ(this->getValue(Key
), copyMap
[this->getKey(Key
)]);
224 // Test copying from a default-constructed map.
225 TYPED_TEST(DenseMapTest
, CopyConstructorFromDefaultTest
) {
226 TypeParam
copyMap(this->Map
);
228 EXPECT_TRUE(copyMap
.empty());
231 // Test copying from an empty map where SmallDenseMap isn't small.
232 TYPED_TEST(DenseMapTest
, CopyConstructorFromEmptyTest
) {
233 for (int Key
= 0; Key
< 5; ++Key
)
234 this->Map
[this->getKey(Key
)] = this->getValue(Key
);
236 TypeParam
copyMap(this->Map
);
238 EXPECT_TRUE(copyMap
.empty());
241 // Test assignment operator method
242 TYPED_TEST(DenseMapTest
, AssignmentTest
) {
243 this->Map
[this->getKey()] = this->getValue();
244 TypeParam copyMap
= this->Map
;
246 EXPECT_EQ(1u, copyMap
.size());
247 EXPECT_EQ(this->getValue(), copyMap
[this->getKey()]);
249 // test self-assignment.
250 copyMap
= static_cast<TypeParam
&>(copyMap
);
251 EXPECT_EQ(1u, copyMap
.size());
252 EXPECT_EQ(this->getValue(), copyMap
[this->getKey()]);
255 TYPED_TEST(DenseMapTest
, AssignmentTestNotSmall
) {
256 for (int Key
= 0; Key
< 5; ++Key
)
257 this->Map
[this->getKey(Key
)] = this->getValue(Key
);
258 TypeParam copyMap
= this->Map
;
260 EXPECT_EQ(5u, copyMap
.size());
261 for (int Key
= 0; Key
< 5; ++Key
)
262 EXPECT_EQ(this->getValue(Key
), copyMap
[this->getKey(Key
)]);
264 // test self-assignment.
265 copyMap
= static_cast<TypeParam
&>(copyMap
);
266 EXPECT_EQ(5u, copyMap
.size());
267 for (int Key
= 0; Key
< 5; ++Key
)
268 EXPECT_EQ(this->getValue(Key
), copyMap
[this->getKey(Key
)]);
272 TYPED_TEST(DenseMapTest
, SwapTest
) {
273 this->Map
[this->getKey()] = this->getValue();
276 this->Map
.swap(otherMap
);
277 EXPECT_EQ(0u, this->Map
.size());
278 EXPECT_TRUE(this->Map
.empty());
279 EXPECT_EQ(1u, otherMap
.size());
280 EXPECT_EQ(this->getValue(), otherMap
[this->getKey()]);
282 this->Map
.swap(otherMap
);
283 EXPECT_EQ(0u, otherMap
.size());
284 EXPECT_TRUE(otherMap
.empty());
285 EXPECT_EQ(1u, this->Map
.size());
286 EXPECT_EQ(this->getValue(), this->Map
[this->getKey()]);
288 // Make this more interesting by inserting 100 numbers into the map.
289 for (int i
= 0; i
< 100; ++i
)
290 this->Map
[this->getKey(i
)] = this->getValue(i
);
292 this->Map
.swap(otherMap
);
293 EXPECT_EQ(0u, this->Map
.size());
294 EXPECT_TRUE(this->Map
.empty());
295 EXPECT_EQ(100u, otherMap
.size());
296 for (int i
= 0; i
< 100; ++i
)
297 EXPECT_EQ(this->getValue(i
), otherMap
[this->getKey(i
)]);
299 this->Map
.swap(otherMap
);
300 EXPECT_EQ(0u, otherMap
.size());
301 EXPECT_TRUE(otherMap
.empty());
302 EXPECT_EQ(100u, this->Map
.size());
303 for (int i
= 0; i
< 100; ++i
)
304 EXPECT_EQ(this->getValue(i
), this->Map
[this->getKey(i
)]);
307 // A more complex iteration test
308 TYPED_TEST(DenseMapTest
, IterationTest
) {
310 std::map
<typename
TypeParam::key_type
, unsigned> visitedIndex
;
312 // Insert 100 numbers into the map
313 for (int i
= 0; i
< 100; ++i
) {
315 visitedIndex
[this->getKey(i
)] = i
;
317 this->Map
[this->getKey(i
)] = this->getValue(i
);
320 // Iterate over all numbers and mark each one found.
321 for (typename
TypeParam::iterator it
= this->Map
.begin();
322 it
!= this->Map
.end(); ++it
)
323 visited
[visitedIndex
[it
->first
]] = true;
325 // Ensure every number was visited.
326 for (int i
= 0; i
< 100; ++i
)
327 ASSERT_TRUE(visited
[i
]) << "Entry #" << i
<< " was never visited";
330 // const_iterator test
331 TYPED_TEST(DenseMapTest
, ConstIteratorTest
) {
332 // Check conversion from iterator to const_iterator.
333 typename
TypeParam::iterator it
= this->Map
.begin();
334 typename
TypeParam::const_iterator
cit(it
);
335 EXPECT_TRUE(it
== cit
);
337 // Check copying of const_iterators.
338 typename
TypeParam::const_iterator
cit2(cit
);
339 EXPECT_TRUE(cit
== cit2
);
343 // Simple class that counts how many moves and copy happens when growing a map
344 struct CountCopyAndMove
{
347 CountCopyAndMove() {}
349 CountCopyAndMove(const CountCopyAndMove
&) { Copy
++; }
350 CountCopyAndMove
&operator=(const CountCopyAndMove
&) {
354 CountCopyAndMove(CountCopyAndMove
&&) { Move
++; }
355 CountCopyAndMove
&operator=(const CountCopyAndMove
&&) {
360 int CountCopyAndMove::Copy
= 0;
361 int CountCopyAndMove::Move
= 0;
363 } // anonymous namespace
365 // Test initializer list construction.
366 TEST(DenseMapCustomTest
, InitializerList
) {
367 DenseMap
<int, int> M({{0, 0}, {0, 1}, {1, 2}});
368 EXPECT_EQ(2u, M
.size());
369 EXPECT_EQ(1u, M
.count(0));
371 EXPECT_EQ(1u, M
.count(1));
375 // Test initializer list construction.
376 TEST(DenseMapCustomTest
, EqualityComparison
) {
377 DenseMap
<int, int> M1({{0, 0}, {1, 2}});
378 DenseMap
<int, int> M2({{0, 0}, {1, 2}});
379 DenseMap
<int, int> M3({{0, 0}, {1, 3}});
385 // Test for the default minimum size of a DenseMap
386 TEST(DenseMapCustomTest
, DefaultMinReservedSizeTest
) {
387 // IF THIS VALUE CHANGE, please update InitialSizeTest, InitFromIterator, and
388 // ReserveTest as well!
389 const int ExpectedInitialBucketCount
= 64;
390 // Formula from DenseMap::getMinBucketToReserveForEntries()
391 const int ExpectedMaxInitialEntries
= ExpectedInitialBucketCount
* 3 / 4 - 1;
393 DenseMap
<int, CountCopyAndMove
> Map
;
394 // Will allocate 64 buckets
396 unsigned MemorySize
= Map
.getMemorySize();
397 CountCopyAndMove::Copy
= 0;
398 CountCopyAndMove::Move
= 0;
399 for (int i
= 0; i
< ExpectedMaxInitialEntries
; ++i
)
400 Map
.insert(std::pair
<int, CountCopyAndMove
>(std::piecewise_construct
,
401 std::forward_as_tuple(i
),
402 std::forward_as_tuple()));
403 // Check that we didn't grow
404 EXPECT_EQ(MemorySize
, Map
.getMemorySize());
405 // Check that move was called the expected number of times
406 EXPECT_EQ(ExpectedMaxInitialEntries
, CountCopyAndMove::Move
);
407 // Check that no copy occurred
408 EXPECT_EQ(0, CountCopyAndMove::Copy
);
410 // Adding one extra element should grow the map
411 Map
.insert(std::pair
<int, CountCopyAndMove
>(
412 std::piecewise_construct
,
413 std::forward_as_tuple(ExpectedMaxInitialEntries
),
414 std::forward_as_tuple()));
415 // Check that we grew
416 EXPECT_NE(MemorySize
, Map
.getMemorySize());
417 // Check that move was called the expected number of times
418 // This relies on move-construction elision, and cannot be reliably tested.
419 // EXPECT_EQ(ExpectedMaxInitialEntries + 2, CountCopyAndMove::Move);
420 // Check that no copy occurred
421 EXPECT_EQ(0, CountCopyAndMove::Copy
);
424 // Make sure creating the map with an initial size of N actually gives us enough
425 // buckets to insert N items without increasing allocation size.
426 TEST(DenseMapCustomTest
, InitialSizeTest
) {
427 // Test a few different sizes, 48 is *not* a random choice: we need a value
428 // that is 2/3 of a power of two to stress the grow() condition, and the power
429 // of two has to be at least 64 because of minimum size allocation in the
430 // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the
432 for (auto Size
: {1, 2, 48, 66}) {
433 DenseMap
<int, CountCopyAndMove
> Map(Size
);
434 unsigned MemorySize
= Map
.getMemorySize();
435 CountCopyAndMove::Copy
= 0;
436 CountCopyAndMove::Move
= 0;
437 for (int i
= 0; i
< Size
; ++i
)
438 Map
.insert(std::pair
<int, CountCopyAndMove
>(std::piecewise_construct
,
439 std::forward_as_tuple(i
),
440 std::forward_as_tuple()));
441 // Check that we didn't grow
442 EXPECT_EQ(MemorySize
, Map
.getMemorySize());
443 // Check that move was called the expected number of times
444 EXPECT_EQ(Size
, CountCopyAndMove::Move
);
445 // Check that no copy occurred
446 EXPECT_EQ(0, CountCopyAndMove::Copy
);
450 // Make sure creating the map with a iterator range does not trigger grow()
451 TEST(DenseMapCustomTest
, InitFromIterator
) {
452 std::vector
<std::pair
<int, CountCopyAndMove
>> Values
;
453 // The size is a random value greater than 64 (hardcoded DenseMap min init)
454 const int Count
= 65;
455 for (int i
= 0; i
< Count
; i
++)
456 Values
.emplace_back(i
, CountCopyAndMove());
458 CountCopyAndMove::Move
= 0;
459 CountCopyAndMove::Copy
= 0;
460 DenseMap
<int, CountCopyAndMove
> Map(Values
.begin(), Values
.end());
461 // Check that no move occurred
462 EXPECT_EQ(0, CountCopyAndMove::Move
);
463 // Check that copy was called the expected number of times
464 EXPECT_EQ(Count
, CountCopyAndMove::Copy
);
467 // Make sure reserve actually gives us enough buckets to insert N items
468 // without increasing allocation size.
469 TEST(DenseMapCustomTest
, ReserveTest
) {
470 // Test a few different size, 48 is *not* a random choice: we need a value
471 // that is 2/3 of a power of two to stress the grow() condition, and the power
472 // of two has to be at least 64 because of minimum size allocation in the
473 // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the
475 for (auto Size
: {1, 2, 48, 66}) {
476 DenseMap
<int, CountCopyAndMove
> Map
;
478 unsigned MemorySize
= Map
.getMemorySize();
479 CountCopyAndMove::Copy
= 0;
480 CountCopyAndMove::Move
= 0;
481 for (int i
= 0; i
< Size
; ++i
)
482 Map
.insert(std::pair
<int, CountCopyAndMove
>(std::piecewise_construct
,
483 std::forward_as_tuple(i
),
484 std::forward_as_tuple()));
485 // Check that we didn't grow
486 EXPECT_EQ(MemorySize
, Map
.getMemorySize());
487 // Check that move was called the expected number of times
488 EXPECT_EQ(Size
, CountCopyAndMove::Move
);
489 // Check that no copy occurred
490 EXPECT_EQ(0, CountCopyAndMove::Copy
);
494 // Make sure DenseMap works with StringRef keys.
495 TEST(DenseMapCustomTest
, StringRefTest
) {
496 DenseMap
<StringRef
, int> M
;
502 EXPECT_EQ(3u, M
.size());
503 EXPECT_EQ(1, M
.lookup("a"));
504 EXPECT_EQ(2, M
.lookup("b"));
505 EXPECT_EQ(3, M
.lookup("c"));
507 EXPECT_EQ(0, M
.lookup("q"));
509 // Test the empty string, spelled various ways.
510 EXPECT_EQ(0, M
.lookup(""));
511 EXPECT_EQ(0, M
.lookup(StringRef()));
512 EXPECT_EQ(0, M
.lookup(StringRef("a", 0)));
514 EXPECT_EQ(42, M
.lookup(""));
515 EXPECT_EQ(42, M
.lookup(StringRef()));
516 EXPECT_EQ(42, M
.lookup(StringRef("a", 0)));
519 // Key traits that allows lookup with either an unsigned or char* key;
520 // In the latter case, "a" == 0, "b" == 1 and so on.
521 struct TestDenseMapInfo
{
522 static inline unsigned getEmptyKey() { return ~0; }
523 static inline unsigned getTombstoneKey() { return ~0U - 1; }
524 static unsigned getHashValue(const unsigned& Val
) { return Val
* 37U; }
525 static unsigned getHashValue(const char* Val
) {
526 return (unsigned)(Val
[0] - 'a') * 37U;
528 static bool isEqual(const unsigned& LHS
, const unsigned& RHS
) {
531 static bool isEqual(const char* LHS
, const unsigned& RHS
) {
532 return (unsigned)(LHS
[0] - 'a') == RHS
;
537 TEST(DenseMapCustomTest
, FindAsTest
) {
538 DenseMap
<unsigned, unsigned, TestDenseMapInfo
> map
;
544 EXPECT_EQ(3u, map
.size());
546 // Normal lookup tests
547 EXPECT_EQ(1u, map
.count(1));
548 EXPECT_EQ(1u, map
.find(0)->second
);
549 EXPECT_EQ(2u, map
.find(1)->second
);
550 EXPECT_EQ(3u, map
.find(2)->second
);
551 EXPECT_TRUE(map
.find(3) == map
.end());
554 EXPECT_EQ(1u, map
.find_as("a")->second
);
555 EXPECT_EQ(2u, map
.find_as("b")->second
);
556 EXPECT_EQ(3u, map
.find_as("c")->second
);
557 EXPECT_TRUE(map
.find_as("d") == map
.end());
560 struct ContiguousDenseMapInfo
{
561 static inline unsigned getEmptyKey() { return ~0; }
562 static inline unsigned getTombstoneKey() { return ~0U - 1; }
563 static unsigned getHashValue(const unsigned& Val
) { return Val
; }
564 static bool isEqual(const unsigned& LHS
, const unsigned& RHS
) {
569 // Test that filling a small dense map with exactly the number of elements in
570 // the map grows to have enough space for an empty bucket.
571 TEST(DenseMapCustomTest
, SmallDenseMapGrowTest
) {
572 SmallDenseMap
<unsigned, unsigned, 32, ContiguousDenseMapInfo
> map
;
573 // Add some number of elements, then delete a few to leave us some tombstones.
574 // If we just filled the map with 32 elements we'd grow because of not enough
575 // tombstones which masks the issue here.
576 for (unsigned i
= 0; i
< 20; ++i
)
578 for (unsigned i
= 0; i
< 10; ++i
)
580 for (unsigned i
= 20; i
< 32; ++i
)
584 EXPECT_EQ(22u, map
.size());
586 // Try to find an element which doesn't exist. There was a bug in
587 // SmallDenseMap which led to a map with num elements == small capacity not
588 // having an empty bucket any more. Finding an element not in the map would
589 // therefore never terminate.
590 EXPECT_TRUE(map
.find(32) == map
.end());
593 TEST(DenseMapCustomTest
, TryEmplaceTest
) {
594 DenseMap
<int, std::unique_ptr
<int>> Map
;
595 std::unique_ptr
<int> P(new int(2));
596 auto Try1
= Map
.try_emplace(0, new int(1));
597 EXPECT_TRUE(Try1
.second
);
598 auto Try2
= Map
.try_emplace(0, std::move(P
));
599 EXPECT_FALSE(Try2
.second
);
600 EXPECT_EQ(Try1
.first
, Try2
.first
);
601 EXPECT_NE(nullptr, P
);
604 TEST(DenseMapCustomTest
, ConstTest
) {
605 // Test that const pointers work okay for count and find, even when the
606 // underlying map is a non-const pointer.
607 DenseMap
<int *, int> Map
;
612 EXPECT_EQ(Map
.count(B
), 1u);
613 EXPECT_EQ(Map
.count(C
), 1u);
614 EXPECT_NE(Map
.find(B
), Map
.end());
615 EXPECT_NE(Map
.find(C
), Map
.end());