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.web09.1916.1634087065560976099 for ; Tue, 12 Oct 2021 18:04:27 -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 ; Wed, 13 Oct 2021 09:04:21 +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: "'Kuo, IanX'" , "'Ni, Ray'" , , "'Kinney, Michael D'" Cc: "'Chan, Amy'" , "'Liu, Zhiguang'" References: <20211012000531.361-1-ianx.kuo@intel.com> <20211012000531.361-2-ianx.kuo@intel.com> In-Reply-To: Subject: =?UTF-8?B?5Zue5aSNOiBbUEFUQ0ggdjkgMS8xXSBNZGVQa2cvQmFzZUxpYjogQWRkIFF1aWNrU29ydCBmdW5jdGlvbiBvbiBCYXNlTGli?= Date: Wed, 13 Oct 2021 09:04:21 +0800 Message-ID: <000701d7bfce$41a6af10$c4f40d30$@byosoft.com.cn> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AQKAaA0zeN94CNhyZgQI7dSnsc+u+QGBTylAAiCwsfcCpPR5GKpMlKOQ Content-Type: text/plain; charset="gb2312" Content-Transfer-Encoding: quoted-printable Content-Language: zh-cn I have no other comments. Reviewed-by: Liming Gao = > -----=D3=CA=BC=FE=D4=AD=BC=FE----- > =B7=A2=BC=FE=C8=CB: Kuo, IanX > =B7=A2=CB=CD=CA=B1=BC=E4: 2021=C4=EA10=D4=C212=C8=D5 11:51 > =CA=D5=BC=FE=C8=CB: Ni, Ray ; devel@edk2.groups.io; = Kinney, Michael > D ; Liming Gao > =B3=AD=CB=CD: Chan, Amy ; Liu, Zhiguang > > =D6=F7=CC=E2: RE: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort = function on > BaseLib >=20 > @Liming Gao and @Kinney, Michael D >=20 > May I get one of yours help for the reviewed from MdePkg maintainer = side ? > Have any concern, please also share for me. >=20 > Thanks, > Ian Kuo >=20 > -----Original Message----- > From: Ni, Ray > Sent: Tuesday, October 12, 2021 10:22 AM > To: Kuo, IanX ; devel@edk2.groups.io > Cc: Chan, Amy ; Kinney, Michael D > ; Liming Gao ; = Liu, > Zhiguang > Subject: RE: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort function on > BaseLib >=20 > Reviewed-by: Ray Ni >=20 > Ian, please take the approval from maintainers of MdePkg as the formal > approval. >=20 > Thanks, > Ray >=20 > > -----Original Message----- > > From: Kuo, IanX > > Sent: Tuesday, October 12, 2021 8:06 AM > > To: devel@edk2.groups.io > > Cc: Chan, Amy ; Ni, Ray ; Kuo, > > IanX ; Kinney, Michael D > > ; Liming Gao ; > > Liu, Zhiguang > > Subject: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort 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 > > 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 > > + 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.
> > > > +# 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