Re: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib

["IanX Kuo" <ianx.kuo@intel.com>]

@Liming Gao

Sorry to bother you. May I get your help for review by again ?

Thanks,
Ian Kuo

-----Original Message-----
From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of IanX Kuo
Sent: Monday, October 18, 2021 12:21 PM
To: devel@edk2.groups.io
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kuo, IanX <ianx.kuo@intel.com>; Wang, Jian J <jian.j.wang@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>
Subject: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib

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



-=-=-=-=-=-=
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#82204): https://edk2.groups.io/g/devel/message/82204
Mute This Topic: https://groups.io/mt/86406843/4830160
Group Owner: devel+owner@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [ianx.kuo@intel.com] -=-=-=-=-=-=