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

["Michael D Kinney" <michael.d.kinney@intel.com>]

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]
> > -=-=-=-=-=-=
> >
> 
> 
> 
> 
> 
> 
>