LLVM 19.0.0git
Classes | Typedefs | Enumerations | Functions
llvm::IntervalMapImpl Namespace Reference

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


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


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


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


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

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

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Definition at line 430 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.

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

References assert().

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

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.
(node, offset) for Position.

Definition at line 120 of file IntervalMap.cpp.

References assert().