[PATCH v5 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib

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

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            | 117 ++++++++++++++++++
 .../Library/BaseLib/UnitTestHostBaseLib.inf   |   3 +-
 4 files changed, 169 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..2423169be4 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -13,6 +13,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
 
 #ifndef __BASE_LIB__
 #define __BASE_LIB__
+#include <Uefi/UefiBaseType.h>
 
 //
 // Definitions for architecture-specific types
@@ -2856,6 +2857,54 @@ 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
+  );
+
+/**
+  Worker function for QuickSorting.  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 Count is < 2 then perform no action.
+  if Size is < 1 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 [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
+                                 It's used by QuickSort() for swapping in sorting.
+
+  @retval EFI_SUCCESS            The quick sort is finished.
+  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL, CompareFunction is NULL or Buffer is NULL
+**/
+EFI_STATUS
+EFIAPI
+QuickSort (
+  IN OUT VOID                           *BufferToSort,
+  IN CONST UINTN                        Count,
+  IN CONST UINTN                        ElementSize,
+  IN       BASE_SORT_COMPARE            CompareFunction,
+  IN 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..f95af9e238
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,117 @@
+/** @file
+  Math worker functions.
+
+  Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
+  SPDX-License-Identifier: BSD-2-Clause-Patent
+
+**/
+
+#include "BaseLibInternals.h"
+#include <Uefi/UefiBaseType.h>
+
+/**
+  Worker function for QuickSorting.  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 Count is < 2 then perform no action.
+  if Size is < 1 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 [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
+                                 It's used by QuickSort() for swapping in sorting.
+
+  @retval EFI_SUCCESS            The quick sort is finished.
+  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL, CompareFunction is NULL, or BufferOneElement is NULL
+
+**/
+EFI_STATUS
+EFIAPI
+QuickSort (
+  IN OUT VOID                           *BufferToSort,
+  IN CONST UINTN                        Count,
+  IN CONST UINTN                        ElementSize,
+  IN       BASE_SORT_COMPARE            CompareFunction,
+  IN VOID                               *BufferOneElement
+  )
+{
+  VOID        *Pivot;
+  UINTN       LoopCount;
+  UINTN       NextSwapLocation;
+
+  if ((BufferToSort == NULL) || (CompareFunction == NULL) || (BufferOneElement == NULL)) {
+    return EFI_INVALID_PARAMETER;
+  }
+
+  if (Count < 2 || ElementSize  < 1) {
+    return EFI_SUCCESS;
+  }
+
+  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 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
+      );
+  }
+  return EFI_SUCCESS;
+}
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