LLVM: llvm::IntervalMapImpl Namespace Reference (original) (raw)
IntervalMapImpl - Namespace used for IntervalMap implementation details. More...
| Classes | |
|---|---|
| class | BranchNode |
| class | LeafNode |
| class | NodeBase |
| class | NodeRef |
| struct | NodeSizer |
| class | Path |
| Enumerations | |
|---|---|
| enum | { Log2CacheLine = 6 , CacheLineBytes = 1 << Log2CacheLine , DesiredNodeBytes = 3 * CacheLineBytes } |
| Functions | |
|---|---|
| template | |
| void | adjustSiblingSizes (NodeT *Node[], unsigned Nodes, unsigned CurSize[], const unsigned NewSize[]) |
| IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. | |
| LLVM_ABI 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. |
IntervalMapImpl - Namespace used for IntervalMap implementation details.
It should be considered private to the implementation.
◆ IdxPair
◆ anonymous enum
| Enumerator |
|---|
| Log2CacheLine |
| CacheLineBytes |
| DesiredNodeBytes |
Definition at line 431 of file IntervalMap.h.
◆ adjustSiblingSizes()
template
| 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 341 of file IntervalMap.h.
References assert().
◆ distribute()
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().