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>

diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec01c03dd629f6759869c2d2a1525aca..0903943ee4b090b602e95be58718c810dc9a0e70 100644 (file)
--- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
+++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
@@ -1,7 +1,7 @@
 /** @file\r
   Library used for sorting routines.\r
 \r
-  Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>\r
+  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>\r
   SPDX-License-Identifier: BSD-2-Clause-Patent\r
 \r
 **/\r
@@ -13,114 +13,6 @@
 #include <Library/MemoryAllocationLib.h>\r
 #include <Library/SortLib.h>\r
 \r
-/**\r
-  Worker function for QuickSorting.  This function is identical to PerformQuickSort,\r
-  except that is uses the pre-allocated buffer so the in place sorting does not need to\r
-  allocate and free buffers constantly.\r
-\r
-  Each element must be equal sized.\r
-\r
-  if BufferToSort is NULL, then ASSERT.\r
-  if CompareFunction is NULL, then ASSERT.\r
-  if Buffer is NULL, then ASSERT.\r
-\r
-  if Count is < 2 then perform no action.\r
-  if Size is < 1 then perform no action.\r
-\r
-  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements\r
-                                 on return a buffer of sorted elements\r
-  @param[in] Count               the number of elements in the buffer to sort\r
-  @param[in] ElementSize         Size of an element in bytes\r
-  @param[in] CompareFunction     The function to call to perform the comparison\r
-                                 of any 2 elements\r
-  @param[in] Buffer              Buffer of size ElementSize for use in swapping\r
-**/\r
-VOID\r
-EFIAPI\r
-QuickSortWorker (\r
-  IN OUT VOID                           *BufferToSort,\r
-  IN CONST UINTN                        Count,\r
-  IN CONST UINTN                        ElementSize,\r
-  IN       SORT_COMPARE                 CompareFunction,\r
-  IN VOID                               *Buffer\r
-  )\r
-{\r
-  VOID        *Pivot;\r
-  UINTN       LoopCount;\r
-  UINTN       NextSwapLocation;\r
-\r
-  ASSERT(BufferToSort     != NULL);\r
-  ASSERT(CompareFunction  != NULL);\r
-  ASSERT(Buffer  != NULL);\r
-\r
-  if ( Count < 2\r
-    || ElementSize  < 1\r
-   ){\r
-    return;\r
-  }\r
-\r
-  NextSwapLocation = 0;\r
-\r
-  //\r
-  // pick a pivot (we choose last element)\r
-  //\r
-  Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));\r
-\r
-  //\r
-  // Now get the pivot such that all on "left" are below it\r
-  // and everything "right" are above it\r
-  //\r
-  for ( LoopCount = 0\r
-      ; LoopCount < Count -1\r
-      ; LoopCount++\r
-     ){\r
-    //\r
-    // if the element is less than the pivot\r
-    //\r
-    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r
-      //\r
-      // swap\r
-      //\r
-      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
-      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);\r
-      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);\r
-\r
-      //\r
-      // increment NextSwapLocation\r
-      //\r
-      NextSwapLocation++;\r
-    }\r
-  }\r
-  //\r
-  // swap pivot to it's final position (NextSwapLocaiton)\r
-  //\r
-  CopyMem (Buffer, Pivot, ElementSize);\r
-  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
-  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);\r
-\r
-  //\r
-  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element\r
-  // IE list is sorted left half, pivot element, sorted right half...\r
-  //\r
-  if (NextSwapLocation >= 2) {\r
-    QuickSortWorker(\r
-      BufferToSort,\r
-      NextSwapLocation,\r
-      ElementSize,\r
-      CompareFunction,\r
-      Buffer);\r
-  }\r
-\r
-  if ((Count - NextSwapLocation - 1) >= 2) {\r
-    QuickSortWorker(\r
-      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,\r
-      Count - NextSwapLocation - 1,\r
-      ElementSize,\r
-      CompareFunction,\r
-      Buffer);\r
-  }\r
-  return;\r
-}\r
 /**\r
   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r
 \r
@@ -156,12 +48,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);\r
   ASSERT(Buffer != NULL);\r
 \r
-  QuickSortWorker(\r
+  QuickSort (\r
     BufferToSort,\r
     Count,\r
     ElementSize,\r
     CompareFunction,\r
-    Buffer);\r
+    Buffer\r
+    );\r
 \r
   FreePool(Buffer);\r
   return;\r

diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
index 46dc4436381ff1cc64db777ea6764b061b1c0377..29d8735c226f32c851ae926c15643eabea40b472 100644 (file)
--- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
+++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
@@ -1,7 +1,7 @@
 /** @file\r
   Library used for sorting routines.\r
 \r
-  Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>\r
+  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>\r
   SPDX-License-Identifier: BSD-2-Clause-Patent\r
 \r
 **/\r
