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

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

Hi Liming

The change "PATCH v6 1/3" is the same with "PATCH v3 1/3".

The difference between "v3 to v6" is on "PATCH v6 3/3"


Thanks,
Ian Kuo
-----Original Message-----
From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming
Sent: Wednesday, October 20, 2021 9:50 AM
To: Kuo, IanX <ianx.kuo@intel.com>; devel@edk2.groups.io
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Wang, Jian J <jian.j.wang@intel.com>
Subject: 回复: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib

What new change is made in new version patch?

Thanks
Liming
> -----邮件原件-----
> 发件人: Kuo, IanX <ianx.kuo@intel.com>
> 发送时间: 2021年10月19日 10:09
> 收件人: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>; Liming Gao 
> <gaoliming@byosoft.com.cn>
> 抄送: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Wang, 
> Jian J <jian.j.wang@intel.com>
> 主题: RE: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add 
> QuickSort function on BaseLib
> 
> @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] 
> -=-=-=-=-=-=
>