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   SPDX-License-Identifier: BSD-2-Clause-Patent
  10 **/
  11
  12 #ifndef __ORDERED_COLLECTION_LIB__
  13 #define __ORDERED_COLLECTION_LIB__
  14
  15 #include <Base.h>
  16
  17 //
  18 // Opaque structure for a collection.
  19 //
  20 typedef struct ORDERED_COLLECTION ORDERED_COLLECTION;
  21
  22 //
  23 // Opaque structure for collection entries.
  24 //
  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.
  29 //
  30 // A pointer-to-ORDERED_COLLECTION_ENTRY is considered an "iterator". Multiple,
  31 // simultaneous iterations are supported.
  32 //
  33 typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY;
  34
  35 //
  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.
  42 //
  43
  44 /**
  45   Comparator function type for two user structures.
  46
  47   @param[in] UserStruct1  Pointer to the first user structure.
  48
  49   @param[in] UserStruct2  Pointer to the second user structure.
  50
  51   @retval <0  If UserStruct1 compares less than UserStruct2.
  52
  53   @retval  0  If UserStruct1 compares equal to UserStruct2.
  54
  55   @retval >0  If UserStruct1 compares greater than UserStruct2.
  56 **/
  57 typedef
  58 INTN
  59 (EFIAPI *ORDERED_COLLECTION_USER_COMPARE)(
  60   IN CONST VOID *UserStruct1,
  61   IN CONST VOID *UserStruct2
  62   );
  63
  64 /**
  65   Compare a standalone key against a user structure containing an embedded key.
  66
  67   @param[in] StandaloneKey  Pointer to the bare key.
  68
  69   @param[in] UserStruct     Pointer to the user structure with the embedded
  70                             key.
  71
  72   @retval <0  If StandaloneKey compares less than UserStruct's key.
  73
  74   @retval  0  If StandaloneKey compares equal to UserStruct's key.
  75
  76   @retval >0  If StandaloneKey compares greater than UserStruct's key.
  77 **/
  78 typedef
  79 INTN
  80 (EFIAPI *ORDERED_COLLECTION_KEY_COMPARE)(
  81   IN CONST VOID *StandaloneKey,
  82   IN CONST VOID *UserStruct
  83   );
  84
  85
  86 //
  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.
  91 //
  92
  93 /**
  94   Retrieve the user structure linked by the specified collection entry.
  95
  96   Read-only operation.
  97
  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.
 101
 102   @return  Pointer to user structure linked by Entry.
 103 **/
 104 VOID *
 105 EFIAPI
 106 OrderedCollectionUserStruct (
 107   IN CONST ORDERED_COLLECTION_ENTRY *Entry
 108   );
 109
 110
 111 /**
 112   Allocate and initialize the ORDERED_COLLECTION structure.
 113
 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.
 117
 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.
 122
 123   @retval NULL  If allocation failed.
 124
 125   @return       Pointer to the allocated, initialized ORDERED_COLLECTION
 126                 structure, otherwise.
 127 **/
 128 ORDERED_COLLECTION *
 129 EFIAPI
 130 OrderedCollectionInit (
 131   IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare,
 132   IN ORDERED_COLLECTION_KEY_COMPARE  KeyCompare
 133   );
 134
 135
 136 /**
 137   Check whether the collection is empty (has no entries).
 138
 139   Read-only operation.
 140
 141   @param[in] Collection  The collection to check for emptiness.
 142
 143   @retval TRUE   The collection is empty.
 144
 145   @retval FALSE  The collection is not empty.
 146 **/
 147 BOOLEAN
 148 EFIAPI
 149 OrderedCollectionIsEmpty (
 150   IN CONST ORDERED_COLLECTION *Collection
 151   );
 152
 153
 154 /**
 155   Uninitialize and release an empty ORDERED_COLLECTION structure.
 156
 157   Read-write operation.
 158
 159   It is the caller's responsibility to delete all entries from the collection
 160   before calling this function.
 161
 162   @param[in] Collection  The empty collection to uninitialize and release.
 163 **/
 164 VOID
 165 EFIAPI
 166 OrderedCollectionUninit (
 167   IN ORDERED_COLLECTION *Collection
 168   );
 169
 170
 171 /**
 172   Look up the collection entry that links the user structure that matches the
 173   specified standalone key.
 174
 175   Read-only operation.
 176
 177   @param[in] Collection     The collection to search for StandaloneKey.
 178
 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.
 182
 183   @retval NULL  StandaloneKey could not be found.
 184
 185   @return       The collection entry that links to the user structure matching
 186                 StandaloneKey, otherwise.
 187 **/
 188 ORDERED_COLLECTION_ENTRY *
 189 EFIAPI
 190 OrderedCollectionFind (
 191   IN CONST ORDERED_COLLECTION *Collection,
 192   IN CONST VOID               *StandaloneKey
 193   );
 194
 195
 196 /**
 197   Find the collection entry of the minimum user structure stored in the
 198   collection.
 199
 200   Read-only operation.
 201
 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.
 205
 206   @retval NULL  If Collection is empty.
 207
 208   @return       The collection entry that links the minimum user structure,
 209                 otherwise.
 210 **/
 211 ORDERED_COLLECTION_ENTRY *
 212 EFIAPI
 213 OrderedCollectionMin (
 214   IN CONST ORDERED_COLLECTION *Collection
 215   );
 216
 217
 218 /**
 219   Find the collection entry of the maximum user structure stored in the
 220   collection.
 221
 222   Read-only operation.
 223
 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
 227                          collection.
 228
 229   @retval NULL  If Collection is empty.
 230
 231   @return       The collection entry that links the maximum user structure,
 232                 otherwise.
 233 **/
 234 ORDERED_COLLECTION_ENTRY *
 235 EFIAPI
 236 OrderedCollectionMax (
 237   IN CONST ORDERED_COLLECTION *Collection
 238   );
 239
 240
 241 /**
 242   Get the collection entry of the least user structure that is greater than the
 243   one linked by Entry.
 244
 245   Read-only operation.
 246
 247   @param[in] Entry  The entry to get the successor entry of.
 248
 249   @retval NULL  If Entry is NULL, or Entry is the maximum entry of its
 250                 containing collection (ie. Entry has no successor entry).
 251
 252   @return       The collection entry linking the least user structure that is
 253                 greater than the one linked by Entry, otherwise.
 254 **/
 255 ORDERED_COLLECTION_ENTRY *
 256 EFIAPI
 257 OrderedCollectionNext (
 258   IN CONST ORDERED_COLLECTION_ENTRY *Entry
 259   );
 260
 261
 262 /**
 263   Get the collection entry of the greatest user structure that is less than the
 264   one linked by Entry.
 265
 266   Read-only operation.
 267
 268   @param[in] Entry  The entry to get the predecessor entry of.
 269
 270   @retval NULL  If Entry is NULL, or Entry is the minimum entry of its
 271                 containing collection (ie. Entry has no predecessor entry).
 272
 273   @return       The collection entry linking the greatest user structure that
 274                 is less than the one linked by Entry, otherwise.
 275 **/
 276 ORDERED_COLLECTION_ENTRY *
 277 EFIAPI
 278 OrderedCollectionPrev (
 279   IN CONST ORDERED_COLLECTION_ENTRY *Entry
 280   );
 281
 282
 283 /**
 284   Insert (link) a user structure into the collection, allocating a new
 285   collection entry.
 286
 287   Read-write operation.
 288
 289   @param[in,out] Collection  The collection to insert UserStruct into.
 290
 291   @param[out]    Entry       The meaning of this optional, output-only
 292                              parameter depends on the return value of the
 293                              function.
 294
 295                              When insertion is successful (RETURN_SUCCESS),
 296                              Entry is set on output to the new collection entry
 297                              that now links UserStruct.
 298
 299                              When insertion fails due to lack of memory
 300                              (RETURN_OUT_OF_RESOURCES), Entry is not changed.
 301
 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.
 310
 311   @param[in]     UserStruct  The user structure to link into the collection.
 312                              UserStruct is ordered against in-collection user
 313                              structures with the
 314                              ORDERED_COLLECTION_USER_COMPARE function.
 315
 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).
 320
 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.
 328
 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.
 334
 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.
 343 **/
 344 RETURN_STATUS
 345 EFIAPI
 346 OrderedCollectionInsert (
 347   IN OUT ORDERED_COLLECTION       *Collection,
 348   OUT    ORDERED_COLLECTION_ENTRY **Entry      OPTIONAL,
 349   IN     VOID                     *UserStruct
 350   );
 351
 352
 353 /**
 354   Delete an entry from the collection, unlinking the associated user structure.
 355
 356   Read-write operation.
 357
 358   @param[in,out] Collection  The collection to delete Entry from.
 359
 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:
 365
 366                              - OrderedCollectionFind(), for deleting an entry
 367                                by user structure key,
 368
 369                              - OrderedCollectionMin() / OrderedCollectionMax(),
 370                                for deleting the minimum / maximum entry,
 371
 372                              - OrderedCollectionNext() /
 373                                OrderedCollectionPrev(), for deleting an entry
 374                                found during an iteration,
 375
 376                              - OrderedCollectionInsert() with return value
 377                                RETURN_ALREADY_STARTED, for deleting an entry
 378                                whose linked user structure caused collision
 379                                during insertion.
 380
 381                              Existing ORDERED_COLLECTION_ENTRY pointers (ie.
 382                              iterators) *different* from Entry remain valid.
 383                              For example:
 384
 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,
 392                                then delete Entry.
 393
 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
 399                                mid-iteration.
 400
 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
 404                              freed).
 405
 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.
 410 **/
 411 VOID
 412 EFIAPI
 413 OrderedCollectionDelete (
 414   IN OUT ORDERED_COLLECTION       *Collection,
 415   IN     ORDERED_COLLECTION_ENTRY *Entry,
 416   OUT    VOID                     **UserStruct OPTIONAL
 417   );
 418
 419 #endif