From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mout02.posteo.de (mout02.posteo.de [185.67.36.66]) by mx.groups.io with SMTP id smtpd.web10.11529.1633709360569925848 for ; Fri, 08 Oct 2021 09:09:21 -0700 Authentication-Results: mx.groups.io; dkim=fail reason="body hash did not verify" header.i=@posteo.de header.s=2017 header.b=LAs61VMJ; spf=pass (domain: posteo.de, ip: 185.67.36.66, mailfrom: mhaeuser@posteo.de) Received: from submission (posteo.de [89.146.220.130]) by mout02.posteo.de (Postfix) with ESMTPS id 6017424010A for ; Fri, 8 Oct 2021 18:09:17 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.de; s=2017; t=1633709357; bh=uKKMptrhufdWXjhFr+CCxkvJ+ZvKLKx/m2ww5IcHSMQ=; h=Date:Subject:To:Cc:From:From; b=LAs61VMJSLbRz2G4jKlZ58p5kqbDHqVcDy+IeHxr6k3O44Zay6jeBvBZwepQYbK9m WsKBsCfU2F8dANCW9Ce+8+6o4f0KlYBY9BZF5wnu0aSwkYuxeh+ZYYN2h3gM7iHdFl 4TsiYaDaabIQB48JPT2ZYi+3CpuSwH5zrHYJtRKX3DgXdGAenVuV3pOUrJWHQFfoiS WZK+EUn+a3Vlkgb6H56s/ZQAXQZsbMkY7Wsd5podP3H82ngKR6IaladAiwd5UcX+Mj B2ji94YlzFDh5LsVD19gIBU7+vJhRqJg6nEenj/69bGoRZ6wR6S9zm57PzlBnG7BvV HNGw8KC697jgA== Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4HQtRb1rN0z9rxQ; Fri, 8 Oct 2021 18:09:14 +0200 (CEST) Message-ID: <6895b571-c067-c9ac-c0ed-42f6a793b43c@posteo.de> Date: Fri, 8 Oct 2021 16:09:14 +0000 MIME-Version: 1.0 Subject: Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib To: devel@edk2.groups.io, michael.d.kinney@intel.com, "gaoliming@byosoft.com.cn" , "Kuo, IanX" Cc: "Chan, Amy" , "Ni, Ray" , "Liu, Zhiguang" References: <20211008002710.763-1-ianx.kuo@intel.com> <20211008002710.763-2-ianx.kuo@intel.com> <006601d7bbea$69db2570$3d917050$@byosoft.com.cn> From: =?UTF-8?B?TWFydmluIEjDpHVzZXI=?= In-Reply-To: Content-Language: en-GB Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: quoted-printable Hey all, I also don't think it makes much logical sense. They are distinct APIs=20 in separate libraries that happen to take a function with the same=20 prototype. I think the patches look good now, thanks! Best regards, Marvin On 08/10/2021 17:46, Michael D Kinney wrote: > Hi Liming, > > In general it is not a good idea to include a library include file from a= nother library include file. > > This becomes a hidden dependency. > > Mike > >> -----Original Message----- >> From: devel@edk2.groups.io On Behalf Of gaoliming >> Sent: Thursday, October 7, 2021 7:16 PM >> To: devel@edk2.groups.io; Kuo, IanX >> Cc: Chan, Amy ; Ni, Ray ; Kinney, = Michael D ; Liu, >> Zhiguang >> Subject: =E5=9B=9E=E5=A4=8D: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib:= Add QuickSort function on BaseLib >> >> Kuo: >> I suggest to move SORT_COMPARE definition from >> MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib= .h, >> and then let SortLib.h include BaseLib.h. >> >> Thanks >> Liming >>> -----=E9=82=AE=E4=BB=B6=E5=8E=9F=E4=BB=B6----- >>> =E5=8F=91=E4=BB=B6=E4=BA=BA: devel@edk2.groups.io =E4=BB=A3=E8=A1=A8 IanX Kuo >>> =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2021=E5=B9=B410=E6=9C=888=E6=97= =A5 8:27 >>> =E6=94=B6=E4=BB=B6=E4=BA=BA: devel@edk2.groups.io >>> =E6=8A=84=E9=80=81: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo >>> ; Michael D Kinney ; >>> Liming Gao ; Zhiguang Liu >>> >>> =E4=B8=BB=E9=A2=98: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add Qui= ckSort function >>> on BaseLib >>> >>> From: IanX Kuo >>> >>> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675 >>> >>> Add QuickSort function into BaseLib >>> >>> Cc: Ray Ni >>> Cc: Michael D Kinney >>> Cc: Liming Gao >>> Cc: Zhiguang Liu >>> Signed-off-by: IanX Kuo >>> --- >>> MdePkg/Include/Library/BaseLib.h | 49 ++++++++ >>> MdePkg/Library/BaseLib/BaseLib.inf | 1 + >>> MdePkg/Library/BaseLib/QuickSort.c | 116 >>> ++++++++++++++++++ >>> .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +- >>> 4 files changed, 168 insertions(+), 1 deletion(-) >>> create mode 100644 MdePkg/Library/BaseLib/QuickSort.c >>> >>> diff --git a/MdePkg/Include/Library/BaseLib.h >>> b/MdePkg/Include/Library/BaseLib.h >>> index 2452c1d92e..0ae0f4e6af 100644 >>> --- a/MdePkg/Include/Library/BaseLib.h >>> +++ b/MdePkg/Include/Library/BaseLib.h >>> @@ -2856,6 +2856,55 @@ RemoveEntryList ( >>> // >>> >>> // Math Services >>> >>> // >>> >>> +/** >>> >>> + Prototype for comparison function for any two element types. >>> >>> + >>> >>> + @param[in] Buffer1 The pointer to first buffer. >>> >>> + @param[in] Buffer2 The pointer to second buffer. >>> >>> + >>> >>> + @retval 0 Buffer1 equal to Buffer2. >>> >>> + @return <0 Buffer1 is less than Buffer2. >>> >>> + @return >0 Buffer1 is greater than >>> Buffer2. >>> >>> +**/ >>> >>> +typedef >>> >>> +INTN >>> >>> +(EFIAPI *BASE_SORT_COMPARE)( >>> >>> + IN CONST VOID *Buffer1, >>> >>> + IN CONST VOID *Buffer2 >>> >>> + ); >>> >>> + >>> >>> +/** >>> >>> + This function is identical to perform QuickSort, >>> >>> + except that is uses the pre-allocated buffer so the in place sorting >> does not >>> need to >>> >>> + allocate and free buffers constantly. >>> >>> + >>> >>> + Each element must be equal sized. >>> >>> + >>> >>> + if BufferToSort is NULL, then ASSERT. >>> >>> + if CompareFunction is NULL, then ASSERT. >>> >>> + if BufferOneElement is NULL, then ASSERT. >>> >>> + if ElementSize is < 1, then ASSERT. >>> >>> + >>> >>> + if Count is < 2 then perform no action. >>> >>> + >>> >>> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted) >>> elements >>> >>> + on return a buffer of sorted >>> elements >>> >>> + @param[in] Count the number of elements in the >>> buffer to sort >>> >>> + @param[in] ElementSize Size of an element in bytes >>> >>> + @param[in] CompareFunction The function to call to perform the >>> comparison >>> >>> + of any 2 elements >>> >>> + @param[out] BufferOneElement Caller provided buffer whose size >>> equals to ElementSize. >>> >>> + It's used by QuickSort() for >>> swapping in sorting. >>> >>> +**/ >>> >>> +VOID >>> >>> +EFIAPI >>> >>> +QuickSort ( >>> >>> + IN OUT VOID *BufferToSort, >>> >>> + IN CONST UINTN Count, >>> >>> + IN CONST UINTN ElementSize, >>> >>> + IN BASE_SORT_COMPARE CompareFunction, >>> >>> + OUT VOID *BufferOneElement >>> >>> + ); >>> >>> >>> >>> /** >>> >>> Shifts a 64-bit integer left between 0 and 63 bits. The low bits ar= e >> filled >>> diff --git a/MdePkg/Library/BaseLib/BaseLib.inf >>> b/MdePkg/Library/BaseLib/BaseLib.inf >>> index 6efa5315b6..cebda3b210 100644 >>> --- a/MdePkg/Library/BaseLib/BaseLib.inf >>> +++ b/MdePkg/Library/BaseLib/BaseLib.inf >>> @@ -32,6 +32,7 @@ >>> SwapBytes16.c >>> >>> LongJump.c >>> >>> SetJump.c >>> >>> + QuickSort.c >>> >>> RShiftU64.c >>> >>> RRotU64.c >>> >>> RRotU32.c >>> >>> diff --git a/MdePkg/Library/BaseLib/QuickSort.c >>> b/MdePkg/Library/BaseLib/QuickSort.c >>> new file mode 100644 >>> index 0000000000..a825c072b0 >>> --- /dev/null >>> +++ b/MdePkg/Library/BaseLib/QuickSort.c >>> @@ -0,0 +1,116 @@ >>> +/** @file >>> >>> + Math worker functions. >>> >>> + >>> >>> + Copyright (c) 2021, Intel Corporation. All rights reserved.
>>> >>> + SPDX-License-Identifier: BSD-2-Clause-Patent >>> >>> + >>> >>> +**/ >>> >>> + >>> >>> +#include "BaseLibInternals.h" >>> >>> + >>> >>> +/** >>> >>> + This function is identical to perform QuickSort, >>> >>> + except that is uses the pre-allocated buffer so the in place sorting >> does not >>> need to >>> >>> + allocate and free buffers constantly. >>> >>> + >>> >>> + Each element must be equal sized. >>> >>> + >>> >>> + if BufferToSort is NULL, then ASSERT. >>> >>> + if CompareFunction is NULL, then ASSERT. >>> >>> + if BufferOneElement is NULL, then ASSERT. >>> >>> + if ElementSize is < 1, then ASSERT. >>> >>> + >>> >>> + if Count is < 2 then perform no action. >>> >>> + >>> >>> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted) >>> elements >>> >>> + on return a buffer of sorted >>> elements >>> >>> + @param[in] Count the number of elements in the >>> buffer to sort >>> >>> + @param[in] ElementSize Size of an element in bytes >>> >>> + @param[in] CompareFunction The function to call to perform the >>> comparison >>> >>> + of any 2 elements >>> >>> + @param[out] BufferOneElement Caller provided buffer whose size >>> equals to ElementSize. >>> >>> + It's used by QuickSort() for >>> swapping in sorting. >>> >>> +**/ >>> >>> +VOID >>> >>> +EFIAPI >>> >>> +QuickSort ( >>> >>> + IN OUT VOID *BufferToSort, >>> >>> + IN CONST UINTN Count, >>> >>> + IN CONST UINTN ElementSize, >>> >>> + IN BASE_SORT_COMPARE CompareFunction, >>> >>> + OUT VOID *BufferOneElement >>> >>> + ) >>> >>> +{ >>> >>> + VOID *Pivot; >>> >>> + UINTN LoopCount; >>> >>> + UINTN NextSwapLocation; >>> >>> + >>> >>> + ASSERT (BufferToSort !=3D NULL); >>> >>> + ASSERT (CompareFunction !=3D NULL); >>> >>> + ASSERT (BufferOneElement !=3D NULL); >>> >>> + ASSERT (ElementSize >=3D 1); >>> >>> + >>> >>> + if (Count < 2) { >>> >>> + return; >>> >>> + } >>> >>> + >>> >>> + NextSwapLocation =3D 0; >>> >>> + >>> >>> + // >>> >>> + // pick a pivot (we choose last element) >>> >>> + // >>> >>> + Pivot =3D ((UINT8*) BufferToSort + ((Count - 1) * ElementSize)); >>> >>> + >>> >>> + // >>> >>> + // Now get the pivot such that all on "left" are below it >>> >>> + // and everything "right" are above it >>> >>> + // >>> >>> + for (LoopCount =3D 0; LoopCount < Count -1; LoopCount++) { >>> >>> + // >>> >>> + // if the element is less than or equal to the pivot >>> >>> + // >>> >>> + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount)= * >>> ElementSize)), Pivot) <=3D 0){ >>> >>> + // >>> >>> + // swap >>> >>> + // >>> >>> + CopyMem (BufferOneElement, (UINT8*) BufferToSort + >>> (NextSwapLocation * ElementSize), ElementSize); >>> >>> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * >>> ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), >>> ElementSize); >>> >>> + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), >>> BufferOneElement, ElementSize); >>> >>> + >>> >>> + // >>> >>> + // increment NextSwapLocation >>> >>> + // >>> >>> + NextSwapLocation++; >>> >>> + } >>> >>> + } >>> >>> + // >>> >>> + // swap pivot to it's final position (NextSwapLocation) >>> >>> + // >>> >>> + CopyMem (BufferOneElement, Pivot, ElementSize); >>> >>> + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * >>> ElementSize), ElementSize); >>> >>> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), >>> BufferOneElement, ElementSize); >>> >>> + >>> >>> + // >>> >>> + // Now recurse on 2 partial lists. neither of these will have the >> 'pivot' >>> element >>> >>> + // IE list is sorted left half, pivot element, sorted right half... >>> >>> + // >>> >>> + if (NextSwapLocation >=3D 2) { >>> >>> + QuickSort ( >>> >>> + BufferToSort, >>> >>> + NextSwapLocation, >>> >>> + ElementSize, >>> >>> + CompareFunction, >>> >>> + BufferOneElement >>> >>> + ); >>> >>> + } >>> >>> + >>> >>> + if ((Count - NextSwapLocation - 1) >=3D 2) { >>> >>> + QuickSort ( >>> >>> + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize, >>> >>> + Count - NextSwapLocation - 1, >>> >>> + ElementSize, >>> >>> + CompareFunction, >>> >>> + BufferOneElement >>> >>> + ); >>> >>> + } >>> >>> +} >>> >>> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf >>> b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf >>> index eae1a7158d..d09bd12bef 100644 >>> --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf >>> +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf >>> @@ -1,7 +1,7 @@ >>> ## @file >>> >>> # Base Library implementation for use with host based unit tests. >>> >>> # >>> >>> -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<= BR> >>> >>> +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<= BR> >>> >>> # Portions copyright (c) 2008 - 2009, Apple Inc. All rights >> reserved.
>>> # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<= BR> >>> >>> # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All >>> rights reserved.
>>> >>> @@ -33,6 +33,7 @@ >>> SwapBytes16.c >>> >>> LongJump.c >>> >>> SetJump.c >>> >>> + QuickSort.c >>> >>> RShiftU64.c >>> >>> RRotU64.c >>> >>> RRotU32.c >>> >>> -- >>> 2.30.0.windows.1 >>> >>> >>> >>> -=3D-=3D-=3D-=3D-=3D-=3D >>> Groups.io Links: You receive all messages sent to this group. >>> View/Reply Online (#81615): https://edk2.groups.io/g/devel/message/8161= 5 >>> Mute This Topic: https://groups.io/mt/86159728/4905953 >>> Group Owner: devel+owner@edk2.groups.io >>> Unsubscribe: https://edk2.groups.io/g/devel/unsub >>> [gaoliming@byosoft.com.cn] >>> -=3D-=3D-=3D-=3D-=3D-=3D >>> >> >> >> >> >> >> > > >=20 > >