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 // Some functions below are read-only, while others are read-write. If any
  87 // write operation is expected to run concurrently with any other operation on
  88 // the same collection, then the caller is responsible for implementing locking
  89 // for the whole collection.
  90 //
  91
  92 /**
  93   Retrieve the user structure linked by the specified collection entry.
  94
  95   Read-only operation.
  96
  97   @param[in] Entry  Pointer to the collection entry whose associated user
  98                     structure we want to retrieve. The caller is responsible
  99                     for passing a non-NULL argument.
 100
 101   @return  Pointer to user structure linked by Entry.
 102 **/
 103 VOID *
 104 EFIAPI
 105 OrderedCollectionUserStruct (
 106   IN CONST ORDERED_COLLECTION_ENTRY  *Entry
 107   );
 108
 109 /**
 110   Allocate and initialize the ORDERED_COLLECTION structure.
 111
 112   @param[in]  UserStructCompare  This caller-provided function will be used to
 113                                  order two user structures linked into the
 114                                  collection, during the insertion procedure.
 115
 116   @param[in]  KeyCompare         This caller-provided function will be used to
 117                                  order the standalone search key against user
 118                                  structures linked into the collection, during
 119                                  the lookup procedure.
 120
 121   @retval NULL  If allocation failed.
 122
 123   @return       Pointer to the allocated, initialized ORDERED_COLLECTION
 124                 structure, otherwise.
 125 **/
 126 ORDERED_COLLECTION *
 127 EFIAPI
 128 OrderedCollectionInit (
 129   IN ORDERED_COLLECTION_USER_COMPARE  UserStructCompare,
 130   IN ORDERED_COLLECTION_KEY_COMPARE   KeyCompare
 131   );
 132
 133 /**
 134   Check whether the collection is empty (has no entries).
 135
 136   Read-only operation.
 137
 138   @param[in] Collection  The collection to check for emptiness.
 139
 140   @retval TRUE   The collection is empty.
 141
 142   @retval FALSE  The collection is not empty.
 143 **/
 144 BOOLEAN
 145 EFIAPI
 146 OrderedCollectionIsEmpty (
 147   IN CONST ORDERED_COLLECTION  *Collection
 148   );
 149
 150 /**
 151   Uninitialize and release an empty ORDERED_COLLECTION structure.
 152
 153   Read-write operation.
 154
 155   It is the caller's responsibility to delete all entries from the collection
 156   before calling this function.
 157
 158   @param[in] Collection  The empty collection to uninitialize and release.
 159 **/
 160 VOID
 161 EFIAPI
 162 OrderedCollectionUninit (
 163   IN ORDERED_COLLECTION  *Collection
 164   );
 165
 166 /**
 167   Look up the collection entry that links the user structure that matches the
 168   specified standalone key.
 169
 170   Read-only operation.
 171
 172   @param[in] Collection     The collection to search for StandaloneKey.
 173
 174   @param[in] StandaloneKey  The key to locate among the user structures linked
 175                             into Collection. StandaloneKey will be passed to
 176                             ORDERED_COLLECTION_KEY_COMPARE.
 177
 178   @retval NULL  StandaloneKey could not be found.
 179
 180   @return       The collection entry that links to the user structure matching
 181                 StandaloneKey, otherwise.
 182 **/
 183 ORDERED_COLLECTION_ENTRY *
 184 EFIAPI
 185 OrderedCollectionFind (
 186   IN CONST ORDERED_COLLECTION  *Collection,
 187   IN CONST VOID                *StandaloneKey
 188   );
 189
 190 /**
 191   Find the collection entry of the minimum user structure stored in the
 192   collection.
 193
 194   Read-only operation.
 195
 196   @param[in] Collection  The collection to return the minimum entry of. The
 197                          user structure linked by the minimum entry compares
 198                          less than all other user structures in the collection.
 199
 200   @retval NULL  If Collection is empty.
 201
 202   @return       The collection entry that links the minimum user structure,
 203                 otherwise.
 204 **/
 205 ORDERED_COLLECTION_ENTRY *
 206 EFIAPI
 207 OrderedCollectionMin (
 208   IN CONST ORDERED_COLLECTION  *Collection
 209   );
 210
 211 /**
 212   Find the collection entry of the maximum user structure stored in the
 213   collection.
 214
 215   Read-only operation.
 216
 217   @param[in] Collection  The collection to return the maximum entry of. The
 218                          user structure linked by the maximum entry compares
 219                          greater than all other user structures in the
 220                          collection.
 221
 222   @retval NULL  If Collection is empty.
 223
 224   @return       The collection entry that links the maximum user structure,
 225                 otherwise.
 226 **/
 227 ORDERED_COLLECTION_ENTRY *
 228 EFIAPI
 229 OrderedCollectionMax (
 230   IN CONST ORDERED_COLLECTION  *Collection
 231   );
 232
 233 /**
 234   Get the collection entry of the least user structure that is greater than the
 235   one linked by Entry.
 236
 237   Read-only operation.
 238
 239   @param[in] Entry  The entry to get the successor entry of.
 240
 241   @retval NULL  If Entry is NULL, or Entry is the maximum entry of its
 242                 containing collection (ie. Entry has no successor entry).
 243
 244   @return       The collection entry linking the least user structure that is
 245                 greater than the one linked by Entry, otherwise.
 246 **/
 247 ORDERED_COLLECTION_ENTRY *
 248 EFIAPI
 249 OrderedCollectionNext (
 250   IN CONST ORDERED_COLLECTION_ENTRY  *Entry
 251   );
 252
 253 /**
 254   Get the collection entry of the greatest user structure that is less than the
 255   one linked by Entry.
 256
 257   Read-only operation.
 258
 259   @param[in] Entry  The entry to get the predecessor entry of.
 260
 261   @retval NULL  If Entry is NULL, or Entry is the minimum entry of its
 262                 containing collection (ie. Entry has no predecessor entry).
 263
 264   @return       The collection entry linking the greatest user structure that
 265                 is less than the one linked by Entry, otherwise.
 266 **/
 267 ORDERED_COLLECTION_ENTRY *
 268 EFIAPI
 269 OrderedCollectionPrev (
 270   IN CONST ORDERED_COLLECTION_ENTRY  *Entry
 271   );
 272
 273 /**
 274   Insert (link) a user structure into the collection, allocating a new
 275   collection entry.
 276
 277   Read-write operation.
 278
 279   @param[in,out] Collection  The collection to insert UserStruct into.
 280
 281   @param[out]    Entry       The meaning of this optional, output-only
 282                              parameter depends on the return value of the
 283                              function.
 284
 285                              When insertion is successful (RETURN_SUCCESS),
 286                              Entry is set on output to the new collection entry
 287                              that now links UserStruct.
 288
 289                              When insertion fails due to lack of memory
 290                              (RETURN_OUT_OF_RESOURCES), Entry is not changed.
 291
 292                              When insertion fails due to key collision (ie.
 293                              another user structure is already in the
 294                              collection that compares equal to UserStruct),
 295                              with return value RETURN_ALREADY_STARTED, then
 296                              Entry is set on output to the entry that links the
 297                              colliding user structure. This enables
 298                              "find-or-insert" in one function call, or helps
 299                              with later removal of the colliding element.
 300
 301   @param[in]     UserStruct  The user structure to link into the collection.
 302                              UserStruct is ordered against in-collection user
 303                              structures with the
 304                              ORDERED_COLLECTION_USER_COMPARE function.
 305
 306   @retval RETURN_SUCCESS           Insertion successful. A new collection entry
 307                                    has been allocated, linking UserStruct. The
 308                                    new collection entry is reported back in
 309                                    Entry (if the caller requested it).
 310
 311                                    Existing ORDERED_COLLECTION_ENTRY pointers
 312                                    into Collection remain valid. For example,
 313                                    on-going iterations in the caller can
 314                                    continue with OrderedCollectionNext() /
 315                                    OrderedCollectionPrev(), and they will
 316                                    return the new entry at some point if user
 317                                    structure order dictates it.
 318
 319   @retval RETURN_OUT_OF_RESOURCES  The function failed to allocate memory for
 320                                    the new collection entry. The collection has
 321                                    not been changed. Existing
 322                                    ORDERED_COLLECTION_ENTRY pointers into
 323                                    Collection remain valid.
 324
 325   @retval RETURN_ALREADY_STARTED   A user structure has been found in the
 326                                    collection that compares equal to
 327                                    UserStruct. The entry linking the colliding
 328                                    user structure is reported back in Entry (if
 329                                    the caller requested it). The collection has
 330                                    not been changed. Existing
 331                                    ORDERED_COLLECTION_ENTRY pointers into
 332                                    Collection remain valid.
 333 **/
 334 RETURN_STATUS
 335 EFIAPI
 336 OrderedCollectionInsert (
 337   IN OUT ORDERED_COLLECTION        *Collection,
 338   OUT    ORDERED_COLLECTION_ENTRY  **Entry      OPTIONAL,
 339   IN     VOID                      *UserStruct
 340   );
 341
 342 /**
 343   Delete an entry from the collection, unlinking the associated user structure.
 344
 345   Read-write operation.
 346
 347   @param[in,out] Collection  The collection to delete Entry from.
 348
 349   @param[in]     Entry       The collection entry to delete from Collection.
 350                              The caller is responsible for ensuring that Entry
 351                              belongs to Collection, and that Entry is non-NULL
 352                              and valid. Entry is typically an earlier return
 353                              value, or output parameter, of:
 354
 355                              - OrderedCollectionFind(), for deleting an entry
 356                                by user structure key,
 357
 358                              - OrderedCollectionMin() / OrderedCollectionMax(),
 359                                for deleting the minimum / maximum entry,
 360
 361                              - OrderedCollectionNext() /
 362                                OrderedCollectionPrev(), for deleting an entry
 363                                found during an iteration,
 364
 365                              - OrderedCollectionInsert() with return value
 366                                RETURN_ALREADY_STARTED, for deleting an entry
 367                                whose linked user structure caused collision
 368                                during insertion.
 369
 370                              Existing ORDERED_COLLECTION_ENTRY pointers (ie.
 371                              iterators) *different* from Entry remain valid.
 372                              For example:
 373
 374                              - OrderedCollectionNext() /
 375                                OrderedCollectionPrev() iterations in the caller
 376                                can be continued from Entry, if
 377                                OrderedCollectionNext() or
 378                                OrderedCollectionPrev() is called on Entry
 379                                *before* OrderedCollectionDelete() is. That is,
 380                                fetch the successor / predecessor entry first,
 381                                then delete Entry.
 382
 383                              - On-going iterations in the caller that would
 384                                have otherwise returned Entry at some point, as
 385                                dictated by user structure order, will correctly
 386                                reflect the absence of Entry after
 387                                OrderedCollectionDelete() is called
 388                                mid-iteration.
 389
 390   @param[out]    UserStruct  If the caller provides this optional output-only
 391                              parameter, then on output it is set to the user
 392                              structure originally linked by Entry (which is now
 393                              freed).
 394
 395                              This is a convenience that may save the caller a
 396                              OrderedCollectionUserStruct() invocation before
 397                              calling OrderedCollectionDelete(), in order to
 398                              retrieve the user structure being unlinked.
 399 **/
 400 VOID
 401 EFIAPI
 402 OrderedCollectionDelete (
 403   IN OUT ORDERED_COLLECTION        *Collection,
 404   IN     ORDERED_COLLECTION_ENTRY  *Entry,
 405   OUT    VOID                      **UserStruct OPTIONAL
 406   );
 407
 408 #endif