#include <Library/OrderedCollectionLib.h>
#include <Library/DebugLib.h>
#include <Library/MemoryAllocationLib.h>

Data Structures
struct	ORDERED_COLLECTION

struct	ORDERED_COLLECTION_ENTRY

Typedefs
typedef ORDERED_COLLECTION	RED_BLACK_TREE

typedef ORDERED_COLLECTION_ENTRY	RED_BLACK_TREE_NODE

typedef ORDERED_COLLECTION_USER_COMPARE	RED_BLACK_TREE_USER_COMPARE

typedef ORDERED_COLLECTION_KEY_COMPARE	RED_BLACK_TREE_KEY_COMPARE

Enumerations
enum	RED_BLACK_TREE_COLOR { RedBlackTreeRed , RedBlackTreeBlack }

Functions
VOID *EFIAPI	OrderedCollectionUserStruct (IN CONST RED_BLACK_TREE_NODE *Node)

VOID	RedBlackTreeValidate (IN CONST RED_BLACK_TREE *Tree)

RED_BLACK_TREE *EFIAPI	OrderedCollectionInit (IN RED_BLACK_TREE_USER_COMPARE UserStructCompare, IN RED_BLACK_TREE_KEY_COMPARE KeyCompare)

BOOLEAN EFIAPI	OrderedCollectionIsEmpty (IN CONST RED_BLACK_TREE *Tree)

VOID EFIAPI	OrderedCollectionUninit (IN RED_BLACK_TREE *Tree)

RED_BLACK_TREE_NODE *EFIAPI	OrderedCollectionFind (IN CONST RED_BLACK_TREE Tree, IN CONST VOID StandaloneKey)

RED_BLACK_TREE_NODE *EFIAPI	OrderedCollectionMin (IN CONST RED_BLACK_TREE *Tree)

RED_BLACK_TREE_NODE *EFIAPI	OrderedCollectionMax (IN CONST RED_BLACK_TREE *Tree)

RED_BLACK_TREE_NODE *EFIAPI	OrderedCollectionNext (IN CONST RED_BLACK_TREE_NODE *Node)

RED_BLACK_TREE_NODE *EFIAPI	OrderedCollectionPrev (IN CONST RED_BLACK_TREE_NODE *Node)

VOID	RedBlackTreeRotateRight (IN OUT RED_BLACK_TREE_NODE Pivot, OUT RED_BLACK_TREE_NODE *NewRoot)

VOID	RedBlackTreeRotateLeft (IN OUT RED_BLACK_TREE_NODE Pivot, OUT RED_BLACK_TREE_NODE *NewRoot)

RETURN_STATUS EFIAPI	OrderedCollectionInsert (IN OUT RED_BLACK_TREE Tree, OUT RED_BLACK_TREE_NODE Node OPTIONAL, IN VOID UserStruct)

BOOLEAN	NodeIsNullOrBlack (IN CONST RED_BLACK_TREE_NODE *Node)

VOID EFIAPI	OrderedCollectionDelete (IN OUT RED_BLACK_TREE Tree, IN RED_BLACK_TREE_NODE Node, OUT VOID **UserStruct OPTIONAL)

UINT32	RedBlackTreeRecursiveCheck (IN CONST RED_BLACK_TREE_NODE *Node)

Detailed Description

An OrderedCollectionLib instance that provides a red-black tree implementation, and allocates and releases tree nodes with MemoryAllocationLib.

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.

SPDX-License-Identifier: BSD-2-Clause-Patent

Definition in file BaseOrderedCollectionRedBlackTreeLib.c.

Typedef Documentation

◆ RED_BLACK_TREE

typedef ORDERED_COLLECTION RED_BLACK_TREE

Definition at line 33 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ RED_BLACK_TREE_KEY_COMPARE

typedef ORDERED_COLLECTION_KEY_COMPARE RED_BLACK_TREE_KEY_COMPARE

Definition at line 36 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ RED_BLACK_TREE_NODE

typedef ORDERED_COLLECTION_ENTRY RED_BLACK_TREE_NODE

Definition at line 34 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ RED_BLACK_TREE_USER_COMPARE

typedef ORDERED_COLLECTION_USER_COMPARE RED_BLACK_TREE_USER_COMPARE

Definition at line 35 of file BaseOrderedCollectionRedBlackTreeLib.c.

Enumeration Type Documentation

◆ RED_BLACK_TREE_COLOR

enum RED_BLACK_TREE_COLOR

Definition at line 23 of file BaseOrderedCollectionRedBlackTreeLib.c.

Function Documentation

◆ NodeIsNullOrBlack()

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.

Returns: If Node is NULL or colored black.

Definition at line 848 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionDelete()

VOID EFIAPI OrderedCollectionDelete	(	IN OUT RED_BLACK_TREE *	Tree,
		IN RED_BLACK_TREE_NODE *	Node,
		OUT VOID **UserStruct	OPTIONAL
	)

Delete a node from the tree, unlinking the associated user structure.

Read-write operation.

Parameters

