diff --git a/MdePkg/Include/Library/OrderedCollectionLib.h b/MdePkg/Include/Library/OrderedCollectionLib.h
new file mode 100644
index 0000000..81d63ce
--- /dev/null
+++ b/MdePkg/Include/Library/OrderedCollectionLib.h
@@ -0,0 +1,443 @@
+/** @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 a 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 a entry by
+                               user structure key,
+
+                             - OrderedCollectionMin() / OrderedCollectionMax(),
+                               for deleting the minimum / maximum entry,
+
+                             - OrderedCollectionNext() /
+                               OrderedCollectionPrev(), for deleting a entry
+                               found during an iteration,
+
+                             - OrderedCollectionInsert() with return value
+                               RETURN_ALREADY_STARTED, for deleting a 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
+  );
+
+
+/**
+  A potentially slow function that asserts that the collection satisfies its
+  internal defining properties, and that it orders user structures correctly.
+
+  Read-only operation.
+
+  This function might use the stack for recursion and is not recommended for
+  "production use".
+
+  @param[in] Collection  The collection to validate.
+**/
+VOID
+EFIAPI
+OrderedCollectionValidate (
+  IN CONST ORDERED_COLLECTION *Collection
+  );
+
+#endif
diff --git a/MdePkg/MdePkg.dec b/MdePkg/MdePkg.dec
index 4daf3e6..63ffb51 100644
--- a/MdePkg/MdePkg.dec
+++ b/MdePkg/MdePkg.dec
@@ -100,6 +100,9 @@
   ##
   PrintLib|Include/Library/PrintLib.h
 
+  ##  @libraryclass  Provides an ordered collection data structure.
+  OrderedCollectionLib|Include/Library/OrderedCollectionLib.h
+
   ##  @libraryclass  Provides services to send progress/error codes to a POST card.
   PostCodeLib|Include/Library/PostCodeLib.h
 
