llvm::IntervalMapImpl Namespace Reference

IntervalMapImpl - Namespace used for IntervalMap implementation details. More...

Classes
class	BranchNode
class	LeafNode
class	NodeBase
class	NodeRef
struct	NodeSizer
class	Path

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

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

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

IntervalMapImpl - Namespace used for IntervalMap implementation details.

It should be considered private to the implementation.

Typedef Documentation

IdxPair

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

Definition at line 191 of file IntervalMap.h.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
Log2CacheLine
CacheLineBytes
DesiredNodeBytes

Definition at line 428 of file IntervalMap.h.

Function Documentation

adjustSiblingSizes()

template<typename NodeT >

void llvm::IntervalMapImpl::adjustSiblingSizes	(	NodeT *	Node[],
		unsigned	Nodes,
		unsigned	CurSize[],
		const unsigned	NewSize[]
	)

IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.

Parameters

Node	Array of pointers to sibling nodes.
Nodes	Number of nodes.
CurSize	Array of current node sizes, will be overwritten.
NewSize	Array of desired node sizes.

Definition at line 338 of file IntervalMap.h.

Referenced by llvm::IntervalMap< KeyT, ValT, N, Traits >::iterator::erase().

distribute()

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.

Reserve space for a new element at Position, and compute the node that will hold Position after redistributing node elements.

It is required that

Elements == sum(CurSize), and Elements + Grow <= Nodes * Capacity.

NewSize[] will be filled in such that:

sum(NewSize) == Elements, and NewSize[i] <= Capacity.

The returned index is the node where Position will go, so:

sum(NewSize[0..idx-1]) <= Position sum(NewSize[0..idx]) >= Position

The last equality, sum(NewSize[0..idx]) == Position, can only happen when Grow is set and NewSize[idx] == Capacity-1. The index points to the node before the one holding the Position'th element where there is room for an insertion.

Parameters

Nodes	The number of nodes.
Elements	Total elements in all nodes.
Capacity	The capacity of each node.
CurSize	Array[Nodes] of current node sizes, or NULL.
NewSize	Array[Nodes] to receive the new node sizes.
Position	Insert position.
Grow	Reserve space for a new element at Position.

Returns

(node, offset) for Position.

Definition at line 120 of file IntervalMap.cpp.

References assert().

Referenced by llvm::IntervalMap< KeyT, ValT, N, Traits >::iterator::erase(), and llvm::IntervalMap< SlotIndex, unsigned >::overlaps().