--- /dev/null
+/** @file\r
+ An ordered collection library interface.\r
+\r
+ The library class provides a set of APIs to manage an ordered collection of\r
+ items.\r
+\r
+ Copyright (C) 2014, Red Hat, Inc.\r
+\r
+ This program and the accompanying materials are licensed and made available\r
+ under the terms and conditions of the BSD License that accompanies this\r
+ distribution. The full text of the license may be found at\r
+ http://opensource.org/licenses/bsd-license.php.\r
+\r
+ THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT\r
+ WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
+**/\r
+\r
+#ifndef __ORDERED_COLLECTION_LIB__\r
+#define __ORDERED_COLLECTION_LIB__\r
+\r
+#include <Base.h>\r
+\r
+//\r
+// Opaque structure for a collection.\r
+//\r
+typedef struct ORDERED_COLLECTION ORDERED_COLLECTION;\r
+\r
+//\r
+// Opaque structure for collection entries.\r
+//\r
+// Collection entries do not take ownership of the associated user structures,\r
+// they only link them. This makes it easy to link the same user structure into\r
+// several collections. If reference counting is required, the caller is\r
+// responsible for implementing it, as part of the user structure.\r
+//\r
+// A pointer-to-ORDERED_COLLECTION_ENTRY is considered an "iterator". Multiple,\r
+// simultaneous iterations are supported.\r
+//\r
+typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY;\r
+\r
+//\r
+// Altering the key field of an in-collection user structure (ie. the portion\r
+// of the user structure that ORDERED_COLLECTION_USER_COMPARE and\r
+// ORDERED_COLLECTION_KEY_COMPARE, below, read) is not allowed in-place. The\r
+// caller is responsible for bracketing the key change with the deletion and\r
+// the reinsertion of the user structure, so that the changed key value is\r
+// reflected in the collection.\r
+//\r
+\r
+/**\r
+ Comparator function type for two user structures.\r
+\r
+ @param[in] UserStruct1 Pointer to the first user structure.\r
+\r
+ @param[in] UserStruct2 Pointer to the second user structure.\r
+\r
+ @retval <0 If UserStruct1 compares less than UserStruct2.\r
+\r
+ @retval 0 If UserStruct1 compares equal to UserStruct2.\r
+\r
+ @retval >0 If UserStruct1 compares greater than UserStruct2.\r
+**/\r
+typedef\r
+INTN\r
+(EFIAPI *ORDERED_COLLECTION_USER_COMPARE)(\r
+ IN CONST VOID *UserStruct1,\r
+ IN CONST VOID *UserStruct2\r
+ );\r
+\r
+/**\r
+ Compare a standalone key against a user structure containing an embedded key.\r
+\r
+ @param[in] StandaloneKey Pointer to the bare key.\r
+\r
+ @param[in] UserStruct Pointer to the user structure with the embedded\r
+ key.\r
+\r
+ @retval <0 If StandaloneKey compares less than UserStruct's key.\r
+\r
+ @retval 0 If StandaloneKey compares equal to UserStruct's key.\r
+\r
+ @retval >0 If StandaloneKey compares greater than UserStruct's key.\r
+**/\r
+typedef\r
+INTN\r
+(EFIAPI *ORDERED_COLLECTION_KEY_COMPARE)(\r
+ IN CONST VOID *StandaloneKey,\r
+ IN CONST VOID *UserStruct\r
+ );\r
+\r
+\r
+//\r
+// Some functions below are read-only, while others are read-write. If any\r
+// write operation is expected to run concurrently with any other operation on\r
+// the same collection, then the caller is responsible for implementing locking\r
+// for the whole collection.\r
+//\r
+\r
+/**\r
+ Retrieve the user structure linked by the specified collection entry.\r
+\r
+ Read-only operation.\r
+\r
+ @param[in] Entry Pointer to the collection entry whose associated user\r
+ structure we want to retrieve. The caller is responsible\r
+ for passing a non-NULL argument.\r
+\r
+ @return Pointer to user structure linked by Entry.\r
+**/\r
+VOID *\r
+EFIAPI\r
+OrderedCollectionUserStruct (\r
+ IN CONST ORDERED_COLLECTION_ENTRY *Entry\r
+ );\r
+\r
+\r
+/**\r
+ Allocate and initialize the ORDERED_COLLECTION structure.\r
+\r
+ @param[in] UserStructCompare This caller-provided function will be used to\r
+ order two user structures linked into the\r
+ collection, during the insertion procedure.\r
+\r
+ @param[in] KeyCompare This caller-provided function will be used to\r
+ order the standalone search key against user\r
+ structures linked into the collection, during\r
+ the lookup procedure.\r
+\r
+ @retval NULL If allocation failed.\r
+\r
+ @return Pointer to the allocated, initialized ORDERED_COLLECTION\r
+ structure, otherwise.\r
+**/\r
+ORDERED_COLLECTION *\r
+EFIAPI\r
+OrderedCollectionInit (\r
+ IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare,\r
+ IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare\r
+ );\r
+\r
+\r
+/**\r
+ Check whether the collection is empty (has no entries).\r
+\r
+ Read-only operation.\r
+\r
+ @param[in] Collection The collection to check for emptiness.\r
+\r
+ @retval TRUE The collection is empty.\r
+\r
+ @retval FALSE The collection is not empty.\r
+**/\r
+BOOLEAN\r
+EFIAPI\r
+OrderedCollectionIsEmpty (\r
+ IN CONST ORDERED_COLLECTION *Collection\r
+ );\r
+\r
+\r
+/**\r
+ Uninitialize and release an empty ORDERED_COLLECTION structure.\r
+\r
+ Read-write operation.\r
+\r
+ It is the caller's responsibility to delete all entries from the collection\r
+ before calling this function.\r
+\r
+ @param[in] Collection The empty collection to uninitialize and release.\r
+**/\r
+VOID\r
+EFIAPI\r
+OrderedCollectionUninit (\r
+ IN ORDERED_COLLECTION *Collection\r
+ );\r
+\r
+\r
+/**\r
+ Look up the collection entry that links the user structure that matches the\r
+ specified standalone key.\r
+\r
+ Read-only operation.\r
+\r
+ @param[in] Collection The collection to search for StandaloneKey.\r
+\r
+ @param[in] StandaloneKey The key to locate among the user structures linked\r
+ into Collection. StandaloneKey will be passed to\r
+ ORDERED_COLLECTION_KEY_COMPARE.\r
+\r
+ @retval NULL StandaloneKey could not be found.\r
+\r
+ @return The collection entry that links to the user structure matching\r
+ StandaloneKey, otherwise.\r
+**/\r
+ORDERED_COLLECTION_ENTRY *\r
+EFIAPI\r
+OrderedCollectionFind (\r
+ IN CONST ORDERED_COLLECTION *Collection,\r
+ IN CONST VOID *StandaloneKey\r
+ );\r
+\r
+\r
+/**\r
+ Find the collection entry of the minimum user structure stored in the\r
+ collection.\r
+\r
+ Read-only operation.\r
+\r
+ @param[in] Collection The collection to return the minimum entry of. The\r
+ user structure linked by the minimum entry compares\r
+ less than all other user structures in the collection.\r
+\r
+ @retval NULL If Collection is empty.\r
+\r
+ @return The collection entry that links the minimum user structure,\r
+ otherwise.\r
+**/\r
+ORDERED_COLLECTION_ENTRY *\r
+EFIAPI\r
+OrderedCollectionMin (\r
+ IN CONST ORDERED_COLLECTION *Collection\r
+ );\r
+\r
+\r
+/**\r
+ Find the collection entry of the maximum user structure stored in the\r
+ collection.\r
+\r
+ Read-only operation.\r
+\r
+ @param[in] Collection The collection to return the maximum entry of. The\r
+ user structure linked by the maximum entry compares\r
+ greater than all other user structures in the\r
+ collection.\r
+\r
+ @retval NULL If Collection is empty.\r
+\r
+ @return The collection entry that links the maximum user structure,\r
+ otherwise.\r
+**/\r
+ORDERED_COLLECTION_ENTRY *\r
+EFIAPI\r
+OrderedCollectionMax (\r
+ IN CONST ORDERED_COLLECTION *Collection\r
+ );\r
+\r
+\r
+/**\r
+ Get the collection entry of the least user structure that is greater than the\r
+ one linked by Entry.\r
+\r
+ Read-only operation.\r
+\r
+ @param[in] Entry The entry to get the successor entry of.\r
+\r
+ @retval NULL If Entry is NULL, or Entry is the maximum entry of its\r
+ containing collection (ie. Entry has no successor entry).\r
+\r
+ @return The collection entry linking the least user structure that is\r
+ greater than the one linked by Entry, otherwise.\r
+**/\r
+ORDERED_COLLECTION_ENTRY *\r
+EFIAPI\r
+OrderedCollectionNext (\r
+ IN CONST ORDERED_COLLECTION_ENTRY *Entry\r
+ );\r
+\r
+\r
+/**\r
+ Get the collection entry of the greatest user structure that is less than the\r
+ one linked by Entry.\r
+\r
+ Read-only operation.\r
+\r
+ @param[in] Entry The entry to get the predecessor entry of.\r
+\r
+ @retval NULL If Entry is NULL, or Entry is the minimum entry of its\r
+ containing collection (ie. Entry has no predecessor entry).\r
+\r
+ @return The collection entry linking the greatest user structure that\r
+ is less than the one linked by Entry, otherwise.\r
+**/\r
+ORDERED_COLLECTION_ENTRY *\r
+EFIAPI\r
+OrderedCollectionPrev (\r
+ IN CONST ORDERED_COLLECTION_ENTRY *Entry\r
+ );\r
+\r
+\r
+/**\r
+ Insert (link) a user structure into the collection, allocating a new\r
+ collection entry.\r
+\r
+ Read-write operation.\r
+\r
+ @param[in,out] Collection The collection to insert UserStruct into.\r
+\r
+ @param[out] Entry The meaning of this optional, output-only\r
+ parameter depends on the return value of the\r
+ function.\r
+\r
+ When insertion is successful (RETURN_SUCCESS),\r
+ Entry is set on output to the new collection entry\r
+ that now links UserStruct.\r
+\r
+ When insertion fails due to lack of memory\r
+ (RETURN_OUT_OF_RESOURCES), Entry is not changed.\r
+\r
+ When insertion fails due to key collision (ie.\r
+ another user structure is already in the\r
+ collection that compares equal to UserStruct),\r
+ with return value RETURN_ALREADY_STARTED, then\r
+ Entry is set on output to the entry that links the\r
+ colliding user structure. This enables\r
+ "find-or-insert" in one function call, or helps\r
+ with later removal of the colliding element.\r
+\r
+ @param[in] UserStruct The user structure to link into the collection.\r
+ UserStruct is ordered against in-collection user\r
+ structures with the\r
+ ORDERED_COLLECTION_USER_COMPARE function.\r
+\r
+ @retval RETURN_SUCCESS Insertion successful. A new collection entry\r
+ has been allocated, linking UserStruct. The\r
+ new collection entry is reported back in\r
+ Entry (if the caller requested it).\r
+\r
+ Existing ORDERED_COLLECTION_ENTRY pointers\r
+ into Collection remain valid. For example,\r
+ on-going iterations in the caller can\r
+ continue with OrderedCollectionNext() /\r
+ OrderedCollectionPrev(), and they will\r
+ return the new entry at some point if user\r
+ structure order dictates it.\r
+\r
+ @retval RETURN_OUT_OF_RESOURCES The function failed to allocate memory for\r
+ the new collection entry. The collection has\r
+ not been changed. Existing\r
+ ORDERED_COLLECTION_ENTRY pointers into\r
+ Collection remain valid.\r
+\r
+ @retval RETURN_ALREADY_STARTED A user structure has been found in the\r
+ collection that compares equal to\r
+ UserStruct. The entry linking the colliding\r
+ user structure is reported back in Entry (if\r
+ the caller requested it). The collection has\r
+ not been changed. Existing\r
+ ORDERED_COLLECTION_ENTRY pointers into\r
+ Collection remain valid.\r
+**/\r
+RETURN_STATUS\r
+EFIAPI\r
+OrderedCollectionInsert (\r
+ IN OUT ORDERED_COLLECTION *Collection,\r
+ OUT ORDERED_COLLECTION_ENTRY **Entry OPTIONAL,\r
+ IN VOID *UserStruct\r
+ );\r
+\r
+\r
+/**\r
+ Delete an entry from the collection, unlinking the associated user structure.\r
+\r
+ Read-write operation.\r
+\r
+ @param[in,out] Collection The collection to delete Entry from.\r
+\r
+ @param[in] Entry The collection entry to delete from Collection.\r
+ The caller is responsible for ensuring that Entry\r
+ belongs to Collection, and that Entry is non-NULL\r
+ and valid. Entry is typically an earlier return\r
+ value, or output parameter, of:\r
+\r
+ - OrderedCollectionFind(), for deleting an entry\r
+ by user structure key,\r
+\r
+ - OrderedCollectionMin() / OrderedCollectionMax(),\r
+ for deleting the minimum / maximum entry,\r
+\r
+ - OrderedCollectionNext() /\r
+ OrderedCollectionPrev(), for deleting an entry\r
+ found during an iteration,\r
+\r
+ - OrderedCollectionInsert() with return value\r
+ RETURN_ALREADY_STARTED, for deleting an entry\r
+ whose linked user structure caused collision\r
+ during insertion.\r
+\r
+ Existing ORDERED_COLLECTION_ENTRY pointers (ie.\r
+ iterators) *different* from Entry remain valid.\r
+ For example:\r
+\r
+ - OrderedCollectionNext() /\r
+ OrderedCollectionPrev() iterations in the caller\r
+ can be continued from Entry, if\r
+ OrderedCollectionNext() or\r
+ OrderedCollectionPrev() is called on Entry\r
+ *before* OrderedCollectionDelete() is. That is,\r
+ fetch the successor / predecessor entry first,\r
+ then delete Entry.\r
+\r
+ - On-going iterations in the caller that would\r
+ have otherwise returned Entry at some point, as\r
+ dictated by user structure order, will correctly\r
+ reflect the absence of Entry after\r
+ OrderedCollectionDelete() is called\r
+ mid-iteration.\r
+\r
+ @param[out] UserStruct If the caller provides this optional output-only\r
+ parameter, then on output it is set to the user\r
+ structure originally linked by Entry (which is now\r
+ freed).\r
+\r
+ This is a convenience that may save the caller a\r
+ OrderedCollectionUserStruct() invocation before\r
+ calling OrderedCollectionDelete(), in order to\r
+ retrieve the user structure being unlinked.\r
+**/\r
+VOID\r
+EFIAPI\r
+OrderedCollectionDelete (\r
+ IN OUT ORDERED_COLLECTION *Collection,\r
+ IN ORDERED_COLLECTION_ENTRY *Entry,\r
+ OUT VOID **UserStruct OPTIONAL\r
+ );\r
+\r
+#endif\r