]>
Commit | Line | Data |
---|---|---|
4225a464 IK |
1 | /** @file\r |
2 | Math worker functions.\r | |
3 | \r | |
4 | Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>\r | |
5 | SPDX-License-Identifier: BSD-2-Clause-Patent\r | |
6 | \r | |
7 | **/\r | |
8 | \r | |
9 | #include "BaseLibInternals.h"\r | |
10 | \r | |
11 | /**\r | |
12 | This function is identical to perform QuickSort,\r | |
13 | except that is uses the pre-allocated buffer so the in place sorting does not need to\r | |
14 | allocate and free buffers constantly.\r | |
15 | \r | |
16 | Each element must be equal sized.\r | |
17 | \r | |
18 | if BufferToSort is NULL, then ASSERT.\r | |
19 | if CompareFunction is NULL, then ASSERT.\r | |
20 | if BufferOneElement is NULL, then ASSERT.\r | |
21 | if ElementSize is < 1, then ASSERT.\r | |
22 | \r | |
23 | if Count is < 2 then perform no action.\r | |
24 | \r | |
25 | @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r | |
26 | on return a buffer of sorted elements\r | |
27 | @param[in] Count the number of elements in the buffer to sort\r | |
28 | @param[in] ElementSize Size of an element in bytes\r | |
29 | @param[in] CompareFunction The function to call to perform the comparison\r | |
30 | of any 2 elements\r | |
31 | @param[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.\r | |
32 | It's used by QuickSort() for swapping in sorting.\r | |
33 | **/\r | |
34 | VOID\r | |
35 | EFIAPI\r | |
36 | QuickSort (\r | |
2f88bd3a MK |
37 | IN OUT VOID *BufferToSort,\r |
38 | IN CONST UINTN Count,\r | |
39 | IN CONST UINTN ElementSize,\r | |
40 | IN BASE_SORT_COMPARE CompareFunction,\r | |
41 | OUT VOID *BufferOneElement\r | |
4225a464 IK |
42 | )\r |
43 | {\r | |
2f88bd3a MK |
44 | VOID *Pivot;\r |
45 | UINTN LoopCount;\r | |
46 | UINTN NextSwapLocation;\r | |
4225a464 IK |
47 | \r |
48 | ASSERT (BufferToSort != NULL);\r | |
49 | ASSERT (CompareFunction != NULL);\r | |
50 | ASSERT (BufferOneElement != NULL);\r | |
51 | ASSERT (ElementSize >= 1);\r | |
52 | \r | |
53 | if (Count < 2) {\r | |
54 | return;\r | |
55 | }\r | |
56 | \r | |
57 | NextSwapLocation = 0;\r | |
58 | \r | |
59 | //\r | |
60 | // pick a pivot (we choose last element)\r | |
61 | //\r | |
2f88bd3a | 62 | Pivot = ((UINT8 *)BufferToSort + ((Count - 1) * ElementSize));\r |
4225a464 IK |
63 | \r |
64 | //\r | |
65 | // Now get the pivot such that all on "left" are below it\r | |
66 | // and everything "right" are above it\r | |
67 | //\r | |
68 | for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {\r | |
69 | //\r | |
70 | // if the element is less than or equal to the pivot\r | |
71 | //\r | |
2f88bd3a | 72 | if (CompareFunction ((VOID *)((UINT8 *)BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0) {\r |
4225a464 IK |
73 | //\r |
74 | // swap\r | |
75 | //\r | |
2f88bd3a MK |
76 | CopyMem (BufferOneElement, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);\r |
77 | CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), (UINT8 *)BufferToSort + ((LoopCount) * ElementSize), ElementSize);\r | |
78 | CopyMem ((UINT8 *)BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, ElementSize);\r | |
4225a464 IK |
79 | \r |
80 | //\r | |
81 | // increment NextSwapLocation\r | |
82 | //\r | |
83 | NextSwapLocation++;\r | |
84 | }\r | |
85 | }\r | |
2f88bd3a | 86 | \r |
4225a464 IK |
87 | //\r |
88 | // swap pivot to it's final position (NextSwapLocation)\r | |
89 | //\r | |
90 | CopyMem (BufferOneElement, Pivot, ElementSize);\r | |
2f88bd3a MK |
91 | CopyMem (Pivot, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);\r |
92 | CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), BufferOneElement, ElementSize);\r | |
4225a464 IK |
93 | \r |
94 | //\r | |
95 | // Now recurse on 2 partial lists. neither of these will have the 'pivot' element\r | |
96 | // IE list is sorted left half, pivot element, sorted right half...\r | |
97 | //\r | |
98 | if (NextSwapLocation >= 2) {\r | |
99 | QuickSort (\r | |
100 | BufferToSort,\r | |
101 | NextSwapLocation,\r | |
102 | ElementSize,\r | |
103 | CompareFunction,\r | |
104 | BufferOneElement\r | |
105 | );\r | |
106 | }\r | |
107 | \r | |
108 | if ((Count - NextSwapLocation - 1) >= 2) {\r | |
109 | QuickSort (\r | |
110 | (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,\r | |
111 | Count - NextSwapLocation - 1,\r | |
112 | ElementSize,\r | |
113 | CompareFunction,\r | |
114 | BufferOneElement\r | |
115 | );\r | |
116 | }\r | |
117 | }\r |