2 An ordered collection library interface.
4 The library class provides a set of APIs to manage an ordered collection of
7 Copyright (C) 2014, Red Hat, Inc.
9 SPDX-License-Identifier: BSD-2-Clause-Patent
12 #ifndef __ORDERED_COLLECTION_LIB__
13 #define __ORDERED_COLLECTION_LIB__
18 // Opaque structure for a collection.
20 typedef struct ORDERED_COLLECTION ORDERED_COLLECTION
;
23 // Opaque structure for collection entries.
25 // Collection entries do not take ownership of the associated user structures,
26 // they only link them. This makes it easy to link the same user structure into
27 // several collections. If reference counting is required, the caller is
28 // responsible for implementing it, as part of the user structure.
30 // A pointer-to-ORDERED_COLLECTION_ENTRY is considered an "iterator". Multiple,
31 // simultaneous iterations are supported.
33 typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY
;
36 // Altering the key field of an in-collection user structure (ie. the portion
37 // of the user structure that ORDERED_COLLECTION_USER_COMPARE and
38 // ORDERED_COLLECTION_KEY_COMPARE, below, read) is not allowed in-place. The
39 // caller is responsible for bracketing the key change with the deletion and
40 // the reinsertion of the user structure, so that the changed key value is
41 // reflected in the collection.
45 Comparator function type for two user structures.
47 @param[in] UserStruct1 Pointer to the first user structure.
49 @param[in] UserStruct2 Pointer to the second user structure.
51 @retval <0 If UserStruct1 compares less than UserStruct2.
53 @retval 0 If UserStruct1 compares equal to UserStruct2.
55 @retval >0 If UserStruct1 compares greater than UserStruct2.
59 (EFIAPI
*ORDERED_COLLECTION_USER_COMPARE
)(
60 IN CONST VOID
*UserStruct1
,
61 IN CONST VOID
*UserStruct2
65 Compare a standalone key against a user structure containing an embedded key.
67 @param[in] StandaloneKey Pointer to the bare key.
69 @param[in] UserStruct Pointer to the user structure with the embedded
72 @retval <0 If StandaloneKey compares less than UserStruct's key.
74 @retval 0 If StandaloneKey compares equal to UserStruct's key.
76 @retval >0 If StandaloneKey compares greater than UserStruct's key.
80 (EFIAPI
*ORDERED_COLLECTION_KEY_COMPARE
)(
81 IN CONST VOID
*StandaloneKey
,
82 IN CONST VOID
*UserStruct
86 // Some functions below are read-only, while others are read-write. If any
87 // write operation is expected to run concurrently with any other operation on
88 // the same collection, then the caller is responsible for implementing locking
89 // for the whole collection.
93 Retrieve the user structure linked by the specified collection entry.
97 @param[in] Entry Pointer to the collection entry whose associated user
98 structure we want to retrieve. The caller is responsible
99 for passing a non-NULL argument.
101 @return Pointer to user structure linked by Entry.
105 OrderedCollectionUserStruct (
106 IN CONST ORDERED_COLLECTION_ENTRY
*Entry
110 Allocate and initialize the ORDERED_COLLECTION structure.
112 @param[in] UserStructCompare This caller-provided function will be used to
113 order two user structures linked into the
114 collection, during the insertion procedure.
116 @param[in] KeyCompare This caller-provided function will be used to
117 order the standalone search key against user
118 structures linked into the collection, during
119 the lookup procedure.
121 @retval NULL If allocation failed.
123 @return Pointer to the allocated, initialized ORDERED_COLLECTION
124 structure, otherwise.
128 OrderedCollectionInit (
129 IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare
,
130 IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare
134 Check whether the collection is empty (has no entries).
138 @param[in] Collection The collection to check for emptiness.
140 @retval TRUE The collection is empty.
142 @retval FALSE The collection is not empty.
146 OrderedCollectionIsEmpty (
147 IN CONST ORDERED_COLLECTION
*Collection
151 Uninitialize and release an empty ORDERED_COLLECTION structure.
153 Read-write operation.
155 It is the caller's responsibility to delete all entries from the collection
156 before calling this function.
158 @param[in] Collection The empty collection to uninitialize and release.
162 OrderedCollectionUninit (
163 IN ORDERED_COLLECTION
*Collection
167 Look up the collection entry that links the user structure that matches the
168 specified standalone key.
172 @param[in] Collection The collection to search for StandaloneKey.
174 @param[in] StandaloneKey The key to locate among the user structures linked
175 into Collection. StandaloneKey will be passed to
176 ORDERED_COLLECTION_KEY_COMPARE.
178 @retval NULL StandaloneKey could not be found.
180 @return The collection entry that links to the user structure matching
181 StandaloneKey, otherwise.
183 ORDERED_COLLECTION_ENTRY
*
185 OrderedCollectionFind (
186 IN CONST ORDERED_COLLECTION
*Collection
,
187 IN CONST VOID
*StandaloneKey
191 Find the collection entry of the minimum user structure stored in the
196 @param[in] Collection The collection to return the minimum entry of. The
197 user structure linked by the minimum entry compares
198 less than all other user structures in the collection.
200 @retval NULL If Collection is empty.
202 @return The collection entry that links the minimum user structure,
205 ORDERED_COLLECTION_ENTRY
*
207 OrderedCollectionMin (
208 IN CONST ORDERED_COLLECTION
*Collection
212 Find the collection entry of the maximum user structure stored in the
217 @param[in] Collection The collection to return the maximum entry of. The
218 user structure linked by the maximum entry compares
219 greater than all other user structures in the
222 @retval NULL If Collection is empty.
224 @return The collection entry that links the maximum user structure,
227 ORDERED_COLLECTION_ENTRY
*
229 OrderedCollectionMax (
230 IN CONST ORDERED_COLLECTION
*Collection
234 Get the collection entry of the least user structure that is greater than the
239 @param[in] Entry The entry to get the successor entry of.
241 @retval NULL If Entry is NULL, or Entry is the maximum entry of its
242 containing collection (ie. Entry has no successor entry).
244 @return The collection entry linking the least user structure that is
245 greater than the one linked by Entry, otherwise.
247 ORDERED_COLLECTION_ENTRY
*
249 OrderedCollectionNext (
250 IN CONST ORDERED_COLLECTION_ENTRY
*Entry
254 Get the collection entry of the greatest user structure that is less than the
259 @param[in] Entry The entry to get the predecessor entry of.
261 @retval NULL If Entry is NULL, or Entry is the minimum entry of its
262 containing collection (ie. Entry has no predecessor entry).
264 @return The collection entry linking the greatest user structure that
265 is less than the one linked by Entry, otherwise.
267 ORDERED_COLLECTION_ENTRY
*
269 OrderedCollectionPrev (
270 IN CONST ORDERED_COLLECTION_ENTRY
*Entry
274 Insert (link) a user structure into the collection, allocating a new
277 Read-write operation.
279 @param[in,out] Collection The collection to insert UserStruct into.
281 @param[out] Entry The meaning of this optional, output-only
282 parameter depends on the return value of the
285 When insertion is successful (RETURN_SUCCESS),
286 Entry is set on output to the new collection entry
287 that now links UserStruct.
289 When insertion fails due to lack of memory
290 (RETURN_OUT_OF_RESOURCES), Entry is not changed.
292 When insertion fails due to key collision (ie.
293 another user structure is already in the
294 collection that compares equal to UserStruct),
295 with return value RETURN_ALREADY_STARTED, then
296 Entry is set on output to the entry that links the
297 colliding user structure. This enables
298 "find-or-insert" in one function call, or helps
299 with later removal of the colliding element.
301 @param[in] UserStruct The user structure to link into the collection.
302 UserStruct is ordered against in-collection user
304 ORDERED_COLLECTION_USER_COMPARE function.
306 @retval RETURN_SUCCESS Insertion successful. A new collection entry
307 has been allocated, linking UserStruct. The
308 new collection entry is reported back in
309 Entry (if the caller requested it).
311 Existing ORDERED_COLLECTION_ENTRY pointers
312 into Collection remain valid. For example,
313 on-going iterations in the caller can
314 continue with OrderedCollectionNext() /
315 OrderedCollectionPrev(), and they will
316 return the new entry at some point if user
317 structure order dictates it.
319 @retval RETURN_OUT_OF_RESOURCES The function failed to allocate memory for
320 the new collection entry. The collection has
321 not been changed. Existing
322 ORDERED_COLLECTION_ENTRY pointers into
323 Collection remain valid.
325 @retval RETURN_ALREADY_STARTED A user structure has been found in the
326 collection that compares equal to
327 UserStruct. The entry linking the colliding
328 user structure is reported back in Entry (if
329 the caller requested it). The collection has
330 not been changed. Existing
331 ORDERED_COLLECTION_ENTRY pointers into
332 Collection remain valid.
336 OrderedCollectionInsert (
337 IN OUT ORDERED_COLLECTION
*Collection
,
338 OUT ORDERED_COLLECTION_ENTRY
**Entry OPTIONAL
,
343 Delete an entry from the collection, unlinking the associated user structure.
345 Read-write operation.
347 @param[in,out] Collection The collection to delete Entry from.
349 @param[in] Entry The collection entry to delete from Collection.
350 The caller is responsible for ensuring that Entry
351 belongs to Collection, and that Entry is non-NULL
352 and valid. Entry is typically an earlier return
353 value, or output parameter, of:
355 - OrderedCollectionFind(), for deleting an entry
356 by user structure key,
358 - OrderedCollectionMin() / OrderedCollectionMax(),
359 for deleting the minimum / maximum entry,
361 - OrderedCollectionNext() /
362 OrderedCollectionPrev(), for deleting an entry
363 found during an iteration,
365 - OrderedCollectionInsert() with return value
366 RETURN_ALREADY_STARTED, for deleting an entry
367 whose linked user structure caused collision
370 Existing ORDERED_COLLECTION_ENTRY pointers (ie.
371 iterators) *different* from Entry remain valid.
374 - OrderedCollectionNext() /
375 OrderedCollectionPrev() iterations in the caller
376 can be continued from Entry, if
377 OrderedCollectionNext() or
378 OrderedCollectionPrev() is called on Entry
379 *before* OrderedCollectionDelete() is. That is,
380 fetch the successor / predecessor entry first,
383 - On-going iterations in the caller that would
384 have otherwise returned Entry at some point, as
385 dictated by user structure order, will correctly
386 reflect the absence of Entry after
387 OrderedCollectionDelete() is called
390 @param[out] UserStruct If the caller provides this optional output-only
391 parameter, then on output it is set to the user
392 structure originally linked by Entry (which is now
395 This is a convenience that may save the caller a
396 OrderedCollectionUserStruct() invocation before
397 calling OrderedCollectionDelete(), in order to
398 retrieve the user structure being unlinked.
402 OrderedCollectionDelete (
403 IN OUT ORDERED_COLLECTION
*Collection
,
404 IN ORDERED_COLLECTION_ENTRY
*Entry
,
405 OUT VOID
**UserStruct OPTIONAL