summaryrefslogtreecommitdiff
path: root/unittests/ADT
Commit message (Collapse)AuthorAge
...
* Fix includes of llvm files that used angle brackets.Craig Topper2012-09-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163979 91177308-0d34-0410-b5e6-96231b3b80d8
* ADTTests: [CMake] Exclude DenseMapTest.cpp and SmallVectorTest.cpp on MSVC9 ↵NAKAMURA Takumi2012-08-30
| | | | | | due to its bug. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162918 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix another roundToIntegral bug where very large values could become ↵Owen Anderson2012-08-15
| | | | | | infinity. Problem and solution identified by Steve Canon. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161969 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a problem with APFloat::roundToIntegral where it would return incorrect ↵Owen Anderson2012-08-15
| | | | | | results for negative inputs to trunc. Add unit tests to verify this behavior. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161929 91177308-0d34-0410-b5e6-96231b3b80d8
* Add range erase, element insert, and range insert methods toChandler Carruth2012-08-01
| | | | | | | | | | | | | | | TinyPtrVector. With these, it is sufficiently functional for my more normal / pedestrian uses. I've not included some r-value reference stuff here because the value type for a TinyPtrVector is, necessarily, just a pointer. I've added tests that cover the basic behavior of these routines, but they aren't as comprehensive as I'd like. In particular, they don't really test the iterator semantics as thoroughly as they should. Maybe some brave soul will feel enterprising and flesh them out. ;] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161104 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement copy and move assignment for TinyPtrVector. These try toChandler Carruth2012-07-31
| | | | | | re-use allocated vectors as much as possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161041 91177308-0d34-0410-b5e6-96231b3b80d8
* Bring TinyPtrVector under test. Somehow we never picked up unit testsChandler Carruth2012-07-31
| | | | | | | | | | | | | | | | | | | | | | | | | | | for this class. These tests exercise most of the basic properties, but the API for TinyPtrVector is very strange currently. My plan is to start fleshing out the API to match that of SmallVector, but I wanted a test for what is there first. Sadly, it doesn't look reasonable to just re-use the SmallVector tests, as this container can only ever store pointers, and much of the SmallVector testing is to get construction and destruction right. Just to get this basic test working, I had to add value_type to the interface. While here I found a subtle bug in the combination of 'erase', 'begin', and 'end'. Both 'begin' and 'end' wanted to use a null pointer to indicate the "end" iterator of an empty vector, regardless of whether there is actually a vector allocated or the pointer union is null. Everything else was fine with this except for erase. If you erase the last element of a vector after it has held more than one element, we return the end iterator of the underlying SmallVector which need not be a null pointer. Instead, simply use the pointer, and poniter + size() begin/end definitions in the tiny case, and delegate to the inner vector whenever it is present. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161024 91177308-0d34-0410-b5e6-96231b3b80d8
* Move the SmallVector unit tests to be type-parameterized so that we canChandler Carruth2012-07-30
| | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161001 91177308-0d34-0410-b5e6-96231b3b80d8
* Completely refactor the structuring of unittest CMake files to match theChandler Carruth2012-06-21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158909 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix PR13148, an inf-loop in StringMap.Chandler Carruth2012-06-19
| | | | | | | | | | | | | | | 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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158725 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove some superfluous SCOPED_TRACEs from this unit test.Chandler Carruth2012-06-19
| | | | | | | GoogleTest already prints errors with all the information about which test case contained the error. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158724 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove SmallMap unittests, unbreaking the build.Benjamin Kramer2012-06-17
| | | | | | I don't know how useful these are for SmallDenseMap, I'll leave that decision to Chandler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158646 91177308-0d34-0410-b5e6-96231b3b80d8
* Bring the return value of SmallVector::insert in line with std::vector::insert.Benjamin Kramer2012-06-17
| | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158645 91177308-0d34-0410-b5e6-96231b3b80d8
* SmallVector: return a valid iterator for the rare case of inserting an empty ↵Benjamin Kramer2012-06-17
| | | | | | | | range into a SmallVector. Patch by Johannes Schaub! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158643 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a unit test for 'swap', and fix a pile of bugs inChandler Carruth2012-06-17
| | | | | | | | | | | | | | | 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
* Add tests for *DenesMap for both key and value types' construction andChandler Carruth2012-06-17
| | | | | | | | | | | | | | | | | | | 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
* Introduce a SmallDenseMap container that re-uses the existing DenseMapChandler Carruth2012-06-17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Merge the SmallBitVector and BitVector unit tests with gtest's typed test ↵Benjamin Kramer2012-06-16
| | | | | | magic and bring SmallBitVector up to date. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158600 91177308-0d34-0410-b5e6-96231b3b80d8
* Work around a bug with MSVC 10 where it fails to recognize a valid useChandler Carruth2012-06-16
| | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158593 91177308-0d34-0410-b5e6-96231b3b80d8
* Type parameterize the DenseMap unit tests.Chandler Carruth2012-06-16
| | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158589 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer2012-06-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157885 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove the PTX back-end and all of its artifacts (triple, etc.)Justin Holewinski2012-05-24
| | | | | | | | This back-end was deprecated in favor of the NVPTX back-end. NV_CONTRIB git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157417 91177308-0d34-0410-b5e6-96231b3b80d8
* fix the quotient returned by sdivrem() for the case when LHS is negative and ↵Nuno Lopes2012-05-22
| | | | | | | | RHS is positive based on a patch by Preston Briggs, with some modifications git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157231 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove warning about testing unsigned int with int.Bill Wendling2012-05-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156812 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixed one small stupid, but critical bug.Stepan Dyatkovskiy2012-05-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156810 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove the expensive BitVector::operator~().Jakob Stoklund Olesen2012-05-14
| | | | | | | Returning a temporary BitVector is very expensive. If you must, create the temporary explicitly: Use BitVector(A).flip() instead of ~A. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156768 91177308-0d34-0410-b5e6-96231b3b80d8
* Add BitVector::anyCommon().Jakob Stoklund Olesen2012-05-14
| | | | | | The existing operation (A & B).any() is very slow. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156760 91177308-0d34-0410-b5e6-96231b3b80d8
* [Support/StringRef] Add find_last_not_of and {r,l,}trim.Michael J. Spencer2012-05-11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156652 91177308-0d34-0410-b5e6-96231b3b80d8
* Add unittests for Triple::getMacOSXVersion and Triple::getiOSVersion.Chad Rosier2012-05-09
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156507 91177308-0d34-0410-b5e6-96231b3b80d8
* SmallVector: Don't rely on having an assignment operator around in push_back ↵Benjamin Kramer2012-04-29
| | | | | | for POD-like types. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155791 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixed SmallMap test. The order of items is undefined in DenseMap. So being ↵Stepan Dyatkovskiy2012-04-26
| | | | | | checking the increment for big mode, we can only check that all items are in map. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155651 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply the SmallMap patch with a fix.Benjamin Kramer2012-04-25
| | | | | | Comparing ~0UL with an unsigned will always return false when long is 64 bits long. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155568 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "First implementation of:"Eric Christopher2012-04-25
| | | | | | | | This reverts commit 76271a3366731d4c372fdebcd8d3437e6e09a61b. as it's breaking the bots. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155562 91177308-0d34-0410-b5e6-96231b3b80d8
* First implementation of:Stepan Dyatkovskiy2012-04-25
| | | | | | | | | | | | | - 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155557 91177308-0d34-0410-b5e6-96231b3b80d8
* SparseSet: Add support for key-derived indexes and arbitrary key types.Andrew Trick2012-04-20
| | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155227 91177308-0d34-0410-b5e6-96231b3b80d8
* Add triple support for the IBM BG/P and BG/Q supercomputers.Hal Finkel2012-04-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153882 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix warnings.Michael J. Spencer2012-03-11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152522 91177308-0d34-0410-b5e6-96231b3b80d8
* Make StringRef::getAsInteger work with all integer types. Before this changeMichael J. Spencer2012-03-10
| | | | | | | | it would fail with {,u}int64_t on x86-64 Linux. This also removes code duplication. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152517 91177308-0d34-0410-b5e6-96231b3b80d8
* Add support to the hashing infrastructure for automatically hashing bothChandler Carruth2012-03-07
| | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152217 91177308-0d34-0410-b5e6-96231b3b80d8
* SmallPtrSet: Provide a more efficient implementation of swap than the ↵Benjamin Kramer2012-03-06
| | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152143 91177308-0d34-0410-b5e6-96231b3b80d8
* Add generic support for hashing StringRef objects using the new hashing library.Chandler Carruth2012-03-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152003 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach the hashing facilities how to hash std::string objects.Chandler Carruth2012-03-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152000 91177308-0d34-0410-b5e6-96231b3b80d8
* Split this test up into two smaller, and more focused tests.Chandler Carruth2012-03-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151999 91177308-0d34-0410-b5e6-96231b3b80d8
* Move the NonPOD struct out of the anonymous namespace instead of adding ↵Francois Pichet2012-03-03
| | | | | | | | llvm:: everywhere to fix the HashingTest on MSVC . chandlerc proposed this better solution on IRC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151974 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixes the Hashing tests on MSVC by adding llvm:: prefix to hash_value ↵Francois Pichet2012-03-03
| | | | | | function call. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151971 91177308-0d34-0410-b5e6-96231b3b80d8
* unittests/ADT/HashingTest.cpp: Temporarily disable a new test introduced in ↵NAKAMURA Takumi2012-03-03
| | | | | | r151891, to appease msvc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151970 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify the pair optimization. Rather than using complex type traits,Chandler Carruth2012-03-02
| | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151891 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a golden data test that I missed somehow the first time around.Chandler Carruth2012-03-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151886 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix bad indenting that was left over from cut/paste of the golden valuesChandler Carruth2012-03-02
| | | | | | for 32-bit builds in here. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151885 91177308-0d34-0410-b5e6-96231b3b80d8
* We really want to hash pairs of directly-hashable data as directlyChandler Carruth2012-03-02
| | | | | | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151883 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-30 19:31:14 +0000