This library instance is useful when a fast associative container is needed. Worst case time complexity is O(log n) for Find(), Next(), Prev(), Min(), Max(), Insert(), and Delete(), where "n" is the number of elements in the tree. Complete ordered traversal takes O(n) time.
The implementation is also useful as a fast priority queue.
Copyright (C) 2014, Red Hat, Inc. Copyright (c) 2014, Intel Corporation. All rights reserved.
This program and the accompanying materials are licensed and made available under the terms and conditions of the BSD License that accompanies this distribution. The full text of the license may be found at http://opensource.org/licenses/bsd-license.php.
THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
typedef ORDERED_COLLECTION RED_BLACK_TREE |
enum RED_BLACK_TREE_COLOR |
BOOLEAN NodeIsNullOrBlack | ( | IN CONST RED_BLACK_TREE_NODE * | Node | ) |
Check if a node is black, allowing for leaf nodes (see property #2).
This is a convenience shorthand.
param[in] Node The node to check. Node may be NULL, corresponding to a leaf.
References NULL, and RedBlackTreeBlack.
Referenced by OrderedCollectionDelete(), RedBlackTreeRecursiveCheck(), and RedBlackTreeValidate().
VOID EFIAPI OrderedCollectionDelete | ( | IN OUT RED_BLACK_TREE * | Tree, | |
IN RED_BLACK_TREE_NODE * | Node, | |||
OUT VOID ** | UserStruct | |||
) |
Delete a node from the tree, unlinking the associated user structure.
Read-write operation.
[in,out] | Tree | The tree to delete Node from. |
[in] | Node | The tree node to delete from Tree. The caller is responsible for ensuring that Node belongs to Tree, and that Node is non-NULL and valid. Node is typically an earlier return value, or output parameter, of: |
Given a non-empty Tree, Tree->Root is also a valid Node argument (typically used for simplicity in loops that empty the tree completely).
Node is released with MemoryAllocationLib's FreePool() function.
Existing RED_BLACK_TREE_NODE pointers (ie. iterators) *different* from Node remain valid. For example:
[out] | UserStruct | If the caller provides this optional output-only parameter, then on output it is set to the user structure originally linked by Node (which is now freed). |
References ASSERT, FeaturePcdGet, FreePool(), NodeIsNullOrBlack(), NULL, RedBlackTreeBlack, RedBlackTreeRed, RedBlackTreeRotateLeft(), RedBlackTreeRotateRight(), and RedBlackTreeValidate().
RED_BLACK_TREE_NODE* EFIAPI OrderedCollectionFind | ( | IN CONST RED_BLACK_TREE * | Tree, | |
IN CONST VOID * | StandaloneKey | |||
) |
Look up the tree node that links the user structure that matches the specified standalone key.
Read-only operation.
[in] | Tree | The tree to search for StandaloneKey. |
[in] | StandaloneKey | The key to locate among the user structures linked into Tree. StandaloneKey will be passed to Tree->KeyCompare(). |
NULL | StandaloneKey could not be found. |
References NULL.
RED_BLACK_TREE* EFIAPI OrderedCollectionInit | ( | IN RED_BLACK_TREE_USER_COMPARE | UserStructCompare, | |
IN RED_BLACK_TREE_KEY_COMPARE | KeyCompare | |||
) |
Allocate and initialize the RED_BLACK_TREE structure.
Allocation occurs via MemoryAllocationLib's AllocatePool() function.
[in] | UserStructCompare | This caller-provided function will be used to order two user structures linked into the tree, during the insertion procedure. |
[in] | KeyCompare | This caller-provided function will be used to order the standalone search key against user structures linked into the tree, during the lookup procedure. |
NULL | If allocation failed. |
References AllocatePool(), FeaturePcdGet, NULL, and RedBlackTreeValidate().
RETURN_STATUS EFIAPI OrderedCollectionInsert | ( | IN OUT RED_BLACK_TREE * | Tree, | |
OUT RED_BLACK_TREE_NODE ** | Node, | |||
IN VOID * | UserStruct | |||
) |
Insert (link) a user structure into the tree.
Read-write operation.
This function allocates the new tree node with MemoryAllocationLib's AllocatePool() function.
[in,out] | Tree | The tree to insert UserStruct into. |
[out] | Node | The meaning of this optional, output-only parameter depends on the return value of the function. |
When insertion fails due to lack of memory (RETURN_OUT_OF_RESOURCES), Node is not changed.
When insertion fails due to key collision (ie. another user structure is already in the tree that compares equal to UserStruct), with return value RETURN_ALREADY_STARTED, then Node is set on output to the node that links the colliding user structure. This enables "find-or-insert" in one function call, or helps with later removal of the colliding element.
[in] | UserStruct | The user structure to link into the tree. UserStruct is ordered against in-tree user structures with the Tree->UserStructCompare() function. |
RETURN_SUCCESS | Insertion successful. A new tree node has been allocated, linking UserStruct. The new tree node is reported back in Node (if the caller requested it). |
RETURN_OUT_OF_RESOURCES | AllocatePool() failed to allocate memory for the new tree node. The tree has not been changed. Existing RED_BLACK_TREE_NODE pointers into Tree remain valid. | |
RETURN_ALREADY_STARTED | A user structure has been found in the tree that compares equal to UserStruct. The node linking the colliding user structure is reported back in Node (if the caller requested it). The tree has not been changed. Existing RED_BLACK_TREE_NODE pointers into Tree remain valid. |
References AllocatePool(), ASSERT, FeaturePcdGet, NULL, RedBlackTreeBlack, RedBlackTreeRed, RedBlackTreeRotateLeft(), RedBlackTreeRotateRight(), RedBlackTreeValidate(), RETURN_ALREADY_STARTED, RETURN_OUT_OF_RESOURCES, and RETURN_SUCCESS.
BOOLEAN EFIAPI OrderedCollectionIsEmpty | ( | IN CONST RED_BLACK_TREE * | Tree | ) |
Check whether the tree is empty (has no nodes).
Read-only operation.
[in] | Tree | The tree to check for emptiness. |
TRUE | The tree is empty. | |
FALSE | The tree is not empty. |
References NULL.
Referenced by OrderedCollectionUninit().
RED_BLACK_TREE_NODE* EFIAPI OrderedCollectionMax | ( | IN CONST RED_BLACK_TREE * | Tree | ) |
Find the tree node of the maximum user structure stored in the tree.
Read-only operation.
[in] | Tree | The tree to return the maximum node of. The user structure linked by the maximum node compares greater than all other user structures in the tree. |
NULL | If Tree is empty. |
References NULL.
Referenced by RedBlackTreeValidate().
RED_BLACK_TREE_NODE* EFIAPI OrderedCollectionMin | ( | IN CONST RED_BLACK_TREE * | Tree | ) |
Find the tree node of the minimum user structure stored in the tree.
Read-only operation.
[in] | Tree | The tree to return the minimum node of. The user structure linked by the minimum node compares less than all other user structures in the tree. |
NULL | If Tree is empty. |
References NULL.
Referenced by RedBlackTreeValidate().
RED_BLACK_TREE_NODE* EFIAPI OrderedCollectionNext | ( | IN CONST RED_BLACK_TREE_NODE * | Node | ) |
Get the tree node of the least user structure that is greater than the one linked by Node.
Read-only operation.
[in] | Node | The node to get the successor node of. |
NULL | If Node is NULL, or Node is the maximum node of its containing tree (ie. Node has no successor node). |
Referenced by RedBlackTreeValidate().
RED_BLACK_TREE_NODE* EFIAPI OrderedCollectionPrev | ( | IN CONST RED_BLACK_TREE_NODE * | Node | ) |
Get the tree node of the greatest user structure that is less than the one linked by Node.
Read-only operation.
[in] | Node | The node to get the predecessor node of. |
NULL | If Node is NULL, or Node is the minimum node of its containing tree (ie. Node has no predecessor node). |
Referenced by RedBlackTreeValidate().
VOID EFIAPI OrderedCollectionUninit | ( | IN RED_BLACK_TREE * | Tree | ) |
Uninitialize and release an empty RED_BLACK_TREE structure.
Read-write operation.
Release occurs via MemoryAllocationLib's FreePool() function.
It is the caller's responsibility to delete all nodes from the tree before calling this function.
[in] | Tree | The empty tree to uninitialize and release. |
References ASSERT, FreePool(), and OrderedCollectionIsEmpty().
VOID* EFIAPI OrderedCollectionUserStruct | ( | IN CONST RED_BLACK_TREE_NODE * | Node | ) |
Retrieve the user structure linked by the specified tree node.
Read-only operation.
[in] | Node | Pointer to the tree node whose associated user structure we want to retrieve. The caller is responsible for passing a non-NULL argument. |
UINT32 RedBlackTreeRecursiveCheck | ( | IN CONST RED_BLACK_TREE_NODE * | Node | ) |
Recursively check the red-black tree properties #1 to #4 on a node.
[in] | Node | The root of the subtree to validate. |
The | black-height of Node's parent. |
References ASSERT, NodeIsNullOrBlack(), NULL, RedBlackTreeBlack, and RedBlackTreeRed.
Referenced by RedBlackTreeValidate().
VOID RedBlackTreeRotateLeft | ( | IN OUT RED_BLACK_TREE_NODE * | Pivot, | |
OUT RED_BLACK_TREE_NODE ** | NewRoot | |||
) |
Rotate tree nodes around Pivot to the left.
Parent Parent | | Pivot RightChild . \ / . Node1 RightChild ---> Pivot Node2 /. . RightLeftChild Node2 Node1 RightLeftChild
The ordering Node1 < Pivot < RightLeftChild < RightChild < Node2 is kept intact. Parent (if any) is either at the left extreme or the right extreme of this ordering, and that relation is also kept intact.
Edges marked with a dot (".") don't change during rotation.
Internal read-write operation.
[in,out] | Pivot | The tree node to rotate other nodes left around. It is the caller's responsibility to ensure that Pivot->Right is not NULL. |
[out] | NewRoot | If Pivot has a parent node on input, then the function updates Pivot's original parent on output according to the rotation, and NewRoot is not accessed. |
References NULL.
Referenced by OrderedCollectionDelete(), and OrderedCollectionInsert().
VOID RedBlackTreeRotateRight | ( | IN OUT RED_BLACK_TREE_NODE * | Pivot, | |
OUT RED_BLACK_TREE_NODE ** | NewRoot | |||
) |
Rotate tree nodes around Pivot to the right.
Parent Parent | | Pivot LeftChild / . . LeftChild Node1 ---> Node2 Pivot . \ / . Node2 LeftRightChild LeftRightChild Node1
The ordering Node2 < LeftChild < LeftRightChild < Pivot < Node1 is kept intact. Parent (if any) is either at the left extreme or the right extreme of this ordering, and that relation is also kept intact.
Edges marked with a dot (".") don't change during rotation.
Internal read-write operation.
[in,out] | Pivot | The tree node to rotate other nodes right around. It is the caller's responsibility to ensure that Pivot->Left is not NULL. |
[out] | NewRoot | If Pivot has a parent node on input, then the function updates Pivot's original parent on output according to the rotation, and NewRoot is not accessed. |
References NULL.
Referenced by OrderedCollectionDelete(), and OrderedCollectionInsert().
VOID RedBlackTreeValidate | ( | IN CONST RED_BLACK_TREE * | Tree | ) |
A slow function that asserts that the tree is a valid red-black tree, and that it orders user structures correctly.
Read-only operation.
This function uses the stack for recursion and is not recommended for "production use".
[in] | Tree | The tree to validate. |
References ASSERT, CONST, DEBUG, DEBUG_VERBOSE, NodeIsNullOrBlack(), NULL, OrderedCollectionMax(), OrderedCollectionMin(), OrderedCollectionNext(), OrderedCollectionPrev(), and RedBlackTreeRecursiveCheck().
Referenced by OrderedCollectionDelete(), OrderedCollectionInit(), and OrderedCollectionInsert().