[mirror_edk2.git] / MdePkg / Include / Library / OrderedCollectionLib.h

/** @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
  SPDX-License-Identifier: BSD-2-Clause-Patent\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
// 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
  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
  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
  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
  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
  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
  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
  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
  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
  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
  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
Commit	Line	Data
250e4b0d KM	1	/** @file\r
	2	An ordered collection library interface.\r
	3	\r
	4	The library class provides a set of APIs to manage an ordered collection of\r
	5	items.\r
	6	\r
	7	Copyright (C) 2014, Red Hat, Inc.\r
	8	\r
9344f092	9	SPDX-License-Identifier: BSD-2-Clause-Patent\r
250e4b0d KM	10	**/\r
	11	\r
	12	#ifndef __ORDERED_COLLECTION_LIB__\r
	13	#define __ORDERED_COLLECTION_LIB__\r
	14	\r
	15	#include <Base.h>\r
	16	\r
	17	//\r
	18	// Opaque structure for a collection.\r
	19	//\r
	20	typedef struct ORDERED_COLLECTION ORDERED_COLLECTION;\r
	21	\r
	22	//\r
	23	// Opaque structure for collection entries.\r
	24	//\r
	25	// Collection entries do not take ownership of the associated user structures,\r
	26	// they only link them. This makes it easy to link the same user structure into\r
	27	// several collections. If reference counting is required, the caller is\r
	28	// responsible for implementing it, as part of the user structure.\r
	29	//\r
	30	// A pointer-to-ORDERED_COLLECTION_ENTRY is considered an "iterator". Multiple,\r
	31	// simultaneous iterations are supported.\r
	32	//\r
	33	typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY;\r
	34	\r
	35	//\r
	36	// Altering the key field of an in-collection user structure (ie. the portion\r
	37	// of the user structure that ORDERED_COLLECTION_USER_COMPARE and\r
	38	// ORDERED_COLLECTION_KEY_COMPARE, below, read) is not allowed in-place. The\r
	39	// caller is responsible for bracketing the key change with the deletion and\r
	40	// the reinsertion of the user structure, so that the changed key value is\r
	41	// reflected in the collection.\r
	42	//\r
	43	\r
	44	/**\r
	45	Comparator function type for two user structures.\r
	46	\r
	47	@param[in] UserStruct1 Pointer to the first user structure.\r
	48	\r
	49	@param[in] UserStruct2 Pointer to the second user structure.\r
	50	\r
	51	@retval <0 If UserStruct1 compares less than UserStruct2.\r
	52	\r
	53	@retval 0 If UserStruct1 compares equal to UserStruct2.\r
	54	\r
	55	@retval >0 If UserStruct1 compares greater than UserStruct2.\r
	56	**/\r
	57	typedef\r
	58	INTN\r
	59	(EFIAPI *ORDERED_COLLECTION_USER_COMPARE)(\r
	60	IN CONST VOID *UserStruct1,\r
	61	IN CONST VOID *UserStruct2\r
	62	);\r
	63	\r
	64	/**\r
	65	Compare a standalone key against a user structure containing an embedded key.\r
	66	\r
	67	@param[in] StandaloneKey Pointer to the bare key.\r
	68	\r
	69	@param[in] UserStruct Pointer to the user structure with the embedded\r
	70	key.\r
	71	\r
	72	@retval <0 If StandaloneKey compares less than UserStruct's key.\r
	73	\r
74	@retval 0 If StandaloneKey compares equal to UserStruct's key.\r
75	\r
76	@retval >0 If StandaloneKey compares greater than UserStruct's key.\r
77	**/\r
78	typedef\r
79	INTN\r
80	(EFIAPI *ORDERED_COLLECTION_KEY_COMPARE)(\r
81	IN CONST VOID *StandaloneKey,\r
82	IN CONST VOID *UserStruct\r
83	);\r
84	\r
250e4b0d KM	85	//\r
	86	// Some functions below are read-only, while others are read-write. If any\r
	87	// write operation is expected to run concurrently with any other operation on\r
	88	// the same collection, then the caller is responsible for implementing locking\r
	89	// for the whole collection.\r
	90	//\r
	91	\r
	92	/**\r
	93	Retrieve the user structure linked by the specified collection entry.\r
	94	\r
	95	Read-only operation.\r
	96	\r
	97	@param[in] Entry Pointer to the collection entry whose associated user\r
	98	structure we want to retrieve. The caller is responsible\r
	99	for passing a non-NULL argument.\r
	100	\r
	101	@return Pointer to user structure linked by Entry.\r
	102	**/\r
	103	VOID *\r
	104	EFIAPI\r
	105	OrderedCollectionUserStruct (\r
2f88bd3a	106	IN CONST ORDERED_COLLECTION_ENTRY *Entry\r
250e4b0d KM	107	);\r
250e4b0d KM	108	\r
250e4b0d KM	109	/**\r
	110	Allocate and initialize the ORDERED_COLLECTION structure.\r
	111	\r
	112	@param[in] UserStructCompare This caller-provided function will be used to\r
	113	order two user structures linked into the\r
	114	collection, during the insertion procedure.\r
	115	\r
	116	@param[in] KeyCompare This caller-provided function will be used to\r
	117	order the standalone search key against user\r
	118	structures linked into the collection, during\r
	119	the lookup procedure.\r
	120	\r
	121	@retval NULL If allocation failed.\r
	122	\r
	123	@return Pointer to the allocated, initialized ORDERED_COLLECTION\r
	124	structure, otherwise.\r
	125	**/\r
	126	ORDERED_COLLECTION *\r
	127	EFIAPI\r
	128	OrderedCollectionInit (\r
2f88bd3a MK	129	IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare,\r
2f88bd3a MK	130	IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare\r
250e4b0d KM	131	);\r
250e4b0d KM	132	\r
250e4b0d KM	133	/**\r
	134	Check whether the collection is empty (has no entries).\r
	135	\r
	136	Read-only operation.\r
	137	\r
	138	@param[in] Collection The collection to check for emptiness.\r
	139	\r
	140	@retval TRUE The collection is empty.\r
	141	\r
	142	@retval FALSE The collection is not empty.\r
	143	**/\r
	144	BOOLEAN\r
	145	EFIAPI\r
	146	OrderedCollectionIsEmpty (\r
2f88bd3a	147	IN CONST ORDERED_COLLECTION *Collection\r
250e4b0d KM	148	);\r
250e4b0d KM	149	\r
250e4b0d KM	150	/**\r
	151	Uninitialize and release an empty ORDERED_COLLECTION structure.\r
	152	\r
	153	Read-write operation.\r
	154	\r
	155	It is the caller's responsibility to delete all entries from the collection\r
	156	before calling this function.\r
	157	\r
	158	@param[in] Collection The empty collection to uninitialize and release.\r
	159	**/\r
	160	VOID\r
	161	EFIAPI\r
	162	OrderedCollectionUninit (\r
2f88bd3a	163	IN ORDERED_COLLECTION *Collection\r
250e4b0d KM	164	);\r
250e4b0d KM	165	\r
250e4b0d KM	166	/**\r
	167	Look up the collection entry that links the user structure that matches the\r
	168	specified standalone key.\r
	169	\r
	170	Read-only operation.\r
	171	\r
	172	@param[in] Collection The collection to search for StandaloneKey.\r
	173	\r
	174	@param[in] StandaloneKey The key to locate among the user structures linked\r
	175	into Collection. StandaloneKey will be passed to\r
	176	ORDERED_COLLECTION_KEY_COMPARE.\r
	177	\r
	178	@retval NULL StandaloneKey could not be found.\r
	179	\r
	180	@return The collection entry that links to the user structure matching\r
	181	StandaloneKey, otherwise.\r
	182	**/\r
	183	ORDERED_COLLECTION_ENTRY *\r
	184	EFIAPI\r
	185	OrderedCollectionFind (\r
2f88bd3a MK	186	IN CONST ORDERED_COLLECTION *Collection,\r
2f88bd3a MK	187	IN CONST VOID *StandaloneKey\r
250e4b0d KM	188	);\r
250e4b0d KM	189	\r
250e4b0d KM	190	/**\r
	191	Find the collection entry of the minimum user structure stored in the\r
	192	collection.\r
	193	\r
	194	Read-only operation.\r
	195	\r
	196	@param[in] Collection The collection to return the minimum entry of. The\r
	197	user structure linked by the minimum entry compares\r
	198	less than all other user structures in the collection.\r
	199	\r
	200	@retval NULL If Collection is empty.\r
	201	\r
	202	@return The collection entry that links the minimum user structure,\r
	203	otherwise.\r
	204	**/\r
	205	ORDERED_COLLECTION_ENTRY *\r
	206	EFIAPI\r
	207	OrderedCollectionMin (\r
2f88bd3a	208	IN CONST ORDERED_COLLECTION *Collection\r
250e4b0d KM	209	);\r
250e4b0d KM	210	\r
250e4b0d KM	211	/**\r
	212	Find the collection entry of the maximum user structure stored in the\r
	213	collection.\r
	214	\r
	215	Read-only operation.\r
	216	\r
	217	@param[in] Collection The collection to return the maximum entry of. The\r
	218	user structure linked by the maximum entry compares\r
	219	greater than all other user structures in the\r
	220	collection.\r
	221	\r
	222	@retval NULL If Collection is empty.\r
	223	\r
	224	@return The collection entry that links the maximum user structure,\r
	225	otherwise.\r
	226	**/\r
	227	ORDERED_COLLECTION_ENTRY *\r
	228	EFIAPI\r
	229	OrderedCollectionMax (\r
2f88bd3a	230	IN CONST ORDERED_COLLECTION *Collection\r
250e4b0d KM	231	);\r
250e4b0d KM	232	\r
250e4b0d KM	233	/**\r
	234	Get the collection entry of the least user structure that is greater than the\r
	235	one linked by Entry.\r
	236	\r
	237	Read-only operation.\r
	238	\r
	239	@param[in] Entry The entry to get the successor entry of.\r
	240	\r
	241	@retval NULL If Entry is NULL, or Entry is the maximum entry of its\r
	242	containing collection (ie. Entry has no successor entry).\r
	243	\r
	244	@return The collection entry linking the least user structure that is\r
	245	greater than the one linked by Entry, otherwise.\r
	246	**/\r
	247	ORDERED_COLLECTION_ENTRY *\r
	248	EFIAPI\r
	249	OrderedCollectionNext (\r
2f88bd3a	250	IN CONST ORDERED_COLLECTION_ENTRY *Entry\r
250e4b0d KM	251	);\r
250e4b0d KM	252	\r
250e4b0d KM	253	/**\r
	254	Get the collection entry of the greatest user structure that is less than the\r
	255	one linked by Entry.\r
	256	\r
	257	Read-only operation.\r
	258	\r
	259	@param[in] Entry The entry to get the predecessor entry of.\r
	260	\r
	261	@retval NULL If Entry is NULL, or Entry is the minimum entry of its\r
	262	containing collection (ie. Entry has no predecessor entry).\r
	263	\r
	264	@return The collection entry linking the greatest user structure that\r
	265	is less than the one linked by Entry, otherwise.\r
	266	**/\r
	267	ORDERED_COLLECTION_ENTRY *\r
	268	EFIAPI\r
	269	OrderedCollectionPrev (\r
2f88bd3a	270	IN CONST ORDERED_COLLECTION_ENTRY *Entry\r
250e4b0d KM	271	);\r
250e4b0d KM	272	\r
250e4b0d KM	273	/**\r
	274	Insert (link) a user structure into the collection, allocating a new\r
	275	collection entry.\r
	276	\r
	277	Read-write operation.\r
	278	\r
	279	@param[in,out] Collection The collection to insert UserStruct into.\r
	280	\r
	281	@param[out] Entry The meaning of this optional, output-only\r
	282	parameter depends on the return value of the\r
	283	function.\r
	284	\r
	285	When insertion is successful (RETURN_SUCCESS),\r
	286	Entry is set on output to the new collection entry\r
	287	that now links UserStruct.\r
	288	\r
	289	When insertion fails due to lack of memory\r
	290	(RETURN_OUT_OF_RESOURCES), Entry is not changed.\r
	291	\r
	292	When insertion fails due to key collision (ie.\r
	293	another user structure is already in the\r
	294	collection that compares equal to UserStruct),\r
	295	with return value RETURN_ALREADY_STARTED, then\r
	296	Entry is set on output to the entry that links the\r
	297	colliding user structure. This enables\r
	298	"find-or-insert" in one function call, or helps\r
	299	with later removal of the colliding element.\r
	300	\r
	301	@param[in] UserStruct The user structure to link into the collection.\r
	302	UserStruct is ordered against in-collection user\r
	303	structures with the\r
	304	ORDERED_COLLECTION_USER_COMPARE function.\r
	305	\r
	306	@retval RETURN_SUCCESS Insertion successful. A new collection entry\r
	307	has been allocated, linking UserStruct. The\r
	308	new collection entry is reported back in\r
	309	Entry (if the caller requested it).\r
	310	\r
	311	Existing ORDERED_COLLECTION_ENTRY pointers\r
	312	into Collection remain valid. For example,\r
	313	on-going iterations in the caller can\r
	314	continue with OrderedCollectionNext() /\r
	315	OrderedCollectionPrev(), and they will\r
	316	return the new entry at some point if user\r
	317	structure order dictates it.\r
	318	\r
	319	@retval RETURN_OUT_OF_RESOURCES The function failed to allocate memory for\r
	320	the new collection entry. The collection has\r
	321	not been changed. Existing\r
	322	ORDERED_COLLECTION_ENTRY pointers into\r
	323	Collection remain valid.\r
	324	\r
	325	@retval RETURN_ALREADY_STARTED A user structure has been found in the\r
	326	collection that compares equal to\r
	327	UserStruct. The entry linking the colliding\r
	328	user structure is reported back in Entry (if\r
	329	the caller requested it). The collection has\r
	330	not been changed. Existing\r
	331	ORDERED_COLLECTION_ENTRY pointers into\r
	332	Collection remain valid.\r
	333	**/\r
	334	RETURN_STATUS\r
	335	EFIAPI\r
	336	OrderedCollectionInsert (\r
2f88bd3a MK	337	IN OUT ORDERED_COLLECTION *Collection,\r
	338	OUT ORDERED_COLLECTION_ENTRY **Entry OPTIONAL,\r
	339	IN VOID *UserStruct\r
250e4b0d KM	340	);\r
250e4b0d KM	341	\r
250e4b0d KM	342	/**\r
	343	Delete an entry from the collection, unlinking the associated user structure.\r
	344	\r
	345	Read-write operation.\r
	346	\r
	347	@param[in,out] Collection The collection to delete Entry from.\r
	348	\r
	349	@param[in] Entry The collection entry to delete from Collection.\r
	350	The caller is responsible for ensuring that Entry\r
	351	belongs to Collection, and that Entry is non-NULL\r
	352	and valid. Entry is typically an earlier return\r
	353	value, or output parameter, of:\r
	354	\r
	355	- OrderedCollectionFind(), for deleting an entry\r
	356	by user structure key,\r
	357	\r
	358	- OrderedCollectionMin() / OrderedCollectionMax(),\r
	359	for deleting the minimum / maximum entry,\r
	360	\r
	361	- OrderedCollectionNext() /\r
	362	OrderedCollectionPrev(), for deleting an entry\r
	363	found during an iteration,\r
	364	\r
	365	- OrderedCollectionInsert() with return value\r
	366	RETURN_ALREADY_STARTED, for deleting an entry\r
	367	whose linked user structure caused collision\r
	368	during insertion.\r
	369	\r
	370	Existing ORDERED_COLLECTION_ENTRY pointers (ie.\r
	371	iterators) different from Entry remain valid.\r
	372	For example:\r
	373	\r
	374	- OrderedCollectionNext() /\r
	375	OrderedCollectionPrev() iterations in the caller\r
	376	can be continued from Entry, if\r
	377	OrderedCollectionNext() or\r
	378	OrderedCollectionPrev() is called on Entry\r
	379	before OrderedCollectionDelete() is. That is,\r
	380	fetch the successor / predecessor entry first,\r
	381	then delete Entry.\r
	382	\r
	383	- On-going iterations in the caller that would\r
	384	have otherwise returned Entry at some point, as\r
	385	dictated by user structure order, will correctly\r
	386	reflect the absence of Entry after\r
	387	OrderedCollectionDelete() is called\r
	388	mid-iteration.\r
	389	\r
	390	@param[out] UserStruct If the caller provides this optional output-only\r
	391	parameter, then on output it is set to the user\r
	392	structure originally linked by Entry (which is now\r
	393	freed).\r
	394	\r
	395	This is a convenience that may save the caller a\r
	396	OrderedCollectionUserStruct() invocation before\r
	397	calling OrderedCollectionDelete(), in order to\r
	398	retrieve the user structure being unlinked.\r
	399	**/\r
	400	VOID\r
	401	EFIAPI\r
	402	OrderedCollectionDelete (\r
2f88bd3a MK	403	IN OUT ORDERED_COLLECTION *Collection,\r
	404	IN ORDERED_COLLECTION_ENTRY *Entry,\r
	405	OUT VOID **UserStruct OPTIONAL\r
250e4b0d KM	406	);\r
	407	\r
	408	#endif\r