From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail.byosoft.com.cn (mail.byosoft.com.cn [58.240.74.242]) by mx.groups.io with SMTP id smtpd.web12.5956.1633915262569042943 for ; Sun, 10 Oct 2021 18:21:03 -0700 Authentication-Results: mx.groups.io; dkim=missing; spf=none, err=permanent DNS error (domain: byosoft.com.cn, ip: 58.240.74.242, mailfrom: gaoliming@byosoft.com.cn) Received: from DESKTOPS6D0PVI ([58.246.60.130]) (envelope-sender ) by 192.168.6.13 with ESMTP for ; Mon, 11 Oct 2021 09:21:00 +0800 X-WM-Sender: gaoliming@byosoft.com.cn X-Originating-IP: 58.246.60.130 X-WM-AuthFlag: YES X-WM-AuthUser: gaoliming@byosoft.com.cn From: "gaoliming" To: =?UTF-8?Q?'Marvin_H=C3=A4user'?= , , , "'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> <6895b571-c067-c9ac-c0ed-42f6a793b43c@posteo.de> In-Reply-To: <6895b571-c067-c9ac-c0ed-42f6a793b43c@posteo.de> Subject: =?UTF-8?B?5Zue5aSNOiBbZWRrMi1kZXZlbF0gW1BBVENIIHY3IDEvMV0gTWRlUGtnL0Jhc2VMaWI6IEFkZCBRdWlja1NvcnQgZnVuY3Rpb24gb24gQmFzZUxpYg==?= Date: Mon, 11 Oct 2021 09:21:00 +0800 Message-ID: <006501d7be3e$40420fc0$c0c62f40$@byosoft.com.cn> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AQGgeeG31re1u3l8E3F70CJyBeItRAHV98JgArWWMiMCG8TlKgNB6/neq+w8bGA= Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Content-Language: zh-cn Michael and Marvin: I understand your concern. I want to reduce the duplicated definition for= the same function. I will not keep my idea if you are both OK to define BA= SE_SORT_COMPARE and SORT_COMPARE.=20 Thanks Liming > -----=E9=82=AE=E4=BB=B6=E5=8E=9F=E4=BB=B6----- > =E5=8F=91=E4=BB=B6=E4=BA=BA: Marvin H=C3=A4user > =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2021=E5=B9=B410=E6=9C=889=E6=97=A5 = 0:09 > =E6=94=B6=E4=BB=B6=E4=BA=BA: devel@edk2.groups.io; michael.d.kinney@intel= .com; > gaoliming@byosoft.com.cn; Kuo, IanX > =E6=8A=84=E9=80=81: Chan, Amy ; Ni, Ray ; Liu, > Zhiguang > =E4=B8=BB=E9=A2=98: Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add Q= uickSort > function on BaseLib >=20 > Hey all, >=20 > I also don't think it makes much logical sense. They are distinct APIs > in separate libraries that happen to take a function with the same > prototype. >=20 > I think the patches look good now, thanks! >=20 > Best regards, > Marvin >=20 > 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= another > 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/BaseLi= b: 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 Q= uickSort > 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 sorti= ng > >> 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 sorte= d) > >>> 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 = are > >> 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 sorti= ng > >> 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 sorte= d) > >>> 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 + ((LoopCoun= t) > * > >>> 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= .
> >>> > >>> +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved= .
> >>> > >>> # Portions copyright (c) 2008 - 2009, Apple Inc. All rights > >> reserved.
> >>> # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights > reserved.
> >>> > >>> # 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/81615 > >>> 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 > > > >