@@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL   *mUnicodeCollation = NULL;
   }                                   \\r
 }\r
 \r
-/**\r
-  Worker function for QuickSorting.  This function is identical to PerformQuickSort,\r
-  except that is uses the pre-allocated buffer so the in place sorting does not need to\r
-  allocate and free buffers constantly.\r
-\r
-  Each element must be equal sized.\r
-\r
-  if BufferToSort is NULL, then ASSERT.\r
-  if CompareFunction is NULL, then ASSERT.\r
-  if Buffer is NULL, then ASSERT.\r
-\r
-  if Count is < 2 then perform no action.\r
-  if Size is < 1 then perform no action.\r
-\r
-  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements\r
-                                 on return a buffer of sorted elements\r
-  @param[in] Count               the number of elements in the buffer to sort\r
-  @param[in] ElementSize         Size of an element in bytes\r
-  @param[in] CompareFunction     The function to call to perform the comparison\r
-                                 of any 2 elements\r
-  @param[in] Buffer              Buffer of size ElementSize for use in swapping\r
-**/\r
-VOID\r
-EFIAPI\r
-QuickSortWorker (\r
-  IN OUT VOID                           *BufferToSort,\r
-  IN CONST UINTN                        Count,\r
-  IN CONST UINTN                        ElementSize,\r
-  IN       SORT_COMPARE                 CompareFunction,\r
-  IN VOID                               *Buffer\r
-  )\r
-{\r
-  VOID        *Pivot;\r
-  UINTN       LoopCount;\r
-  UINTN       NextSwapLocation;\r
-\r
-  ASSERT(BufferToSort     != NULL);\r
-  ASSERT(CompareFunction  != NULL);\r
-  ASSERT(Buffer  != NULL);\r
-\r
-  if ( Count < 2\r
-    || ElementSize  < 1\r
-   ){\r
-    return;\r
-  }\r
-\r
-  NextSwapLocation = 0;\r
-\r
-  //\r
-  // pick a pivot (we choose last element)\r
-  //\r
-  Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));\r
-\r
-  //\r
-  // Now get the pivot such that all on "left" are below it\r
-  // and everything "right" are above it\r
-  //\r
-  for ( LoopCount = 0\r
-      ; LoopCount < Count -1\r
-      ; LoopCount++\r
-     ){\r
-    //\r
-    // if the element is less than the pivot\r
-    //\r
-    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r
-      //\r
-      // swap\r
-      //\r
-      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
-      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);\r
-      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);\r
-\r
-      //\r
-      // increment NextSwapLocation\r
-      //\r
-      NextSwapLocation++;\r
-    }\r
-  }\r
-  //\r
-  // swap pivot to it's final position (NextSwapLocaiton)\r
-  //\r
-  CopyMem (Buffer, Pivot, ElementSize);\r
-  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
-  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);\r
-\r
-  //\r
-  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element\r
-  // IE list is sorted left half, pivot element, sorted right half...\r
-  //\r
-  if (NextSwapLocation >= 2) {\r
-    QuickSortWorker(\r
-      BufferToSort,\r
-      NextSwapLocation,\r
-      ElementSize,\r
-      CompareFunction,\r
-      Buffer);\r
-  }\r
-\r
-  if ((Count - NextSwapLocation - 1) >= 2) {\r
-    QuickSortWorker(\r
-      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,\r
-      Count - NextSwapLocation - 1,\r
-      ElementSize,\r
-      CompareFunction,\r
-      Buffer);\r
-  }\r
-\r
-  return;\r
-}\r
 /**\r
   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r
 \r
@@ -173,12 +64,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);\r
   ASSERT(Buffer != NULL);\r
 \r
-  QuickSortWorker(\r
+  QuickSort (\r
     BufferToSort,\r
     Count,\r
     ElementSize,\r
     CompareFunction,\r
-    Buffer);\r
+    Buffer\r
+    );\r
 \r
   FreePool(Buffer);\r
   return;\r