aboutsummaryrefslogtreecommitdiff
path: root/llvm/unittests/ADT/DenseMapTest.cpp
AgeCommit message (Collapse)AuthorFilesLines
2025-09-14[ADT] Fix the initial size calculation of SmallDenseMap (#158458)Kazu Hirata1-0/+69
The initial size calculation of SmallDenseMap is strange in several ways: - SmallDenseMap(unsigned) seems to want to take the number of initial buckets as far as I can tell from the variable name NumInitBuckets. In contrast, DenseMap(unsigned) seems to want to take the number of initial entries as far as I can tell from the comment: /// Create a DenseMap with an optional \p InitialReserve that guarantee that /// this number of elements can be inserted in the map without grow() - SmallDenseMap(unsigned) uses llvm::bit_ceil to obtain a power of two. SmallDenseMap(I, E) uses NextPowerOf2 to obtain a power of two. - Presumably, the init() call is to ensure that we won't call grow() while populating the initial elements [I, E). However, NextPowerOf2(std::distance(I, E)) does not ensure that a rehash won't happen. For example, if the number of initial elements is 50, we need 128 buckets, but NextPowerOf2(std::distance(I, E)) would return 64. This patch fixes all these inconsistencies by teaching SmallDenseMap::init to call BaseT::getMinBucketToReserveForEntries just like DenseMap::init. With this patch, all constructors of SmallDenseMap are textually identical to their respective counterparts in DenseMap.
2025-08-21[ADT] Use SmallPtrSet or SmallSet flexibly (NFC) (#154680)Kazu Hirata1-8/+15
I'm trying to remove the redirection in SmallSet.h: template <typename PointeeType, unsigned N> class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; to make it clear that we are using SmallPtrSet. There are only handful places that rely on this redirection. Now, this unit test is unique in that supply multiple key types via TYPED_TESTS. This patch adds UniversalSmallSet to work around the problem.
2025-08-14[ADT] Add `from_range` constructor for (Small)DenseMap (#153515)Jakub Kuderski1-0/+29
This follows how we support range construction for (Small)DenseSet.
2025-07-10[ADT] Fix a warningKazu Hirata1-4/+0
This patch fixes: llvm/unittests/ADT/DenseMapTest.cpp:94:25: error: unused function 'getTestValue' [-Werror,-Wunused-function]
2025-07-10DenseMapInfo: support std::optional<T> (#147851)Elijah Kin1-1/+12
2025-05-28[DenseMap] Fix constness issues with lookup_or (#139247)Ramkumar Ramachandra1-0/+7
Also demonstrate its use in ScalarEvolution.
2025-05-08[DenseMap] Introduce emplace_or_assign (#138886)Ramkumar Ramachandra1-0/+35
Introduce emplace_or_assign, a variant of insert_or_assign that has slightly better characteristics.
2025-05-08[DenseMap] Introduce lookup_or (#138887)Ramkumar Ramachandra1-0/+20
Introduce lookup_or, a variant of lookup, for non-default-constructible values.
2025-05-07[DenseMap] Introduce keys, values iterators (#138848)Ramkumar Ramachandra1-0/+46
2025-03-30[ADT] Add `DenseMap::insert_range` (#133600)Baranov Victor1-0/+22
This PR add `DenseMap::insert_range` to `DenseMap` for consistency with existing `DenseSet::insert_range`, `SmallSet::insert_range` and `std::map::insert_range`.
2024-06-19DenseMap: support enum class keys (#95972)Ramkumar Ramachandra1-2/+14
Implemented using std::underlying_type.
2024-06-05[ADT] Add C++17-style insert_or_assign for DenseMap (#94151)c8ef1-0/+36
add C++17-style insert_or_assign for DenseMap close: #94115
2024-06-04[ADT] refactor MoveOnly type in ADT unittest (#94421)c8ef1-41/+17
context: https://github.com/llvm/llvm-project/pull/94151#pullrequestreview-2097098530
2023-06-28[unittest] teach gTest to print entries of DenseMap as pairsSam McCall1-0/+9
When an assertion like the following fails: EXPECT_THAT(map, ElementsAre(Pair("p", "nullable")))); Error message before: Actual: { 40-byte object <E8-A5 9C-7F 25-37 00-00 58-7E 51-51 D0-7F 00-00 00-00 00-00 00-00 00-00 01-00 00-00 00-00 00-00 00-DA C7-7F 25-37 00-00> } After: Actual: { ("p", "nonnull") } It is not ideal that we need to refer directly to DenseMapPair inside the internal namespace, but I believe the practical maintenance risk is low. This change is covered by DenseMap's unittests, as we've covered SmallString etc in the past. Differential Revision: https://reviews.llvm.org/D153930
2023-06-22[llvm] Split out DenseMapInfo<variant> specializationElliot Goodrich1-0/+1
Remove the `DenseMapInfo<std::variant<Ts...>>` variant out from `llvm/ADT/DenseMapInfo.h` into a separate header `llvm/ADT/DenseMapInfoVariant.h` This allows us to remove the `<variant>` include, which is being transitively and unncessary included in all translation units that include `llvm/ADT/DenseMap.h`. There have been similar changes to move out specializations for * `APInt.h` fd7e309e02fd226b0390888388ed732608e52c73 and * `StringRef.h`/`ArrayRef.h` 983565a6fe4a9f40c7caf82b65c650c20dbcc104 to reduce the compilation time. As we are unable to move the specialization into `<variant>`, we create a separate `DenseMapInfoVariant.h` header that can be used by anyone who needs this specialization. This reduces the total number of preprocessing tokens across the LLVM source files in lib from (roughly) 1,964,876,961 to 1,936,551,496 - a reduction of ~1.44%. This should result in a small improvement in compilation time. Differential Revision: https://reviews.llvm.org/D150997
2023-06-06[ADT] Fix DenseMapInfo<variant>::isEqual to delegate to DenseMapInfo, not ==Sam McCall1-1/+19
Differential Revision: https://reviews.llvm.org/D151557
2023-03-13[ADT] Implement {DenseMap,MapVector,StringMap}::containsKazu Hirata1-0/+2
This patch implements the C++20-style contains() for DenseMap, MapVector, and StringMap. With this patch, every set and map container type that has count() also has contains(). Differential Revision: https://reviews.llvm.org/D145895
2023-02-17[ADT] Fix tests for `StringMap::at` and `DenseMap::at`Ryan Guo1-7/+8
These methods won't assert for release build.
2023-02-17[ADT] Add `at` method (assertive lookup) to DenseMap and StringMapRyan Guo1-0/+8
This patch makes it easier for users when they want to use validated lookup on DenseMap/StringMap as a composable C++ expression. For instance: ``` // instead of if (auto val = map.lookup(key)) return val; assert("..."); // we can write return map.at(key); ``` Differential Revision: https://reviews.llvm.org/D143976
2022-12-08[llvm] Call reserve before push_back in a loopGregory Alfonso1-0/+1
It is generally good practice, if you know how big the vector is going to be in the end, to reserve before continually calling "push_back" or "emplace_back" Reviewed By: MaskRay Differential Revision: https://reviews.llvm.org/D139483
2022-11-08Reland "[llvm][NFC] Use c++17 style variable type traits"Nathan James1-1/+1
This reverts commit 632a389f96355cbe7ed8fa7b8d2ed6267c92457c. This relands commit 1834a310d060d55748ca38d4ae0482864c2047d8. Differential Revision: https://reviews.llvm.org/D137493
2022-11-08Revert "[llvm][NFC] Use c++17 style variable type traits"Nathan James1-1/+1
This reverts commit 1834a310d060d55748ca38d4ae0482864c2047d8.
2022-11-08[llvm][NFC] Use c++17 style variable type traitsNathan James1-1/+1
This was done as a test for D137302 and it makes sense to push these changes Reviewed By: dblaikie Differential Revision: https://reviews.llvm.org/D137493
2022-09-02[llvm][Support] Add DenseMapInfo for std::variantKadir Cetinkaya1-0/+18
Differential Revision: https://reviews.llvm.org/D133200
2022-07-25Fix assertion in SmallDenseMap constructor with reserve from non-power-of-2 ↵Vladislav Dzhidzhoev1-0/+9
buckets count `SmallDenseMap` constructor with reserve gets an arbitrary `NumInitBuckets` value and passes it below to `init` method. If `NumInitBuckets` is greater then `InlineBuckets`, then `SmallDenseMap` initializes to large representation passing `NumInitBuckets` below to `DenseMap` initialization. `DenseMap::initEmpty` method asserts that initial buckets count must be a power of 2. Proposed solution is to update `NumInitBuckets` value in `SmallDenseMap` constructor till the next power of 2. It should satisfy both `DenseMap` preconditions and required minimum buckets count for reservation. Reviewed By: atrick Differential Revision: https://reviews.llvm.org/D129825
2021-11-16[llvm] Add a SFINAE template parameter to DenseMapInfoRiver Riddle1-0/+43
This allows for using SFINAE partial specialization for DenseMapInfo. In MLIR, this is particularly useful as it will allow for defining partial specializations that support all Attribute, Op, and Type classes without needing to specialize DenseMapInfo for each individual class. Differential Revision: https://reviews.llvm.org/D113641
2021-07-21[ADT] Add initializer_list constructor to SmallDenseMapJakub Kuderski1-0/+9
Make it easier to initialize small maps inline. Note that DenseMap already has an initializer_list constructor. Reviewed By: dblaikie Differential Revision: https://reviews.llvm.org/D106363
2021-05-17Put back the trailing commas on TYPED_TEST_SUITEBenjamin Kramer1-1/+1
This avoids a -pedantic warning: warning: ISO C++11 requires at least one argument for the "..." in a variadic macro See also https://github.com/google/googletest/issues/2271
2021-05-14Bump googletest to 1.10.0Benjamin Kramer1-1/+1
2020-02-28[ADT] Allow K to be incomplete during DenseMap<K*, V> instantiationReid Kleckner1-0/+24
DenseMap requires two sentinel values for keys: empty and tombstone values. To avoid undefined behavior, LLVM aligns the two sentinel pointers to alignof(T). This requires T to be complete, which is needlessly restrictive. Instead, assume that DenseMap pointer keys have a maximum alignment of 4096, and use the same sentinel values for all pointer keys. The new sentinels are: empty: static_cast<uintptr_t>(-1) << 12 tombstone: static_cast<uintptr_t>(-2) << 12 These correspond to the addresses of -4096 and -8192. Hopefully, such a key is never inserted into a DenseMap. I encountered this while looking at making clang's SourceManager not require FileManager.h, but it has several maps keyed on classes defined in FileManager.h. FileManager depends on various LLVM FS headers, which cumulatively take ~200ms to parse, and are generally not needed. Reviewed By: hans Differential Revision: https://reviews.llvm.org/D75301
2019-12-11[ADT] Fix SmallDenseMap assertion with large InlineBucketsNikita Popov1-0/+18
Fixes issue encountered in D56362, where I tried to use a SmallSetVector<Instruction*, 128> with an excessively large number of inline elements. This triggers an "Must allocate more buckets than are inline" assertion inside allocateBuckets() under certain usage patterns. The issue is as follows: The grow() method is used either to grow the map, or to rehash it and remove tombstones. The latter is done if the fraction of empty (non-used, non-tombstone) elements is below 1/8. In this case grow() is invoked with the current number of buckets. This is currently incorrectly handled for dense maps using the small rep. The current implementation will switch them over to the large rep, which violates the invariant that the large rep is only used if there are more than InlineBuckets buckets. This patch fixes the issue by staying in the small rep and only moving the buckets. An alternative, if we do want to switch to the large rep in this case, would be to relax the assertion in allocateBuckets(). Differential Revision: https://reviews.llvm.org/D56455
2019-07-09[ADT] Remove MSVC-only "no two-phase name lookup" typename path.Simon Pilgrim1-9/+0
Now that we've dropped VS2015 support (D64326) we can use the regular codepath as VS2017+ correctly handles it llvm-svn: 365502
2019-01-19Update the file headers across all of the LLVM projects in the monorepoChandler Carruth1-4/+3
to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
2018-10-15[ADT] Adds equality operators for DenseMap and DenseSet, and an initializer_listLang Hames1-0/+20
constructor for DenseMap (DenseSet already had an initializer_list constructor). These changes make it easier to migrate existing code that uses std::map and std::set (which support initializer_list construction and equality comparison) to DenseMap and DenseSet. llvm-svn: 344522
2018-05-01Remove \brief commands from doxygen comments.Adrian Prantl1-1/+1
We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
2018-04-07[unittests] ADT: silence -Wself-assign diagnosticsRoman Lebedev1-2/+2
Summary: D44883 extends -Wself-assign to also work on C++ classes. In it's current state (as suggested by @rjmccall), it is not under it's own sub-group. Since that diag is enabled by `-Wall`, stage2 testing showed that: * It does not fire on any llvm code * It does fire for these 3 unittests * It does fire for libc++ tests This diff simply silences those new warnings in llvm's unittests. A similar diff will be needed for libcxx. (`libcxx/test/std/language.support/support.types/byteops/`, maybe something else) Since i don't think we want to repeat rL322901, let's talk about it. I've subscribed everyone who i think might be interested... There are several ways forward: * Not extend -Wself-assign, close D44883. Not very productive outcome i'd say. * Keep D44883 in it's current state. Unless your custom overloaded operators do something unusual for when self-assigning, the warning is no less of a false-positive than the current -Wself-assign. Except for tests of course, there you'd want to silence it. The current suggestion is: ``` S a; a = (S &)a; ``` * Split the diagnostic in two - `-Wself-assign-builtin` (i.e. what is `-Wself-assign` in trunk), and `-Wself-assign-overloaded` - the new part in D44883. Since, as i said, i'm not really sure why it would be less of a error than the current `-Wself-assign`, both would still be in `-Wall`. That way one could simply pass `-Wno-self-assign-overloaded` for all the tests. Pretty simple to do, and will surely work. * Split the diagnostic in two - `-Wself-assign-trivial`, and `-Wself-assign-nontrivial`. The choice of which diag to emit would depend on trivial-ness of that particular operator. The current `-Wself-assign` would be `-Wself-assign-trivial`. https://godbolt.org/g/gwDASe - `A`, `B` and `C` case would be treated as trivial, and `D`, `E` and `F` as non-trivial. Will be the most complicated to implement. Thoughts? Reviewers: aaron.ballman, rsmith, rtrieu, rjmccall, dblaikie, atrick, gottesmm Reviewed By: dblaikie Subscribers: lebedev.ri, phosek, vsk, rnk, thakis, sammccall, mclow.lists, llvm-commits, rjmccall Differential Revision: https://reviews.llvm.org/D45082 llvm-svn: 329491
2018-01-24Fix typos of occurred and occurrenceMalcolm Parsons1-5/+5
llvm-svn: 323318
2017-06-06Re-sort #include lines for unittests. This uses a slightly modifiedChandler Carruth1-1/+1
clang-format (https://reviews.llvm.org/D33932) to keep primary headers at the top and handle new utility headers like 'gmock' consistently with other utility headers. No other change was made. I did no manual edits, all of this is clang-format. This should allow other changes to have more clear and focused diffs, and is especially motivated by moving some headers into more focused libraries. llvm-svn: 304786
2017-03-10Add support for DenseMap/DenseSet count and find using const pointersDaniel Berlin1-0/+14
Summary: Similar to SmallPtrSet, this makes find and count work with both const referneces and const pointers. Reviewers: dblaikie Subscribers: llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D30713 llvm-svn: 297424
2016-10-18[ADT] Remove CachedHash<T>.Justin Lebar1-49/+0
Nobody is using it. Differential Revision: https://reviews.llvm.org/D25630 llvm-svn: 284503
2016-07-21[DenseMap] Add a C++17-style try_emplace method.Benjamin Kramer1-0/+10
This provides an elegant pattern to solve the "construct if not in map already" problem we have many times in LLVM. Without try_emplace we either have to rely on a sentinel value (nullptr) or do two lookups. llvm-svn: 276277
2016-04-21Add a CachedHash structure.Rafael Espindola1-0/+49
A DenseMap doesn't store the hashes, so it needs to recompute them when the table is resized. In some applications the hashing cost is noticeable. That is the case for example in lld for symbol names (StringRef). This patch adds a templated structure that can wraps any value that can go in a DenseMap and caches the hash. llvm-svn: 266981
2016-03-25StringMap/DenseMap unittests: use piecewise_construct and ensure no copy occurs.Mehdi Amini1-11/+16
This makes us no longer relying on move-construction elision by the compiler. Suggested by D. Blaikie. From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 264475
2016-03-25Disable counting the number of move in the unittest, it seems to rely on ↵Mehdi Amini1-3/+6
move-construction elision From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 264412
2016-03-25Fix DenseMap::reserve(): the formula was wrongMehdi Amini1-7/+118
Summary: Just running the loop in the unittests for a few more iterations (till 48) exhibit that the condition on the limit was not handled properly in r263522. Rewrite the test to use a class to count move/copies that happens when inserting into the map. Also take the opportunity to refactor the logic to compute the number of buckets required for a given number of entries in the map. Use this when constructing a DenseMap with a desired size given to the constructor (and add a tests for this). Reviewers: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D18345 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 264384
2016-03-22Fix unittests: resize() -> reserve()Mehdi Amini1-1/+1
From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 264029
2016-03-15DenseMap: make .resize() do the intuitive thingFiona Glaser1-0/+13
In some places, like InstCombine, we resize a DenseMap to fit the elements we intend to put in it, then insert those elements (to avoid continual reallocations as it grows). But .resize(foo) doesn't actually do what people think; it resizes to foo buckets (which is really an implementation detail the user of DenseMap probably shouldn't care about), not the space required to fit foo elements. DenseMap grows if 3/4 of its buckets are full, so this actually causes one forced reallocation every time instead of avoiding a reallocation. This patch makes .resize(foo) do the intuitive thing: it grows to the size necessary to fit foo elements without new allocations. Also include a test to verify that .resize() actually does what we think it does. llvm-svn: 263522
2015-10-31Add a unittest for SmallDenseMap that tests assigning a SmallDenseMap when ↵Michael Gottesman1-0/+16
it is not small. This complements CopyConstructorNotSmallTest. If we are testing the copy constructor in such a way, we should also probably test assignment in the same way. llvm-svn: 251736
2015-06-24[ADT] Teach DenseMap to support StringRef keys.Chandler Carruth1-0/+25
While often you want to use something specialized like StringMap, when the strings already have persistent storage a normal densemap over them can be more efficient. This can't go into StringRef.h because of really obnoxious header chains from the hashing code to the endian detection code to CPU feature detection code to StringMap. llvm-svn: 240528
2015-03-04Explicitly default DenseMapTest::CtorTest::operator=David Blaikie1-0/+1
Using the implicit default copy assignment operator in the presence of a user-declared copy ctor is deprecated in C++11. llvm-svn: 231225
generated by cgit v1.1 at 2025-09-29 19:30:10 +0000