[PATCH v4 2/4] MdeModulePkg/SortLib: 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

Use QuickSort instead of QuickSortWorker

Cc: Ray Ni <ray.ni@intel.com>
Cc: Jian J Wang <jian.j.wang@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
 .../Library/BaseSortLib/BaseSortLib.c         | 117 +----------------
 .../Library/UefiSortLib/UefiSortLib.c         | 118 +-----------------
 2 files changed, 10 insertions(+), 225 deletions(-)

diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec..b33339ac7c 100644
--- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
+++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
@@ -1,7 +1,7 @@
 /** @file
   Library used for sorting routines.
 
-  Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>
+  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
   SPDX-License-Identifier: BSD-2-Clause-Patent
 
 **/
@@ -13,114 +13,6 @@
 #include <Library/MemoryAllocationLib.h>
 #include <Library/SortLib.h>
 
-/**
-  Worker function for QuickSorting.  This function is identical to PerformQuickSort,
-  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 Buffer is NULL, then ASSERT.
-
-  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] Buffer              Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-QuickSortWorker (
-  IN OUT VOID                           *BufferToSort,
-  IN CONST UINTN                        Count,
-  IN CONST UINTN                        ElementSize,
-  IN       SORT_COMPARE                 CompareFunction,
-  IN VOID                               *Buffer
-  )
-{
-  VOID        *Pivot;
-  UINTN       LoopCount;
-  UINTN       NextSwapLocation;
-
-  ASSERT(BufferToSort     != NULL);
-  ASSERT(CompareFunction  != NULL);
-  ASSERT(Buffer  != NULL);
-
-  if ( Count < 2
-    || ElementSize  < 1
-   ){
-    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 the pivot
-    //
-    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
-      //
-      // swap
-      //
-      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
-      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
-
-      //
-      // increment NextSwapLocation
-      //
-      NextSwapLocation++;
-    }
-  }
-  //
-  // swap pivot to it's final position (NextSwapLocaiton)
-  //
-  CopyMem (Buffer, Pivot, ElementSize);
-  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
-  //
-  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element
-  // IE list is sorted left half, pivot element, sorted right half...
-  //
-  if (NextSwapLocation >= 2) {
-    QuickSortWorker(
-      BufferToSort,
-      NextSwapLocation,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-
-  if ((Count - NextSwapLocation - 1) >= 2) {
-    QuickSortWorker(
-      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
-      Count - NextSwapLocation - 1,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-  return;
-}
 /**
   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 
@@ -156,12 +48,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);
   ASSERT(Buffer != NULL);
 
-  QuickSortWorker(
+  QuickSort (
     BufferToSort,
     Count,
     ElementSize,
-    CompareFunction,
-    Buffer);
+    (SORT_COMPARE) CompareFunction,
+    Buffer
+    );
 
   FreePool(Buffer);
   return;
diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
index 46dc443638..151a5a9ac3 100644
--- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
+++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
@@ -1,7 +1,7 @@
 /** @file
   Library used for sorting routines.
 
-  Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>
+  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
   SPDX-License-Identifier: BSD-2-Clause-Patent
 
 **/
@@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL   *mUnicodeCollation = NULL;
   }                                   \
 }
 
-/**
-  Worker function for QuickSorting.  This function is identical to PerformQuickSort,
-  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 Buffer is NULL, then ASSERT.
-
-  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] Buffer              Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-QuickSortWorker (
-  IN OUT VOID                           *BufferToSort,
-  IN CONST UINTN                        Count,
-  IN CONST UINTN                        ElementSize,
-  IN       SORT_COMPARE                 CompareFunction,
-  IN VOID                               *Buffer
-  )
-{
-  VOID        *Pivot;
-  UINTN       LoopCount;
-  UINTN       NextSwapLocation;
-
-  ASSERT(BufferToSort     != NULL);
-  ASSERT(CompareFunction  != NULL);
-  ASSERT(Buffer  != NULL);
-
-  if ( Count < 2
-    || ElementSize  < 1
-   ){
-    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 the pivot
-    //
-    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
-      //
-      // swap
-      //
-      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
-      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
-
-      //
-      // increment NextSwapLocation
-      //
-      NextSwapLocation++;
-    }
-  }
-  //
-  // swap pivot to it's final position (NextSwapLocaiton)
-  //
-  CopyMem (Buffer, Pivot, ElementSize);
-  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
-  //
-  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element
-  // IE list is sorted left half, pivot element, sorted right half...
-  //
-  if (NextSwapLocation >= 2) {
-    QuickSortWorker(
-      BufferToSort,
-      NextSwapLocation,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-
-  if ((Count - NextSwapLocation - 1) >= 2) {
-    QuickSortWorker(
-      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
-      Count - NextSwapLocation - 1,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-
-  return;
-}
 /**
   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 
@@ -173,12 +64,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);
   ASSERT(Buffer != NULL);
 
-  QuickSortWorker(
+  QuickSort (
     BufferToSort,
     Count,
     ElementSize,
-    CompareFunction,
-    Buffer);
+    (SORT_COMPARE) CompareFunction,
+    Buffer
+    );
 
   FreePool(Buffer);
   return;
-- 
2.30.0.windows.1