aboutsummaryrefslogtreecommitdiffstats
path: root/unittests/ADT
Commit message (Collapse)AuthorAgeFilesLines
* Add IntervalMap::iterator::set{Start,Stop,Value} methods that allow limitedJakob Stoklund Olesen2010-12-031-7/+119
| | | | | | | | | | | editing of the current interval. These methods may cause coalescing, there are corresponding set*Unchecked methods for editing without coalescing. The non-coalescing methods are useful for applying monotonic transforms to all keys or values in a map without accidentally coalescing transformed and untransformed intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120829 91177308-0d34-0410-b5e6-96231b3b80d8
* Support/ADT/Twine: Add toNullTerminatedStringRef.Michael J. Spencer2010-12-011-0/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120600 91177308-0d34-0410-b5e6-96231b3b80d8
* PR5207: Rename overloaded APInt methods set(), clear(), flip() toJay Foad2010-12-011-1/+1
| | | | | | setAllBits(), setBit(unsigned), etc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120564 91177308-0d34-0410-b5e6-96231b3b80d8
* Merge System into Support.Michael J. Spencer2010-11-291-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120298 91177308-0d34-0410-b5e6-96231b3b80d8
* Disallow overlapping inserts, even when inserting the same value.Jakob Stoklund Olesen2010-11-281-97/+9
| | | | | | | | | | | We always disallowed overlapping inserts with different values, and this makes the insertion code smaller and faster. If an overwriting insert is needed, it can be added as a separate method that trims any existing intervals before inserting. The immediate use cases for IntervalMap don't need this - they only use disjoint insertions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120264 91177308-0d34-0410-b5e6-96231b3b80d8
* Add default constructors for iterators.Jakob Stoklund Olesen2010-11-281-0/+8
| | | | | | | These iterators don't point anywhere, and they can't be compared to anything. They are only good for assigning to. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120239 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement const_iterator::advanceTo().Jakob Stoklund Olesen2010-11-281-0/+42
| | | | | | | This is a version of find() that always searches forwards and is faster for local searches. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120237 91177308-0d34-0410-b5e6-96231b3b80d8
* Add more tests for erase(). Fix a few exposed bugs.Jakob Stoklund Olesen2010-11-271-1/+29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120227 91177308-0d34-0410-b5e6-96231b3b80d8
* Add test case with randomly ordered insertions, massive coalescing.Jakob Stoklund Olesen2010-11-271-0/+24
| | | | | | | | | | Implement iterator::erase() in a simple version that erases nodes when they become empty, but doesn't try to redistribute elements among siblings for better packing. Handle coalescing across leaf nodes which may require erasing entries. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120226 91177308-0d34-0410-b5e6-96231b3b80d8
* Add B+-tree test case that creates a height 3 tree with a smaller root node.Jakob Stoklund Olesen2010-11-261-0/+51
| | | | | | Change temporary debugging code to write a dot file directly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120171 91177308-0d34-0410-b5e6-96231b3b80d8
* Tweak ImmutableMap/ImmutableSet/ImmutableList APIsTed Kremenek2010-11-241-24/+24
| | | | | | | | | | to use lowercase letters for the start of most method names and to replace some method names with more descriptive names (e.g., "getLeft()" instead of "Left()"). No real functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120070 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement IntervalMap::clear().Jakob Stoklund Olesen2010-11-191-0/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119872 91177308-0d34-0410-b5e6-96231b3b80d8
* Support backwards iteration starting from end().Jakob Stoklund Olesen2010-11-191-0/+10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119871 91177308-0d34-0410-b5e6-96231b3b80d8
* Add test for PR 8111. By Frits van Bommel.Dale Johannesen2010-11-191-0/+39
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119870 91177308-0d34-0410-b5e6-96231b3b80d8
* Add ADT/IntervalMap.Jakob Stoklund Olesen2010-11-191-0/+357
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a sorted interval map data structure for small keys and values with automatic coalescing and bidirectional iteration over coalesced intervals. Except for coalescing intervals, it provides similar functionality to std::map. It is however much more compact for small keys and values, and hopefully faster too. The container object itself can hold the first few intervals without any allocations, then it switches to a cache conscious B+-tree representation. A recycling allocator can be shared between many containers, even between containers holding different types. The IntervalMap is initially intended to be used with SlotIndex intervals for: - Backing store for LiveIntervalUnion that is smaller and faster than std::set. - Backing store for LiveInterval with less overhead than std::vector for typical intervals and O(N log N) merging of large intervals. 99% of virtual registers need 4 entries or less and would benefit from the small object optimization. - Backing store for LiveDebugVariable which doesn't exist yet, but will track debug variables during register allocation. This is a work in progress. Missing items are: - Performance metrics. - erase(). - insert() shrinkage. - clear(). - More performance metrics. - Simplification and detemplatization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119787 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "Add ADT/IntervalMap.", GCC doesn't like it.Jakob Stoklund Olesen2010-11-191-357/+0
| | | | | | This reverts r119772. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119773 91177308-0d34-0410-b5e6-96231b3b80d8
* Add ADT/IntervalMap.Jakob Stoklund Olesen2010-11-191-0/+357
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a sorted interval map data structure for small keys and values with automatic coalescing and bidirectional iteration over coalesced intervals. Except for coalescing intervals, it provides similar functionality to std::map. It is however much more compact for small keys and values, and hopefully faster too. The container object itself can hold the first few intervals without any allocations, then it switches to a cache conscious B+-tree representation. A recycling allocator can be shared between many containers, even between containers holding different types. The IntervalMap is initially intended to be used with SlotIndex intervals for: - Backing store for LiveIntervalUnion that is smaller and faster than std::set. - Backing store for LiveInterval with less overhead than std::vector for typical intervals and O(N log N) merging of large intervals. 99% of virtual registers need 4 entries or less and would benefit from the small object optimization. - Backing store for LiveDebugVariable which doesn't exist yet, but will track debug variables during register allocation. This is a work in progress. Missing items are: - Performance metrics. - erase(). - insert() shrinkage. - clear(). - More performance metrics. - Simplification and detemplatization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119772 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch attribute macros to use 'LLVM_' as a prefix. We retain the old namesChandler Carruth2010-10-231-1/+1
| | | | | | | until other LLVM projects using these are cleaned up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117200 91177308-0d34-0410-b5e6-96231b3b80d8
* Move ValueMapTest from ADT to VMCore so that ADT doesn't needDan Gohman2010-09-272-295/+1
| | | | | | | to link in "core". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114831 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an all() method to BitVector, for testing whether all bits are set.Dan Gohman2010-09-272-0/+14
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114830 91177308-0d34-0410-b5e6-96231b3b80d8
* Add better support for environment portion of triple. Original patch byDuncan Sands2010-09-161-0/+8
| | | | | | | Cameron Esfahani, tweaked to use array_lengthof. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114073 91177308-0d34-0410-b5e6-96231b3b80d8
* Attempt to unbreak the FreeBSD buildbot by XFAILing a unit test that seems to beJakob Stoklund Olesen2010-09-141-0/+5
| | | | | | | | miscompiled by the system gcc-4.2.1 The test remains enabled for the second-stage test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113824 91177308-0d34-0410-b5e6-96231b3b80d8
* StringRef::compare_numeric also differed from StringRef::compare for ↵Benjamin Kramer2010-08-261-0/+1
| | | | | | characters > 127. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112189 91177308-0d34-0410-b5e6-96231b3b80d8
* Do unsigned char comparisons in StringRef::compare_lower to be more ↵Benjamin Kramer2010-08-261-0/+8
| | | | | | consistent with compare in corner cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112185 91177308-0d34-0410-b5e6-96231b3b80d8
* Silence 'unused' warning.Bill Wendling2010-08-191-1/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111539 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a 'normalize' method to the Triple class, which takes a mucked upDuncan Sands2010-08-121-9/+108
| | | | | | | | | | | | | | | | target triple and straightens it out. This does less than gcc's script config.sub, for example it turns i386-mingw32 into i386--mingw32 not i386-pc-mingw32, but it does a decent job of turning funky triples into something that the rest of the Triple class can understand. The plan is to use this to canonicalize triple's when they are first provided by users, and have the rest of LLVM only deal with canonical triples. Once this is done the special case workarounds in the Triple constructor can be removed, making the class more regular and easier to use. The comments and unittests for the Triple class are already adjusted in this patch appropriately for this brave new world of increased uniformity. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110909 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove the ValueMap copy constructor. It's not used anywhere,Duncan Sands2010-08-081-9/+0
| | | | | | | | and removing it catches the mistake of passing a ValueMap by copy rather than by reference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110549 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the ValueMap copy constructor. The issue is that the map keys are valueDuncan Sands2010-07-301-0/+9
| | | | | | | | | | | | | | | | | handles with a pointer to the containing map. When a map is copied, these pointers need to be corrected to point to the new map. If not, then consider the case of a map M1 which maps a value V to something. Create a copy M2 of M1. At this point there are two value handles on V, one representing V as a key in M1, the other representing V as a key in M2. But both value handles point to M1 as the containing map. Now delete V. The value handles remove themselves from their containing map (which destroys them), but only the first value handle is successful: the second one cannot remove itself from M1 as (once the first one has removed itself) there is nothing there to remove; it is therefore not destroyed. This causes an assertion failure "All references to V were not removed?". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109851 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch from EXPECT_EQ({true,false, ...) to the more canonicalChandler Carruth2010-07-131-2/+2
| | | | | | | | EXPECT_{TRUE,FALSE}(...) macros. This also prevents suprious warnings about bool-to-pointer conversion that occurs withit EXPECT_EQ. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108248 91177308-0d34-0410-b5e6-96231b3b80d8
* Use non-bool values for .count.Bill Wendling2010-07-101-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108048 91177308-0d34-0410-b5e6-96231b3b80d8
* ADT: Add DAGDeltaAlgorithm, which is a DAG minimization algorithm built on ↵Daniel Dunbar2010-06-081-0/+122
| | | | | | | | top of the standard 'delta debugging' algorithm. - This can give substantial speedups in the delta process for inputs we can construct dependency information for. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@105612 91177308-0d34-0410-b5e6-96231b3b80d8
* Add StringRef::compare_numeric and use it to sort TableGen register records.Jakob Stoklund Olesen2010-05-261-0/+11
| | | | | | | This means that our Registers are now ordered R7, R8, R9, R10, R12, ... Not R1, R10, R11, R12, R2, R3, ... git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104745 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix const ilist_node::get{Prev,Next}Node() to actually compile. Picky, picky.Daniel Dunbar2010-05-131-0/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103723 91177308-0d34-0410-b5e6-96231b3b80d8
* ADT: Add ilist_node::get{Prev,Next}Node, which return the adjacent node or null.Daniel Dunbar2010-05-121-0/+39
| | | | | | | | | | | | | | | | | | | | - This provides a convenient alternative to using something llvm::prior or manual iterator access, for example:: if (T *Prev = foo->getPrevNode()) ... instead of:: iterator it(foo); if (it != begin()) { --it; ... } - Chris, please review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103647 91177308-0d34-0410-b5e6-96231b3b80d8
* Update BitVectorTest.cpp to stay in sync with SmallBitVectorTest.cpp,Dan Gohman2010-04-302-3/+16
| | | | | | | and fix a bug in BitVector's reference proxy class which this exposed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@102768 91177308-0d34-0410-b5e6-96231b3b80d8
* SmallBitVector: Rework find_first/find_next and tweak test to test them (at ↵Benjamin Kramer2010-04-301-2/+3
| | | | | | least on 64 bit platforms). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@102712 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement a read/write operator[] for SmallBitVector with a proxy class.Benjamin Kramer2010-04-301-0/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@102709 91177308-0d34-0410-b5e6-96231b3b80d8
* silence some unused-value warnings.Chris Lattner2010-04-181-4/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@101689 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix SmallVector's insert to handle non-random-access iterators.Dan Gohman2010-03-261-0/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@99633 91177308-0d34-0410-b5e6-96231b3b80d8
* Make this test more lenient; with SmallVector now using actuallyDan Gohman2010-03-181-1/+1
| | | | | | | | aligned storage, the capacity may be more than what is explicitly requested. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@98846 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix death tests in -Asserts builds.Jeffrey Yasskin2010-03-172-0/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@98701 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach APFloat how to create both QNaNs and SNaNs and with arbitrary-widthJohn McCall2010-02-281-0/+29
| | | | | | | | | | payloads. APFloat's internal folding routines always make QNaNs now, instead of sometimes making QNaNs and sometimes SNaNs depending on the type. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97364 91177308-0d34-0410-b5e6-96231b3b80d8
* Make APFloat's string-parsing routines a bit safer against very large exponents.John McCall2010-02-261-0/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97278 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix (harmless) memory leak found by memcheck.Jeffrey Yasskin2010-02-111-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95862 91177308-0d34-0410-b5e6-96231b3b80d8
* Silence GCC warnings.Benjamin Kramer2010-02-102-12/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95779 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement operators |=, &=, and ^= for SmallBitVector, and remove theDan Gohman2010-02-102-0/+79
| | | | | | | | restriction in BitVector for |= and ^= that the operand must be the same length. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95768 91177308-0d34-0410-b5e6-96231b3b80d8
* Disable unittests/ADT/BitVectorTest on PPC Darwin.Dale Johannesen2010-02-092-0/+10
| | | | | | | | | | | It fails with a release build only, for reasons as yet unknown. (If there's a better way to Xfail things here let me know, doesn't seem to be any prior art in unittests.) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95700 91177308-0d34-0410-b5e6-96231b3b80d8
* Make APInt::countLeadingZerosSlowCase() treat the contents of padding bitsJohn McCall2010-02-031-0/+2
| | | | | | | | as undefined. Fixes an assertion in APFloat::toString noticed by Dale. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95196 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a SmallBitVector class, which mimics BitVector but uses onlyDan Gohman2010-01-052-0/+280
| | | | | | | | | | | | | a single pointer (PointerIntPair) member. In "small" mode, the pointer field is reinterpreted as a set of bits. In "large" mode, the pointer points to a heap-allocated object. Also, give BitVector empty and swap functions. And, add some simple unittests for BitVector and SmallBitVector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92730 91177308-0d34-0410-b5e6-96231b3b80d8
* Silence compiler warning.Benjamin Kramer2009-12-311-1/+1
| | | | | | | warning: comparison between signed and unsigned integer expressions git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92359 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-02-07 21:15:21 +0000