#include <Base.h>

Typedefs
typedef struct ORDERED_COLLECTION	ORDERED_COLLECTION

typedef struct ORDERED_COLLECTION_ENTRY	ORDERED_COLLECTION_ENTRY

typedef INTN(EFIAPI *	ORDERED_COLLECTION_USER_COMPARE) (IN CONST VOID UserStruct1, IN CONST VOID UserStruct2)

typedef INTN(EFIAPI *	ORDERED_COLLECTION_KEY_COMPARE) (IN CONST VOID StandaloneKey, IN CONST VOID UserStruct)

Functions
VOID *EFIAPI	OrderedCollectionUserStruct (IN CONST ORDERED_COLLECTION_ENTRY *Entry)

ORDERED_COLLECTION *EFIAPI	OrderedCollectionInit (IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare, IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare)

BOOLEAN EFIAPI	OrderedCollectionIsEmpty (IN CONST ORDERED_COLLECTION *Collection)

VOID EFIAPI	OrderedCollectionUninit (IN ORDERED_COLLECTION *Collection)

ORDERED_COLLECTION_ENTRY *EFIAPI	OrderedCollectionFind (IN CONST ORDERED_COLLECTION Collection, IN CONST VOID StandaloneKey)

ORDERED_COLLECTION_ENTRY *EFIAPI	OrderedCollectionMin (IN CONST ORDERED_COLLECTION *Collection)

ORDERED_COLLECTION_ENTRY *EFIAPI	OrderedCollectionMax (IN CONST ORDERED_COLLECTION *Collection)

ORDERED_COLLECTION_ENTRY *EFIAPI	OrderedCollectionNext (IN CONST ORDERED_COLLECTION_ENTRY *Entry)

ORDERED_COLLECTION_ENTRY *EFIAPI	OrderedCollectionPrev (IN CONST ORDERED_COLLECTION_ENTRY *Entry)

RETURN_STATUS EFIAPI	OrderedCollectionInsert (IN OUT ORDERED_COLLECTION Collection, OUT ORDERED_COLLECTION_ENTRY Entry OPTIONAL, IN VOID UserStruct)

VOID EFIAPI	OrderedCollectionDelete (IN OUT ORDERED_COLLECTION Collection, IN ORDERED_COLLECTION_ENTRY Entry, OUT VOID **UserStruct OPTIONAL)

Detailed Description

An ordered collection library interface.

The library class provides a set of APIs to manage an ordered collection of items.

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

Definition in file OrderedCollectionLib.h.

Typedef Documentation

◆ ORDERED_COLLECTION

typedef struct ORDERED_COLLECTION ORDERED_COLLECTION

Definition at line 20 of file OrderedCollectionLib.h.

◆ ORDERED_COLLECTION_ENTRY

typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY

Definition at line 33 of file OrderedCollectionLib.h.

◆ ORDERED_COLLECTION_KEY_COMPARE

typedef INTN(EFIAPI * ORDERED_COLLECTION_KEY_COMPARE) (IN CONST VOID *StandaloneKey, IN CONST VOID *UserStruct)

Compare a standalone key against a user structure containing an embedded key.

Parameters

[in]	StandaloneKey	Pointer to the bare key.
[in]	UserStruct	Pointer to the user structure with the embedded key.

Return values

<0	If StandaloneKey compares less than UserStruct's key.
0	If StandaloneKey compares equal to UserStruct's key.
>0	If StandaloneKey compares greater than UserStruct's key.

Definition at line 79 of file OrderedCollectionLib.h.

◆ ORDERED_COLLECTION_USER_COMPARE

typedef INTN(EFIAPI * ORDERED_COLLECTION_USER_COMPARE) (IN CONST VOID *UserStruct1, IN CONST VOID *UserStruct2)

Comparator function type for two user structures.

Parameters

[in]	UserStruct1	Pointer to the first user structure.
[in]	UserStruct2	Pointer to the second user structure.

Return values

<0	If UserStruct1 compares less than UserStruct2.
0	If UserStruct1 compares equal to UserStruct2.
>0	If UserStruct1 compares greater than UserStruct2.

Definition at line 58 of file OrderedCollectionLib.h.

Function Documentation

◆ OrderedCollectionDelete()

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

Delete an entry from the collection, unlinking the associated user structure.

Read-write operation.

Parameters

[in,out]	Collection	The collection to delete Entry from.
[in]	Entry	The collection entry to delete from Collection. The caller is responsible for ensuring that Entry belongs to Collection, and that Entry is non-NULL and valid. Entry is typically an earlier return value, or output parameter, of:

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

Existing ORDERED_COLLECTION_ENTRY pointers (ie. iterators) different from Entry remain valid. For example:

OrderedCollectionNext() / OrderedCollectionPrev() iterations in the caller can be continued from Entry, if OrderedCollectionNext() or OrderedCollectionPrev() is called on Entry before* OrderedCollectionDelete() is. That is, fetch the successor / predecessor entry first, then delete Entry.
On-going iterations in the caller that would have otherwise returned Entry at some point, as dictated by user structure order, will correctly reflect the absence of Entry 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 Entry (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.

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

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

Look up the collection entry that links the user structure that matches the specified standalone key.

Read-only operation.

Parameters

[in]	Collection	The collection to search for StandaloneKey.
[in]	StandaloneKey	The key to locate among the user structures linked into Collection. StandaloneKey will be passed to ORDERED_COLLECTION_KEY_COMPARE.

Return values

NULL	StandaloneKey could not be found.

Returns: The collection entry that links to the user structure matching StandaloneKey, otherwise.

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

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

Allocate and initialize the ORDERED_COLLECTION structure.

Parameters

[in]	UserStructCompare	This caller-provided function will be used to order two user structures linked into the collection, 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 collection, during the lookup procedure.

Return values

NULL	If allocation failed.

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

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 ORDERED_COLLECTION *	Collection,
		OUT ORDERED_COLLECTION_ENTRY **Entry	OPTIONAL,
		IN VOID *	UserStruct
	)

