1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
|
/** @file
An ordered collection library interface.
The library class provides a set of APIs to manage an ordered collection of
items.
Copyright (C) 2014, Red Hat, Inc.
SPDX-License-Identifier: BSD-2-Clause-Patent
**/
#ifndef __ORDERED_COLLECTION_LIB__
#define __ORDERED_COLLECTION_LIB__
#include <Base.h>
//
// Opaque structure for a collection.
//
typedef struct ORDERED_COLLECTION ORDERED_COLLECTION;
//
// Opaque structure for collection entries.
//
// Collection entries do not take ownership of the associated user structures,
// they only link them. This makes it easy to link the same user structure into
// several collections. If reference counting is required, the caller is
// responsible for implementing it, as part of the user structure.
//
// A pointer-to-ORDERED_COLLECTION_ENTRY is considered an "iterator". Multiple,
// simultaneous iterations are supported.
//
typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY;
//
// Altering the key field of an in-collection user structure (ie. the portion
// of the user structure that ORDERED_COLLECTION_USER_COMPARE and
// ORDERED_COLLECTION_KEY_COMPARE, below, read) is not allowed in-place. The
// caller is responsible for bracketing the key change with the deletion and
// the reinsertion of the user structure, so that the changed key value is
// reflected in the collection.
//
/**
Comparator function type for two user structures.
@param[in] UserStruct1 Pointer to the first user structure.
@param[in] UserStruct2 Pointer to the second user structure.
@retval <0 If UserStruct1 compares less than UserStruct2.
@retval 0 If UserStruct1 compares equal to UserStruct2.
@retval >0 If UserStruct1 compares greater than UserStruct2.
**/
typedef
INTN
(EFIAPI *ORDERED_COLLECTION_USER_COMPARE)(
IN CONST VOID *UserStruct1,
IN CONST VOID *UserStruct2
);
/**
Compare a standalone key against a user structure containing an embedded key.
@param[in] StandaloneKey Pointer to the bare key.
@param[in] UserStruct Pointer to the user structure with the embedded
key.
@retval <0 If StandaloneKey compares less than UserStruct's key.
@retval 0 If StandaloneKey compares equal to UserStruct's key.
@retval >0 If StandaloneKey compares greater than UserStruct's key.
**/
typedef
INTN
(EFIAPI *ORDERED_COLLECTION_KEY_COMPARE)(
IN CONST VOID *StandaloneKey,
IN CONST VOID *UserStruct
);
//
// Some functions below are read-only, while others are read-write. If any
// write operation is expected to run concurrently with any other operation on
// the same collection, then the caller is responsible for implementing locking
// for the whole collection.
//
/**
Retrieve the user structure linked by the specified collection entry.
Read-only operation.
@param[in] Entry Pointer to the collection entry whose associated user
structure we want to retrieve. The caller is responsible
for passing a non-NULL argument.
@return Pointer to user structure linked by Entry.
**/
VOID *
EFIAPI
OrderedCollectionUserStruct (
IN CONST ORDERED_COLLECTION_ENTRY *Entry
);
/**
Allocate and initialize the ORDERED_COLLECTION structure.
@param[in] UserStructCompare This caller-provided function will be used to
order two user structures linked into the
collection, during the insertion procedure.
@param[in] KeyCompare This caller-provided function will be used to
order the standalone search key against user
structures linked into the collection, during
the lookup procedure.
@retval NULL If allocation failed.
@return Pointer to the allocated, initialized ORDERED_COLLECTION
structure, otherwise.
**/
ORDERED_COLLECTION *
EFIAPI
OrderedCollectionInit (
IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare,
IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare
);
/**
Check whether the collection is empty (has no entries).
Read-only operation.
@param[in] Collection The collection to check for emptiness.
@retval TRUE The collection is empty.
@retval FALSE The collection is not empty.
**/
BOOLEAN
EFIAPI
OrderedCollectionIsEmpty (
IN CONST ORDERED_COLLECTION *Collection
);
/**
Uninitialize and release an empty ORDERED_COLLECTION structure.
Read-write operation.
It is the caller's responsibility to delete all entries from the collection
before calling this function.
@param[in] Collection The empty collection to uninitialize and release.
**/
VOID
EFIAPI
OrderedCollectionUninit (
IN ORDERED_COLLECTION *Collection
);
/**
Look up the collection entry that links the user structure that matches the
specified standalone key.
Read-only operation.
@param[in] Collection The collection to search for StandaloneKey.
@param[in] StandaloneKey The key to locate among the user structures linked
into Collection. StandaloneKey will be passed to
ORDERED_COLLECTION_KEY_COMPARE.
@retval NULL StandaloneKey could not be found.
@return The collection entry that links to the user structure matching
StandaloneKey, otherwise.
**/
ORDERED_COLLECTION_ENTRY *
EFIAPI
OrderedCollectionFind (
IN CONST ORDERED_COLLECTION *Collection,
IN CONST VOID *StandaloneKey
);
/**
Find the collection entry of the minimum user structure stored in the
collection.
Read-only operation.
@param[in] Collection The collection to return the minimum entry of. The
user structure linked by the minimum entry compares
less than all other user structures in the collection.
@retval NULL If Collection is empty.
@return The collection entry that links the minimum user structure,
otherwise.
**/
ORDERED_COLLECTION_ENTRY *
EFIAPI
OrderedCollectionMin (
IN CONST ORDERED_COLLECTION *Collection
);
/**
Find the collection entry of the maximum user structure stored in the
collection.
Read-only operation.
@param[in] Collection The collection to return the maximum entry of. The
user structure linked by the maximum entry compares
greater than all other user structures in the
collection.
@retval NULL If Collection is empty.
@return The collection entry that links the maximum user structure,
otherwise.
**/
ORDERED_COLLECTION_ENTRY *
EFIAPI
OrderedCollectionMax (
IN CONST ORDERED_COLLECTION *Collection
);
/**
Get the collection entry of the least user structure that is greater than the
one linked by Entry.
Read-only operation.
@param[in] Entry The entry to get the successor entry of.
@retval NULL If Entry is NULL, or Entry is the maximum entry of its
containing collection (ie. Entry has no successor entry).
@return The collection entry linking the least user structure that is
greater than the one linked by Entry, otherwise.
**/
ORDERED_COLLECTION_ENTRY *
EFIAPI
OrderedCollectionNext (
IN CONST ORDERED_COLLECTION_ENTRY *Entry
);
/**
Get the collection entry of the greatest user structure that is less than the
one linked by Entry.
Read-only operation.
@param[in] Entry The entry to get the predecessor entry of.
@retval NULL If Entry is NULL, or Entry is the minimum entry of its
containing collection (ie. Entry has no predecessor entry).
@return The collection entry linking the greatest user structure that
is less than the one linked by Entry, otherwise.
**/
ORDERED_COLLECTION_ENTRY *
EFIAPI
OrderedCollectionPrev (
IN CONST ORDERED_COLLECTION_ENTRY *Entry
);
/**
Insert (link) a user structure into the collection, allocating a new
collection entry.
Read-write operation.
@param[in,out] Collection The collection to insert UserStruct into.
@param[out] Entry The meaning of this optional, output-only
parameter depends on the return value of the
function.
When insertion is successful (RETURN_SUCCESS),
Entry is set on output to the new collection entry
that now links UserStruct.
When insertion fails due to lack of memory
(RETURN_OUT_OF_RESOURCES), Entry is not changed.
When insertion fails due to key collision (ie.
another user structure is already in the
collection that compares equal to UserStruct),
with return value RETURN_ALREADY_STARTED, then
Entry is set on output to the entry that links the
colliding user structure. This enables
"find-or-insert" in one function call, or helps
with later removal of the colliding element.
@param[in] UserStruct The user structure to link into the collection.
UserStruct is ordered against in-collection user
structures with the
ORDERED_COLLECTION_USER_COMPARE function.
@retval RETURN_SUCCESS Insertion successful. A new collection entry
has been allocated, linking UserStruct. The
new collection entry is reported back in
Entry (if the caller requested it).
Existing ORDERED_COLLECTION_ENTRY pointers
into Collection remain valid. For example,
on-going iterations in the caller can
continue with OrderedCollectionNext() /
OrderedCollectionPrev(), and they will
return the new entry at some point if user
structure order dictates it.
@retval RETURN_OUT_OF_RESOURCES The function failed to allocate memory for
the new collection entry. The collection has
not been changed. Existing
ORDERED_COLLECTION_ENTRY pointers into
Collection remain valid.
@retval RETURN_ALREADY_STARTED A user structure has been found in the
collection that compares equal to
UserStruct. The entry linking the colliding
user structure is reported back in Entry (if
the caller requested it). The collection has
not been changed. Existing
ORDERED_COLLECTION_ENTRY pointers into
Collection remain valid.
**/
RETURN_STATUS
EFIAPI
OrderedCollectionInsert (
IN OUT ORDERED_COLLECTION *Collection,
OUT ORDERED_COLLECTION_ENTRY **Entry OPTIONAL,
IN VOID *UserStruct
);
/**
Delete an entry from the collection, unlinking the associated user structure.
Read-write operation.
@param[in,out] Collection The collection to delete Entry from.
@param[in] Entry The collection entry to delete from Collection.
The caller is responsible for ensuring that Entry
belongs to Collection, and that Entry is non-NULL
and valid. Entry is typically an earlier return
value, or output parameter, of:
- OrderedCollectionFind(), for deleting an entry
by user structure key,
- OrderedCollectionMin() / OrderedCollectionMax(),
for deleting the minimum / maximum entry,
- OrderedCollectionNext() /
OrderedCollectionPrev(), for deleting an entry
found during an iteration,
- OrderedCollectionInsert() with return value
RETURN_ALREADY_STARTED, for deleting an entry
whose linked user structure caused collision
during insertion.
Existing ORDERED_COLLECTION_ENTRY pointers (ie.
iterators) *different* from Entry remain valid.
For example:
- OrderedCollectionNext() /
OrderedCollectionPrev() iterations in the caller
can be continued from Entry, if
OrderedCollectionNext() or
OrderedCollectionPrev() is called on Entry
*before* OrderedCollectionDelete() is. That is,
fetch the successor / predecessor entry first,
then delete Entry.
- On-going iterations in the caller that would
have otherwise returned Entry at some point, as
dictated by user structure order, will correctly
reflect the absence of Entry after
OrderedCollectionDelete() is called
mid-iteration.
@param[out] UserStruct If the caller provides this optional output-only
parameter, then on output it is set to the user
structure originally linked by Entry (which is now
freed).
This is a convenience that may save the caller a
OrderedCollectionUserStruct() invocation before
calling OrderedCollectionDelete(), in order to
retrieve the user structure being unlinked.
**/
VOID
EFIAPI
OrderedCollectionDelete (
IN OUT ORDERED_COLLECTION *Collection,
IN ORDERED_COLLECTION_ENTRY *Entry,
OUT VOID **UserStruct OPTIONAL
);
#endif
|
