LLVM  15.0.0git
Classes | Namespaces | Typedefs | Enumerations | Functions
IntervalMap.h File Reference
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/RecyclingAllocator.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <new>
#include <utility>
Include dependency graph for IntervalMap.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.


struct  llvm::IntervalMapInfo< T >
struct  llvm::IntervalMapHalfOpenInfo< T >
class  llvm::IntervalMapImpl::NodeBase< T1, T2, N >
struct  llvm::IntervalMapImpl::NodeSizer< KeyT, ValT >
class  llvm::IntervalMapImpl::NodeRef
class  llvm::IntervalMapImpl::LeafNode< KeyT, ValT, N, Traits >
class  llvm::IntervalMapImpl::BranchNode< KeyT, ValT, N, Traits >
class  llvm::IntervalMapImpl::Path
class  llvm::IntervalMap< KeyT, ValT, N, Traits >
class  llvm::IntervalMap< KeyT, ValT, N, Traits >::const_iterator
class  llvm::IntervalMap< KeyT, ValT, N, Traits >::iterator
class  llvm::IntervalMapOverlaps< MapA, MapB >
 IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two IntervalMaps. More...


 This is an optimization pass for GlobalISel generic memory operations.
 IntervalMapImpl - Namespace used for IntervalMap implementation details.


using llvm::IntervalMapImpl::IdxPair = std::pair< unsigned, unsigned >


enum  { llvm::IntervalMapImpl::Log2CacheLine = 6, llvm::IntervalMapImpl::CacheLineBytes = 1 << Log2CacheLine, llvm::IntervalMapImpl::DesiredNodeBytes = 3 * CacheLineBytes }


template<typename NodeT >
void llvm::IntervalMapImpl::adjustSiblingSizes (NodeT *Node[], unsigned Nodes, unsigned CurSize[], const unsigned NewSize[])
 IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. More...
IdxPair llvm::IntervalMapImpl::distribute (unsigned Nodes, unsigned Elements, unsigned Capacity, const unsigned *CurSize, unsigned NewSize[], unsigned Position, bool Grow)
 IntervalMapImpl::distribute - Compute a new distribution of node elements after an overflow or underflow. More...

Detailed Description

This file implements a coalescing interval map for small objects.

KeyT objects are mapped to ValT objects. Intervals of keys that map to the same value are represented in a compressed form.

Iterators provide ordered access to the compressed intervals rather than the individual keys, and insert and erase operations use key intervals as well.

Like SmallVector, IntervalMap will store the first N intervals in the map object itself without any allocations. When space is exhausted it switches to a B+-tree representation with very small overhead for small key and value objects.

A Traits class specifies how keys are compared. It also allows IntervalMap to work with both closed and half-open intervals.

Keys and values are not stored next to each other in a std::pair, so we don't provide such a value_type. Dereferencing iterators only returns the mapped value. The interval bounds are accessible through the start() and stop() iterator methods.

IntervalMap is optimized for small key and value objects, 4 or 8 bytes each is the optimal size. For large objects use std::map instead.

Definition in file IntervalMap.h.