diff options
| author | IanX Kuo <ianx.kuo@intel.com> | 2021-10-12 08:05:31 +0800 |
|---|---|---|
| committer | mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> | 2021-10-13 02:37:37 +0000 |
| commit | 4225a464c6daff979330c20387ade21fff85690e (patch) | |
| tree | 75eab73bced9a4e76748ffe3c3238e06aa4c767b /MdePkg | |
| parent | f22feb0e3b3f08b95201b258b104c45a2acef71f (diff) | |
| download | edk2-4225a464c6daff979330c20387ade21fff85690e.tar.gz edk2-4225a464c6daff979330c20387ade21fff85690e.tar.bz2 edk2-4225a464c6daff979330c20387ade21fff85690e.zip | |
MdePkg/BaseLib: Add QuickSort function on BaseLib
REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
Add QuickSort function into BaseLib
Reviewed-by: Ray Ni <ray.ni@intel.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Reviewed-by: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
Diffstat (limited to 'MdePkg')
| -rw-r--r-- | MdePkg/Include/Library/BaseLib.h | 49 | ||||
| -rw-r--r-- | MdePkg/Library/BaseLib/BaseLib.inf | 1 | ||||
| -rw-r--r-- | MdePkg/Library/BaseLib/QuickSort.c | 116 | ||||
| -rw-r--r-- | MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf | 3 |
4 files changed, 168 insertions, 1 deletions
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
|