diff options
| -rw-r--r-- | MdePkg/Include/Library/OrderedCollectionLib.h | 425 | ||||
| -rw-r--r-- | MdePkg/MdePkg.dec | 9 |
2 files changed, 434 insertions, 0 deletions
diff --git a/MdePkg/Include/Library/OrderedCollectionLib.h b/MdePkg/Include/Library/OrderedCollectionLib.h new file mode 100644 index 0000000000..fc45d6dab7 --- /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
diff --git a/MdePkg/MdePkg.dec b/MdePkg/MdePkg.dec index 4daf3e6a75..bd5ce07269 100644 --- a/MdePkg/MdePkg.dec +++ b/MdePkg/MdePkg.dec @@ -100,6 +100,9 @@ ##
PrintLib|Include/Library/PrintLib.h
+ ## @libraryclass Provides an ordered collection data structure.
+ OrderedCollectionLib|Include/Library/OrderedCollectionLib.h
+
## @libraryclass Provides services to send progress/error codes to a POST card.
PostCodeLib|Include/Library/PostCodeLib.h
@@ -1387,6 +1390,12 @@ # SwapListEntries()
gEfiMdePkgTokenSpaceGuid.PcdVerifyNodeInList|FALSE|BOOLEAN|0x00000028
+ ## If TRUE, OrderedCollectionLib is instructed to validate the
+ # ORDERED_COLLECTION structure at the end of such operations (typically
+ # structure modifications) that justify validation of the structure for unit
+ # testing purposes.
+ gEfiMdePkgTokenSpaceGuid.PcdValidateOrderedCollection|FALSE|BOOLEAN|0x0000002a
+
[PcdsFixedAtBuild]
## Indicates the maximum length of unicode string
gEfiMdePkgTokenSpaceGuid.PcdMaximumUnicodeStringLength|1000000|UINT32|0x00000001
|