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.web10.31064.1634525407689202749 for ; Sun, 17 Oct 2021 19:50:08 -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, 18 Oct 2021 10:50:04 +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: , , "'Jian J Wang'" References: <20211016223406.935-1-ianx.kuo@intel.com> <20211016223406.935-2-ianx.kuo@intel.com> In-Reply-To: <20211016223406.935-2-ianx.kuo@intel.com> Subject: =?UTF-8?B?5Zue5aSNOiBbZWRrMi1kZXZlbF0gW1BBVENIIHYzIDEvM10gTWRlTW9kdWxlUGtnL1NvcnRMaWI6IEFkZCBRdWlja1NvcnQgZnVuY3Rpb24gb24gQmFzZUxpYg==?= Date: Mon, 18 Oct 2021 10:50:04 +0800 Message-ID: <02e501d7c3ca$daa908c0$8ffb1a40$@byosoft.com.cn> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AQKHGnfU/4aeUrQ9URDnFcY2Xg+9/wH11RYqqmmyB+A= Content-Type: text/plain; charset="gb2312" Content-Transfer-Encoding: quoted-printable Content-Language: zh-cn Reviewed-by: Liming Gao > -----=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=C217=C8=D5 6:34 > =CA=D5=BC=FE=C8=CB: devel@edk2.groups.io > =B3=AD=CB=CD: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo > ; Jian J Wang ; Liming Gao > > =D6=F7=CC=E2: [edk2-devel] [PATCH v3 1/3] MdeModulePkg/SortLib: Add = QuickSort > function on BaseLib >=20 > From: IanX Kuo >=20 > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675 >=20 > Use QuickSort instead of QuickSortWorker >=20 > Cc: Ray Ni > Cc: Jian J Wang > Cc: Liming Gao > Signed-off-by: IanX Kuo > --- > .../Library/BaseSortLib/BaseSortLib.c | 115 +---------------- > .../Library/UefiSortLib/UefiSortLib.c | 116 = +----------------- > 2 files changed, 8 insertions(+), 223 deletions(-) >=20 > diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c > b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c > index a12c7bc0ec..0903943ee4 100644 > --- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c > +++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c > @@ -1,7 +1,7 @@ > /** @file >=20 > Library used for sorting routines. >=20 >=20 >=20 > - Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. =
>=20 > + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. =
>=20 > SPDX-License-Identifier: BSD-2-Clause-Patent >=20 >=20 >=20 > **/ >=20 > @@ -13,114 +13,6 @@ > #include >=20 > #include >=20 >=20 >=20 > -/** >=20 > - Worker function for QuickSorting. This function is identical to > PerformQuickSort, >=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 Buffer is NULL, then ASSERT. >=20 > - >=20 > - if Count is < 2 then perform no action. >=20 > - if Size is < 1 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[in] Buffer Buffer of size ElementSize for use = in > swapping >=20 > -**/ >=20 > -VOID >=20 > -EFIAPI >=20 > -QuickSortWorker ( >=20 > - IN OUT VOID *BufferToSort, >=20 > - IN CONST UINTN Count, >=20 > - IN CONST UINTN ElementSize, >=20 > - IN SORT_COMPARE CompareFunction, >=20 > - IN VOID *Buffer >=20 > - ) >=20 > -{ >=20 > - VOID *Pivot; >=20 > - UINTN LoopCount; >=20 > - UINTN NextSwapLocation; >=20 > - >=20 > - ASSERT(BufferToSort !=3D NULL); >=20 > - ASSERT(CompareFunction !=3D NULL); >=20 > - ASSERT(Buffer !=3D NULL); >=20 > - >=20 > - if ( Count < 2 >=20 > - || ElementSize < 1 >=20 > - ){ >=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 >=20 > - ; LoopCount < Count -1 >=20 > - ; LoopCount++ >=20 > - ){ >=20 > - // >=20 > - // if the element is less than the pivot >=20 > - // >=20 > - if > = (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize) > ),Pivot) <=3D 0){ >=20 > - // >=20 > - // swap >=20 > - // >=20 > - CopyMem (Buffer, > (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), = Buffer, > ElementSize); >=20 > - >=20 > - // >=20 > - // increment NextSwapLocation >=20 > - // >=20 > - NextSwapLocation++; >=20 > - } >=20 > - } >=20 > - // >=20 > - // swap pivot to it's final position (NextSwapLocaiton) >=20 > - // >=20 > - CopyMem (Buffer, Pivot, ElementSize); >=20 > - CopyMem (Pivot, = (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > Buffer, ElementSize); >=20 > - >=20 > - // >=20 > - // Now recurse on 2 paritial 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 > - QuickSortWorker( >=20 > - BufferToSort, >=20 > - NextSwapLocation, >=20 > - ElementSize, >=20 > - CompareFunction, >=20 > - Buffer); >=20 > - } >=20 > - >=20 > - if ((Count - NextSwapLocation - 1) >=3D 2) { >=20 > - QuickSortWorker( >=20 > - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize, >=20 > - Count - NextSwapLocation - 1, >=20 > - ElementSize, >=20 > - CompareFunction, >=20 > - Buffer); >=20 > - } >=20 > - return; >=20 > -} >=20 > /** >=20 > Function to perform a Quick Sort alogrithm on a buffer of = comparable > elements. >=20 >=20 >=20 > @@ -156,12 +48,13 @@ PerformQuickSort ( > Buffer =3D AllocateZeroPool(ElementSize); >=20 > ASSERT(Buffer !=3D NULL); >=20 >=20 >=20 > - QuickSortWorker( >=20 > + QuickSort ( >=20 > BufferToSort, >=20 > Count, >=20 > ElementSize, >=20 > CompareFunction, >=20 > - Buffer); >=20 > + Buffer >=20 > + ); >=20 >=20 >=20 > FreePool(Buffer); >=20 > return; >=20 > diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c > b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c > index 46dc443638..29d8735c22 100644 > --- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c > +++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c > @@ -1,7 +1,7 @@ > /** @file >=20 > Library used for sorting routines. >=20 >=20 >=20 > - Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. =
>=20 > + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. =
>=20 > SPDX-License-Identifier: BSD-2-Clause-Patent >=20 >=20 >=20 > **/ >=20 > @@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL > *mUnicodeCollation =3D NULL; > } \ >=20 > } >=20 >=20 >=20 > -/** >=20 > - Worker function for QuickSorting. This function is identical to > PerformQuickSort, >=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 Buffer is NULL, then ASSERT. >=20 > - >=20 > - if Count is < 2 then perform no action. >=20 > - if Size is < 1 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[in] Buffer Buffer of size ElementSize for use = in > swapping >=20 > -**/ >=20 > -VOID >=20 > -EFIAPI >=20 > -QuickSortWorker ( >=20 > - IN OUT VOID *BufferToSort, >=20 > - IN CONST UINTN Count, >=20 > - IN CONST UINTN ElementSize, >=20 > - IN SORT_COMPARE CompareFunction, >=20 > - IN VOID *Buffer >=20 > - ) >=20 > -{ >=20 > - VOID *Pivot; >=20 > - UINTN LoopCount; >=20 > - UINTN NextSwapLocation; >=20 > - >=20 > - ASSERT(BufferToSort !=3D NULL); >=20 > - ASSERT(CompareFunction !=3D NULL); >=20 > - ASSERT(Buffer !=3D NULL); >=20 > - >=20 > - if ( Count < 2 >=20 > - || ElementSize < 1 >=20 > - ){ >=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 >=20 > - ; LoopCount < Count -1 >=20 > - ; LoopCount++ >=20 > - ){ >=20 > - // >=20 > - // if the element is less than the pivot >=20 > - // >=20 > - if > = (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize) > ),Pivot) <=3D 0){ >=20 > - // >=20 > - // swap >=20 > - // >=20 > - CopyMem (Buffer, > (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), = Buffer, > ElementSize); >=20 > - >=20 > - // >=20 > - // increment NextSwapLocation >=20 > - // >=20 > - NextSwapLocation++; >=20 > - } >=20 > - } >=20 > - // >=20 > - // swap pivot to it's final position (NextSwapLocaiton) >=20 > - // >=20 > - CopyMem (Buffer, Pivot, ElementSize); >=20 > - CopyMem (Pivot, = (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > Buffer, ElementSize); >=20 > - >=20 > - // >=20 > - // Now recurse on 2 paritial 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 > - QuickSortWorker( >=20 > - BufferToSort, >=20 > - NextSwapLocation, >=20 > - ElementSize, >=20 > - CompareFunction, >=20 > - Buffer); >=20 > - } >=20 > - >=20 > - if ((Count - NextSwapLocation - 1) >=3D 2) { >=20 > - QuickSortWorker( >=20 > - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize, >=20 > - Count - NextSwapLocation - 1, >=20 > - ElementSize, >=20 > - CompareFunction, >=20 > - Buffer); >=20 > - } >=20 > - >=20 > - return; >=20 > -} >=20 > /** >=20 > Function to perform a Quick Sort alogrithm on a buffer of = comparable > elements. >=20 >=20 >=20 > @@ -173,12 +64,13 @@ PerformQuickSort ( > Buffer =3D AllocateZeroPool(ElementSize); >=20 > ASSERT(Buffer !=3D NULL); >=20 >=20 >=20 > - QuickSortWorker( >=20 > + QuickSort ( >=20 > BufferToSort, >=20 > Count, >=20 > ElementSize, >=20 > CompareFunction, >=20 > - Buffer); >=20 > + Buffer >=20 > + ); >=20 >=20 >=20 > FreePool(Buffer); >=20 > return; >=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 (#82182): = https://edk2.groups.io/g/devel/message/82182 > Mute This Topic: https://groups.io/mt/86381252/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