Reviewed-by: Liming Gao <gaolim...@byosoft.com.cn> > -----邮件原件----- > 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo > 发送时间: 2021年10月17日 6:34 > 收件人: devel@edk2.groups.io > 抄送: amy.c...@intel.com; ray...@intel.com; IanX Kuo > <ianx....@intel.com>; Jian J Wang <jian.j.w...@intel.com>; Liming Gao > <gaolim...@byosoft.com.cn> > 主题: [edk2-devel] [PATCH v3 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 (#82182): https://edk2.groups.io/g/devel/message/82182 > Mute This Topic: https://groups.io/mt/86381252/4905953 > Group Owner: devel+ow...@edk2.groups.io > Unsubscribe: https://edk2.groups.io/g/devel/unsub > [gaolim...@byosoft.com.cn] > -=-=-=-=-=-= >
-=-=-=-=-=-=-=-=-=-=-=- Groups.io Links: You receive all messages sent to this group. View/Reply Online (#82192): https://edk2.groups.io/g/devel/message/82192 Mute This Topic: https://groups.io/mt/86405813/21656 Group Owner: devel+ow...@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [arch...@mail-archive.com] -=-=-=-=-=-=-=-=-=-=-=-
