4 Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
5 SPDX-License-Identifier: BSD-2-Clause-Patent
9 #include "BaseLibInternals.h"
12 This function is identical to perform QuickSort,
13 except that is uses the pre-allocated buffer so the in place sorting does not need to
14 allocate and free buffers constantly.
16 Each element must be equal sized.
18 if BufferToSort is NULL, then ASSERT.
19 if CompareFunction is NULL, then ASSERT.
20 if BufferOneElement is NULL, then ASSERT.
21 if ElementSize is < 1, then ASSERT.
23 if Count is < 2 then perform no action.
25 @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
26 on return a buffer of sorted elements
27 @param[in] Count the number of elements in the buffer to sort
28 @param[in] ElementSize Size of an element in bytes
29 @param[in] CompareFunction The function to call to perform the comparison
31 @param[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.
32 It's used by QuickSort() for swapping in sorting.
37 IN OUT VOID
*BufferToSort
,
39 IN CONST UINTN ElementSize
,
40 IN BASE_SORT_COMPARE CompareFunction
,
41 OUT VOID
*BufferOneElement
46 UINTN NextSwapLocation
;
48 ASSERT (BufferToSort
!= NULL
);
49 ASSERT (CompareFunction
!= NULL
);
50 ASSERT (BufferOneElement
!= NULL
);
51 ASSERT (ElementSize
>= 1);
60 // pick a pivot (we choose last element)
62 Pivot
= ((UINT8
*) BufferToSort
+ ((Count
- 1) * ElementSize
));
65 // Now get the pivot such that all on "left" are below it
66 // and everything "right" are above it
68 for (LoopCount
= 0; LoopCount
< Count
-1; LoopCount
++) {
70 // if the element is less than or equal to the pivot
72 if (CompareFunction ((VOID
*) ((UINT8
*) BufferToSort
+ ((LoopCount
) * ElementSize
)), Pivot
) <= 0){
76 CopyMem (BufferOneElement
, (UINT8
*) BufferToSort
+ (NextSwapLocation
* ElementSize
), ElementSize
);
77 CopyMem ((UINT8
*) BufferToSort
+ (NextSwapLocation
* ElementSize
), (UINT8
*) BufferToSort
+ ((LoopCount
) * ElementSize
), ElementSize
);
78 CopyMem ((UINT8
*) BufferToSort
+ ((LoopCount
)*ElementSize
), BufferOneElement
, ElementSize
);
81 // increment NextSwapLocation
87 // swap pivot to it's final position (NextSwapLocation)
89 CopyMem (BufferOneElement
, Pivot
, ElementSize
);
90 CopyMem (Pivot
, (UINT8
*) BufferToSort
+ (NextSwapLocation
* ElementSize
), ElementSize
);
91 CopyMem ((UINT8
*) BufferToSort
+ (NextSwapLocation
* ElementSize
), BufferOneElement
, ElementSize
);
94 // Now recurse on 2 partial lists. neither of these will have the 'pivot' element
95 // IE list is sorted left half, pivot element, sorted right half...
97 if (NextSwapLocation
>= 2) {
107 if ((Count
- NextSwapLocation
- 1) >= 2) {
109 (UINT8
*)BufferToSort
+ (NextSwapLocation
+ 1) * ElementSize
,
110 Count
- NextSwapLocation
- 1,