Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib

["Marvin Häuser" <mhaeuser@posteo.de>]

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@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming
>> Sent: Thursday, October 7, 2021 7:16 PM
>> To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>
>> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kinney, Michael D <michael.d.kinney@intel.com>; Liu,
>> Zhiguang <zhiguang.liu@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@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo
>>> 发送时间: 2021年10月8日 8:27
>>> 收件人: devel@edk2.groups.io
>>> 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo
>>> <ianx.kuo@intel.com>; Michael D Kinney <michael.d.kinney@intel.com>;
>>> Liming Gao <gaoliming@byosoft.com.cn>; Zhiguang Liu
>>> <zhiguang.liu@intel.com>
>>> 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function
>>> on BaseLib
>>>
>>> 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..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@edk2.groups.io
>>> Unsubscribe: https://edk2.groups.io/g/devel/unsub
>>> [gaoliming@byosoft.com.cn]
>>> -=-=-=-=-=-=
>>>
>>
>>
>>
>>
>>
>>
>
>
> 
>
>