From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mout02.posteo.de (mout02.posteo.de [185.67.36.66]) by mx.groups.io with SMTP id smtpd.web08.1664.1634325083509555270 for ; Fri, 15 Oct 2021 12:11:24 -0700 Authentication-Results: mx.groups.io; dkim=pass header.i=@posteo.de header.s=2017 header.b=NRDvSSE1; spf=pass (domain: posteo.de, ip: 185.67.36.66, mailfrom: mhaeuser@posteo.de) Received: from submission (posteo.de [89.146.220.130]) by mout02.posteo.de (Postfix) with ESMTPS id 51DFE240105 for ; Fri, 15 Oct 2021 21:11:20 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.de; s=2017; t=1634325080; bh=QrY5nkWm0kEsK4O3P2+7chs0gzFeo6FyT6jPyavKm6s=; h=Date:Subject:To:Cc:From:From; b=NRDvSSE1YUZpxqbbQmMUDS/F7hh26oQwOIiYMze6OhPnND7zOgAmoAmNGaIBm5iht GyNyBxGKfdu3PzfoNLu0xKhVqeqhY1VgNE/nDNBKcDTSFdxWk09HdI7M6QGT5oQvtF SBQLqamy2+e7CHA8LKvtA8ZCTjNkZhXjs6g+izkv4YP1+YtHCYqDHp5vonZqieSrm6 ixs9OXCG9If9/R3owMu3S8tTZTE+VindFXTeZXxGKAMD7y2If9T5lIgcJ2VXC9srfA ex8+K7OJH4CPttjbpznkmt6TLn6qXVcwe7yV2Es1CCnUomJRBzY8JSaAKf0Di3kvKW LbBcIB1vtFDvw== Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4HWG8Q5hJHz9rxR; Fri, 15 Oct 2021 21:11:18 +0200 (CEST) Message-ID: <831d7a8f-628d-9b1f-f9ff-ee0214e5b941@posteo.de> Date: Fri, 15 Oct 2021 19:11:18 +0000 MIME-Version: 1.0 Subject: Re: [edk2-devel] [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib To: devel@edk2.groups.io, ianx.kuo@intel.com Cc: amy.chan@intel.com, ray.ni@intel.com, Jian J Wang , Liming Gao References: <20211015143346.31-1-ianx.kuo@intel.com> <20211015143346.31-2-ianx.kuo@intel.com> From: =?UTF-8?B?TWFydmluIEjDpHVzZXI=?= In-Reply-To: <20211015143346.31-2-ianx.kuo@intel.com> Content-Language: en-GB Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit 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;