Geoff Chappell - Software Analyst
The RtlRbInsertNodeEx function inserts a node into a Red Black tree.
VOID
RtlRbInsertNodeEx (
RTL_RB_TREE *Tree,
RTL_BALANCED_NODE *Parent,
BOOLEAN Right,
RTL_BALANCED_NODE *Node);
The required Tree argument is the address of a control structure for the tree. It maintains pointers to the tree’s root node and left-most node.
The optional Parent argument is the address of a node, assumed to be already in the tree, which is to become the inserted node’s parent. This argument can be NULL if the inserted node is to be the tree’s root.
The Right argument is TRUE or FALSE to insert to the right or left of the Parent, which is assumed to have no right or left child already. This argument is ignored if inserting as the root.
The required Node argument is the address of the node that is to be inserted. This node is assumed to be not already in the tree.
The function returns no indication of success or failure. It can fail, notably for perceiving the tree as corrupt, but it indicates this by __fastfail with FAST_FAIL_INVALID_BALANCED_TREE as the error code.
The RtlRbInsertNodeEx function is exported by name from the kernel and from NTDLL in version 6.2 and higher.
The RtlRbInsertNodeEx function is not documented. The function’s type is disclosed in public symbol files, starting with Windows 8, but Microsoft’s names for the arguments are not. The names used in this note are suppositions.
The function initialises the inserted Node as having no children. Insertion is trivial if Parent is NULL: the Node becomes the Tree’s root node and left-most node; the Node has no parent; and the Node is black. Ordinarily, the Node is inserted as the Parent’s right or left child according to the Right argument, and is red. If inserting to the left of a parent that is the tree’s left-most node, then the newly inserted node becomes the tree’s left-most node.
And that would be the whole of it except for red-black colouring and balancing!
The essential rules of the tree’s colouring are that: each node is either red or black; a red node is not allowed any red child; and the root node is necessarily black. The algorithm for inserting a node starts with the node as red (if it’s not the root). If the new node’s parent is red, this insertion conflicts with the rules and is put right by non-trivial adjustment of the tree. Because the parent is not black, it cannot be the root. It may therefore have a sibling. If this sibling is also red, then the adjustment starts as a relatively simple recolouring. The parent and its sibling are both changed to black, and if the grandparent is not the root, it is changed to red. (It cannot have been red already, since it had a red child.) This adjustment then recurses as if the grandparent were the newly inserted (red) node. It stops trivially on reaching the root. The adjustment becomes very much more substantial if the recursion reaches a (red) node whose parent is red and either has no sibling or has a black sibling. The tree gets rebalanced by promoting the node to be closer to the root than is its present grandparent. The node, which now has the (red) ex-parent as a child, and may now be the root, is changed to black. The ex-grandparent, which now either has no child or has as its one child the ex-parent’s (black) ex-sibling, is changed to red, and the tree’s adjustment is complete.
The Node’s insertion to the Right of the Parent (or as the root if Parent is NULL) replaces anything that was there. For all practical effect, the function assumes that the Parent has no Right node. In the intended circumstances, the caller has scanned the tree enough to identify Parent and Right as the appropriate location and direction for inserting the Node consistently with some left-right ordering that is the caller’s to design and manage. The function knows nothing of what governs the ordering, only that rebalancing the tree preserves the left-right ordering established by the insertions.
By inserting Node to the right of Parent, the caller establishes that Parent is the right-most node to the left of Node and that Parent had no right child. If Parent had a right child that the caller regards as being left of Node, then this child would have been the proper choice of Parent. If Parent had a right child that the caller regards as right of Node, then the proper insertion would be to the left of this child’s left-most descendant (else of the child itself). Microsoft’s programmers have inline routines named RtlTreeFindInsertLocation and RtlTreeFindInsertLocationOrExistingNode for scanning the tree to obtain Node and Right arguments for the call to RtlRbInsertNodeEx.
Beware that the function merely assumes that Right is either TRUE or FALSE, being immediately ready for use as an index into the Children array of an RTL_BALANCED_NODE. Indeed, for all that can be known without documentation, Right is not a BOOLEAN but is instead a UCHAR, perhaps taking values from macro definitions of 0 and 1 for left and right.
The function assumes that nodes have (at least) four-byte alignment. This allows that the one-bit colour of red versus black is safely encoded into the node’s pointer to its parent and therefore keeps the overhead per node to the space taken by its three pointers to left, right and parent nodes.
The function is self-contained in a non-paged code section. Provided all inputs are also in non-paged memory, the function can safely be called at any IRQL.