[edk2-devel] [PATCH v4 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
IanX Kuo
ianx.kuo at intel.com
Mon Oct 18 03:52:21 UTC 2021
From: IanX Kuo <ianx.kuo at intel.com>
REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
Use QuickSort instead of QuickSortWorker
Cc: Ray Ni <ray.ni at intel.com>
Cc: Jiewen Yao <jiewen.yao at intel.com>
Cc: Jian J Wang <jian.j.wang at intel.com>
Cc: Xiaoyu Lu <xiaoyux.lu at intel.com>
Cc: Guomin Jiang <guomin.jiang at intel.com>
Signed-off-by: IanX Kuo <ianx.kuo at 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
-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#82196): https://edk2.groups.io/g/devel/message/82196
Mute This Topic: https://groups.io/mt/86406508/1813853
Group Owner: devel+owner at edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [edk2-devel-archive at redhat.com]
-=-=-=-=-=-=-=-=-=-=-=-
More information about the edk2-devel-archive
mailing list