[PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib


IanX Kuo
 

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

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

Add QuickSort function into BaseLib

Cc: Ray Ni <ray.ni@intel.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
MdePkg/Include/Library/BaseLib.h | 49 ++++++++
MdePkg/Library/BaseLib/BaseLib.inf | 1 +
MdePkg/Library/BaseLib/QuickSort.c | 116 ++++++++++++++++++
.../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
4 files changed, 168 insertions(+), 1 deletion(-)
create mode 100644 MdePkg/Library/BaseLib/QuickSort.c

diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/Base=
Lib.h
index 2452c1d92e..0ae0f4e6af 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -2856,6 +2856,55 @@ RemoveEntryList (
//=0D
// Math Services=0D
//=0D
+/**=0D
+ Prototype for comparison function for any two element types.=0D
+=0D
+ @param[in] Buffer1 The pointer to first buffer.=0D
+ @param[in] Buffer2 The pointer to second buffer.=0D
+=0D
+ @retval 0 Buffer1 equal to Buffer2.=0D
+ @return <0 Buffer1 is less than Buffer2.=0D
+ @return >0 Buffer1 is greater than Buffer2.=0D
+**/=0D
+typedef=0D
+INTN=0D
+(EFIAPI *BASE_SORT_COMPARE)(=0D
+ IN CONST VOID *Buffer1,=0D
+ IN CONST VOID *Buffer2=0D
+ );=0D
+=0D
+/**=0D
+ This function is identical to perform QuickSort,=0D
+ except that is uses the pre-allocated buffer so the in place sorting doe=
s not need to=0D
+ allocate and free buffers constantly.=0D
+=0D
+ Each element must be equal sized.=0D
+=0D
+ if BufferToSort is NULL, then ASSERT.=0D
+ if CompareFunction is NULL, then ASSERT.=0D
+ if BufferOneElement is NULL, then ASSERT.=0D
+ if ElementSize is < 1, then ASSERT.=0D
+=0D
+ if Count is < 2 then perform no action.=0D
+=0D
+ @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele=
ments=0D
+ on return a buffer of sorted elements=0D
+ @param[in] Count the number of elements in the buffer to s=
ort=0D
+ @param[in] ElementSize Size of an element in bytes=0D
+ @param[in] CompareFunction The function to call to perform the compa=
rison=0D
+ of any 2 elements=0D
+ @param[out] BufferOneElement Caller provided buffer whose size equals =
to ElementSize.=0D
+ It's used by QuickSort() for swapping in =
sorting.=0D
+**/=0D
+VOID=0D
+EFIAPI=0D
+QuickSort (=0D
+ IN OUT VOID *BufferToSort,=0D
+ IN CONST UINTN Count,=0D
+ IN CONST UINTN ElementSize,=0D
+ IN BASE_SORT_COMPARE CompareFunction,=0D
+ OUT VOID *BufferOneElement=0D
+ );=0D
=0D
/**=0D
Shifts a 64-bit integer left between 0 and 63 bits. The low bits are fil=
led=0D
diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/Ba=
seLib.inf
index 6efa5315b6..cebda3b210 100644
--- a/MdePkg/Library/BaseLib/BaseLib.inf
+++ b/MdePkg/Library/BaseLib/BaseLib.inf
@@ -32,6 +32,7 @@
SwapBytes16.c=0D
LongJump.c=0D
SetJump.c=0D
+ QuickSort.c=0D
RShiftU64.c=0D
RRotU64.c=0D
RRotU32.c=0D
diff --git a/MdePkg/Library/BaseLib/QuickSort.c b/MdePkg/Library/BaseLib/Qu=
ickSort.c
new file mode 100644
index 0000000000..a825c072b0
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,116 @@
+/** @file=0D
+ Math worker functions.=0D
+=0D
+ Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>=0D
+ SPDX-License-Identifier: BSD-2-Clause-Patent=0D
+=0D
+**/=0D
+=0D
+#include "BaseLibInternals.h"=0D
+=0D
+/**=0D
+ This function is identical to perform QuickSort,=0D
+ except that is uses the pre-allocated buffer so the in place sorting doe=
s not need to=0D
+ allocate and free buffers constantly.=0D
+=0D
+ Each element must be equal sized.=0D
+=0D
+ if BufferToSort is NULL, then ASSERT.=0D
+ if CompareFunction is NULL, then ASSERT.=0D
+ if BufferOneElement is NULL, then ASSERT.=0D
+ if ElementSize is < 1, then ASSERT.=0D
+=0D
+ if Count is < 2 then perform no action.=0D
+=0D
+ @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele=
ments=0D
+ on return a buffer of sorted elements=0D
+ @param[in] Count the number of elements in the buffer to s=
ort=0D
+ @param[in] ElementSize Size of an element in bytes=0D
+ @param[in] CompareFunction The function to call to perform the compa=
rison=0D
+ of any 2 elements=0D
+ @param[out] BufferOneElement Caller provided buffer whose size equals =
to ElementSize.=0D
+ It's used by QuickSort() for swapping in =
sorting.=0D
+**/=0D
+VOID=0D
+EFIAPI=0D
+QuickSort (=0D
+ IN OUT VOID *BufferToSort,=0D
+ IN CONST UINTN Count,=0D
+ IN CONST UINTN ElementSize,=0D
+ IN BASE_SORT_COMPARE CompareFunction,=0D
+ OUT VOID *BufferOneElement=0D
+ )=0D
+{=0D
+ VOID *Pivot;=0D
+ UINTN LoopCount;=0D
+ UINTN NextSwapLocation;=0D
+=0D
+ ASSERT (BufferToSort !=3D NULL);=0D
+ ASSERT (CompareFunction !=3D NULL);=0D
+ ASSERT (BufferOneElement !=3D NULL);=0D
+ ASSERT (ElementSize >=3D 1);=0D
+=0D
+ if (Count < 2) {=0D
+ return;=0D
+ }=0D
+=0D
+ NextSwapLocation =3D 0;=0D
+=0D
+ //=0D
+ // pick a pivot (we choose last element)=0D
+ //=0D
+ Pivot =3D ((UINT8*) BufferToSort + ((Count - 1) * ElementSize));=0D
+=0D
+ //=0D
+ // Now get the pivot such that all on "left" are below it=0D
+ // and everything "right" are above it=0D
+ //=0D
+ for (LoopCount =3D 0; LoopCount < Count -1; LoopCount++) {=0D
+ //=0D
+ // if the element is less than or equal to the pivot=0D
+ //=0D
+ if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) * E=
lementSize)), Pivot) <=3D 0){=0D
+ //=0D
+ // swap=0D
+ //=0D
+ CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation=
* ElementSize), ElementSize);=0D
+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (=
UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);=0D
+ CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOn=
eElement, ElementSize);=0D
+=0D
+ //=0D
+ // increment NextSwapLocation=0D
+ //=0D
+ NextSwapLocation++;=0D
+ }=0D
+ }=0D
+ //=0D
+ // swap pivot to it's final position (NextSwapLocation)=0D
+ //=0D
+ CopyMem (BufferOneElement, Pivot, ElementSize);=0D
+ CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize)=
, ElementSize);=0D
+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), Buffe=
rOneElement, ElementSize);=0D
+=0D
+ //=0D
+ // Now recurse on 2 partial lists. neither of these will have the 'pivo=
t' element=0D
+ // IE list is sorted left half, pivot element, sorted right half...=0D
+ //=0D
+ if (NextSwapLocation >=3D 2) {=0D
+ QuickSort (=0D
+ BufferToSort,=0D
+ NextSwapLocation,=0D
+ ElementSize,=0D
+ CompareFunction,=0D
+ BufferOneElement=0D
+ );=0D
+ }=0D
+=0D
+ if ((Count - NextSwapLocation - 1) >=3D 2) {=0D
+ QuickSort (=0D
+ (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,=0D
+ Count - NextSwapLocation - 1,=0D
+ ElementSize,=0D
+ CompareFunction,=0D
+ BufferOneElement=0D
+ );=0D
+ }=0D
+}=0D
diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Librar=
y/BaseLib/UnitTestHostBaseLib.inf
index eae1a7158d..d09bd12bef 100644
--- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
+++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
@@ -1,7 +1,7 @@
## @file=0D
# Base Library implementation for use with host based unit tests.=0D
#=0D
-# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>=
=0D
+# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>=
=0D
# Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>=
=0D
# Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>=0D
# Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All righ=
ts reserved.<BR>=0D
@@ -33,6 +33,7 @@
SwapBytes16.c=0D
LongJump.c=0D
SetJump.c=0D
+ QuickSort.c=0D
RShiftU64.c=0D
RRotU64.c=0D
RRotU32.c=0D
--=20
2.30.0.windows.1

Join devel@edk2.groups.io to automatically receive all group messages.