MdePkg/BaseLib: Add QuickSort function on BaseLib

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

Add QuickSort function into BaseLib

Reviewed-by: Ray Ni <ray.ni@intel.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Reviewed-by: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>

diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/BaseLib.h
index 2452c1d92e511920d594be8f910d15c8fab9341f..0ae0f4e6af5ed1a8d5178dce238173871e9e0c7f 100644 (file)
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -2856,6 +2856,55 @@ RemoveEntryList (
 //\r
 // Math Services\r
 //\r
+/**\r
+  Prototype for comparison function for any two element types.\r
+\r
+  @param[in] Buffer1                  The pointer to first buffer.\r
+  @param[in] Buffer2                  The pointer to second buffer.\r
+\r
+  @retval 0                           Buffer1 equal to Buffer2.\r
+  @return <0                          Buffer1 is less than Buffer2.\r
+  @return >0                          Buffer1 is greater than Buffer2.\r
+**/\r
+typedef\r
+INTN\r
+(EFIAPI *BASE_SORT_COMPARE)(\r
+  IN CONST VOID                 *Buffer1,\r
+  IN CONST VOID                 *Buffer2\r
+  );\r
+\r
+/**\r
+  This function is identical to perform QuickSort,\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 BufferOneElement is NULL, then ASSERT.\r
+  if ElementSize is < 1, then ASSERT.\r
+\r
+  if Count is < 2 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[out] BufferOneElement   Caller provided buffer whose size equals to ElementSize.\r
+                                 It's used by QuickSort() for swapping in sorting.\r
+**/\r
+VOID\r
+EFIAPI\r
+QuickSort (\r
+  IN OUT VOID                           *BufferToSort,\r
+  IN CONST UINTN                        Count,\r
+  IN CONST UINTN                        ElementSize,\r
+  IN       BASE_SORT_COMPARE            CompareFunction,\r
+  OUT VOID                              *BufferOneElement\r
+  );\r
 \r
 /**\r
   Shifts a 64-bit integer left between 0 and 63 bits. The low bits are filled\r

diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/BaseLib.inf
index 6efa5315b653bb3c8e5101aebb5127db1cb4975e..cebda3b210c1fe1bd73fd02e6e0fbe96d335faf0 100644 (file)
--- a/MdePkg/Library/BaseLib/BaseLib.inf
+++ b/MdePkg/Library/BaseLib/BaseLib.inf
@@ -32,6 +32,7 @@
   SwapBytes16.c\r
   LongJump.c\r
   SetJump.c\r
+  QuickSort.c\r
   RShiftU64.c\r
   RRotU64.c\r
   RRotU32.c\r

diff --git a/MdePkg/Library/BaseLib/QuickSort.c b/MdePkg/Library/BaseLib/QuickSort.c
new file mode 100644 (file)
index 0000000..a825c07
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,116 @@
+/** @file\r
+  Math worker functions.\r
+\r
+  Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>\r
+  SPDX-License-Identifier: BSD-2-Clause-Patent\r
+\r
+**/\r
+\r
+#include "BaseLibInternals.h"\r
+\r
+/**\r
+  This function is identical to perform QuickSort,\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 BufferOneElement is NULL, then ASSERT.\r
+  if ElementSize is < 1, then ASSERT.\r
+\r
+  if Count is < 2 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[out] BufferOneElement   Caller provided buffer whose size equals to ElementSize.\r
+                                 It's used by QuickSort() for swapping in sorting.\r
+**/\r
+VOID\r
+EFIAPI\r
+QuickSort (\r
+  IN OUT VOID                           *BufferToSort,\r
+  IN CONST UINTN                        Count,\r
+  IN CONST UINTN                        ElementSize,\r
+  IN       BASE_SORT_COMPARE            CompareFunction,\r
+  OUT VOID                              *BufferOneElement\r
+  )\r
+{\r
+  VOID        *Pivot;\r
+  UINTN       LoopCount;\r
+  UINTN       NextSwapLocation;\r
+\r
+  ASSERT (BufferToSort     != NULL);\r
+  ASSERT (CompareFunction  != NULL);\r
+  ASSERT (BufferOneElement != NULL);\r
+  ASSERT (ElementSize      >= 1);\r
+\r
+  if (Count < 2) {\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; LoopCount < Count -1; LoopCount++) {\r
+    //\r
+    // if the element is less than or equal to the pivot\r
+    //\r
+    if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0){\r
+      //\r
+      // swap\r
+      //\r
+      CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);\r
+      CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);\r
+      CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, ElementSize);\r
+\r
+      //\r
+      // increment NextSwapLocation\r
+      //\r
+      NextSwapLocation++;\r
+    }\r
+  }\r
+  //\r
+  // swap pivot to it's final position (NextSwapLocation)\r
+  //\r
+  CopyMem (BufferOneElement, Pivot, ElementSize);\r
+  CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);\r
+  CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), BufferOneElement, ElementSize);\r
+\r
+  //\r
+  // Now recurse on 2 partial 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
+    QuickSort (\r
+      BufferToSort,\r
+      NextSwapLocation,\r
+      ElementSize,\r
+      CompareFunction,\r
+      BufferOneElement\r
+      );\r
+  }\r
+\r
+  if ((Count - NextSwapLocation - 1) >= 2) {\r
+    QuickSort (\r
+      (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,\r
+      Count - NextSwapLocation - 1,\r
+      ElementSize,\r
+      CompareFunction,\r
+      BufferOneElement\r
+      );\r
+  }\r
+}\r

diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
index eae1a7158d73b793e17ae803889ff1170f3d373d..d09bd12bef19dcd994ce89f0045ca887478a12c0 100644 (file)
--- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
+++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
@@ -1,7 +1,7 @@
 ## @file\r
 #  Base Library implementation for use with host based unit tests.\r
 #\r
-#  Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>\r
+#  Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>\r
 #  Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>\r
 #  Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>\r
 #  Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All rights reserved.<BR>\r
@@ -33,6 +33,7 @@
   SwapBytes16.c\r
   LongJump.c\r
   SetJump.c\r
+  QuickSort.c\r
   RShiftU64.c\r
   RRotU64.c\r
   RRotU32.c\r