* Re: [edk2-devel] [PATCH v6 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
2021-10-06 0:30 ` [PATCH v6 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo
@ 2021-10-06 1:15 ` guajen0710
2021-10-07 10:29 ` Marvin Häuser
1 sibling, 0 replies; 4+ messages in thread
From: guajen0710 @ 2021-10-06 1:15 UTC (permalink / raw)
To: devel, ianx.kuo, mhaeuser
[-- Attachment #1: Type: text/plain, Size: 9419 bytes --]
Hi Marvin
Thanks for reply on Patch V5
I think the patch should eliminate your concern.
IanX Kuo <ianx.kuo@intel.com> 於 2021年10月6日 週三 上午8:31 寫道：
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Add QuickSort function into BaseLib
>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Michael D Kinney <michael.d.kinney@intel.com>
> Cc: Liming Gao <gaoliming@byosoft.com.cn>
> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
> MdePkg/Include/Library/BaseLib.h | 49 ++++++++
> MdePkg/Library/BaseLib/BaseLib.inf | 1 +
> MdePkg/Library/BaseLib/QuickSort.c | 116 ++++++++++++++++++
> .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
> 4 files changed, 168 insertions(+), 1 deletion(-)
> create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
>
> diff --git a/MdePkg/Include/Library/BaseLib.h
> b/MdePkg/Include/Library/BaseLib.h
> index 2452c1d92e..0ae0f4e6af 100644
> --- a/MdePkg/Include/Library/BaseLib.h
> +++ b/MdePkg/Include/Library/BaseLib.h
> @@ -2856,6 +2856,55 @@ RemoveEntryList (
> //
> // Math Services
> //
> +/**
> + Prototype for comparison function for any two element types.
> +
> + @param[in] Buffer1 The pointer to first buffer.
> + @param[in] Buffer2 The pointer to second buffer.
> +
> + @retval 0 Buffer1 equal to Buffer2.
> + @return <0 Buffer1 is less than Buffer2.
> + @return >0 Buffer1 is greater than Buffer2.
> +**/
> +typedef
> +INTN
> +(EFIAPI *BASE_SORT_COMPARE)(
> + IN CONST VOID *Buffer1,
> + IN CONST VOID *Buffer2
> + );
> +
> +/**
> + This function is identical to perform QuickSort,
> + 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 BufferOneElement is NULL, then ASSERT.
> + if ElementSize is < 1, then ASSERT.
> +
> + if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equals
> to ElementSize.
> + It's used by QuickSort() for swapping in
> sorting.
> +**/
> +VOID
> +EFIAPI
> +QuickSort (
> + IN OUT VOID *BufferToSort,
> + IN CONST UINTN Count,
> + IN CONST UINTN ElementSize,
> + IN BASE_SORT_COMPARE CompareFunction,
> + OUT VOID *BufferOneElement
> + );
>
> /**
> Shifts a 64-bit integer left between 0 and 63 bits. The low bits are
> filled
> diff --git a/MdePkg/Library/BaseLib/BaseLib.inf
> b/MdePkg/Library/BaseLib/BaseLib.inf
> index 6efa5315b6..cebda3b210 100644
> --- a/MdePkg/Library/BaseLib/BaseLib.inf
> +++ b/MdePkg/Library/BaseLib/BaseLib.inf
> @@ -32,6 +32,7 @@
> SwapBytes16.c
> LongJump.c
> SetJump.c
> + QuickSort.c
> RShiftU64.c
> RRotU64.c
> RRotU32.c
> diff --git a/MdePkg/Library/BaseLib/QuickSort.c
> b/MdePkg/Library/BaseLib/QuickSort.c
> new file mode 100644
> index 0000000000..3aff18188b
> --- /dev/null
> +++ b/MdePkg/Library/BaseLib/QuickSort.c
> @@ -0,0 +1,116 @@
> +/** @file
> + Math worker functions.
> +
> + Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
> + SPDX-License-Identifier: BSD-2-Clause-Patent
> +
> +**/
> +
> +#include "BaseLibInternals.h"
> +
> +/**
> + This function is identical to perform QuickSort,
> + 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 BufferOneElement is NULL, then ASSERT.
> + if ElementSize is < 1, then ASSERT.
> +
> + if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equals
> to ElementSize.
> + It's used by QuickSort() for swapping in
> sorting.
> +**/
> +VOID
> +EFIAPI
> +QuickSort (
> + IN OUT VOID *BufferToSort,
> + IN CONST UINTN Count,
> + IN CONST UINTN ElementSize,
> + IN BASE_SORT_COMPARE CompareFunction,
> + OUT VOID *BufferOneElement
> + )
> +{
> + VOID *Pivot;
> + UINTN LoopCount;
> + UINTN NextSwapLocation;
> +
> + ASSERT (BufferToSort != NULL);
> + ASSERT (CompareFunction != NULL);
> + ASSERT (BufferOneElement != NULL);
> + ASSERT (ElementSize >= 1);
> +
> + if (Count < 2) {
> + 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 pivot is greater than the element.
> + //
> + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) *
> ElementSize)), Pivot) <= 0){
> + //
> + // swap
> + //
> + CopyMem (BufferOneElement, (UINT8*) BufferToSort +
> (NextSwapLocation * ElementSize), ElementSize);
> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize),
> (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);
> + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize),
> BufferOneElement, ElementSize);
> +
> + //
> + // increment NextSwapLocation
> + //
> + NextSwapLocation++;
> + }
> + }
> + //
> + // swap pivot to it's final position (NextSwapLocation)
> + //
> + CopyMem (BufferOneElement, Pivot, ElementSize);
> + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation *
> ElementSize), ElementSize);
> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize),
> BufferOneElement, ElementSize);
> +
> + //
> + // Now recurse on 2 partial lists. neither of these will have the
> 'pivot' element
> + // IE list is sorted left half, pivot element, sorted right half...
> + //
> + if (NextSwapLocation >= 2) {
> + QuickSort (
> + BufferToSort,
> + NextSwapLocation,
> + ElementSize,
> + CompareFunction,
> + BufferOneElement
> + );
> + }
> +
> + if ((Count - NextSwapLocation - 1) >= 2) {
> + QuickSort (
> + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
> + Count - NextSwapLocation - 1,
> + ElementSize,
> + CompareFunction,
> + BufferOneElement
> + );
> + }
> +}
> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> index eae1a7158d..d09bd12bef 100644
> --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> @@ -1,7 +1,7 @@
> ## @file
> # Base Library implementation for use with host based unit tests.
> #
> -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>
> +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
> # Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
> # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
> # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All
> rights reserved.<BR>
> @@ -33,6 +33,7 @@
> SwapBytes16.c
> LongJump.c
> SetJump.c
> + QuickSort.c
> RShiftU64.c
> RRotU64.c
> RRotU32.c
> --
> 2.30.0.windows.1
>
>
>
> ------------
> Groups.io Links: You receive all messages sent to this group.
> View/Reply Online (#81531): https://edk2.groups.io/g/devel/message/81531
> Mute This Topic: https://groups.io/mt/86108888/4133238
> Group Owner: devel+owner@edk2.groups.io
> Unsubscribe: https://edk2.groups.io/g/devel/unsub [guajen0710@gmail.com]
> ------------
>
>
>
[-- Attachment #2: Type: text/html, Size: 11952 bytes --]
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [edk2-devel] [PATCH v6 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
2021-10-06 0:30 ` [PATCH v6 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-06 1:15 ` [edk2-devel] " guajen0710
@ 2021-10-07 10:29 ` Marvin Häuser
1 sibling, 0 replies; 4+ messages in thread
From: Marvin Häuser @ 2021-10-07 10:29 UTC (permalink / raw)
To: devel, ianx.kuo
Cc: amy.chan, ray.ni, Michael D Kinney, Liming Gao, Zhiguang Liu
On 06/10/2021 02:30, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Add QuickSort function into BaseLib
>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Michael D Kinney <michael.d.kinney@intel.com>
> Cc: Liming Gao <gaoliming@byosoft.com.cn>
> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
> MdePkg/Include/Library/BaseLib.h | 49 ++++++++
> MdePkg/Library/BaseLib/BaseLib.inf | 1 +
> MdePkg/Library/BaseLib/QuickSort.c | 116 ++++++++++++++++++
> .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
> 4 files changed, 168 insertions(+), 1 deletion(-)
> create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
>
> diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/BaseLib.h
> index 2452c1d92e..0ae0f4e6af 100644
> --- a/MdePkg/Include/Library/BaseLib.h
> +++ b/MdePkg/Include/Library/BaseLib.h
> @@ -2856,6 +2856,55 @@ RemoveEntryList (
> //
> // Math Services
> //
> +/**
> + Prototype for comparison function for any two element types.
> +
> + @param[in] Buffer1 The pointer to first buffer.
> + @param[in] Buffer2 The pointer to second buffer.
> +
> + @retval 0 Buffer1 equal to Buffer2.
> + @return <0 Buffer1 is less than Buffer2.
> + @return >0 Buffer1 is greater than Buffer2.
> +**/
> +typedef
> +INTN
> +(EFIAPI *BASE_SORT_COMPARE)(
> + IN CONST VOID *Buffer1,
> + IN CONST VOID *Buffer2
> + );
> +
> +/**
> + This function is identical to perform QuickSort,
> + 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 BufferOneElement is NULL, then ASSERT.
> + if ElementSize is < 1, then ASSERT.
> +
> + if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.
> + It's used by QuickSort() for swapping in sorting.
> +**/
> +VOID
> +EFIAPI
> +QuickSort (
> + IN OUT VOID *BufferToSort,
> + IN CONST UINTN Count,
> + IN CONST UINTN ElementSize,
> + IN BASE_SORT_COMPARE CompareFunction,
> + OUT VOID *BufferOneElement
> + );
>
> /**
> Shifts a 64-bit integer left between 0 and 63 bits. The low bits are filled
> diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/BaseLib.inf
> index 6efa5315b6..cebda3b210 100644
> --- a/MdePkg/Library/BaseLib/BaseLib.inf
> +++ b/MdePkg/Library/BaseLib/BaseLib.inf
> @@ -32,6 +32,7 @@
> SwapBytes16.c
> LongJump.c
> SetJump.c
> + QuickSort.c
> RShiftU64.c
> RRotU64.c
> RRotU32.c
> diff --git a/MdePkg/Library/BaseLib/QuickSort.c b/MdePkg/Library/BaseLib/QuickSort.c
> new file mode 100644
> index 0000000000..3aff18188b
> --- /dev/null
> +++ b/MdePkg/Library/BaseLib/QuickSort.c
> @@ -0,0 +1,116 @@
> +/** @file
> + Math worker functions.
> +
> + Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
> + SPDX-License-Identifier: BSD-2-Clause-Patent
> +
> +**/
> +
> +#include "BaseLibInternals.h"
> +
> +/**
> + This function is identical to perform QuickSort,
> + 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 BufferOneElement is NULL, then ASSERT.
> + if ElementSize is < 1, then ASSERT.
> +
> + if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.
> + It's used by QuickSort() for swapping in sorting.
> +**/
> +VOID
> +EFIAPI
> +QuickSort (
> + IN OUT VOID *BufferToSort,
> + IN CONST UINTN Count,
> + IN CONST UINTN ElementSize,
> + IN BASE_SORT_COMPARE CompareFunction,
> + OUT VOID *BufferOneElement
> + )
> +{
> + VOID *Pivot;
> + UINTN LoopCount;
> + UINTN NextSwapLocation;
> +
> + ASSERT (BufferToSort != NULL);
> + ASSERT (CompareFunction != NULL);
> + ASSERT (BufferOneElement != NULL);
> + ASSERT (ElementSize >= 1);
> +
> + if (Count < 2) {
> + 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 pivot is greater than the element.
This comment was rewritten, but semantically means the exact same thing
as before. The point is that the below code swaps also on equality (<*=*
0) as well.
Thanks for the changes!
Best regards,
Marvin
> + //
> + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0){
> + //
> + // swap
> + //
> + CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);
> + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, ElementSize);
> +
> + //
> + // increment NextSwapLocation
> + //
> + NextSwapLocation++;
> + }
> + }
> + //
> + // swap pivot to it's final position (NextSwapLocation)
> + //
> + CopyMem (BufferOneElement, Pivot, ElementSize);
> + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), BufferOneElement, ElementSize);
> +
> + //
> + // Now recurse on 2 partial lists. neither of these will have the 'pivot' element
> + // IE list is sorted left half, pivot element, sorted right half...
> + //
> + if (NextSwapLocation >= 2) {
> + QuickSort (
> + BufferToSort,
> + NextSwapLocation,
> + ElementSize,
> + CompareFunction,
> + BufferOneElement
> + );
> + }
> +
> + if ((Count - NextSwapLocation - 1) >= 2) {
> + QuickSort (
> + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
> + Count - NextSwapLocation - 1,
> + ElementSize,
> + CompareFunction,
> + BufferOneElement
> + );
> + }
> +}
> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> index eae1a7158d..d09bd12bef 100644
> --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> @@ -1,7 +1,7 @@
> ## @file
> # Base Library implementation for use with host based unit tests.
> #
> -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>
> +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
> # Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
> # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
> # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All rights reserved.<BR>
> @@ -33,6 +33,7 @@
> SwapBytes16.c
> LongJump.c
> SetJump.c
> + QuickSort.c
> RShiftU64.c
> RRotU64.c
> RRotU32.c
^ permalink raw reply [flat|nested] 4+ messages in thread