summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/ADT/IntervalMapTest.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [ADT] IntervalMap: fix setStart and setStopMichael LeMay2016-11-031-0/+47
| | | | | | | | | | | | | | | | Summary: These functions currently require that the new closed interval has a length of at least 2. They also currently permit empty half-open intervals. This patch defines nonEmpty in each traits structure and uses it to correct the implementations of setStart and setStop. Reviewers: stoklund, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D26064 llvm-svn: 285957
* Add more checks to IntervalMapOverlaps::advance() to ensure that advanceTo seesJakob Stoklund Olesen2010-12-171-0/+25
| | | | | | monotonic keys. llvm-svn: 122093
* It is allowed to call IntervalMap::const_iterator::advanceTo() with a key thatJakob Stoklund Olesen2010-12-171-0/+14
| | | | | | | | moves the iterator to end(), and it is valid to call it on end(). That means it is valid to call advanceTo() with any monotonic key sequence. llvm-svn: 122092
* Fix crash when IntervalMapOverlaps::advanceTo moves past the last overlap.Jakob Stoklund Olesen2010-12-171-1/+5
| | | | llvm-svn: 122081
* Complete tests for IntervalMapOverlaps.Jakob Stoklund Olesen2010-12-171-1/+106
| | | | llvm-svn: 122019
* Add basic test exposing many bugs.Jakob Stoklund Olesen2010-12-161-0/+15
| | | | llvm-svn: 121995
* 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. llvm-svn: 120829
* 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. llvm-svn: 120264
* 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. llvm-svn: 120239
* 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. llvm-svn: 120237
* Add more tests for erase(). Fix a few exposed bugs.Jakob Stoklund Olesen2010-11-271-1/+29
| | | | llvm-svn: 120227
* 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. llvm-svn: 120226
* 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. llvm-svn: 120171
* Implement IntervalMap::clear().Jakob Stoklund Olesen2010-11-191-0/+9
| | | | llvm-svn: 119872
* Support backwards iteration starting from end().Jakob Stoklund Olesen2010-11-191-0/+10
| | | | llvm-svn: 119871
* 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. llvm-svn: 119787
* Revert "Add ADT/IntervalMap.", GCC doesn't like it.Jakob Stoklund Olesen2010-11-191-357/+0
| | | | | | This reverts r119772. llvm-svn: 119773
* 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. llvm-svn: 119772
OpenPOWER on IntegriCloud