[edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
Marvin Häuser
mhaeuser at posteo.de
Fri Oct 8 16:09:14 UTC 2021
Hey all,
I also don't think it makes much logical sense. They are distinct APIs
in separate libraries that happen to take a function with the same
prototype.
I think the patches look good now, thanks!
Best regards,
Marvin
On 08/10/2021 17:46, Michael D Kinney wrote:
> Hi Liming,
>
> In general it is not a good idea to include a library include file from another library include file.
>
> This becomes a hidden dependency.
>
> Mike
>
>> -----Original Message-----
>> From: devel at edk2.groups.io <devel at edk2.groups.io> On Behalf Of gaoliming
>> Sent: Thursday, October 7, 2021 7:16 PM
>> 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>; Kinney, Michael D <michael.d.kinney at intel.com>; Liu,
>> Zhiguang <zhiguang.liu at intel.com>
>> Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
>>
>> Kuo:
>> I suggest to move SORT_COMPARE definition from
>> MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h,
>> and then let SortLib.h include BaseLib.h.
>>
>> Thanks
>> Liming
>>> -----邮件原件-----
>>> 发件人: devel at edk2.groups.io <devel at edk2.groups.io> 代表 IanX Kuo
>>> 发送时间: 2021年10月8日 8:27
>>> 收件人: devel at edk2.groups.io
>>> 抄送: amy.chan at intel.com; ray.ni at intel.com; IanX Kuo
>>> <ianx.kuo at intel.com>; Michael D Kinney <michael.d.kinney at intel.com>;
>>> Liming Gao <gaoliming at byosoft.com.cn>; Zhiguang Liu
>>> <zhiguang.liu at intel.com>
>>> 主题: [edk2-devel] [PATCH v7 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 (#81615): https://edk2.groups.io/g/devel/message/81615
>>> Mute This Topic: https://groups.io/mt/86159728/4905953
>>> Group Owner: devel+owner at edk2.groups.io
>>> Unsubscribe: https://edk2.groups.io/g/devel/unsub
>>> [gaoliming at byosoft.com.cn]
>>> -=-=-=-=-=-=
>>>
>>
>>
>>
>>
>>
>>
>
>
>
>
>
-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#81716): https://edk2.groups.io/g/devel/message/81716
Mute This Topic: https://groups.io/mt/86173594/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