Insert (link) a user structure into the collection, allocating a new collection entry.

Read-write operation.

Parameters

[in,out]	Collection	The collection to insert UserStruct into.
[out]	Entry	The meaning of this optional, output-only parameter depends on the return value of the function.

When insertion is successful (RETURN_SUCCESS), Entry is set on output to the new collection entry that now links UserStruct.

When insertion fails due to lack of memory (RETURN_OUT_OF_RESOURCES), Entry is not changed.

When insertion fails due to key collision (ie. another user structure is already in the collection that compares equal to UserStruct), with return value RETURN_ALREADY_STARTED, then Entry is set on output to the entry 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 collection. UserStruct is ordered against in-collection user structures with the ORDERED_COLLECTION_USER_COMPARE function.

Return values

RETURN_SUCCESS Insertion successful. A new collection entry has been allocated, linking UserStruct. The new collection entry is reported back in Entry (if the caller requested it).

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

Return values

RETURN_OUT_OF_RESOURCES	The function failed to allocate memory for the new collection entry. The collection has not been changed. Existing ORDERED_COLLECTION_ENTRY pointers into Collection remain valid.
RETURN_ALREADY_STARTED	A user structure has been found in the collection that compares equal to UserStruct. The entry linking the colliding user structure is reported back in Entry (if the caller requested it). The collection has not been changed. Existing ORDERED_COLLECTION_ENTRY pointers into Collection remain valid.

◆ OrderedCollectionIsEmpty()

BOOLEAN EFIAPI OrderedCollectionIsEmpty ( IN CONST RED_BLACK_TREE * Tree )

Check whether the collection is empty (has no entries).

Read-only operation.

Parameters

[in] Collection The collection to check for emptiness.

Return values

TRUE	The collection is empty.
FALSE	The collection is not empty.

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

ORDERED_COLLECTION_ENTRY *EFIAPI OrderedCollectionMax ( IN CONST RED_BLACK_TREE * Tree )

Find the collection entry of the maximum user structure stored in the collection.

Read-only operation.

Parameters

[in] Collection The collection to return the maximum entry of. The user structure linked by the maximum entry compares greater than all other user structures in the collection.

Return values

NULL	If Collection is empty.

Returns: The collection entry that links the maximum user structure, otherwise.

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

ORDERED_COLLECTION_ENTRY *EFIAPI OrderedCollectionMin ( IN CONST RED_BLACK_TREE * Tree )

Find the collection entry of the minimum user structure stored in the collection.

Read-only operation.

Parameters

[in] Collection The collection to return the minimum entry of. The user structure linked by the minimum entry compares less than all other user structures in the collection.

Return values

NULL	If Collection is empty.

Returns: The collection entry that links the minimum user structure, otherwise.

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

ORDERED_COLLECTION_ENTRY *EFIAPI OrderedCollectionNext ( IN CONST RED_BLACK_TREE_NODE * Node )

Get the collection entry of the least user structure that is greater than the one linked by Entry.

Read-only operation.

Parameters

[in] Entry The entry to get the successor entry of.

Return values

NULL	If Entry is NULL, or Entry is the maximum entry of its containing collection (ie. Entry has no successor entry).

Returns: The collection entry linking the least user structure that is greater than the one linked by Entry, otherwise.

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

ORDERED_COLLECTION_ENTRY *EFIAPI OrderedCollectionPrev ( IN CONST RED_BLACK_TREE_NODE * Node )

Get the collection entry of the greatest user structure that is less than the one linked by Entry.

Read-only operation.

Parameters

[in] Entry The entry to get the predecessor entry of.

Return values

NULL	If Entry is NULL, or Entry is the minimum entry of its containing collection (ie. Entry has no predecessor entry).

Returns: The collection entry linking the greatest user structure that is less than the one linked by Entry, otherwise.

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 ORDERED_COLLECTION structure.

Read-write operation.

It is the caller's responsibility to delete all entries from the collection before calling this function.

Parameters

[in] Collection The empty collection to uninitialize and release.

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 collection entry.

Read-only operation.

Parameters

[in] Entry Pointer to the collection entry 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 Entry.

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.

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ ORDERED_COLLECTION

◆ ORDERED_COLLECTION_ENTRY

◆ ORDERED_COLLECTION_KEY_COMPARE

◆ ORDERED_COLLECTION_USER_COMPARE

Function Documentation

◆ OrderedCollectionDelete()

◆ OrderedCollectionFind()

◆ OrderedCollectionInit()

◆ OrderedCollectionInsert()

◆ OrderedCollectionIsEmpty()

◆ OrderedCollectionMax()

◆ OrderedCollectionMin()

◆ OrderedCollectionNext()

◆ OrderedCollectionPrev()

◆ OrderedCollectionUninit()

◆ OrderedCollectionUserStruct()