MdePkg: introduce OrderedCollectionLib library class
[mirror_edk2.git] / MdePkg / Include / Library / OrderedCollectionLib.h
1 /** @file
2 An ordered collection library interface.
3
4 The library class provides a set of APIs to manage an ordered collection of
5 items.
6
7 Copyright (C) 2014, Red Hat, Inc.
8
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.
13
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.
16 **/
17
18 #ifndef __ORDERED_COLLECTION_LIB__
19 #define __ORDERED_COLLECTION_LIB__
20
21 #include <Base.h>
22
23 //
24 // Opaque structure for a collection.
25 //
26 typedef struct ORDERED_COLLECTION ORDERED_COLLECTION;
27
28 //
29 // Opaque structure for collection entries.
30 //
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.
35 //
36 // A pointer-to-ORDERED_COLLECTION_ENTRY is considered an "iterator". Multiple,
37 // simultaneous iterations are supported.
38 //
39 typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY;
40
41 //
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.
48 //
49
50 /**
51 Comparator function type for two user structures.
52
53 @param[in] UserStruct1 Pointer to the first user structure.
54
55 @param[in] UserStruct2 Pointer to the second user structure.
56
57 @retval <0 If UserStruct1 compares less than UserStruct2.
58
59 @retval 0 If UserStruct1 compares equal to UserStruct2.
60
61 @retval >0 If UserStruct1 compares greater than UserStruct2.
62 **/
63 typedef
64 INTN
65 (EFIAPI *ORDERED_COLLECTION_USER_COMPARE)(
66 IN CONST VOID *UserStruct1,
67 IN CONST VOID *UserStruct2
68 );
69
70 /**
71 Compare a standalone key against a user structure containing an embedded key.
72
73 @param[in] StandaloneKey Pointer to the bare key.
74
75 @param[in] UserStruct Pointer to the user structure with the embedded
76 key.
77
78 @retval <0 If StandaloneKey compares less than UserStruct's key.
79
80 @retval 0 If StandaloneKey compares equal to UserStruct's key.
81
82 @retval >0 If StandaloneKey compares greater than UserStruct's key.
83 **/
84 typedef
85 INTN
86 (EFIAPI *ORDERED_COLLECTION_KEY_COMPARE)(
87 IN CONST VOID *StandaloneKey,
88 IN CONST VOID *UserStruct
89 );
90
91
92 //
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.
97 //
98
99 /**
100 Retrieve the user structure linked by the specified collection entry.
101
102 Read-only operation.
103
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.
107
108 @return Pointer to user structure linked by Entry.
109 **/
110 VOID *
111 EFIAPI
112 OrderedCollectionUserStruct (
113 IN CONST ORDERED_COLLECTION_ENTRY *Entry
114 );
115
116
117 /**
118 Allocate and initialize the ORDERED_COLLECTION structure.
119
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.
123
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.
128
129 @retval NULL If allocation failed.
130
131 @return Pointer to the allocated, initialized ORDERED_COLLECTION
132 structure, otherwise.
133 **/
134 ORDERED_COLLECTION *
135 EFIAPI
136 OrderedCollectionInit (
137 IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare,
138 IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare
139 );
140
141
142 /**
143 Check whether the collection is empty (has no entries).
144
145 Read-only operation.
146
147 @param[in] Collection The collection to check for emptiness.
148
149 @retval TRUE The collection is empty.
150
151 @retval FALSE The collection is not empty.
152 **/
153 BOOLEAN
154 EFIAPI
155 OrderedCollectionIsEmpty (
156 IN CONST ORDERED_COLLECTION *Collection
157 );
158
159
160 /**
161 Uninitialize and release an empty ORDERED_COLLECTION structure.
162
163 Read-write operation.
164
165 It is the caller's responsibility to delete all entries from the collection
166 before calling this function.
167
168 @param[in] Collection The empty collection to uninitialize and release.
169 **/
170 VOID
171 EFIAPI
172 OrderedCollectionUninit (
173 IN ORDERED_COLLECTION *Collection
174 );
175
176
177 /**
178 Look up the collection entry that links the user structure that matches the
179 specified standalone key.
180
181 Read-only operation.
182
183 @param[in] Collection The collection to search for StandaloneKey.
184
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.
188
189 @retval NULL StandaloneKey could not be found.
190
191 @return The collection entry that links to the user structure matching
192 StandaloneKey, otherwise.
193 **/
194 ORDERED_COLLECTION_ENTRY *
195 EFIAPI
196 OrderedCollectionFind (
197 IN CONST ORDERED_COLLECTION *Collection,
198 IN CONST VOID *StandaloneKey
199 );
200
201
202 /**
203 Find the collection entry of the minimum user structure stored in the
204 collection.
205
206 Read-only operation.
207
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.
211
212 @retval NULL If Collection is empty.
213
214 @return The collection entry that links the minimum user structure,
215 otherwise.
216 **/
217 ORDERED_COLLECTION_ENTRY *
218 EFIAPI
219 OrderedCollectionMin (
220 IN CONST ORDERED_COLLECTION *Collection
221 );
222
223
224 /**
225 Find the collection entry of the maximum user structure stored in the
226 collection.
227
228 Read-only operation.
229
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
233 collection.
234
235 @retval NULL If Collection is empty.
236
237 @return The collection entry that links the maximum user structure,
238 otherwise.
239 **/
240 ORDERED_COLLECTION_ENTRY *
241 EFIAPI
242 OrderedCollectionMax (
243 IN CONST ORDERED_COLLECTION *Collection
244 );
245
246
247 /**
248 Get the collection entry of the least user structure that is greater than the
249 one linked by Entry.
250
251 Read-only operation.
252
253 @param[in] Entry The entry to get the successor entry of.
254
255 @retval NULL If Entry is NULL, or Entry is the maximum entry of its
256 containing collection (ie. Entry has no successor entry).
257
258 @return The collection entry linking the least user structure that is
259 greater than the one linked by Entry, otherwise.
260 **/
261 ORDERED_COLLECTION_ENTRY *
262 EFIAPI
263 OrderedCollectionNext (
264 IN CONST ORDERED_COLLECTION_ENTRY *Entry
265 );
266
267
268 /**
269 Get the collection entry of the greatest user structure that is less than the
270 one linked by Entry.
271
272 Read-only operation.
273
274 @param[in] Entry The entry to get the predecessor entry of.
275
276 @retval NULL If Entry is NULL, or Entry is the minimum entry of its
277 containing collection (ie. Entry has no predecessor entry).
278
279 @return The collection entry linking the greatest user structure that
280 is less than the one linked by Entry, otherwise.
281 **/
282 ORDERED_COLLECTION_ENTRY *
283 EFIAPI
284 OrderedCollectionPrev (
285 IN CONST ORDERED_COLLECTION_ENTRY *Entry
286 );
287
288
289 /**
290 Insert (link) a user structure into the collection, allocating a new
291 collection entry.
292
293 Read-write operation.
294
295 @param[in,out] Collection The collection to insert UserStruct into.
296
297 @param[out] Entry The meaning of this optional, output-only
298 parameter depends on the return value of the
299 function.
300
301 When insertion is successful (RETURN_SUCCESS),
302 Entry is set on output to the new collection entry
303 that now links UserStruct.
304
305 When insertion fails due to lack of memory
306 (RETURN_OUT_OF_RESOURCES), Entry is not changed.
307
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.
316
317 @param[in] UserStruct The user structure to link into the collection.
318 UserStruct is ordered against in-collection user
319 structures with the
320 ORDERED_COLLECTION_USER_COMPARE function.
321
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).
326
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.
334
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.
340
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.
349 **/
350 RETURN_STATUS
351 EFIAPI
352 OrderedCollectionInsert (
353 IN OUT ORDERED_COLLECTION *Collection,
354 OUT ORDERED_COLLECTION_ENTRY **Entry OPTIONAL,
355 IN VOID *UserStruct
356 );
357
358
359 /**
360 Delete an entry from the collection, unlinking the associated user structure.
361
362 Read-write operation.
363
364 @param[in,out] Collection The collection to delete Entry from.
365
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:
371
372 - OrderedCollectionFind(), for deleting an entry
373 by user structure key,
374
375 - OrderedCollectionMin() / OrderedCollectionMax(),
376 for deleting the minimum / maximum entry,
377
378 - OrderedCollectionNext() /
379 OrderedCollectionPrev(), for deleting an entry
380 found during an iteration,
381
382 - OrderedCollectionInsert() with return value
383 RETURN_ALREADY_STARTED, for deleting an entry
384 whose linked user structure caused collision
385 during insertion.
386
387 Existing ORDERED_COLLECTION_ENTRY pointers (ie.
388 iterators) *different* from Entry remain valid.
389 For example:
390
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,
398 then delete Entry.
399
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
405 mid-iteration.
406
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
410 freed).
411
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.
416 **/
417 VOID
418 EFIAPI
419 OrderedCollectionDelete (
420 IN OUT ORDERED_COLLECTION *Collection,
421 IN ORDERED_COLLECTION_ENTRY *Entry,
422 OUT VOID **UserStruct OPTIONAL
423 );
424
425 #endif