@Marvin Häuser 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 Sent: Saturday, October 16, 2021 3:11 AM To: devel@edk2.groups.io; Kuo, IanX Cc: Chan, Amy ; Ni, Ray ; Wang, Jian J ; Liming Gao 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 > > > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 > > 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 > Library used for sorting routines. > > - Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. >
> + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. > +
> SPDX-License-Identifier: BSD-2-Clause-Patent > > **/ > @@ -13,114 +13,6 @@ > #include > #include > > -/** > - 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. >
> + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. > +
> 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;