| 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
|
|---|
