回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib


gaoliming
 

Kuo:
I suggest to move SORT_COMPARE definition from
MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h,
and then let SortLib.h include BaseLib.h.

Thanks
Liming
-----邮件原件-----
发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo
发送时间: 2021年10月8日 8:27
收件人: devel@edk2.groups.io
抄送: amy.chan@...; ray.ni@...; IanX Kuo
<ianx.kuo@...>; Michael D Kinney <michael.d.kinney@...>;
Liming Gao <gaoliming@...>; Zhiguang Liu
<zhiguang.liu@...>
主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function
on BaseLib

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

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

Add QuickSort function into BaseLib

Cc: Ray Ni <ray.ni@...>
Cc: Michael D Kinney <michael.d.kinney@...>
Cc: Liming Gao <gaoliming@...>
Cc: Zhiguang Liu <zhiguang.liu@...>
Signed-off-by: IanX Kuo <ianx.kuo@...>
---
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/BaseLib.h
index 2452c1d92e..0ae0f4e6af 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -2856,6 +2856,55 @@ RemoveEntryList (
//

// Math Services

//

+/**

+ Prototype for comparison function for any two element types.

+

+ @param[in] Buffer1 The pointer to first buffer.

+ @param[in] Buffer2 The pointer to second buffer.

+

+ @retval 0 Buffer1 equal to Buffer2.

+ @return <0 Buffer1 is less than Buffer2.

+ @return >0 Buffer1 is greater than
Buffer2.

+**/

+typedef

+INTN

+(EFIAPI *BASE_SORT_COMPARE)(

+ IN CONST VOID *Buffer1,

+ IN CONST VOID *Buffer2

+ );

+

+/**

+ This function is identical to perform QuickSort,

+ 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 BufferOneElement is NULL, then ASSERT.

+ if ElementSize is < 1, then ASSERT.

+

+ if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size
equals to ElementSize.

+ It's used by QuickSort() for
swapping in sorting.

+**/

+VOID

+EFIAPI

+QuickSort (

+ IN OUT VOID *BufferToSort,

+ IN CONST UINTN Count,

+ IN CONST UINTN ElementSize,

+ IN BASE_SORT_COMPARE CompareFunction,

+ OUT VOID *BufferOneElement

+ );



/**

Shifts a 64-bit integer left between 0 and 63 bits. The low bits are
filled

diff --git a/MdePkg/Library/BaseLib/BaseLib.inf
b/MdePkg/Library/BaseLib/BaseLib.inf
index 6efa5315b6..cebda3b210 100644
--- a/MdePkg/Library/BaseLib/BaseLib.inf
+++ b/MdePkg/Library/BaseLib/BaseLib.inf
@@ -32,6 +32,7 @@
SwapBytes16.c

LongJump.c

SetJump.c

+ QuickSort.c

RShiftU64.c

RRotU64.c

RRotU32.c

diff --git a/MdePkg/Library/BaseLib/QuickSort.c
b/MdePkg/Library/BaseLib/QuickSort.c
new file mode 100644
index 0000000000..a825c072b0
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,116 @@
+/** @file

+ Math worker functions.

+

+ Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>

+ SPDX-License-Identifier: BSD-2-Clause-Patent

+

+**/

+

+#include "BaseLibInternals.h"

+

+/**

+ This function is identical to perform QuickSort,

+ 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 BufferOneElement is NULL, then ASSERT.

+ if ElementSize is < 1, then ASSERT.

+

+ if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size
equals to ElementSize.

+ It's used by QuickSort() for
swapping in sorting.

+**/

+VOID

+EFIAPI

+QuickSort (

+ IN OUT VOID *BufferToSort,

+ IN CONST UINTN Count,

+ IN CONST UINTN ElementSize,

+ IN BASE_SORT_COMPARE CompareFunction,

+ OUT VOID *BufferOneElement

+ )

+{

+ VOID *Pivot;

+ UINTN LoopCount;

+ UINTN NextSwapLocation;

+

+ ASSERT (BufferToSort != NULL);

+ ASSERT (CompareFunction != NULL);

+ ASSERT (BufferOneElement != NULL);

+ ASSERT (ElementSize >= 1);

+

+ if (Count < 2) {

+ 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 or equal to the pivot

+ //

+ if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) *
ElementSize)), Pivot) <= 0){

+ //

+ // swap

+ //

+ CopyMem (BufferOneElement, (UINT8*) BufferToSort +
(NextSwapLocation * ElementSize), ElementSize);

+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation *
ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize),
ElementSize);

+ CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize),
BufferOneElement, ElementSize);

+

+ //

+ // increment NextSwapLocation

+ //

+ NextSwapLocation++;

+ }

+ }

+ //

+ // swap pivot to it's final position (NextSwapLocation)

+ //

+ CopyMem (BufferOneElement, Pivot, ElementSize);

+ CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation *
ElementSize), ElementSize);

+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize),
BufferOneElement, 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...

+ //

+ if (NextSwapLocation >= 2) {

+ QuickSort (

+ BufferToSort,

+ NextSwapLocation,

+ ElementSize,

+ CompareFunction,

+ BufferOneElement

+ );

+ }

+

+ if ((Count - NextSwapLocation - 1) >= 2) {

+ QuickSort (

+ (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,

+ Count - NextSwapLocation - 1,

+ ElementSize,

+ CompareFunction,

+ BufferOneElement

+ );

+ }

+}

diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
index eae1a7158d..d09bd12bef 100644
--- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
+++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
@@ -1,7 +1,7 @@
## @file

# Base Library implementation for use with host based unit tests.

#

-# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>

+# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>

# Portions copyright (c) 2008 - 2009, Apple Inc. All rights
reserved.<BR>

# Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>

# Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All
rights reserved.<BR>

@@ -33,6 +33,7 @@
SwapBytes16.c

LongJump.c

SetJump.c

+ QuickSort.c

RShiftU64.c

RRotU64.c

RRotU32.c

--
2.30.0.windows.1



-=-=-=-=-=-=
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#81615): https://edk2.groups.io/g/devel/message/81615
Mute This Topic: https://groups.io/mt/86159728/4905953
Group Owner: devel+owner@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub
[gaoliming@...]
-=-=-=-=-=-=

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