diff options
Diffstat (limited to 'MdePkg/Include/Library/OrderedCollectionLib.h')
| -rw-r--r-- | MdePkg/Include/Library/OrderedCollectionLib.h | 425 |
1 files changed, 425 insertions, 0 deletions
diff --git a/MdePkg/Include/Library/OrderedCollectionLib.h b/MdePkg/Include/Library/OrderedCollectionLib.h new file mode 100644 index 000000000000..e4191b82026f --- /dev/null +++ b/MdePkg/Include/Library/OrderedCollectionLib.h @@ -0,0 +1,425 @@ +/** @file + An ordered collection library interface. + + The library class provides a set of APIs to manage an ordered collection of + items. + + Copyright (C) 2014, Red Hat, Inc. + + 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. +**/ + +#ifndef __ORDERED_COLLECTION_LIB__ +#define __ORDERED_COLLECTION_LIB__ + +#include <Base.h> + +// +// Opaque structure for a collection. +// +typedef struct ORDERED_COLLECTION ORDERED_COLLECTION; + +// +// Opaque structure for collection entries. +// +// Collection entries do not take ownership of the associated user structures, +// they only link them. This makes it easy to link the same user structure into +// several collections. If reference counting is required, the caller is +// responsible for implementing it, as part of the user structure. +// +// A pointer-to-ORDERED_COLLECTION_ENTRY is considered an "iterator". Multiple, +// simultaneous iterations are supported. +// +typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY; + +// +// Altering the key field of an in-collection user structure (ie. the portion +// of the user structure that ORDERED_COLLECTION_USER_COMPARE and +// ORDERED_COLLECTION_KEY_COMPARE, below, read) is not allowed in-place. The +// caller is responsible for bracketing the key change with the deletion and +// the reinsertion of the user structure, so that the changed key value is +// reflected in the collection. +// + +/** + Comparator function type for two user structures. + + @param[in] UserStruct1 Pointer to the first user structure. + + @param[in] UserStruct2 Pointer to the second user structure. + + @retval <0 If UserStruct1 compares less than UserStruct2. + + @retval 0 If UserStruct1 compares equal to UserStruct2. + + @retval >0 If UserStruct1 compares greater than UserStruct2. +**/ +typedef +INTN +(EFIAPI *ORDERED_COLLECTION_USER_COMPARE)( + IN CONST VOID *UserStruct1, + IN CONST VOID *UserStruct2 + ); + +/** + Compare a standalone key against a user structure containing an embedded key. + + @param[in] StandaloneKey Pointer to the bare key. + + @param[in] UserStruct Pointer to the user structure with the embedded + key. + + @retval <0 If StandaloneKey compares less than UserStruct's key. + + @retval 0 If StandaloneKey compares equal to UserStruct's key. + + @retval >0 If StandaloneKey compares greater than UserStruct's key. +**/ +typedef +INTN +(EFIAPI *ORDERED_COLLECTION_KEY_COMPARE)( + IN CONST VOID *StandaloneKey, + IN CONST VOID *UserStruct + ); + + +// +// Some functions below are read-only, while others are read-write. If any +// write operation is expected to run concurrently with any other operation on +// the same collection, then the caller is responsible for implementing locking +// for the whole collection. +// + +/** + Retrieve the user structure linked by the specified collection entry. + + Read-only operation. + + @param[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. + + @return Pointer to user structure linked by Entry. +**/ +VOID * +EFIAPI +OrderedCollectionUserStruct ( + IN CONST ORDERED_COLLECTION_ENTRY *Entry + ); + + +/** + Allocate and initialize the ORDERED_COLLECTION structure. + + @param[in] UserStructCompare This caller-provided function will be used to + order two user structures linked into the + collection, during the insertion procedure. + + @param[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. + + @retval NULL If allocation failed. + + @return Pointer to the allocated, initialized ORDERED_COLLECTION + structure, otherwise. +**/ +ORDERED_COLLECTION * +EFIAPI +OrderedCollectionInit ( + IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare, + IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare + ); + + +/** + Check whether the collection is empty (has no entries). + + Read-only operation. + + @param[in] Collection The collection to check for emptiness. + + @retval TRUE The collection is empty. + + @retval FALSE The collection is not empty. +**/ +BOOLEAN +EFIAPI +OrderedCollectionIsEmpty ( + IN CONST ORDERED_COLLECTION *Collection + ); + + +/** + 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. + + @param[in] Collection The empty collection to uninitialize and release. +**/ +VOID +EFIAPI +OrderedCollectionUninit ( + IN ORDERED_COLLECTION *Collection + ); + + +/** + Look up the collection entry that links the user structure that matches the + specified standalone key. + + Read-only operation. + + @param[in] Collection The collection to search for StandaloneKey. + + @param[in] StandaloneKey The key to locate among the user structures linked + into Collection. StandaloneKey will be passed to + ORDERED_COLLECTION_KEY_COMPARE. + + @retval NULL StandaloneKey could not be found. + + @return The collection entry that links to the user structure matching + StandaloneKey, otherwise. +**/ +ORDERED_COLLECTION_ENTRY * +EFIAPI +OrderedCollectionFind ( + IN CONST ORDERED_COLLECTION *Collection, + IN CONST VOID *StandaloneKey + ); + + +/** + Find the collection entry of the minimum user structure stored in the + collection. + + Read-only operation. + + @param[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. + + @retval NULL If Collection is empty. + + @return The collection entry that links the minimum user structure, + otherwise. +**/ +ORDERED_COLLECTION_ENTRY * +EFIAPI +OrderedCollectionMin ( + IN CONST ORDERED_COLLECTION *Collection + ); + + +/** + Find the collection entry of the maximum user structure stored in the + collection. + + Read-only operation. + + @param[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. + + @retval NULL If Collection is empty. + + @return The collection entry that links the maximum user structure, + otherwise. +**/ +ORDERED_COLLECTION_ENTRY * +EFIAPI +OrderedCollectionMax ( + IN CONST ORDERED_COLLECTION *Collection + ); + + +/** + Get the collection entry of the least user structure that is greater than the + one linked by Entry. + + Read-only operation. + + @param[in] Entry The entry to get the successor entry of. + + @retval NULL If Entry is NULL, or Entry is the maximum entry of its + containing collection (ie. Entry has no successor entry). + + @return The collection entry linking the least user structure that is + greater than the one linked by Entry, otherwise. +**/ +ORDERED_COLLECTION_ENTRY * +EFIAPI +OrderedCollectionNext ( + IN CONST ORDERED_COLLECTION_ENTRY *Entry + ); + + +/** + Get the collection entry of the greatest user structure that is less than the + one linked by Entry. + + Read-only operation. + + @param[in] Entry The entry to get the predecessor entry of. + + @retval NULL If Entry is NULL, or Entry is the minimum entry of its + containing collection (ie. Entry has no predecessor entry). + + @return The collection entry linking the greatest user structure that + is less than the one linked by Entry, otherwise. +**/ +ORDERED_COLLECTION_ENTRY * +EFIAPI +OrderedCollectionPrev ( + IN CONST ORDERED_COLLECTION_ENTRY *Entry + ); + + +/** + Insert (link) a user structure into the collection, allocating a new + collection entry. + + Read-write operation. + + @param[in,out] Collection The collection to insert UserStruct into. + + @param[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. + + @param[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. + + @retval 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. + + @retval 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. + + @retval 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. +**/ +RETURN_STATUS +EFIAPI +OrderedCollectionInsert ( + IN OUT ORDERED_COLLECTION *Collection, + OUT ORDERED_COLLECTION_ENTRY **Entry OPTIONAL, + IN VOID *UserStruct + ); + + +/** + Delete an entry from the collection, unlinking the associated user structure. + + Read-write operation. + + @param[in,out] Collection The collection to delete Entry from. + + @param[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. + + @param[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. +**/ +VOID +EFIAPI +OrderedCollectionDelete ( + IN OUT ORDERED_COLLECTION *Collection, + IN ORDERED_COLLECTION_ENTRY *Entry, + OUT VOID **UserStruct OPTIONAL + ); + +#endif |