MdePkg/Include/Library/OrderedCollectionLib.h

/** @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.

  This program and the accompanying materials are licensed and made available
  under the terms and conditions of the BSD License that accompanies this
  distribution. The full text of the license may be found at
  http://opensource.org/licenses/bsd-license.php.

  THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
  WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
**/

#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