@Liming Gao Sorry to bother you. May I get your help for review by again ?
Thanks, Ian Kuo -----Original Message----- From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of IanX Kuo Sent: Monday, October 18, 2021 12:21 PM To: devel@edk2.groups.io Cc: Chan, Amy <amy.c...@intel.com>; Ni, Ray <ray...@intel.com>; Kuo, IanX <ianx....@intel.com>; Wang, Jian J <jian.j.w...@intel.com>; Liming Gao <gaolim...@byosoft.com.cn> Subject: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib From: IanX Kuo <ianx....@intel.com> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 Use QuickSort instead of QuickSortWorker Cc: Ray Ni <ray...@intel.com> Cc: Jian J Wang <jian.j.w...@intel.com> Cc: Liming Gao <gaolim...@byosoft.com.cn> Signed-off-by: IanX Kuo <ianx....@intel.com> --- .../Library/BaseSortLib/BaseSortLib.c | 115 +---------------- .../Library/UefiSortLib/UefiSortLib.c | 116 +----------------- 2 files changed, 8 insertions(+), 223 deletions(-) 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 Library used for sorting routines. - Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR> SPDX-License-Identifier: BSD-2-Clause-Patent **/@@ -13,114 +13,6 @@ #include <Library/MemoryAllocationLib.h> #include <Library/SortLib.h> -/**- Worker function for QuickSorting. This function is identical to PerformQuickSort,- 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 Buffer is NULL, then ASSERT.-- if Count is < 2 then perform no action.- if Size is < 1 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[in] Buffer Buffer of size ElementSize for use in swapping-**/-VOID-EFIAPI-QuickSortWorker (- IN OUT VOID *BufferToSort,- IN CONST UINTN Count,- IN CONST UINTN ElementSize,- IN SORT_COMPARE CompareFunction,- IN VOID *Buffer- )-{- VOID *Pivot;- UINTN LoopCount;- UINTN NextSwapLocation;-- ASSERT(BufferToSort != NULL);- ASSERT(CompareFunction != NULL);- ASSERT(Buffer != NULL);-- if ( Count < 2- || ElementSize < 1- ){- return;- }-- NextSwapLocation = 0;-- //- // pick a pivot (we choose last element)- //- Pivot = ((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 = 0- ; LoopCount < Count -1- ; LoopCount++- ){- //- // if the element is less than the pivot- //- if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){- //- // swap- //- CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);- CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);-- //- // increment NextSwapLocation- //- NextSwapLocation++;- }- }- //- // swap pivot to it's final position (NextSwapLocaiton)- //- CopyMem (Buffer, Pivot, ElementSize);- CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);-- //- // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element- // IE list is sorted left half, pivot element, sorted right half...- //- if (NextSwapLocation >= 2) {- QuickSortWorker(- BufferToSort,- NextSwapLocation,- ElementSize,- CompareFunction,- Buffer);- }-- if ((Count - NextSwapLocation - 1) >= 2) {- QuickSortWorker(- (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,- Count - NextSwapLocation - 1,- ElementSize,- CompareFunction,- Buffer);- }- return;-} /** Function to perform a Quick Sort alogrithm on a buffer of comparable elements. @@ -156,12 +48,13 @@ PerformQuickSort ( Buffer = AllocateZeroPool(ElementSize); ASSERT(Buffer != NULL); - QuickSortWorker(+ QuickSort ( BufferToSort, Count, ElementSize, CompareFunction,- Buffer);+ Buffer+ ); FreePool(Buffer); return;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 Library used for sorting routines. - Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR> SPDX-License-Identifier: BSD-2-Clause-Patent **/@@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation = NULL; } \ } -/**- Worker function for QuickSorting. This function is identical to PerformQuickSort,- 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 Buffer is NULL, then ASSERT.-- if Count is < 2 then perform no action.- if Size is < 1 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[in] Buffer Buffer of size ElementSize for use in swapping-**/-VOID-EFIAPI-QuickSortWorker (- IN OUT VOID *BufferToSort,- IN CONST UINTN Count,- IN CONST UINTN ElementSize,- IN SORT_COMPARE CompareFunction,- IN VOID *Buffer- )-{- VOID *Pivot;- UINTN LoopCount;- UINTN NextSwapLocation;-- ASSERT(BufferToSort != NULL);- ASSERT(CompareFunction != NULL);- ASSERT(Buffer != NULL);-- if ( Count < 2- || ElementSize < 1- ){- return;- }-- NextSwapLocation = 0;-- //- // pick a pivot (we choose last element)- //- Pivot = ((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 = 0- ; LoopCount < Count -1- ; LoopCount++- ){- //- // if the element is less than the pivot- //- if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){- //- // swap- //- CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);- CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);-- //- // increment NextSwapLocation- //- NextSwapLocation++;- }- }- //- // swap pivot to it's final position (NextSwapLocaiton)- //- CopyMem (Buffer, Pivot, ElementSize);- CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);-- //- // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element- // IE list is sorted left half, pivot element, sorted right half...- //- if (NextSwapLocation >= 2) {- QuickSortWorker(- BufferToSort,- NextSwapLocation,- ElementSize,- CompareFunction,- Buffer);- }-- if ((Count - NextSwapLocation - 1) >= 2) {- QuickSortWorker(- (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,- Count - NextSwapLocation - 1,- ElementSize,- CompareFunction,- Buffer);- }-- return;-} /** Function to perform a Quick Sort alogrithm on a buffer of comparable elements. @@ -173,12 +64,13 @@ PerformQuickSort ( Buffer = AllocateZeroPool(ElementSize); ASSERT(Buffer != NULL); - QuickSortWorker(+ QuickSort ( BufferToSort, Count, ElementSize, CompareFunction,- Buffer);+ Buffer+ ); FreePool(Buffer); return;-- 2.30.0.windows.1 -=-=-=-=-=-= Groups.io Links: You receive all messages sent to this group. View/Reply Online (#82204): https://edk2.groups.io/g/devel/message/82204 Mute This Topic: https://groups.io/mt/86406843/4830160 Group Owner: devel+ow...@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [ianx....@intel.com] -=-=-=-=-=-= -=-=-=-=-=-=-=-=-=-=-=- Groups.io Links: You receive all messages sent to this group. View/Reply Online (#82264): https://edk2.groups.io/g/devel/message/82264 Mute This Topic: https://groups.io/mt/86430925/21656 Group Owner: devel+ow...@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [arch...@mail-archive.com] -=-=-=-=-=-=-=-=-=-=-=-
