From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mga05.intel.com (mga05.intel.com [192.55.52.43]) by mx.groups.io with SMTP id smtpd.web10.5202.1633323839899153166 for ; Sun, 03 Oct 2021 22:04:00 -0700 Authentication-Results: mx.groups.io; dkim=missing; spf=pass (domain: intel.com, ip: 192.55.52.43, mailfrom: ianx.kuo@intel.com) X-IronPort-AV: E=McAfee;i="6200,9189,10126"; a="311484670" X-IronPort-AV: E=Sophos;i="5.85,344,1624345200"; d="scan'208";a="311484670" Received: from fmsmga006.fm.intel.com ([10.253.24.20]) by fmsmga105.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 03 Oct 2021 22:03:26 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.85,344,1624345200"; d="scan'208";a="710938513" Received: from ikuox-desk1.gar.corp.intel.com ([10.227.107.18]) by fmsmga006.fm.intel.com with ESMTP; 03 Oct 2021 22:03:24 -0700 From: "IanX Kuo" To: devel@edk2.groups.io Cc: amy.chan@intel.com, ray.ni@intel.com, IanX Kuo , Jian J Wang , Liming Gao Subject: [PATCH v5 2/4] MdeModulePkg/SortLib: Add QuickSort function on BaseLib Date: Mon, 4 Oct 2021 13:03:16 +0800 Message-Id: <20211004050318.1816-3-ianx.kuo@intel.com> X-Mailer: git-send-email 2.30.0.windows.1 In-Reply-To: <20211004050318.1816-1-ianx.kuo@intel.com> References: <20211004050318.1816-1-ianx.kuo@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable From: IanX Kuo REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675 Use QuickSort instead of QuickSortWorker Cc: Ray Ni Cc: Jian J Wang Cc: Liming Gao Signed-off-by: IanX Kuo --- .../Library/BaseSortLib/BaseSortLib.c | 117 +---------------- .../Library/UefiSortLib/UefiSortLib.c | 118 +----------------- 2 files changed, 10 insertions(+), 225 deletions(-) diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/= Library/BaseSortLib/BaseSortLib.c index a12c7bc0ec..b33339ac7c 100644 --- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c +++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c @@ -1,7 +1,7 @@ /** @file=0D Library used for sorting routines.=0D =0D - Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved.
= =0D + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
= =0D SPDX-License-Identifier: BSD-2-Clause-Patent=0D =0D **/=0D @@ -13,114 +13,6 @@ #include =0D #include =0D =0D -/**=0D - Worker function for QuickSorting. This function is identical to Perform= QuickSort,=0D - except that is uses the pre-allocated buffer so the in place sorting doe= s not need to=0D - allocate and free buffers constantly.=0D -=0D - Each element must be equal sized.=0D -=0D - if BufferToSort is NULL, then ASSERT.=0D - if CompareFunction is NULL, then ASSERT.=0D - if Buffer is NULL, then ASSERT.=0D -=0D - if Count is < 2 then perform no action.=0D - if Size is < 1 then perform no action.=0D -=0D - @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele= ments=0D - on return a buffer of sorted elements=0D - @param[in] Count the number of elements in the buffer to s= ort=0D - @param[in] ElementSize Size of an element in bytes=0D - @param[in] CompareFunction The function to call to perform the compa= rison=0D - of any 2 elements=0D - @param[in] Buffer Buffer of size ElementSize for use in swa= pping=0D -**/=0D -VOID=0D -EFIAPI=0D -QuickSortWorker (=0D - IN OUT VOID *BufferToSort,=0D - IN CONST UINTN Count,=0D - IN CONST UINTN ElementSize,=0D - IN SORT_COMPARE CompareFunction,=0D - IN VOID *Buffer=0D - )=0D -{=0D - VOID *Pivot;=0D - UINTN LoopCount;=0D - UINTN NextSwapLocation;=0D -=0D - ASSERT(BufferToSort !=3D NULL);=0D - ASSERT(CompareFunction !=3D NULL);=0D - ASSERT(Buffer !=3D NULL);=0D -=0D - if ( Count < 2=0D - || ElementSize < 1=0D - ){=0D - return;=0D - }=0D -=0D - NextSwapLocation =3D 0;=0D -=0D - //=0D - // pick a pivot (we choose last element)=0D - //=0D - Pivot =3D ((UINT8*)BufferToSort+((Count-1)*ElementSize));=0D -=0D - //=0D - // Now get the pivot such that all on "left" are below it=0D - // and everything "right" are above it=0D - //=0D - for ( LoopCount =3D 0=0D - ; LoopCount < Count -1=0D - ; LoopCount++=0D - ){=0D - //=0D - // if the element is less than the pivot=0D - //=0D - if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementS= ize)),Pivot) <=3D 0){=0D - //=0D - // swap=0D - //=0D - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize)= , ElementSize);=0D - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8= *)BufferToSort+((LoopCount)*ElementSize), ElementSize);=0D - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, Ele= mentSize);=0D -=0D - //=0D - // increment NextSwapLocation=0D - //=0D - NextSwapLocation++;=0D - }=0D - }=0D - //=0D - // swap pivot to it's final position (NextSwapLocaiton)=0D - //=0D - CopyMem (Buffer, Pivot, ElementSize);=0D - CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Ele= mentSize);=0D - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, El= ementSize);=0D -=0D - //=0D - // Now recurse on 2 paritial lists. neither of these will have the 'piv= ot' element=0D - // IE list is sorted left half, pivot element, sorted right half...=0D - //=0D - if (NextSwapLocation >=3D 2) {=0D - QuickSortWorker(=0D - BufferToSort,=0D - NextSwapLocation,=0D - ElementSize,=0D - CompareFunction,=0D - Buffer);=0D - }=0D -=0D - if ((Count - NextSwapLocation - 1) >=3D 2) {=0D - QuickSortWorker(=0D - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,=0D - Count - NextSwapLocation - 1,=0D - ElementSize,=0D - CompareFunction,=0D - Buffer);=0D - }=0D - return;=0D -}=0D /**=0D Function to perform a Quick Sort alogrithm on a buffer of comparable ele= ments.=0D =0D @@ -156,12 +48,13 @@ PerformQuickSort ( Buffer =3D AllocateZeroPool(ElementSize);=0D ASSERT(Buffer !=3D NULL);=0D =0D - QuickSortWorker(=0D + QuickSort (=0D BufferToSort,=0D Count,=0D ElementSize,=0D - CompareFunction,=0D - Buffer);=0D + (SORT_COMPARE) CompareFunction,=0D + Buffer=0D + );=0D =0D FreePool(Buffer);=0D return;=0D diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/= Library/UefiSortLib/UefiSortLib.c index 46dc443638..151a5a9ac3 100644 --- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c +++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c @@ -1,7 +1,7 @@ /** @file=0D Library used for sorting routines.=0D =0D - Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved.
= =0D + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
= =0D SPDX-License-Identifier: BSD-2-Clause-Patent=0D =0D **/=0D @@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollat= ion =3D NULL; } \=0D }=0D =0D -/**=0D - Worker function for QuickSorting. This function is identical to Perform= QuickSort,=0D - except that is uses the pre-allocated buffer so the in place sorting doe= s not need to=0D - allocate and free buffers constantly.=0D -=0D - Each element must be equal sized.=0D -=0D - if BufferToSort is NULL, then ASSERT.=0D - if CompareFunction is NULL, then ASSERT.=0D - if Buffer is NULL, then ASSERT.=0D -=0D - if Count is < 2 then perform no action.=0D - if Size is < 1 then perform no action.=0D -=0D - @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele= ments=0D - on return a buffer of sorted elements=0D - @param[in] Count the number of elements in the buffer to s= ort=0D - @param[in] ElementSize Size of an element in bytes=0D - @param[in] CompareFunction The function to call to perform the compa= rison=0D - of any 2 elements=0D - @param[in] Buffer Buffer of size ElementSize for use in swa= pping=0D -**/=0D -VOID=0D -EFIAPI=0D -QuickSortWorker (=0D - IN OUT VOID *BufferToSort,=0D - IN CONST UINTN Count,=0D - IN CONST UINTN ElementSize,=0D - IN SORT_COMPARE CompareFunction,=0D - IN VOID *Buffer=0D - )=0D -{=0D - VOID *Pivot;=0D - UINTN LoopCount;=0D - UINTN NextSwapLocation;=0D -=0D - ASSERT(BufferToSort !=3D NULL);=0D - ASSERT(CompareFunction !=3D NULL);=0D - ASSERT(Buffer !=3D NULL);=0D -=0D - if ( Count < 2=0D - || ElementSize < 1=0D - ){=0D - return;=0D - }=0D -=0D - NextSwapLocation =3D 0;=0D -=0D - //=0D - // pick a pivot (we choose last element)=0D - //=0D - Pivot =3D ((UINT8*)BufferToSort+((Count-1)*ElementSize));=0D -=0D - //=0D - // Now get the pivot such that all on "left" are below it=0D - // and everything "right" are above it=0D - //=0D - for ( LoopCount =3D 0=0D - ; LoopCount < Count -1=0D - ; LoopCount++=0D - ){=0D - //=0D - // if the element is less than the pivot=0D - //=0D - if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementS= ize)),Pivot) <=3D 0){=0D - //=0D - // swap=0D - //=0D - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize)= , ElementSize);=0D - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8= *)BufferToSort+((LoopCount)*ElementSize), ElementSize);=0D - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, Ele= mentSize);=0D -=0D - //=0D - // increment NextSwapLocation=0D - //=0D - NextSwapLocation++;=0D - }=0D - }=0D - //=0D - // swap pivot to it's final position (NextSwapLocaiton)=0D - //=0D - CopyMem (Buffer, Pivot, ElementSize);=0D - CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Ele= mentSize);=0D - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, El= ementSize);=0D -=0D - //=0D - // Now recurse on 2 paritial lists. neither of these will have the 'piv= ot' element=0D - // IE list is sorted left half, pivot element, sorted right half...=0D - //=0D - if (NextSwapLocation >=3D 2) {=0D - QuickSortWorker(=0D - BufferToSort,=0D - NextSwapLocation,=0D - ElementSize,=0D - CompareFunction,=0D - Buffer);=0D - }=0D -=0D - if ((Count - NextSwapLocation - 1) >=3D 2) {=0D - QuickSortWorker(=0D - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,=0D - Count - NextSwapLocation - 1,=0D - ElementSize,=0D - CompareFunction,=0D - Buffer);=0D - }=0D -=0D - return;=0D -}=0D /**=0D Function to perform a Quick Sort alogrithm on a buffer of comparable ele= ments.=0D =0D @@ -173,12 +64,13 @@ PerformQuickSort ( Buffer =3D AllocateZeroPool(ElementSize);=0D ASSERT(Buffer !=3D NULL);=0D =0D - QuickSortWorker(=0D + QuickSort (=0D BufferToSort,=0D Count,=0D ElementSize,=0D - CompareFunction,=0D - Buffer);=0D + (SORT_COMPARE) CompareFunction,=0D + Buffer=0D + );=0D =0D FreePool(Buffer);=0D return;=0D --=20 2.30.0.windows.1