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.web08.3652.1633659352769705393 for ; Thu, 07 Oct 2021 19:15:53 -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 ; Fri, 08 Oct 2021 10:15:48 +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: , Cc: , , "'Michael D Kinney'" , "'Zhiguang Liu'" References: <20211008002710.763-1-ianx.kuo@intel.com> <20211008002710.763-2-ianx.kuo@intel.com> In-Reply-To: <20211008002710.763-2-ianx.kuo@intel.com> Subject: =?UTF-8?B?5Zue5aSNOiBbZWRrMi1kZXZlbF0gW1BBVENIIHY3IDEvMV0gTWRlUGtnL0Jhc2VMaWI6IEFkZCBRdWlja1NvcnQgZnVuY3Rpb24gb24gQmFzZUxpYg==?= Date: Fri, 8 Oct 2021 10:15:50 +0800 Message-ID: <006601d7bbea$69db2570$3d917050$@byosoft.com.cn> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AQGgeeG31re1u3l8E3F70CJyBeItRAHV98JgrCgvu0A= Content-Type: text/plain; charset="gb2312" Content-Transfer-Encoding: quoted-printable Content-Language: zh-cn 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 > -----=D3=CA=BC=FE=D4=AD=BC=FE----- > =B7=A2=BC=FE=C8=CB: devel@edk2.groups.io = =B4=FA=B1=ED IanX Kuo > =B7=A2=CB=CD=CA=B1=BC=E4: 2021=C4=EA10=D4=C28=C8=D5 8:27 > =CA=D5=BC=FE=C8=CB: devel@edk2.groups.io > =B3=AD=CB=CD: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo > ; Michael D Kinney ; > Liming Gao ; Zhiguang Liu > > =D6=F7=CC=E2: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add = QuickSort function > on BaseLib >=20 > From: IanX Kuo >=20 > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675 >=20 > Add QuickSort function into BaseLib >=20 > 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 >=20 > 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 ( > // >=20 > // Math Services >=20 > // >=20 > +/** >=20 > + Prototype for comparison function for any two element types. >=20 > + >=20 > + @param[in] Buffer1 The pointer to first buffer. >=20 > + @param[in] Buffer2 The pointer to second buffer. >=20 > + >=20 > + @retval 0 Buffer1 equal to Buffer2. >=20 > + @return <0 Buffer1 is less than Buffer2. >=20 > + @return >0 Buffer1 is greater than > Buffer2. >=20 > +**/ >=20 > +typedef >=20 > +INTN >=20 > +(EFIAPI *BASE_SORT_COMPARE)( >=20 > + IN CONST VOID *Buffer1, >=20 > + IN CONST VOID *Buffer2 >=20 > + ); >=20 > + >=20 > +/** >=20 > + This function is identical to perform QuickSort, >=20 > + except that is uses the pre-allocated buffer so the in place = sorting does not > need to >=20 > + allocate and free buffers constantly. >=20 > + >=20 > + Each element must be equal sized. >=20 > + >=20 > + if BufferToSort is NULL, then ASSERT. >=20 > + if CompareFunction is NULL, then ASSERT. >=20 > + if BufferOneElement is NULL, then ASSERT. >=20 > + if ElementSize is < 1, then ASSERT. >=20 > + >=20 > + if Count is < 2 then perform no action. >=20 > + >=20 > + @param[in, out] BufferToSort on call a Buffer of (possibly = sorted) > elements >=20 > + on return a buffer of sorted > elements >=20 > + @param[in] Count the number of elements in the > buffer to sort >=20 > + @param[in] ElementSize Size of an element in bytes >=20 > + @param[in] CompareFunction The function to call to perform the > comparison >=20 > + of any 2 elements >=20 > + @param[out] BufferOneElement Caller provided buffer whose size > equals to ElementSize. >=20 > + It's used by QuickSort() for > swapping in sorting. >=20 > +**/ >=20 > +VOID >=20 > +EFIAPI >=20 > +QuickSort ( >=20 > + IN OUT VOID *BufferToSort, >=20 > + IN CONST UINTN Count, >=20 > + IN CONST UINTN ElementSize, >=20 > + IN BASE_SORT_COMPARE CompareFunction, >=20 > + OUT VOID *BufferOneElement >=20 > + ); >=20 >=20 >=20 > /** >=20 > Shifts a 64-bit integer left between 0 and 63 bits. The low bits = are filled >=20 > 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 >=20 > LongJump.c >=20 > SetJump.c >=20 > + QuickSort.c >=20 > RShiftU64.c >=20 > RRotU64.c >=20 > RRotU32.c >=20 > 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 >=20 > + Math worker functions. >=20 > + >=20 > + Copyright (c) 2021, Intel Corporation. All rights reserved.
>=20 > + SPDX-License-Identifier: BSD-2-Clause-Patent >=20 > + >=20 > +**/ >=20 > + >=20 > +#include "BaseLibInternals.h" >=20 > + >=20 > +/** >=20 > + This function is identical to perform QuickSort, >=20 > + except that is uses the pre-allocated buffer so the in place = sorting does not > need to >=20 > + allocate and free buffers constantly. >=20 > + >=20 > + Each element must be equal sized. >=20 > + >=20 > + if BufferToSort is NULL, then ASSERT. >=20 > + if CompareFunction is NULL, then ASSERT. >=20 > + if BufferOneElement is NULL, then ASSERT. >=20 > + if ElementSize is < 1, then ASSERT. >=20 > + >=20 > + if Count is < 2 then perform no action. >=20 > + >=20 > + @param[in, out] BufferToSort on call a Buffer of (possibly = sorted) > elements >=20 > + on return a buffer of sorted > elements >=20 > + @param[in] Count the number of elements in the > buffer to sort >=20 > + @param[in] ElementSize Size of an element in bytes >=20 > + @param[in] CompareFunction The function to call to perform the > comparison >=20 > + of any 2 elements >=20 > + @param[out] BufferOneElement Caller provided buffer whose size > equals to ElementSize. >=20 > + It's used by QuickSort() for > swapping in sorting. >=20 > +**/ >=20 > +VOID >=20 > +EFIAPI >=20 > +QuickSort ( >=20 > + IN OUT VOID *BufferToSort, >=20 > + IN CONST UINTN Count, >=20 > + IN CONST UINTN ElementSize, >=20 > + IN BASE_SORT_COMPARE CompareFunction, >=20 > + OUT VOID *BufferOneElement >=20 > + ) >=20 > +{ >=20 > + VOID *Pivot; >=20 > + UINTN LoopCount; >=20 > + UINTN NextSwapLocation; >=20 > + >=20 > + ASSERT (BufferToSort !=3D NULL); >=20 > + ASSERT (CompareFunction !=3D NULL); >=20 > + ASSERT (BufferOneElement !=3D NULL); >=20 > + ASSERT (ElementSize >=3D 1); >=20 > + >=20 > + if (Count < 2) { >=20 > + return; >=20 > + } >=20 > + >=20 > + NextSwapLocation =3D 0; >=20 > + >=20 > + // >=20 > + // pick a pivot (we choose last element) >=20 > + // >=20 > + Pivot =3D ((UINT8*) BufferToSort + ((Count - 1) * ElementSize)); >=20 > + >=20 > + // >=20 > + // Now get the pivot such that all on "left" are below it >=20 > + // and everything "right" are above it >=20 > + // >=20 > + for (LoopCount =3D 0; LoopCount < Count -1; LoopCount++) { >=20 > + // >=20 > + // if the element is less than or equal to the pivot >=20 > + // >=20 > + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + = ((LoopCount) * > ElementSize)), Pivot) <=3D 0){ >=20 > + // >=20 > + // swap >=20 > + // >=20 > + CopyMem (BufferOneElement, (UINT8*) BufferToSort + > (NextSwapLocation * ElementSize), ElementSize); >=20 > + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * > ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), > ElementSize); >=20 > + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), > BufferOneElement, ElementSize); >=20 > + >=20 > + // >=20 > + // increment NextSwapLocation >=20 > + // >=20 > + NextSwapLocation++; >=20 > + } >=20 > + } >=20 > + // >=20 > + // swap pivot to it's final position (NextSwapLocation) >=20 > + // >=20 > + CopyMem (BufferOneElement, Pivot, ElementSize); >=20 > + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * > ElementSize), ElementSize); >=20 > + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), > BufferOneElement, ElementSize); >=20 > + >=20 > + // >=20 > + // Now recurse on 2 partial lists. neither of these will have the 'pivot' > element >=20 > + // IE list is sorted left half, pivot element, sorted right half... >=20 > + // >=20 > + if (NextSwapLocation >=3D 2) { >=20 > + QuickSort ( >=20 > + BufferToSort, >=20 > + NextSwapLocation, >=20 > + ElementSize, >=20 > + CompareFunction, >=20 > + BufferOneElement >=20 > + ); >=20 > + } >=20 > + >=20 > + if ((Count - NextSwapLocation - 1) >=3D 2) { >=20 > + QuickSort ( >=20 > + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize, >=20 > + Count - NextSwapLocation - 1, >=20 > + ElementSize, >=20 > + CompareFunction, >=20 > + BufferOneElement >=20 > + ); >=20 > + } >=20 > +} >=20 > 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 >=20 > # Base Library implementation for use with host based unit tests. >=20 > # >=20 > -# Copyright (c) 2007 - 2020, Intel Corporation. All rights = reserved.
>=20 > +# Copyright (c) 2007 - 2021, Intel Corporation. All rights = reserved.
>=20 > # Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.
>=20 > # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights = reserved.
>=20 > # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All > rights reserved.
>=20 > @@ -33,6 +33,7 @@ > SwapBytes16.c >=20 > LongJump.c >=20 > SetJump.c >=20 > + QuickSort.c >=20 > RShiftU64.c >=20 > RRotU64.c >=20 > RRotU32.c >=20 > -- > 2.30.0.windows.1 >=20 >=20 >=20 > -=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