MdeModulePkg/SortLib: Add QuickSort function on BaseLib

REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675

Use QuickSort instead of QuickSortWorker

Cc: Ray Ni <ray.ni@intel.com>
Reviewed-by: Jian J Wang <jian.j.wang@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>

2 files changed, 8 insertions, 223 deletions

diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec..0903943ee4 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

 

 **/

@@ -14,114 +14,6 @@
 #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.

 

   Each element must be equal sized.

@@ -156,12 +48,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);

   ASSERT(Buffer != NULL);

 

-  QuickSortWorker(

+  QuickSort (

     BufferToSort,

     Count,

     ElementSize,

     CompareFunction,

-    Buffer);

+    Buffer

+    );

 

   FreePool(Buffer);

   return;

diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
index 46dc443638..29d8735c22 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

 

 **/

@@ -30,115 +30,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.

 

   Each element must be equal sized.

@@ -173,12 +64,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);

   ASSERT(Buffer != NULL);

 

-  QuickSortWorker(

+  QuickSort (

     BufferToSort,

     Count,

     ElementSize,

     CompareFunction,

-    Buffer);

+    Buffer

+    );

 

   FreePool(Buffer);

   return;