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