[edk2-devel] [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
IanX Kuo
ianx.kuo at intel.com
Fri Oct 15 23:32:30 UTC 2021
@Marvin Häuser<mailto:mhaeuser at 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 <mhaeuser at posteo.de>
Sent: Saturday, October 16, 2021 3:11 AM
To: devel at edk2.groups.io; Kuo, IanX <ianx.kuo at intel.com>
Cc: Chan, Amy <amy.chan at intel.com>; Ni, Ray <ray.ni at intel.com>; Wang, Jian J <jian.j.wang at intel.com>; Liming Gao <gaoliming at 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.kuo at intel.com<mailto:ianx.kuo at intel.com>>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Use QuickSort instead of QuickSortWorker
>
> Cc: Ray Ni <ray.ni at intel.com<mailto:ray.ni at intel.com>>
> Cc: Jian J Wang <jian.j.wang at intel.com<mailto:jian.j.wang at intel.com>>
> Cc: Liming Gao <gaoliming at byosoft.com.cn<mailto:gaoliming at byosoft.com.cn>>
> Signed-off-by: IanX Kuo <ianx.kuo at intel.com<mailto:ianx.kuo at 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/1813853
Group Owner: devel+owner at edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [edk2-devel-archive at redhat.com]
-=-=-=-=-=-=-=-=-=-=-=-
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listman.redhat.com/archives/edk2-devel-archive/attachments/20211015/e597add4/attachment.htm>
More information about the edk2-devel-archive
mailing list