LLVM  9.0.0svn
Classes | Typedefs | Enumerations | Functions
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 190 of file IntervalMap.h.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum
Enumerator
Log2CacheLine 
CacheLineBytes 
DesiredNodeBytes 

Definition at line 427 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
NodeArray of pointers to sibling nodes.
NodesNumber of nodes.
CurSizeArray of current node sizes, will be overwritten.
NewSizeArray of desired node sizes.

Definition at line 337 of file IntervalMap.h.

References assert(), and distribute().

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
NodesThe number of nodes.
ElementsTotal elements in all nodes.
CapacityThe capacity of each node.
CurSizeArray[Nodes] of current node sizes, or NULL.
NewSizeArray[Nodes] to receive the new node sizes.
PositionInsert position.
GrowReserve space for a new element at Position.
Returns
(node, offset) for Position.

Definition at line 119 of file IntervalMap.cpp.

References assert().

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