llvm::IntervalMapImpl Namespace Reference

Classes
class	NodeBase
struct	NodeSizer
class	NodeRef
class	LeafNode
class	BranchNode
class	Path
Typedefs
typedef std::pair< unsigned, unsigned >	IdxPair
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[])
IdxPair	distribute (unsigned Nodes, unsigned Elements, unsigned Capacity, const unsigned *CurSize, unsigned NewSize[], unsigned Position, bool Grow)

---

Detailed Description

IntervalMapImpl - Namespace used for IntervalMap implementation details. It should be considered private to the implementation.

---

Typedef Documentation

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

Definition at line 180 of file IntervalMap.h.

---

Enumeration Type Documentation

anonymous enum

Enumerator:

Log2CacheLine
CacheLineBytes
DesiredNodeBytes

Definition at line 421 of file IntervalMap.h.

---

Function Documentation

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 330 of file IntervalMap.h.

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.