IntervalMap.h File Reference

This file implements a coalescing interval map for small objects. More...

#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>

Go to the source code of this file.

Classes
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...

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

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

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

Functions
template<typename NodeT >
void	llvm::IntervalMapImpl::adjustSiblingSizes (NodeT *Node[], unsigned Nodes, unsigned CurSize[], const unsigned NewSize[])
	IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
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.

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.