Skip to content
  • Jakob Stoklund Olesen's avatar
    Add ADT/IntervalMap. · 345945e3
    Jakob Stoklund Olesen authored
    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
    345945e3
Loading