Lines Matching refs:Node
60 Retrieve the user structure linked by the specified tree node.
64 @param[in] Node Pointer to the tree node whose associated user structure we
68 @return Pointer to user structure linked by Node.
73 IN CONST RED_BLACK_TREE_NODE *Node
76 return Node->UserStruct;
185 Look up the tree node that links the user structure that matches the
198 @return The tree node that links to the user structure matching
208 RED_BLACK_TREE_NODE *Node;
210 Node = Tree->Root;
211 while (Node != NULL) {
214 Result = Tree->KeyCompare (StandaloneKey, Node->UserStruct);
218 Node = (Result < 0) ? Node->Left : Node->Right;
220 return Node;
225 Find the tree node of the minimum user structure stored in the tree.
229 @param[in] Tree The tree to return the minimum node of. The user structure
230 linked by the minimum node compares less than all other user
235 @return The tree node that links the minimum user structure, otherwise.
243 RED_BLACK_TREE_NODE *Node;
245 Node = Tree->Root;
246 if (Node == NULL) {
249 while (Node->Left != NULL) {
250 Node = Node->Left;
252 return Node;
257 Find the tree node of the maximum user structure stored in the tree.
261 @param[in] Tree The tree to return the maximum node of. The user structure
262 linked by the maximum node compares greater than all other
267 @return The tree node that links the maximum user structure, otherwise.
275 RED_BLACK_TREE_NODE *Node;
277 Node = Tree->Root;
278 if (Node == NULL) {
281 while (Node->Right != NULL) {
282 Node = Node->Right;
284 return Node;
289 Get the tree node of the least user structure that is greater than the one
290 linked by Node.
294 @param[in] Node The node to get the successor node of.
296 @retval NULL If Node is NULL, or Node is the maximum node of its containing
297 tree (ie. Node has no successor node).
299 @return The tree node linking the least user structure that is greater
300 than the one linked by Node, otherwise.
305 IN CONST RED_BLACK_TREE_NODE *Node
311 if (Node == NULL) {
316 // If Node has a right subtree, then the successor is the minimum node of
319 Walk = Node->Right;
331 Child = Node;
342 Get the tree node of the greatest user structure that is less than the one
343 linked by Node.
347 @param[in] Node The node to get the predecessor node of.
349 @retval NULL If Node is NULL, or Node is the minimum node of its containing
350 tree (ie. Node has no predecessor node).
352 @return The tree node linking the greatest user structure that is less
353 than the one linked by Node, otherwise.
358 IN CONST RED_BLACK_TREE_NODE *Node
364 if (Node == NULL) {
369 // If Node has a left subtree, then the predecessor is the maximum node of
372 Walk = Node->Left;
384 Child = Node;
413 @param[in,out] Pivot The tree node to rotate other nodes right around. It
417 @param[out] NewRoot If Pivot has a parent node on input, then the
422 If Pivot has no parent node on input (ie. Pivot is
424 new root node of the tree in NewRoot.
478 @param[in,out] Pivot The tree node to rotate other nodes left around. It
482 @param[out] NewRoot If Pivot has a parent node on input, then the
487 If Pivot has no parent node on input (ie. Pivot is
489 new root node of the tree in NewRoot.
529 This function allocates the new tree node with MemoryAllocationLib's
534 @param[out] Node The meaning of this optional, output-only
539 Node is set on output to the new tree node that
543 (RETURN_OUT_OF_RESOURCES), Node is not changed.
548 RETURN_ALREADY_STARTED, then Node is set on output
549 to the node that links the colliding user
559 @retval RETURN_SUCCESS Insertion successful. A new tree node has
561 tree node is reported back in Node (if the
569 return the new node at some point if user
573 the new tree node. The tree has not been
578 that compares equal to UserStruct. The node
580 reported back in Node (if the caller
589 OUT RED_BLACK_TREE_NODE **Node OPTIONAL,
604 // First look for a collision, saving the last examined node for the case
617 if (Node != NULL) {
618 *Node = Tmp;
625 // no collision, allocate a new node
632 if (Node != NULL) {
633 *Node = Tmp;
637 // reference the user structure from the node
642 // Link the node as a child to the correct side of the parent.
643 // If there's no parent, the new node is the root node in the tree.
664 // #1 Each node is either red or black (RED_BLACK_TREE_NODE.Color).
666 // #2 Each leaf (ie. a pseudo-node pointed-to by a NULL valued
669 // #3 Each red node has two black children.
671 // #4 For any node N, and for any leaves L1 and L2 reachable from N, the
674 // #5 The root node is black.
676 // By replacing a leaf with a red node above, only property #3 may have been
687 // Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking
690 // Due to property #5, Tmp's parent cannot be the root node, hence Tmp's
747 // Rotate left, pivoting on node A. This keeps the breakage of
773 // paths going through node E now see a decrease in black count, while
774 // paths going through node B don't.
786 // Property #4 has been restored for node E, and preserved for others.
836 Check if a node is black, allowing for leaf nodes (see property #2).
840 param[in] Node The node to check. Node may be NULL, corresponding to a leaf.
842 @return If Node is NULL or colored black.
846 IN CONST RED_BLACK_TREE_NODE *Node
849 return (BOOLEAN)(Node == NULL || Node->Color == RedBlackTreeBlack);
854 Delete a node from the tree, unlinking the associated user structure.
858 @param[in,out] Tree The tree to delete Node from.
860 @param[in] Node The tree node to delete from Tree. The caller is
861 responsible for ensuring that Node belongs to
862 Tree, and that Node is non-NULL and valid. Node is
866 - OrderedCollectionFind(), for deleting a node by
870 for deleting the minimum / maximum node,
873 OrderedCollectionPrev(), for deleting a node
877 RETURN_ALREADY_STARTED, for deleting a node
882 Node argument (typically used for simplicity in
885 Node is released with MemoryAllocationLib's
889 iterators) *different* from Node remain valid. For
894 can be continued from Node, if
896 OrderedCollectionPrev() is called on Node
898 fetch the successor / predecessor node first,
899 then delete Node.
902 have otherwise returned Node at some point, as
904 reflect the absence of Node after
910 structure originally linked by Node (which is now
922 IN RED_BLACK_TREE_NODE *Node,
935 OrigLeftChild = Node->Left,
936 OrigRightChild = Node->Right,
937 OrigParent = Node->Parent;
940 *UserStruct = Node->UserStruct;
945 // - Child will point to the unique (or NULL) original child of the node that
947 // - Parent will point to the *position* of the original parent of the node
952 // Node has at most one child. We can connect that child (if any) with
953 // Node's parent (if any), unlinking Node. This will preserve ordering
954 // because the subtree rooted in Node's child (if any) remains on the same
955 // side of Node's parent (if any) that Node was before.
959 ColorOfUnlinked = Node->Color;
967 if (Node == OrigParent->Left) {
975 // Node has two children. We unlink Node's successor, and then link it into
976 // Node's place, keeping Node's original color. This preserves ordering
978 // - Node's left subtree is less than Node, hence less than Node's
980 // - Node's right subtree is greater than Node. Node's successor is the
981 // minimum of that subtree, hence Node's successor is less than Node's
983 // - Node's successor is in Node's subtree, hence it falls on the same side
984 // of Node's parent as Node itself. The relinking doesn't change this
992 // OrigRightChild itself is Node's successor, it has no left child:
996 // Node: B
1010 // Node's successor is the minimum of OrigRightChild's proper subtree:
1014 // Node: B
1025 // Unlink Node's successor (ie. ToRelink):
1029 // Node: B
1043 // We start to link Node's unlinked successor into Node's place:
1047 // Node: B C <--- ToRelink
1060 // The rest handles both cases, attaching ToRelink (Node's original
1066 // Node: B | Node: B Parent
1079 // Node's color must be preserved in Node's original place.
1082 ToRelink->Color = Node->Color;
1085 // Finish linking Node's unlinked successor into Node's place.
1088 // Node: B ToRelink Node: B
1103 if (Node == OrigParent->Left) {
1111 FreePool (Node);
1114 // If the node that we unlinked from its original spot (ie. Node itself, or
1115 // Node's successor), was red, then we broke neither property #3 nor property
1121 // However, if the unlinked node was black, then we have to transfer its
1129 // In the following loop we ascend searching for a red node to color black,
1153 // (Sibling can be black of course, but it has to be an internal node.
1160 // Sibling's red color implies its children (if any), node C and node
1183 // node.)
1221 // property #3, LeftNephew has two black children, hence node E is
1224 // Together with the rotation, this enables us to color node F red
1225 // (because property #3 will be satisfied). We flip node D to black
1257 // restoring property #1 for Child (node A): we color RightNephew
1258 // (node E) from red to black.
1262 // (node B). The transformation doesn't change the black count
1264 // - ascending from node A: 2 + x == 1 + 1 + x
1265 // - ascending from node C: y + 1 + x == y + 1 + x
1266 // - ascending from node E: 0 + 1 + x == 1 + x
1269 // both children of node D are black after the transformation
1347 Recursively check the red-black tree properties #1 to #4 on a node.
1349 @param[in] Node The root of the subtree to validate.
1351 @retval The black-height of Node's parent.
1355 IN CONST RED_BLACK_TREE_NODE *Node
1364 if (Node == NULL) {
1371 ASSERT (Node->Color == RedBlackTreeRed || Node->Color == RedBlackTreeBlack);
1376 if (Node->Color == RedBlackTreeRed) {
1377 ASSERT (NodeIsNullOrBlack (Node->Left));
1378 ASSERT (NodeIsNullOrBlack (Node->Right));
1384 LeftHeight = RedBlackTreeRecursiveCheck (Node->Left);
1385 RightHeight = RedBlackTreeRecursiveCheck (Node->Right);
1388 return (Node->Color == RedBlackTreeBlack) + LeftHeight;
1412 CONST RED_BLACK_TREE_NODE *Node;
1431 for (Node = OrderedCollectionNext (Last); Node != NULL;
1432 Node = OrderedCollectionNext (Last)) {
1433 ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) < 0);
1434 Last = Node;
1443 for (Node = OrderedCollectionPrev (Last); Node != NULL;
1444 Node = OrderedCollectionPrev (Last)) {
1445 ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) > 0);
1446 Last = Node;
