[PATCH v4 0/3] Add function QuickSort into MdePkg/BaseLib

[PATCH v4 0/3] Add function QuickSort into MdePkg/BaseLib

[IanX Kuo]

From: IanX Kuo <ianx.kuo@intel.com>

1. MdeModulePkg/SortLib: Use QuickSort instead of QuickSortWorker
1-1: Drop cast (V2)

2. CryptLib/CryptLib: Remove duplicate QuickSortWorker
2-1: Drop cast (V3)

3. CpuCacheInfoLib: Remove MdeModulePkg dependency
3-1: Drop cast (V2)
3-2: Add runtime check (V2)
3-3: Drop assert check (V3)
3-4: Remove allocate pool (V4)

IanX Kuo (3):
  MdeModulePkg/SortLib: Add QuickSort function on BaseLib
  CryptoPkg/CryptLib: Add QuickSort function on BaseLib
  UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib

 .../Library/BaseCryptLib/SysCall/CrtWrapper.c |  92 +-------------
 .../Library/BaseSortLib/BaseSortLib.c         | 115 +----------------
 .../Library/UefiSortLib/UefiSortLib.c         | 116 +-----------------
 .../Library/CpuCacheInfoLib/CpuCacheInfoLib.c |   3 +-
 .../CpuCacheInfoLib/DxeCpuCacheInfoLib.inf    |   2 -
 .../CpuCacheInfoLib/InternalCpuCacheInfoLib.h |   1 -
 .../CpuCacheInfoLib/PeiCpuCacheInfoLib.inf    |   2 -
 7 files changed, 12 insertions(+), 319 deletions(-)

-- 
2.30.0.windows.1

[PATCH v4 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib

[IanX Kuo]

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         | 115 +----------------
 .../Library/UefiSortLib/UefiSortLib.c         | 116 +-----------------
 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
 
 **/
@@ -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);
+    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
 
 **/
@@ -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);
+    Buffer
+    );
 
   FreePool(Buffer);
   return;
-- 
2.30.0.windows.1

[PATCH v4 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib

[IanX Kuo]

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: Jiewen Yao <jiewen.yao@intel.com>
Cc: Jian J Wang <jian.j.wang@intel.com>
Cc: Xiaoyu Lu <xiaoyux.lu@intel.com>
Cc: Guomin Jiang <guomin.jiang@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
 .../Library/BaseCryptLib/SysCall/CrtWrapper.c | 92 +------------------
 1 file changed, 2 insertions(+), 90 deletions(-)

diff --git a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
index 42235ab96a..33ff0fcdb6 100644
--- a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
+++ b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
@@ -2,7 +2,7 @@
   C Run-Time Libraries (CRT) Wrapper Implementation for OpenSSL-based
   Cryptographic Library.
 
-Copyright (c) 2009 - 2017, Intel Corporation. All rights reserved.<BR>
+Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.<BR>
 SPDX-License-Identifier: BSD-2-Clause-Patent
 
 **/
@@ -22,91 +22,6 @@ int
   IN  VOID  *Buffer2
   );
 
-//
-// Duplicated from EDKII BaseSortLib for qsort() wrapper
-//
-STATIC
-VOID
-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 its final position (NextSwapLocation)
-  //
-  CopyMem (Buffer, Pivot, ElementSize);
-  CopyMem (Pivot, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
-  CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), Buffer, 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...
-  //
-  QuickSortWorker (
-    BufferToSort,
-    NextSwapLocation,
-    ElementSize,
-    CompareFunction,
-    Buffer
-    );
-
-  QuickSortWorker (
-    (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
-    Count - NextSwapLocation - 1,
-    ElementSize,
-    CompareFunction,
-    Buffer
-    );
-
-  return;
-}
-
 //---------------------------------------------------------
 // Standard C Run-time Library Interface Wrapper
 //---------------------------------------------------------
@@ -337,10 +252,7 @@ void qsort (void *base, size_t num, size_t width, int (*compare)(const void *, c
   Buffer = malloc (width);
   ASSERT (Buffer != NULL);
 
-  //
-  // Re-use PerformQuickSort() function Implementation in EDKII BaseSortLib.
-  //
-  QuickSortWorker (base, (UINTN)num, (UINTN)width, (SORT_COMPARE)compare, Buffer);
+  QuickSort (base, (UINTN)num, (UINTN)width, compare, Buffer);
 
   free (Buffer);
   return;
-- 
2.30.0.windows.1

[PATCH v4 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib

[IanX Kuo]

From: IanX Kuo <ianx.kuo@intel.com>

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

Remove MdeModulePkg dependency

Cc: Eric Dong <eric.dong@intel.com>
Cc: Ray Ni <ray.ni@intel.com>
Cc: Rahul Kumar <rahul1.kumar@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
 UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c         | 3 ++-
 UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf    | 2 --
 UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 -
 UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf    | 2 --
 4 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
index c0077d6770..d101f8a802 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
@@ -282,6 +282,7 @@ CpuCacheInfoCollectCpuCacheInfoData (
   UINTN                     LocalCacheInfoCount;
   UINTN                     Index;
   UINTN                     NextIndex;
+  CPU_CACHE_INFO            QuickSortBuffer;
 
   //
   // Get number of Packages and Package ID.
@@ -369,7 +370,7 @@ CpuCacheInfoCollectCpuCacheInfoData (
     //
     // Sort LocalCacheInfo array by CPU package ID, core type, cache level and cache type.
     //
-    PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare);
+    QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), CpuCacheInfoCompare, &QuickSortBuffer);
     CopyMem (CacheInfo, LocalCacheInfo, sizeof (*CacheInfo) * LocalCacheInfoCount);
     DEBUG_CODE (
       CpuCacheInfoPrintCpuCacheInfoTable (CacheInfo, LocalCacheInfoCount);
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
index c3d3f1e799..fdd79970f9 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
@@ -25,7 +25,6 @@
 
 [Packages]
   MdePkg/MdePkg.dec
-  MdeModulePkg/MdeModulePkg.dec
   UefiCpuPkg/UefiCpuPkg.dec
 
 [LibraryClasses]
@@ -34,7 +33,6 @@
   BaseMemoryLib
   MemoryAllocationLib
   UefiBootServicesTableLib
-  SortLib
 
 [Protocols]
   gEfiMpServiceProtocolGuid
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
index 26e1f46516..829a9f43ce 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
@@ -17,7 +17,6 @@
 #include <Library/DebugLib.h>
 #include <Library/BaseMemoryLib.h>
 #include <Library/MemoryAllocationLib.h>
-#include <Library/SortLib.h>
 #include <Library/CpuCacheInfoLib.h>
 
 typedef union {
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
index 0864497849..c643fc89be 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
@@ -25,7 +25,6 @@
 
 [Packages]
   MdePkg/MdePkg.dec
-  MdeModulePkg/MdeModulePkg.dec
   UefiCpuPkg/UefiCpuPkg.dec
 
 [LibraryClasses]
@@ -34,7 +33,6 @@
   BaseMemoryLib
   MemoryAllocationLib
   PeiServicesTablePointerLib
-  SortLib
 
 [Ppis]
   gEdkiiPeiMpServices2PpiGuid
-- 
2.30.0.windows.1