[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
//\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
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
85	\r
86	//\r
87	// Some functions below are read-only, while others are read-write. If any\r
88	// write operation is expected to run concurrently with any other operation on\r
89	// the same collection, then the caller is responsible for implementing locking\r
90	// for the whole collection.\r
91	//\r
92	\r
93	/**\r
94	Retrieve the user structure linked by the specified collection entry.\r
95	\r
96	Read-only operation.\r
97	\r
98	@param[in] Entry Pointer to the collection entry whose associated user\r
99	structure we want to retrieve. The caller is responsible\r
100	for passing a non-NULL argument.\r
101	\r
102	@return Pointer to user structure linked by Entry.\r
103	**/\r
104	VOID *\r
105	EFIAPI\r
106	OrderedCollectionUserStruct (\r
107	IN CONST ORDERED_COLLECTION_ENTRY *Entry\r
108	);\r
109	\r
110	\r
111	/**\r
112	Allocate and initialize the ORDERED_COLLECTION structure.\r
113	\r
114	@param[in] UserStructCompare This caller-provided function will be used to\r
115	order two user structures linked into the\r
116	collection, during the insertion procedure.\r
117	\r
118	@param[in] KeyCompare This caller-provided function will be used to\r
119	order the standalone search key against user\r
120	structures linked into the collection, during\r
121	the lookup procedure.\r
122	\r
123	@retval NULL If allocation failed.\r
124	\r
125	@return Pointer to the allocated, initialized ORDERED_COLLECTION\r
126	structure, otherwise.\r
127	**/\r
128	ORDERED_COLLECTION *\r
129	EFIAPI\r
130	OrderedCollectionInit (\r
131	IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare,\r
132	IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare\r
133	);\r
134	\r
135	\r
136	/**\r
137	Check whether the collection is empty (has no entries).\r
138	\r
139	Read-only operation.\r
140	\r
141	@param[in] Collection The collection to check for emptiness.\r
142	\r
143	@retval TRUE The collection is empty.\r
144	\r
145	@retval FALSE The collection is not empty.\r
146	**/\r
147	BOOLEAN\r
148	EFIAPI\r
149	OrderedCollectionIsEmpty (\r
150	IN CONST ORDERED_COLLECTION *Collection\r
151	);\r
152	\r
153	\r
154	/**\r
155	Uninitialize and release an empty ORDERED_COLLECTION structure.\r
156	\r
157	Read-write operation.\r
158	\r
159	It is the caller's responsibility to delete all entries from the collection\r
160	before calling this function.\r
161	\r
162	@param[in] Collection The empty collection to uninitialize and release.\r
163	**/\r
164	VOID\r
165	EFIAPI\r
166	OrderedCollectionUninit (\r
167	IN ORDERED_COLLECTION *Collection\r
168	);\r
169	\r
170	\r
171	/**\r
172	Look up the collection entry that links the user structure that matches the\r
173	specified standalone key.\r
174	\r
175	Read-only operation.\r
176	\r
177	@param[in] Collection The collection to search for StandaloneKey.\r
178	\r
179	@param[in] StandaloneKey The key to locate among the user structures linked\r
180	into Collection. StandaloneKey will be passed to\r
181	ORDERED_COLLECTION_KEY_COMPARE.\r
182	\r
183	@retval NULL StandaloneKey could not be found.\r
184	\r
185	@return The collection entry that links to the user structure matching\r
186	StandaloneKey, otherwise.\r
187	**/\r
188	ORDERED_COLLECTION_ENTRY *\r
189	EFIAPI\r
190	OrderedCollectionFind (\r
191	IN CONST ORDERED_COLLECTION *Collection,\r
192	IN CONST VOID *StandaloneKey\r
193	);\r
194	\r
195	\r
196	/**\r
197	Find the collection entry of the minimum user structure stored in the\r
198	collection.\r
199	\r
200	Read-only operation.\r
201	\r
202	@param[in] Collection The collection to return the minimum entry of. The\r
203	user structure linked by the minimum entry compares\r
204	less than all other user structures in the collection.\r
205	\r
206	@retval NULL If Collection is empty.\r
207	\r
208	@return The collection entry that links the minimum user structure,\r
209	otherwise.\r
210	**/\r
211	ORDERED_COLLECTION_ENTRY *\r
212	EFIAPI\r
213	OrderedCollectionMin (\r
214	IN CONST ORDERED_COLLECTION *Collection\r
215	);\r
216	\r
217	\r
218	/**\r
219	Find the collection entry of the maximum user structure stored in the\r
220	collection.\r
221	\r
222	Read-only operation.\r
223	\r
224	@param[in] Collection The collection to return the maximum entry of. The\r
225	user structure linked by the maximum entry compares\r
226	greater than all other user structures in the\r
227	collection.\r
228	\r
229	@retval NULL If Collection is empty.\r
230	\r
231	@return The collection entry that links the maximum user structure,\r
232	otherwise.\r
233	**/\r
234	ORDERED_COLLECTION_ENTRY *\r
235	EFIAPI\r
236	OrderedCollectionMax (\r
237	IN CONST ORDERED_COLLECTION *Collection\r
238	);\r
239	\r
240	\r
241	/**\r
242	Get the collection entry of the least user structure that is greater than the\r
243	one linked by Entry.\r
244	\r
245	Read-only operation.\r
246	\r
247	@param[in] Entry The entry to get the successor entry of.\r
248	\r
249	@retval NULL If Entry is NULL, or Entry is the maximum entry of its\r
250	containing collection (ie. Entry has no successor entry).\r
251	\r
252	@return The collection entry linking the least user structure that is\r
253	greater than the one linked by Entry, otherwise.\r
254	**/\r
255	ORDERED_COLLECTION_ENTRY *\r
256	EFIAPI\r
257	OrderedCollectionNext (\r
258	IN CONST ORDERED_COLLECTION_ENTRY *Entry\r
259	);\r
260	\r
261	\r
262	/**\r
263	Get the collection entry of the greatest user structure that is less than the\r
264	one linked by Entry.\r
265	\r
266	Read-only operation.\r
267	\r
268	@param[in] Entry The entry to get the predecessor entry of.\r
269	\r
270	@retval NULL If Entry is NULL, or Entry is the minimum entry of its\r
271	containing collection (ie. Entry has no predecessor entry).\r
272	\r
273	@return The collection entry linking the greatest user structure that\r
274	is less than the one linked by Entry, otherwise.\r
275	**/\r
276	ORDERED_COLLECTION_ENTRY *\r
277	EFIAPI\r
278	OrderedCollectionPrev (\r
279	IN CONST ORDERED_COLLECTION_ENTRY *Entry\r
280	);\r
281	\r
282	\r
283	/**\r
284	Insert (link) a user structure into the collection, allocating a new\r
285	collection entry.\r
286	\r
287	Read-write operation.\r
288	\r
289	@param[in,out] Collection The collection to insert UserStruct into.\r
290	\r
291	@param[out] Entry The meaning of this optional, output-only\r
292	parameter depends on the return value of the\r
293	function.\r
294	\r
295	When insertion is successful (RETURN_SUCCESS),\r
296	Entry is set on output to the new collection entry\r
297	that now links UserStruct.\r
298	\r
299	When insertion fails due to lack of memory\r
300	(RETURN_OUT_OF_RESOURCES), Entry is not changed.\r
301	\r
302	When insertion fails due to key collision (ie.\r
303	another user structure is already in the\r
304	collection that compares equal to UserStruct),\r
305	with return value RETURN_ALREADY_STARTED, then\r
306	Entry is set on output to the entry that links the\r
307	colliding user structure. This enables\r
308	"find-or-insert" in one function call, or helps\r
309	with later removal of the colliding element.\r
310	\r
311	@param[in] UserStruct The user structure to link into the collection.\r
312	UserStruct is ordered against in-collection user\r
313	structures with the\r
314	ORDERED_COLLECTION_USER_COMPARE function.\r
315	\r
316	@retval RETURN_SUCCESS Insertion successful. A new collection entry\r
317	has been allocated, linking UserStruct. The\r
318	new collection entry is reported back in\r
319	Entry (if the caller requested it).\r
320	\r
321	Existing ORDERED_COLLECTION_ENTRY pointers\r
322	into Collection remain valid. For example,\r
323	on-going iterations in the caller can\r
324	continue with OrderedCollectionNext() /\r
325	OrderedCollectionPrev(), and they will\r
326	return the new entry at some point if user\r
327	structure order dictates it.\r
328	\r
329	@retval RETURN_OUT_OF_RESOURCES The function failed to allocate memory for\r
330	the new collection entry. The collection has\r
331	not been changed. Existing\r
332	ORDERED_COLLECTION_ENTRY pointers into\r
333	Collection remain valid.\r
334	\r
335	@retval RETURN_ALREADY_STARTED A user structure has been found in the\r
336	collection that compares equal to\r
337	UserStruct. The entry linking the colliding\r
338	user structure is reported back in Entry (if\r
339	the caller requested it). The collection has\r
340	not been changed. Existing\r
341	ORDERED_COLLECTION_ENTRY pointers into\r
342	Collection remain valid.\r
343	**/\r
344	RETURN_STATUS\r
345	EFIAPI\r
346	OrderedCollectionInsert (\r
347	IN OUT ORDERED_COLLECTION *Collection,\r
348	OUT ORDERED_COLLECTION_ENTRY **Entry OPTIONAL,\r
349	IN VOID *UserStruct\r
350	);\r
351	\r
352	\r
353	/**\r
354	Delete an entry from the collection, unlinking the associated user structure.\r
355	\r
356	Read-write operation.\r
357	\r
358	@param[in,out] Collection The collection to delete Entry from.\r
359	\r
360	@param[in] Entry The collection entry to delete from Collection.\r
361	The caller is responsible for ensuring that Entry\r
362	belongs to Collection, and that Entry is non-NULL\r
363	and valid. Entry is typically an earlier return\r
364	value, or output parameter, of:\r
365	\r
366	- OrderedCollectionFind(), for deleting an entry\r
367	by user structure key,\r
368	\r
369	- OrderedCollectionMin() / OrderedCollectionMax(),\r
370	for deleting the minimum / maximum entry,\r
371	\r
372	- OrderedCollectionNext() /\r
373	OrderedCollectionPrev(), for deleting an entry\r
374	found during an iteration,\r
375	\r
376	- OrderedCollectionInsert() with return value\r
377	RETURN_ALREADY_STARTED, for deleting an entry\r
378	whose linked user structure caused collision\r
379	during insertion.\r
380	\r
381	Existing ORDERED_COLLECTION_ENTRY pointers (ie.\r
382	iterators) different from Entry remain valid.\r
383	For example:\r
384	\r
385	- OrderedCollectionNext() /\r
386	OrderedCollectionPrev() iterations in the caller\r
387	can be continued from Entry, if\r
388	OrderedCollectionNext() or\r
389	OrderedCollectionPrev() is called on Entry\r
390	before OrderedCollectionDelete() is. That is,\r
391	fetch the successor / predecessor entry first,\r
392	then delete Entry.\r
393	\r
394	- On-going iterations in the caller that would\r
395	have otherwise returned Entry at some point, as\r
396	dictated by user structure order, will correctly\r
397	reflect the absence of Entry after\r
398	OrderedCollectionDelete() is called\r
399	mid-iteration.\r
400	\r
401	@param[out] UserStruct If the caller provides this optional output-only\r
402	parameter, then on output it is set to the user\r
403	structure originally linked by Entry (which is now\r
404	freed).\r
405	\r
406	This is a convenience that may save the caller a\r
407	OrderedCollectionUserStruct() invocation before\r
408	calling OrderedCollectionDelete(), in order to\r
409	retrieve the user structure being unlinked.\r
410	**/\r
411	VOID\r
412	EFIAPI\r
413	OrderedCollectionDelete (\r
414	IN OUT ORDERED_COLLECTION *Collection,\r
415	IN ORDERED_COLLECTION_ENTRY *Entry,\r
416	OUT VOID **UserStruct OPTIONAL\r
417	);\r
418	\r
419	#endif\r