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 This program and the accompanying materials are licensed and made available
10 under the terms and conditions of the BSD License that accompanies this
11 distribution. The full text of the license may be found at
12 http://opensource.org/licenses/bsd-license.php.
14 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
15 WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
18 #ifndef __ORDERED_COLLECTION_LIB__
19 #define __ORDERED_COLLECTION_LIB__
24 // Opaque structure for a collection.
26 typedef struct ORDERED_COLLECTION ORDERED_COLLECTION
;
29 // Opaque structure for collection entries.
31 // Collection entries do not take ownership of the associated user structures,
32 // they only link them. This makes it easy to link the same user structure into
33 // several collections. If reference counting is required, the caller is
34 // responsible for implementing it, as part of the user structure.
36 // A pointer-to-ORDERED_COLLECTION_ENTRY is considered an "iterator". Multiple,
37 // simultaneous iterations are supported.
39 typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY
;
42 // Altering the key field of an in-collection user structure (ie. the portion
43 // of the user structure that ORDERED_COLLECTION_USER_COMPARE and
44 // ORDERED_COLLECTION_KEY_COMPARE, below, read) is not allowed in-place. The
45 // caller is responsible for bracketing the key change with the deletion and
46 // the reinsertion of the user structure, so that the changed key value is
47 // reflected in the collection.
51 Comparator function type for two user structures.
53 @param[in] UserStruct1 Pointer to the first user structure.
55 @param[in] UserStruct2 Pointer to the second user structure.
57 @retval <0 If UserStruct1 compares less than UserStruct2.
59 @retval 0 If UserStruct1 compares equal to UserStruct2.
61 @retval >0 If UserStruct1 compares greater than UserStruct2.
65 (EFIAPI
*ORDERED_COLLECTION_USER_COMPARE
)(
66 IN CONST VOID
*UserStruct1
,
67 IN CONST VOID
*UserStruct2
71 Compare a standalone key against a user structure containing an embedded key.
73 @param[in] StandaloneKey Pointer to the bare key.
75 @param[in] UserStruct Pointer to the user structure with the embedded
78 @retval <0 If StandaloneKey compares less than UserStruct's key.
80 @retval 0 If StandaloneKey compares equal to UserStruct's key.
82 @retval >0 If StandaloneKey compares greater than UserStruct's key.
86 (EFIAPI
*ORDERED_COLLECTION_KEY_COMPARE
)(
87 IN CONST VOID
*StandaloneKey
,
88 IN CONST VOID
*UserStruct
93 // Some functions below are read-only, while others are read-write. If any
94 // write operation is expected to run concurrently with any other operation on
95 // the same collection, then the caller is responsible for implementing locking
96 // for the whole collection.
100 Retrieve the user structure linked by the specified collection entry.
104 @param[in] Entry Pointer to the collection entry whose associated user
105 structure we want to retrieve. The caller is responsible
106 for passing a non-NULL argument.
108 @return Pointer to user structure linked by Entry.
112 OrderedCollectionUserStruct (
113 IN CONST ORDERED_COLLECTION_ENTRY
*Entry
118 Allocate and initialize the ORDERED_COLLECTION structure.
120 @param[in] UserStructCompare This caller-provided function will be used to
121 order two user structures linked into the
122 collection, during the insertion procedure.
124 @param[in] KeyCompare This caller-provided function will be used to
125 order the standalone search key against user
126 structures linked into the collection, during
127 the lookup procedure.
129 @retval NULL If allocation failed.
131 @return Pointer to the allocated, initialized ORDERED_COLLECTION
132 structure, otherwise.
136 OrderedCollectionInit (
137 IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare
,
138 IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare
143 Check whether the collection is empty (has no entries).
147 @param[in] Collection The collection to check for emptiness.
149 @retval TRUE The collection is empty.
151 @retval FALSE The collection is not empty.
155 OrderedCollectionIsEmpty (
156 IN CONST ORDERED_COLLECTION
*Collection
161 Uninitialize and release an empty ORDERED_COLLECTION structure.
163 Read-write operation.
165 It is the caller's responsibility to delete all entries from the collection
166 before calling this function.
168 @param[in] Collection The empty collection to uninitialize and release.
172 OrderedCollectionUninit (
173 IN ORDERED_COLLECTION
*Collection
178 Look up the collection entry that links the user structure that matches the
179 specified standalone key.
183 @param[in] Collection The collection to search for StandaloneKey.
185 @param[in] StandaloneKey The key to locate among the user structures linked
186 into Collection. StandaloneKey will be passed to
187 ORDERED_COLLECTION_KEY_COMPARE.
189 @retval NULL StandaloneKey could not be found.
191 @return The collection entry that links to the user structure matching
192 StandaloneKey, otherwise.
194 ORDERED_COLLECTION_ENTRY
*
196 OrderedCollectionFind (
197 IN CONST ORDERED_COLLECTION
*Collection
,
198 IN CONST VOID
*StandaloneKey
203 Find the collection entry of the minimum user structure stored in the
208 @param[in] Collection The collection to return the minimum entry of. The
209 user structure linked by the minimum entry compares
210 less than all other user structures in the collection.
212 @retval NULL If Collection is empty.
214 @return The collection entry that links the minimum user structure,
217 ORDERED_COLLECTION_ENTRY
*
219 OrderedCollectionMin (
220 IN CONST ORDERED_COLLECTION
*Collection
225 Find the collection entry of the maximum user structure stored in the
230 @param[in] Collection The collection to return the maximum entry of. The
231 user structure linked by the maximum entry compares
232 greater than all other user structures in the
235 @retval NULL If Collection is empty.
237 @return The collection entry that links the maximum user structure,
240 ORDERED_COLLECTION_ENTRY
*
242 OrderedCollectionMax (
243 IN CONST ORDERED_COLLECTION
*Collection
248 Get the collection entry of the least user structure that is greater than the
253 @param[in] Entry The entry to get the successor entry of.
255 @retval NULL If Entry is NULL, or Entry is the maximum entry of its
256 containing collection (ie. Entry has no successor entry).
258 @return The collection entry linking the least user structure that is
259 greater than the one linked by Entry, otherwise.
261 ORDERED_COLLECTION_ENTRY
*
263 OrderedCollectionNext (
264 IN CONST ORDERED_COLLECTION_ENTRY
*Entry
269 Get the collection entry of the greatest user structure that is less than the
274 @param[in] Entry The entry to get the predecessor entry of.
276 @retval NULL If Entry is NULL, or Entry is the minimum entry of its
277 containing collection (ie. Entry has no predecessor entry).
279 @return The collection entry linking the greatest user structure that
280 is less than the one linked by Entry, otherwise.
282 ORDERED_COLLECTION_ENTRY
*
284 OrderedCollectionPrev (
285 IN CONST ORDERED_COLLECTION_ENTRY
*Entry
290 Insert (link) a user structure into the collection, allocating a new
293 Read-write operation.
295 @param[in,out] Collection The collection to insert UserStruct into.
297 @param[out] Entry The meaning of this optional, output-only
298 parameter depends on the return value of the
301 When insertion is successful (RETURN_SUCCESS),
302 Entry is set on output to the new collection entry
303 that now links UserStruct.
305 When insertion fails due to lack of memory
306 (RETURN_OUT_OF_RESOURCES), Entry is not changed.
308 When insertion fails due to key collision (ie.
309 another user structure is already in the
310 collection that compares equal to UserStruct),
311 with return value RETURN_ALREADY_STARTED, then
312 Entry is set on output to the entry that links the
313 colliding user structure. This enables
314 "find-or-insert" in one function call, or helps
315 with later removal of the colliding element.
317 @param[in] UserStruct The user structure to link into the collection.
318 UserStruct is ordered against in-collection user
320 ORDERED_COLLECTION_USER_COMPARE function.
322 @retval RETURN_SUCCESS Insertion successful. A new collection entry
323 has been allocated, linking UserStruct. The
324 new collection entry is reported back in
325 Entry (if the caller requested it).
327 Existing ORDERED_COLLECTION_ENTRY pointers
328 into Collection remain valid. For example,
329 on-going iterations in the caller can
330 continue with OrderedCollectionNext() /
331 OrderedCollectionPrev(), and they will
332 return the new entry at some point if user
333 structure order dictates it.
335 @retval RETURN_OUT_OF_RESOURCES The function failed to allocate memory for
336 the new collection entry. The collection has
337 not been changed. Existing
338 ORDERED_COLLECTION_ENTRY pointers into
339 Collection remain valid.
341 @retval RETURN_ALREADY_STARTED A user structure has been found in the
342 collection that compares equal to
343 UserStruct. The entry linking the colliding
344 user structure is reported back in Entry (if
345 the caller requested it). The collection has
346 not been changed. Existing
347 ORDERED_COLLECTION_ENTRY pointers into
348 Collection remain valid.
352 OrderedCollectionInsert (
353 IN OUT ORDERED_COLLECTION
*Collection
,
354 OUT ORDERED_COLLECTION_ENTRY
**Entry OPTIONAL
,
360 Delete an entry from the collection, unlinking the associated user structure.
362 Read-write operation.
364 @param[in,out] Collection The collection to delete Entry from.
366 @param[in] Entry The collection entry to delete from Collection.
367 The caller is responsible for ensuring that Entry
368 belongs to Collection, and that Entry is non-NULL
369 and valid. Entry is typically an earlier return
370 value, or output parameter, of:
372 - OrderedCollectionFind(), for deleting an entry
373 by user structure key,
375 - OrderedCollectionMin() / OrderedCollectionMax(),
376 for deleting the minimum / maximum entry,
378 - OrderedCollectionNext() /
379 OrderedCollectionPrev(), for deleting an entry
380 found during an iteration,
382 - OrderedCollectionInsert() with return value
383 RETURN_ALREADY_STARTED, for deleting an entry
384 whose linked user structure caused collision
387 Existing ORDERED_COLLECTION_ENTRY pointers (ie.
388 iterators) *different* from Entry remain valid.
391 - OrderedCollectionNext() /
392 OrderedCollectionPrev() iterations in the caller
393 can be continued from Entry, if
394 OrderedCollectionNext() or
395 OrderedCollectionPrev() is called on Entry
396 *before* OrderedCollectionDelete() is. That is,
397 fetch the successor / predecessor entry first,
400 - On-going iterations in the caller that would
401 have otherwise returned Entry at some point, as
402 dictated by user structure order, will correctly
403 reflect the absence of Entry after
404 OrderedCollectionDelete() is called
407 @param[out] UserStruct If the caller provides this optional output-only
408 parameter, then on output it is set to the user
409 structure originally linked by Entry (which is now
412 This is a convenience that may save the caller a
413 OrderedCollectionUserStruct() invocation before
414 calling OrderedCollectionDelete(), in order to
415 retrieve the user structure being unlinked.
419 OrderedCollectionDelete (
420 IN OUT ORDERED_COLLECTION
*Collection
,
421 IN ORDERED_COLLECTION_ENTRY
*Entry
,
422 OUT VOID
**UserStruct OPTIONAL