[edk2-devel] 回复: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
gaoliming
gaoliming at byosoft.com.cn
Wed Oct 13 01:04:21 UTC 2021
I have no other comments. Reviewed-by: Liming Gao <gaoliming at byosoft.com.cn>
> -----邮件原件-----
> 发件人: Kuo, IanX <ianx.kuo at intel.com>
> 发送时间: 2021年10月12日 11:51
> 收件人: Ni, Ray <ray.ni at intel.com>; devel at edk2.groups.io; Kinney, Michael
> D <michael.d.kinney at intel.com>; Liming Gao <gaoliming at byosoft.com.cn>
> 抄送: Chan, Amy <amy.chan at intel.com>; Liu, Zhiguang
> <zhiguang.liu at intel.com>
> 主题: RE: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort function on
> BaseLib
>
> @Liming Gao and @Kinney, Michael D
>
> May I get one of yours help for the reviewed from MdePkg maintainer side ?
> Have any concern, please also share for me.
>
> Thanks,
> Ian Kuo
>
> -----Original Message-----
> From: Ni, Ray <ray.ni at intel.com>
> Sent: Tuesday, October 12, 2021 10:22 AM
> To: Kuo, IanX <ianx.kuo at intel.com>; devel at edk2.groups.io
> Cc: Chan, Amy <amy.chan at intel.com>; Kinney, Michael D
> <michael.d.kinney at intel.com>; Liming Gao <gaoliming at byosoft.com.cn>; Liu,
> Zhiguang <zhiguang.liu at intel.com>
> Subject: RE: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort function on
> BaseLib
>
> Reviewed-by: Ray Ni <ray.ni at intel.com>
>
> Ian, please take the approval from maintainers of MdePkg as the formal
> approval.
>
> Thanks,
> Ray
>
> > -----Original Message-----
> > From: Kuo, IanX <ianx.kuo at intel.com>
> > Sent: Tuesday, October 12, 2021 8:06 AM
> > To: devel at edk2.groups.io
> > Cc: Chan, Amy <amy.chan at intel.com>; Ni, Ray <ray.ni at intel.com>; Kuo,
> > IanX <ianx.kuo at intel.com>; Kinney, Michael D
> > <michael.d.kinney at intel.com>; Liming Gao <gaoliming at byosoft.com.cn>;
> > Liu, Zhiguang <zhiguang.liu at intel.com>
> > Subject: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort function on
> > BaseLib
> >
> > From: IanX Kuo <ianx.kuo at intel.com>
> >
> > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
> >
> > Add QuickSort function into BaseLib
> >
> > Cc: Ray Ni <ray.ni at intel.com>
> > Cc: Michael D Kinney <michael.d.kinney at intel.com>
> > Cc: Liming Gao <gaoliming at byosoft.com.cn>
> > Cc: Zhiguang Liu <zhiguang.liu at intel.com>
> > Signed-off-by: IanX Kuo <ianx.kuo at 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..a825c072b0
> > --- /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 element is less than or equal to the pivot
> >
> > + //
> >
> > + 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 (#81841): https://edk2.groups.io/g/devel/message/81841
Mute This Topic: https://groups.io/mt/86278008/1813853
Group Owner: devel+owner at edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [edk2-devel-archive at redhat.com]
-=-=-=-=-=-=-=-=-=-=-=-
More information about the edk2-devel-archive
mailing list