summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/ADT
Commit message (Collapse)AuthorAgeFilesLines
* Move the SmallVector unit tests to be type-parameterized so that we canChandler Carruth2012-07-301-149/+176
| | | | | | | | | | | | | | | | | | | | test more than a single instantiation of SmallVector. Add testing for 0, 1, 2, and 4 element sized "small" buffers. These appear to be essentially untested in the unit tests until now. Fix several tests to be robust in the face of a '0' small buffer. As a consequence of this size buffer, the growth patterns are actually observable in the test -- yes this means that many tests never caused a grow to occur before. For some tests I've merely added a reserve call to normalize behavior. For others, the growth is actually interesting, and so I captured the fact that growth would occur and adjusted the assertions to not assume how rapidly growth occured. Also update the specialization for a '0' small buffer length to have all the same interface points as the normal small vector. llvm-svn: 161001
* Completely refactor the structuring of unittest CMake files to match theChandler Carruth2012-06-211-0/+32
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Makefiles, the CMake files in every other part of the LLVM tree, and sanity. This should also restore the output tree structure of all the unit tests, sorry for breaking that, and thanks for letting me know. The fundamental change is to put a CMakeLists.txt file in the unittest directory, with a single test binary produced from it. This has several advantages: - No more weird directory stripping in the unittest macro, allowing it to be used more readily in other projects. - No more directory prefixes on all the source files. - Allows correct and precise use of LLVM's per-directory dependency system. - Allows use of the checking logic for source files that have not been added to the CMake build. This uncovered a file being skipped with CMake in LLVM and one in Clang's unit tests. - Makes Specifying conditional compilation or other custom logic for JIT tests easier. It did require adding the concept of an explicit 'optional' source file to the CMake build so that the missing-file check can skip cases where the file is *supposed* to be missing. =] This is another chunk of refactoring the CMake build in order to make it usable for other clients like CompilerRT / ASan / TSan. Note that this is interdependent with a Clang CMake change. llvm-svn: 158909
* Fix PR13148, an inf-loop in StringMap.Chandler Carruth2012-06-191-0/+22
| | | | | | | | | | | | | | | StringMap suffered from the same bug as DenseMap: when you explicitly construct it with a small number of buckets, you can arrange for the tombstone-based growth path to be followed when the number of buckets was less than '8'. In that case, even with a full map, it would compare '0' as not less than '0', and refuse to grow the table, leading to inf-loops trying to find an empty bucket on the next insertion. The fix is very simple: use '<=' as the comparison. The same fix was applied to DenseMap as well during its recent refactoring. Thanks to Alex Bolz for the great report and test case. =] llvm-svn: 158725
* Remove some superfluous SCOPED_TRACEs from this unit test.Chandler Carruth2012-06-191-6/+0
| | | | | | | GoogleTest already prints errors with all the information about which test case contained the error. llvm-svn: 158724
* Remove SmallMap unittests, unbreaking the build.Benjamin Kramer2012-06-171-162/+0
| | | | | | I don't know how useful these are for SmallDenseMap, I'll leave that decision to Chandler. llvm-svn: 158646
* Bring the return value of SmallVector::insert in line with std::vector::insert.Benjamin Kramer2012-06-171-4/+30
| | | | | | | | It always returns the iterator for the first inserted element, or the passed in iterator if the inserted range was empty. Flesh out the unit test more and fix all the cases it uncovered so far. llvm-svn: 158645
* SmallVector: return a valid iterator for the rare case of inserting an empty ↵Benjamin Kramer2012-06-171-0/+7
| | | | | | | | range into a SmallVector. Patch by Johannes Schaub! llvm-svn: 158643
* Add a unit test for 'swap', and fix a pile of bugs inChandler Carruth2012-06-171-0/+36
| | | | | | | | | | | | | | | 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. llvm-svn: 158641
* Add tests for *DenesMap for both key and value types' construction andChandler Carruth2012-06-171-1/+46
| | | | | | | | | | | | | | | | | | | 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. llvm-svn: 158639
* Introduce a SmallDenseMap container that re-uses the existing DenseMapChandler Carruth2012-06-171-27/+35
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Merge the SmallBitVector and BitVector unit tests with gtest's typed test ↵Benjamin Kramer2012-06-162-212/+25
| | | | | | magic and bring SmallBitVector up to date. llvm-svn: 158600
* Work around a bug with MSVC 10 where it fails to recognize a valid useChandler Carruth2012-06-161-0/+9
| | | | | | | | | 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
* Type parameterize the DenseMap unit tests.Chandler Carruth2012-06-161-87/+102
| | | | | | | | | | | | 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
* Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer2012-06-021-1/+1
| | | | llvm-svn: 157885
* Remove the PTX back-end and all of its artifacts (triple, etc.)Justin Holewinski2012-05-241-6/+6
| | | | | | | | This back-end was deprecated in favor of the NVPTX back-end. NV_CONTRIB llvm-svn: 157417
* fix the quotient returned by sdivrem() for the case when LHS is negative and ↵Nuno Lopes2012-05-221-0/+28
| | | | | | | | RHS is positive based on a patch by Preston Briggs, with some modifications llvm-svn: 157231
* Remove warning about testing unsigned int with int.Bill Wendling2012-05-151-1/+1
| | | | llvm-svn: 156812
* Fixed one small stupid, but critical bug.Stepan Dyatkovskiy2012-05-151-0/+15
| | | | llvm-svn: 156810
* Remove the expensive BitVector::operator~().Jakob Stoklund Olesen2012-05-141-3/+4
| | | | | | | Returning a temporary BitVector is very expensive. If you must, create the temporary explicitly: Use BitVector(A).flip() instead of ~A. llvm-svn: 156768
* Add BitVector::anyCommon().Jakob Stoklund Olesen2012-05-141-1/+29
| | | | | | The existing operation (A & B).any() is very slow. llvm-svn: 156760
* [Support/StringRef] Add find_last_not_of and {r,l,}trim.Michael J. Spencer2012-05-111-0/+28
| | | | llvm-svn: 156652
* Add unittests for Triple::getMacOSXVersion and Triple::getiOSVersion.Chad Rosier2012-05-091-0/+65
| | | | llvm-svn: 156507
* SmallVector: Don't rely on having an assignment operator around in push_back ↵Benjamin Kramer2012-04-291-0/+13
| | | | | | for POD-like types. llvm-svn: 155791
* Fixed SmallMap test. The order of items is undefined in DenseMap. So being ↵Stepan Dyatkovskiy2012-04-261-10/+24
| | | | | | checking the increment for big mode, we can only check that all items are in map. llvm-svn: 155651
* Reapply the SmallMap patch with a fix.Benjamin Kramer2012-04-251-0/+133
| | | | | | Comparing ~0UL with an unsigned will always return false when long is 64 bits long. llvm-svn: 155568
* Revert "First implementation of:"Eric Christopher2012-04-251-133/+0
| | | | | | | | This reverts commit 76271a3366731d4c372fdebcd8d3437e6e09a61b. as it's breaking the bots. llvm-svn: 155562
* First implementation of:Stepan Dyatkovskiy2012-04-251-0/+133
| | | | | | | | | | | - FlatArrayMap. Very simple map container that uses flat array inside. - MultiImplMap. Map container interface, that has two modes, one for small amount of elements and one for big amount. - SmallMap. SmallMap is DenseMap compatible MultiImplMap. It uses FlatArrayMap for small mode, and DenseMap for big mode. Also added unittests for new classes and update for ProgrammersManual. For more details about new classes see ProgrammersManual and comments in sourcecode. llvm-svn: 155557
* SparseSet: Add support for key-derived indexes and arbitrary key types.Andrew Trick2012-04-201-1/+1
| | | | | | | | | | | | | | | | | | | This nicely handles the most common case of virtual register sets, but also handles anticipated cases where we will map pointers to IDs. The goal is not to develop a completely generic SparseSet template. Instead we want to handle the expected uses within llvm without any template antics in the client code. I'm adding a bit of template nastiness here, and some assumption about expected usage in order to make the client code very clean. The expected common uses cases I'm designing for: - integer keys that need to be reindexed, and may map to additional data - densely numbered objects where we want pointer keys because no number->object map exists. llvm-svn: 155227
* Add triple support for the IBM BG/P and BG/Q supercomputers.Hal Finkel2012-04-021-0/+18
| | | | llvm-svn: 153882
* Fix warnings.Michael J. Spencer2012-03-111-4/+4
| | | | llvm-svn: 152522
* Make StringRef::getAsInteger work with all integer types. Before this changeMichael J. Spencer2012-03-101-0/+118
| | | | | | | | it would fail with {,u}int64_t on x86-64 Linux. This also removes code duplication. llvm-svn: 152517
* Add support to the hashing infrastructure for automatically hashing bothChandler Carruth2012-03-071-0/+6
| | | | | | | | | | | | | | | | | | integral and enumeration types. This is accomplished with a bit of template type trait magic. Thanks to Richard Smith for the core idea here to detect viable types by detecting the set of types which can be default constructed in a template parameter. This is used (in conjunction with a system for detecting nullptr_t should it exist) to provide an is_integral_or_enum type trait that doesn't need a whitelist or direct compiler support. With this, the hashing is extended to the more general facility. This will be used in a subsequent commit to hashing more things, but I wanted to make sure the type trait magic went through the build bots separately in case other compilers don't like this formulation. llvm-svn: 152217
* SmallPtrSet: Provide a more efficient implementation of swap than the ↵Benjamin Kramer2012-03-061-0/+72
| | | | | | | | | default triple-copy std::swap. This currently assumes that both sets have the same SmallSize to keep the implementation simple, a limitation that can be lifted if someone cares. llvm-svn: 152143
* Add generic support for hashing StringRef objects using the new hashing library.Chandler Carruth2012-03-041-0/+19
| | | | llvm-svn: 152003
* Teach the hashing facilities how to hash std::string objects.Chandler Carruth2012-03-041-0/+17
| | | | llvm-svn: 152000
* Split this test up into two smaller, and more focused tests.Chandler Carruth2012-03-041-0/+2
| | | | llvm-svn: 151999
* Move the NonPOD struct out of the anonymous namespace instead of adding ↵Francois Pichet2012-03-031-33/+33
| | | | | | | | llvm:: everywhere to fix the HashingTest on MSVC . chandlerc proposed this better solution on IRC. llvm-svn: 151974
* Fixes the Hashing tests on MSVC by adding llvm:: prefix to hash_value ↵Francois Pichet2012-03-031-28/+24
| | | | | | function call. llvm-svn: 151971
* unittests/ADT/HashingTest.cpp: Temporarily disable a new test introduced in ↵NAKAMURA Takumi2012-03-031-0/+4
| | | | | | r151891, to appease msvc. llvm-svn: 151970
* Simplify the pair optimization. Rather than using complex type traits,Chandler Carruth2012-03-021-0/+20
| | | | | | | | | | | | | | just ensure that the number of bytes in the pair is the sum of the bytes in each side of the pair. As long as thats true, there are no extra bytes that might be padding. Also add a few tests that previously would have slipped through the checking. The more accurate checking mechanism catches these and ensures they are handled conservatively correctly. Thanks to Duncan for prodding me to do this right and more simply. llvm-svn: 151891
* Add a golden data test that I missed somehow the first time around.Chandler Carruth2012-03-021-0/+1
| | | | llvm-svn: 151886
* Fix bad indenting that was left over from cut/paste of the golden valuesChandler Carruth2012-03-021-52/+52
| | | | | | for 32-bit builds in here. llvm-svn: 151885
* We really want to hash pairs of directly-hashable data as directlyChandler Carruth2012-03-021-5/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | hashable data. This matters when we have pair<T*, U*> as a key, which is quite common in DenseMap, etc. To that end, we need to detect when this is safe. The requirements on a generic std::pair<T, U> are: 1) Both T and U must satisfy the existing is_hashable_data trait. Note that this includes the requirement that T and U have no internal padding bits or other bits not contributing directly to equality. 2) The alignment constraints of std::pair<T, U> do not require padding between consecutive objects. 3) The alignment constraints of U and the size of T do not conspire to require padding between the first and second elements. Grow two somewhat magical traits to detect this by forming a pod structure and inspecting offset artifacts on it. Hopefully this won't cause any compilers to panic. Added and adjusted tests now that pairs, even nested pairs, are treated as just sequences of data. Thanks to Jeffrey Yasskin for helping me sort through this and reviewing the somewhat subtle traits. llvm-svn: 151883
* Add support for hashing pairs by delegating to each sub-object. There isChandler Carruth2012-03-021-0/+11
| | | | | | | | | | | | | | | | | an open question of whether we can do better than this by treating pairs as boring data containers and directly hashing the two subobjects. This at least makes the API reasonable. In order to make this change, I reorganized the header a bit. I lifted the declarations of the hash_value functions up to the top of the header with their doxygen comments as these are intended for users to interact with. They shouldn't have to wade through implementation details. I then defined them at the very end so that they could be defined in terms of hash_combine or any other hashing infrastructure. Added various pair-hashing unittests. llvm-svn: 151882
* Remove the misguided extension here that reserved two special values inChandler Carruth2012-03-021-11/+1
| | | | | | | | | | | the hash_code. I'm not sure what I was thinking here, the use cases for special values are in the *keys*, not in the hashes of those keys. We can always resurrect this if needed, or clients can accomplish the same goal themselves. This makes the general case somewhat faster (~5 cycles faster on my machine) and smaller with less branching. llvm-svn: 151865
* Re-disable the debug output. The comment is there explaining why we wantChandler Carruth2012-03-011-1/+1
| | | | | | | | to keep this around -- updating golden tests is annoying otherwise. Thanks to Benjamin for pointing this omission out on IRC. llvm-svn: 151860
* Provide the 32-bit variant of the golden tests. Not sure how I forgot toChandler Carruth2012-03-011-3/+60
| | | | | | do this initially, sorry. llvm-svn: 151857
* Rewrite LLVM's generalized support library for hashing to follow the APIChandler Carruth2012-03-011-25/+286
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | of the proposed standard hashing interfaces (N3333), and to use a modified and tuned version of the CityHash algorithm. Some of the highlights of this change: -- Significantly higher quality hashing algorithm with very well distributed results, and extremely few collisions. Should be close to a checksum for up to 64-bit keys. Very little clustering or clumping of hash codes, to better distribute load on probed hash tables. -- Built-in support for reserved values. -- Simplified API that composes cleanly with other C++ idioms and APIs. -- Better scaling performance as keys grow. This is the fastest algorithm I've found and measured for moderately sized keys (such as show up in some of the uniquing and folding use cases) -- Support for enabling per-execution seeds to prevent table ordering or other artifacts of hashing algorithms to impact the output of LLVM. The seeding would make each run different and highlight these problems during bootstrap. This implementation was tested extensively using the SMHasher test suite, and pased with flying colors, doing better than the original CityHash algorithm even. I've included a unittest, although it is somewhat minimal at the moment. I've also added (or refactored into the proper location) type traits necessary to implement this, and converted users of GeneralHash over. My only immediate concerns with this implementation is the performance of hashing small keys. I've already started working to improve this, and will continue to do so. Currently, the only algorithms faster produce lower quality results, but it is likely there is a better compromise than the current one. Many thanks to Jeffrey Yasskin who did most of the work on the N3333 paper, pair-programmed some of this code, and reviewed much of it. Many thanks also go to Geoff Pike Pike and Jyrki Alakuijala, the original authors of CityHash on which this is heavily based, and Austin Appleby who created MurmurHash and the SMHasher test suite. Also thanks to Nadav, Tobias, Howard, Jay, Nick, Ahmed, and Duncan for all of the review comments! If there are further comments or concerns, please let me know and I'll jump on 'em. llvm-svn: 151822
* Fix typos.Jakob Stoklund Olesen2012-02-221-4/+4
| | | | llvm-svn: 151163
* Support was removed from LLVM's MIPS backend for the PSP variant of thatChandler Carruth2012-02-221-9/+0
| | | | | | | | | | | | | chip in r139383, and the PSP components of the triple are really annoying to parse. Let's leave this chapter behind. There is no reason to expect LLVM to see a PSP-related triple these days, and so no reasonable motivation to support them. It might be reasonable to prune a few of the older MIPS triple forms in general, but as those at least cause no burden on parsing (they aren't both a chip and an OS!), I'm happy to leave them in for now. llvm-svn: 151156
OpenPOWER on IntegriCloud