[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:

OrderedCollectionFind(), for deleting a node by user structure key,
OrderedCollectionMin() / OrderedCollectionMax(), for deleting the minimum / maximum node,
OrderedCollectionNext() / OrderedCollectionPrev(), for deleting a node found during an iteration,
OrderedCollectionInsert() with return value RETURN_ALREADY_STARTED, for deleting a node whose linked user structure caused collision during insertion.

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:

OrderedCollectionNext() / OrderedCollectionPrev() iterations in the caller can be continued from Node, if OrderedCollectionNext() or OrderedCollectionPrev() is called on Node before* OrderedCollectionDelete() is. That is, fetch the successor / predecessor node first, then delete Node.
On-going iterations in the caller that would have otherwise returned Node at some point, as dictated by user structure order, will correctly reflect the absence of Node after OrderedCollectionDelete() is called mid-iteration.

Parameters

[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).

This is a convenience that may save the caller a OrderedCollectionUserStruct() invocation before calling OrderedCollectionDelete(), in order to retrieve the user structure being unlinked.

Definition at line 922 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionFind()

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.

Parameters

[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().

Return values

NULL	StandaloneKey could not be found.

Returns: The tree node that links to the user structure matching StandaloneKey, otherwise.

Definition at line 193 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionInit()

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.

Parameters

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

Return values

NULL	If allocation failed.

Returns: Pointer to the allocated, initialized RED_BLACK_TREE structure, otherwise.

Definition at line 109 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionInsert()

RETURN_STATUS EFIAPI OrderedCollectionInsert	(	IN OUT RED_BLACK_TREE *	Tree,
		OUT RED_BLACK_TREE_NODE **Node	OPTIONAL,
		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.

Parameters

[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 is successful (RETURN_SUCCESS), Node is set on output to the new tree node that now links UserStruct.

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.

Parameters

[in] UserStruct The user structure to link into the tree. UserStruct is ordered against in-tree user structures with the Tree->UserStructCompare() function.

Return values

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

Existing RED_BLACK_TREE_NODE pointers into Tree remain valid. For example, on-going iterations in the caller can continue with OrderedCollectionNext() / OrderedCollectionPrev(), and they will return the new node at some point if user structure order dictates it.

Return values

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.

Definition at line 584 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionIsEmpty()

BOOLEAN EFIAPI OrderedCollectionIsEmpty ( IN CONST RED_BLACK_TREE * Tree )

Check whether the tree is empty (has no nodes).

Read-only operation.

Parameters

[in] Tree The tree to check for emptiness.

Return values

TRUE	The tree is empty.
FALSE	The tree is not empty.

Definition at line 145 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionMax()

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.

Parameters

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

Return values

NULL	If Tree is empty.

Returns: The tree node that links the maximum user structure, otherwise.

Definition at line 263 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionMin()

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.

Parameters

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

Return values

NULL	If Tree is empty.

Returns: The tree node that links the minimum user structure, otherwise.

Definition at line 230 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionNext()

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.

Parameters

[in] Node The node to get the successor node of.

Return values

NULL	If Node is NULL, or Node is the maximum node of its containing tree (ie. Node has no successor node).

Returns: The tree node linking the least user structure that is greater than the one linked by Node, otherwise.

Definition at line 297 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionPrev()

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.

Parameters

[in] Node The node to get the predecessor node of.

Return values

NULL	If Node is NULL, or Node is the minimum node of its containing tree (ie. Node has no predecessor node).

Returns: The tree node linking the greatest user structure that is less than the one linked by Node, otherwise.

Definition at line 351 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionUninit()

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.

Parameters

[in] Tree The empty tree to uninitialize and release.

Definition at line 166 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ OrderedCollectionUserStruct()

VOID *EFIAPI OrderedCollectionUserStruct ( IN CONST RED_BLACK_TREE_NODE * Node )

Retrieve the user structure linked by the specified tree node.

Read-only operation.

Parameters

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

Returns: Pointer to user structure linked by Node.

Definition at line 65 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ RedBlackTreeRecursiveCheck()

UINT32 RedBlackTreeRecursiveCheck ( IN CONST RED_BLACK_TREE_NODE * Node )

Recursively check the red-black tree properties #1 to #4 on a node.

Parameters

[in] Node The root of the subtree to validate.

Return values

The	black-height of Node's parent.

Definition at line 1360 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ RedBlackTreeRotateLeft()

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.

Parameters

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

If Pivot has no parent node on input (ie. Pivot is the root of the tree), then the function stores the new root node of the tree in NewRoot.

Definition at line 488 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ RedBlackTreeRotateRight()

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.

Parameters

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

If Pivot has no parent node on input (ie. Pivot is the root of the tree), then the function stores the new root node of the tree in NewRoot.

Definition at line 422 of file BaseOrderedCollectionRedBlackTreeLib.c.

◆ RedBlackTreeValidate()

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

Parameters

[in] Tree The tree to validate.

Definition at line 1409 of file BaseOrderedCollectionRedBlackTreeLib.c.

Data Structures

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

◆ RED_BLACK_TREE

◆ RED_BLACK_TREE_KEY_COMPARE

◆ RED_BLACK_TREE_NODE

◆ RED_BLACK_TREE_USER_COMPARE

Enumeration Type Documentation

◆ RED_BLACK_TREE_COLOR

Function Documentation

◆ NodeIsNullOrBlack()

◆ OrderedCollectionDelete()

◆ OrderedCollectionFind()

◆ OrderedCollectionInit()

◆ OrderedCollectionInsert()

◆ OrderedCollectionIsEmpty()

◆ OrderedCollectionMax()

◆ OrderedCollectionMin()

◆ OrderedCollectionNext()

◆ OrderedCollectionPrev()

◆ OrderedCollectionUninit()

◆ OrderedCollectionUserStruct()

◆ RedBlackTreeRecursiveCheck()

◆ RedBlackTreeRotateLeft()

◆ RedBlackTreeRotateRight()

◆ RedBlackTreeValidate()