Re: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib

["Ni, Ray" <ray.ni@intel.com>]

Reviewed-by: Ray Ni <ray.ni@intel.com>

Ian, please take the approval from maintainers of MdePkg as the formal approval.

Thanks,
Ray

> -----Original Message-----
> From: Kuo, IanX <ianx.kuo@intel.com>
> Sent: Tuesday, October 12, 2021 8:06 AM
> To: devel@edk2.groups.io
> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kuo, IanX <ianx.kuo@intel.com>; Kinney, Michael D
> <michael.d.kinney@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>; Liu, Zhiguang <zhiguang.liu@intel.com>
> Subject: [PATCH v9 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