From patchwork Tue Aug 5 02:12:01 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Laszlo Ersek X-Patchwork-Id: 34886 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-oa0-f72.google.com (mail-oa0-f72.google.com [209.85.219.72]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 7EF1D20F2E for ; Tue, 5 Aug 2014 02:12:30 +0000 (UTC) Received: by mail-oa0-f72.google.com with SMTP id m1sf1349758oag.3 for ; Mon, 04 Aug 2014 19:12:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:from:to:date:message-id:in-reply-to :references:subject:precedence:reply-to:list-id:list-unsubscribe :list-archive:list-post:list-help:list-subscribe:mime-version :errors-to:x-original-sender:x-original-authentication-results :mailing-list:content-type:content-transfer-encoding; bh=2jqGV99ZHP6iILkyrjE0mS8Said3OGdMP1Al7BP4bko=; b=EnhG8BkCzjWeyzMUXVEWEHnn8zxDUllcbAMatlzOypNblw6N3TKk43cIBhbVJYCtsb Gr3DDLFZyzUCzT9BHpakipyxzkjnDhSksTFKcEcZvYW4Nv+I3m2PTGMfxE4C3CjGXe42 akn/0VRvKBoperKstlUJfGEzI73DrvhiMoB2sry+EHH7Q5UXwFINTGVbtr/2/FVbpy5E tRt/QCDfCGJzDrJtfJ+NHqGfYpBIP9ZPK8Rg4VCR0B7t5KafpHbd5iEXS3A/irusf8/d h20Oh1eTeUuc4cnGXTaL2i62FspGMQpebLQjek8DDtdX2oTSYuisemUyj1sIkP3Y61Lq oLLw== X-Gm-Message-State: ALoCoQmhFnmhkupoW0uOxZZDvNeqoOWr+jiVdzXLUt4jbaQfqHF/vQI9Xk1Y6LfZbUvljzP4BGhf X-Received: by 10.182.125.37 with SMTP id mn5mr171272obb.49.1407204750168; Mon, 04 Aug 2014 19:12:30 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.140.94.236 with SMTP id g99ls87146qge.17.gmail; Mon, 04 Aug 2014 19:12:30 -0700 (PDT) X-Received: by 10.220.68.140 with SMTP id v12mr541008vci.13.1407204750066; Mon, 04 Aug 2014 19:12:30 -0700 (PDT) Received: from mail-vc0-f174.google.com (mail-vc0-f174.google.com [209.85.220.174]) by mx.google.com with ESMTPS id rm4si194710vcb.95.2014.08.04.19.12.30 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 04 Aug 2014 19:12:30 -0700 (PDT) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.220.174 as permitted sender) client-ip=209.85.220.174; Received: by mail-vc0-f174.google.com with SMTP id la4so459403vcb.5 for ; Mon, 04 Aug 2014 19:12:30 -0700 (PDT) X-Received: by 10.221.42.135 with SMTP id ty7mr663684vcb.14.1407204749947; Mon, 04 Aug 2014 19:12:29 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.221.37.5 with SMTP id tc5csp348419vcb; Mon, 4 Aug 2014 19:12:29 -0700 (PDT) X-Received: by 10.42.82.6 with SMTP id b6mr1495669icl.51.1407204749026; Mon, 04 Aug 2014 19:12:29 -0700 (PDT) Received: from lists.sourceforge.net (lists.sourceforge.net. [216.34.181.88]) by mx.google.com with ESMTPS id z10si713926igm.16.2014.08.04.19.12.28 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Mon, 04 Aug 2014 19:12:29 -0700 (PDT) Received-SPF: pass (google.com: domain of edk2-devel-bounces@lists.sourceforge.net designates 216.34.181.88 as permitted sender) client-ip=216.34.181.88; Received: from localhost ([127.0.0.1] helo=sfs-ml-1.v29.ch3.sourceforge.com) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1XEUEe-0001cM-9J; Tue, 05 Aug 2014 02:12:20 +0000 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1XEUEb-0001cA-RF for edk2-devel@lists.sourceforge.net; Tue, 05 Aug 2014 02:12:18 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of redhat.com designates 209.132.183.28 as permitted sender) client-ip=209.132.183.28; envelope-from=lersek@redhat.com; helo=mx1.redhat.com; Received: from mx1.redhat.com ([209.132.183.28]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:AES256-SHA:256) (Exim 4.76) id 1XEUEZ-0006kJ-2k for edk2-devel@lists.sourceforge.net; Tue, 05 Aug 2014 02:12:17 +0000 Received: from int-mx13.intmail.prod.int.phx2.redhat.com (int-mx13.intmail.prod.int.phx2.redhat.com [10.5.11.26]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s752C8FA002681 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Mon, 4 Aug 2014 22:12:08 -0400 Received: from lacos-laptop-7.usersys.redhat.com (ovpn-116-31.ams2.redhat.com [10.36.116.31]) by int-mx13.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id s752C5Il005360 for ; Mon, 4 Aug 2014 22:12:07 -0400 From: Laszlo Ersek To: edk2-devel@lists.sourceforge.net Date: Tue, 5 Aug 2014 04:12:01 +0200 Message-Id: <1407204723-16642-2-git-send-email-lersek@redhat.com> In-Reply-To: <1407204723-16642-1-git-send-email-lersek@redhat.com> References: <1407204723-16642-1-git-send-email-lersek@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.26 X-Spam-Score: -2.2 (--) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.0 SPF_PASS SPF: sender matches SPF record -0.7 RP_MATCHES_RCVD Envelope sender domain matches handover relay domain X-Headers-End: 1XEUEZ-0006kJ-2k Subject: [edk2] [PATCH v2 1/3] MdePkg: introduce OrderedCollectionLib library class X-BeenThere: edk2-devel@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list Reply-To: edk2-devel@lists.sourceforge.net List-Id: List-Unsubscribe: , List-Archive: List-Post: , List-Help: , List-Subscribe: , MIME-Version: 1.0 Errors-To: edk2-devel-bounces@lists.sourceforge.net X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: lersek@redhat.com X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.220.174 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 This library class provides a set of APIs to manage an ordered collection of items: - Init(), - UnInit(), - Insert(), - Delete(), - IsEmpty(), - Next(), - Prev(), - Min(), - Max(), - Find(), - UserStruct(), - Validate(). There are many ways to implement an ordered collection. Depending on the frequency of the different actions, different internal implementations may have different performance, memory overhead, or code size. Developers can select the library instance for a platform or module in their DSC files that meets the needs of that platform or module. Commit-message-from: "Kinney, Michael D" Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Laszlo Ersek --- Notes: v2: - Cease including which is not appropriate for a BASE library class; accordingly, replace EFI_STATUS type and values with RETURN_STATUS. [Mike] - Use generic terms in source code and file names [Mike]: - RbTreeLib -> OrderedCollectionLib - Node -> Entry - Tree -> Collection - RB_TREE -> ORDERED_COLLECTION - RB_TREE_NODE -> ORDERED_COLLECTION_ENTRY - RbTree*() -> OrderedCollection*() - Improve information hiding, and keep even ORDERED_COLLECTION internal to library instance. Slight change to Init() and Uninit() semantics; allocation is now internal to the library instance too. [Mike+Laszlo] - Drop references to time complexity, that's a property of the library instance. [Laszlo] - Drop references to MemoryAllocationLib, ditto. [Laszlo] - Introduce library class in separate patch. [Laszlo] MdePkg/Include/Library/OrderedCollectionLib.h | 443 ++++++++++++++++++++++++++ MdePkg/MdePkg.dec | 3 + 2 files changed, 446 insertions(+) create mode 100644 MdePkg/Include/Library/OrderedCollectionLib.h 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 + +// +// 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