@Marvin Häuser<mailto:mhaeu...@posteo.de>
Thank to catch it. I dropped it on my patch v2. Compiler Status Linux GCC5 (gcc 10.2.0/9.3.0/8.4.0/7.5.0/5.5.0/5.4.0) Pass Windows CLANGPDB (clang 12.0.0), Linux CLANGPDB (clang 12.0.0) Pass Windows MSVC (VS2015/VS2017/VS2019) Pass Mac XCODE5 (clang 11.0.0) Pass Thanks, Ian Kuo -----Original Message----- From: Marvin Häuser <mhaeu...@posteo.de> Sent: Saturday, October 16, 2021 3:11 AM To: devel@edk2.groups.io; Kuo, IanX <ianx....@intel.com> Cc: Chan, Amy <amy.c...@intel.com>; Ni, Ray <ray...@intel.com>; Wang, Jian J <jian.j.w...@intel.com>; Liming Gao <gaolim...@byosoft.com.cn> Subject: Re: [edk2-devel] [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib Good day Ianx, On 15.10.21 16:33, IanX Kuo wrote: > From: IanX Kuo <ianx....@intel.com<mailto:ianx....@intel.com>> > > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 > > Use QuickSort instead of QuickSortWorker > > Cc: Ray Ni <ray...@intel.com<mailto:ray...@intel.com>> > Cc: Jian J Wang <jian.j.w...@intel.com<mailto:jian.j.w...@intel.com>> > Cc: Liming Gao <gaolim...@byosoft.com.cn<mailto:gaolim...@byosoft.com.cn>> > Signed-off-by: IanX Kuo <ianx....@intel.com<mailto:ianx....@intel.com>> > --- > .../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 > 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); > + (SORT_COMPARE) CompareFunction, CLANGPDB and GCC5 do not need this cast; I cannot easily test MSVC right now. Does it compile fine for you with the cast dropped? Dropping the cast gives us compile-time checking for actual type-compatibility. > + Buffer > + ); > > FreePool(Buffer); > return; > 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 > 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); > + (SORT_COMPARE) CompareFunction, See above. Best regards, Marvin > + Buffer > + ); > > FreePool(Buffer); > return; -=-=-=-=-=-=-=-=-=-=-=- Groups.io Links: You receive all messages sent to this group. View/Reply Online (#82172): https://edk2.groups.io/g/devel/message/82172 Mute This Topic: https://groups.io/mt/86340400/21656 Group Owner: devel+ow...@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [arch...@mail-archive.com] -=-=-=-=-=-=-=-=-=-=-=-
