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
87 // Some functions below are read-only, while others are read-write. If any
88 // write operation is expected to run concurrently with any other operation on
89 // the same collection, then the caller is responsible for implementing locking
90 // for the whole collection.
94 Retrieve the user structure linked by the specified collection entry.
98 @param[in] Entry Pointer to the collection entry whose associated user
99 structure we want to retrieve. The caller is responsible
100 for passing a non-NULL argument.
102 @return Pointer to user structure linked by Entry.
106 OrderedCollectionUserStruct (
107 IN CONST ORDERED_COLLECTION_ENTRY
*Entry
112 Allocate and initialize the ORDERED_COLLECTION structure.
114 @param[in] UserStructCompare This caller-provided function will be used to
115 order two user structures linked into the
116 collection, during the insertion procedure.
118 @param[in] KeyCompare This caller-provided function will be used to
119 order the standalone search key against user
120 structures linked into the collection, during
121 the lookup procedure.
123 @retval NULL If allocation failed.
125 @return Pointer to the allocated, initialized ORDERED_COLLECTION
126 structure, otherwise.
130 OrderedCollectionInit (
131 IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare
,
132 IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare
137 Check whether the collection is empty (has no entries).
141 @param[in] Collection The collection to check for emptiness.
143 @retval TRUE The collection is empty.
145 @retval FALSE The collection is not empty.
149 OrderedCollectionIsEmpty (
150 IN CONST ORDERED_COLLECTION
*Collection
155 Uninitialize and release an empty ORDERED_COLLECTION structure.
157 Read-write operation.
159 It is the caller's responsibility to delete all entries from the collection
160 before calling this function.
162 @param[in] Collection The empty collection to uninitialize and release.
166 OrderedCollectionUninit (
167 IN ORDERED_COLLECTION
*Collection
172 Look up the collection entry that links the user structure that matches the
173 specified standalone key.
177 @param[in] Collection The collection to search for StandaloneKey.
179 @param[in] StandaloneKey The key to locate among the user structures linked
180 into Collection. StandaloneKey will be passed to
181 ORDERED_COLLECTION_KEY_COMPARE.
183 @retval NULL StandaloneKey could not be found.
185 @return The collection entry that links to the user structure matching
186 StandaloneKey, otherwise.
188 ORDERED_COLLECTION_ENTRY
*
190 OrderedCollectionFind (
191 IN CONST ORDERED_COLLECTION
*Collection
,
192 IN CONST VOID
*StandaloneKey
197 Find the collection entry of the minimum user structure stored in the
202 @param[in] Collection The collection to return the minimum entry of. The
203 user structure linked by the minimum entry compares
204 less than all other user structures in the collection.
206 @retval NULL If Collection is empty.
208 @return The collection entry that links the minimum user structure,
211 ORDERED_COLLECTION_ENTRY
*
213 OrderedCollectionMin (
214 IN CONST ORDERED_COLLECTION
*Collection
219 Find the collection entry of the maximum user structure stored in the
224 @param[in] Collection The collection to return the maximum entry of. The
225 user structure linked by the maximum entry compares
226 greater than all other user structures in the
229 @retval NULL If Collection is empty.
231 @return The collection entry that links the maximum user structure,
234 ORDERED_COLLECTION_ENTRY
*
236 OrderedCollectionMax (
237 IN CONST ORDERED_COLLECTION
*Collection
242 Get the collection entry of the least user structure that is greater than the
247 @param[in] Entry The entry to get the successor entry of.
249 @retval NULL If Entry is NULL, or Entry is the maximum entry of its
250 containing collection (ie. Entry has no successor entry).
252 @return The collection entry linking the least user structure that is
253 greater than the one linked by Entry, otherwise.
255 ORDERED_COLLECTION_ENTRY
*
257 OrderedCollectionNext (
258 IN CONST ORDERED_COLLECTION_ENTRY
*Entry
263 Get the collection entry of the greatest user structure that is less than the
268 @param[in] Entry The entry to get the predecessor entry of.
270 @retval NULL If Entry is NULL, or Entry is the minimum entry of its
271 containing collection (ie. Entry has no predecessor entry).
273 @return The collection entry linking the greatest user structure that
274 is less than the one linked by Entry, otherwise.
276 ORDERED_COLLECTION_ENTRY
*
278 OrderedCollectionPrev (
279 IN CONST ORDERED_COLLECTION_ENTRY
*Entry
284 Insert (link) a user structure into the collection, allocating a new
287 Read-write operation.
289 @param[in,out] Collection The collection to insert UserStruct into.
291 @param[out] Entry The meaning of this optional, output-only
292 parameter depends on the return value of the
295 When insertion is successful (RETURN_SUCCESS),
296 Entry is set on output to the new collection entry
297 that now links UserStruct.
299 When insertion fails due to lack of memory
300 (RETURN_OUT_OF_RESOURCES), Entry is not changed.
302 When insertion fails due to key collision (ie.
303 another user structure is already in the
304 collection that compares equal to UserStruct),
305 with return value RETURN_ALREADY_STARTED, then
306 Entry is set on output to the entry that links the
307 colliding user structure. This enables
308 "find-or-insert" in one function call, or helps
309 with later removal of the colliding element.
311 @param[in] UserStruct The user structure to link into the collection.
312 UserStruct is ordered against in-collection user
314 ORDERED_COLLECTION_USER_COMPARE function.
316 @retval RETURN_SUCCESS Insertion successful. A new collection entry
317 has been allocated, linking UserStruct. The
318 new collection entry is reported back in
319 Entry (if the caller requested it).
321 Existing ORDERED_COLLECTION_ENTRY pointers
322 into Collection remain valid. For example,
323 on-going iterations in the caller can
324 continue with OrderedCollectionNext() /
325 OrderedCollectionPrev(), and they will
326 return the new entry at some point if user
327 structure order dictates it.
329 @retval RETURN_OUT_OF_RESOURCES The function failed to allocate memory for
330 the new collection entry. The collection has
331 not been changed. Existing
332 ORDERED_COLLECTION_ENTRY pointers into
333 Collection remain valid.
335 @retval RETURN_ALREADY_STARTED A user structure has been found in the
336 collection that compares equal to
337 UserStruct. The entry linking the colliding
338 user structure is reported back in Entry (if
339 the caller requested it). The collection has
340 not been changed. Existing
341 ORDERED_COLLECTION_ENTRY pointers into
342 Collection remain valid.
346 OrderedCollectionInsert (
347 IN OUT ORDERED_COLLECTION
*Collection
,
348 OUT ORDERED_COLLECTION_ENTRY
**Entry OPTIONAL
,
354 Delete an entry from the collection, unlinking the associated user structure.
356 Read-write operation.
358 @param[in,out] Collection The collection to delete Entry from.
360 @param[in] Entry The collection entry to delete from Collection.
361 The caller is responsible for ensuring that Entry
362 belongs to Collection, and that Entry is non-NULL
363 and valid. Entry is typically an earlier return
364 value, or output parameter, of:
366 - OrderedCollectionFind(), for deleting an entry
367 by user structure key,
369 - OrderedCollectionMin() / OrderedCollectionMax(),
370 for deleting the minimum / maximum entry,
372 - OrderedCollectionNext() /
373 OrderedCollectionPrev(), for deleting an entry
374 found during an iteration,
376 - OrderedCollectionInsert() with return value
377 RETURN_ALREADY_STARTED, for deleting an entry
378 whose linked user structure caused collision
381 Existing ORDERED_COLLECTION_ENTRY pointers (ie.
382 iterators) *different* from Entry remain valid.
385 - OrderedCollectionNext() /
386 OrderedCollectionPrev() iterations in the caller
387 can be continued from Entry, if
388 OrderedCollectionNext() or
389 OrderedCollectionPrev() is called on Entry
390 *before* OrderedCollectionDelete() is. That is,
391 fetch the successor / predecessor entry first,
394 - On-going iterations in the caller that would
395 have otherwise returned Entry at some point, as
396 dictated by user structure order, will correctly
397 reflect the absence of Entry after
398 OrderedCollectionDelete() is called
401 @param[out] UserStruct If the caller provides this optional output-only
402 parameter, then on output it is set to the user
403 structure originally linked by Entry (which is now
406 This is a convenience that may save the caller a
407 OrderedCollectionUserStruct() invocation before
408 calling OrderedCollectionDelete(), in order to
409 retrieve the user structure being unlinked.
413 OrderedCollectionDelete (
414 IN OUT ORDERED_COLLECTION
*Collection
,
415 IN ORDERED_COLLECTION_ENTRY
*Entry
,
416 OUT VOID
**UserStruct OPTIONAL