diff options
Diffstat (limited to 'MdePkg/Include/Library/OrderedCollectionLib.h')
| -rw-r--r-- | MdePkg/Include/Library/OrderedCollectionLib.h | 425 |
1 files changed, 0 insertions, 425 deletions
diff --git a/MdePkg/Include/Library/OrderedCollectionLib.h b/MdePkg/Include/Library/OrderedCollectionLib.h deleted file mode 100644 index fc45d6dab7..0000000000 --- a/MdePkg/Include/Library/OrderedCollectionLib.h +++ /dev/null @@ -1,425 +0,0 @@ -/** @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
|