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

["IanX Kuo" <ianx.kuo@intel.com>]

I send Patch v9, have anyone free can help me for the reviewed by.
Patch v8 is "move SORT_COMPARE definition from MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h, and then let SortLib.h include BaseLib.h."

Patch v9 is rollback to Patch v7.

Thanks,
Ian Kuo
-----Original Message-----
From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming
Sent: Monday, October 11, 2021 9:21 AM
To: 'Marvin Häuser' <mhaeuser@posteo.de>; devel@edk2.groups.io; Kinney, Michael D <michael.d.kinney@intel.com>; Kuo, IanX <ianx.kuo@intel.com>
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Liu, Zhiguang <zhiguang.liu@intel.com>
Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib

Michael and Marvin:
  I understand your concern. I want to reduce the duplicated definition for the same function. I will not keep my idea if you are both OK to define BASE_SORT_COMPARE and SORT_COMPARE. 

Thanks
Liming
> -----邮件原件-----
> 发件人: Marvin Häuser <mhaeuser@posteo.de>
> 发送时间: 2021年10月9日 0:09
> 收件人: devel@edk2.groups.io; michael.d.kinney@intel.com; 
> gaoliming@byosoft.com.cn; Kuo, IanX <ianx.kuo@intel.com>
> 抄送: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Liu, 
> Zhiguang <zhiguang.liu@intel.com>
> 主题: Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort 
> function on BaseLib
> 
> 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]
> >>> -=-=-=-=-=-=
> >>>
> >>
> >>
> >>
> >>
> >>
> >>
> >
> >
> > 
> >
> >