[PATCH v7 1/1] 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            | 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