Add ADT/IntervalMap.
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
diff --git a/unittests/CMakeLists.txt b/unittests/CMakeLists.txt
index fda1875..eaecc9c 100644
--- a/unittests/CMakeLists.txt
+++ b/unittests/CMakeLists.txt
@@ -45,6 +45,7 @@
ADT/DenseSetTest.cpp
ADT/ilistTest.cpp
ADT/ImmutableSetTest.cpp
+ ADT/IntervalMapTest.cpp
ADT/SmallBitVectorTest.cpp
ADT/SmallStringTest.cpp
ADT/SmallVectorTest.cpp