]>
Commit | Line | Data |
---|---|---|
4983ca93 | 1 | /** @file\r |
2 | Library used for sorting routines.\r | |
3 | \r | |
a653a525 | 4 | Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>\r |
9d510e61 | 5 | SPDX-License-Identifier: BSD-2-Clause-Patent\r |
4983ca93 | 6 | \r |
7 | **/\r | |
4983ca93 | 8 | #include <Uefi.h>\r |
9 | \r | |
10 | #include <Library/BaseLib.h>\r | |
11 | #include <Library/BaseMemoryLib.h>\r | |
12 | #include <Library/DebugLib.h>\r | |
13 | #include <Library/MemoryAllocationLib.h>\r | |
1e6e84c7 | 14 | #include <Library/SortLib.h>\r |
4983ca93 | 15 | \r |
16 | /**\r | |
1e6e84c7 | 17 | Worker function for QuickSorting. This function is identical to PerformQuickSort,\r |
18 | except that is uses the pre-allocated buffer so the in place sorting does not need to\r | |
4983ca93 | 19 | allocate and free buffers constantly.\r |
20 | \r | |
21 | Each element must be equal sized.\r | |
22 | \r | |
23 | if BufferToSort is NULL, then ASSERT.\r | |
24 | if CompareFunction is NULL, then ASSERT.\r | |
25 | if Buffer is NULL, then ASSERT.\r | |
26 | \r | |
27 | if Count is < 2 then perform no action.\r | |
28 | if Size is < 1 then perform no action.\r | |
29 | \r | |
4ff7e37b ED |
30 | @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r |
31 | on return a buffer of sorted elements\r | |
32 | @param[in] Count the number of elements in the buffer to sort\r | |
33 | @param[in] ElementSize Size of an element in bytes\r | |
34 | @param[in] CompareFunction The function to call to perform the comparison\r | |
35 | of any 2 elements\r | |
36 | @param[in] Buffer Buffer of size ElementSize for use in swapping\r | |
4983ca93 | 37 | **/\r |
38 | VOID\r | |
39 | EFIAPI\r | |
40 | QuickSortWorker (\r | |
41 | IN OUT VOID *BufferToSort,\r | |
42 | IN CONST UINTN Count,\r | |
43 | IN CONST UINTN ElementSize,\r | |
44 | IN SORT_COMPARE CompareFunction,\r | |
45 | IN VOID *Buffer\r | |
125c2cf4 | 46 | )\r |
47 | {\r | |
4983ca93 | 48 | VOID *Pivot;\r |
49 | UINTN LoopCount;\r | |
50 | UINTN NextSwapLocation;\r | |
51 | \r | |
52 | ASSERT(BufferToSort != NULL);\r | |
53 | ASSERT(CompareFunction != NULL);\r | |
54 | ASSERT(Buffer != NULL);\r | |
55 | \r | |
1e6e84c7 | 56 | if ( Count < 2\r |
4983ca93 | 57 | || ElementSize < 1\r |
a405b86d | 58 | ){\r |
4983ca93 | 59 | return;\r |
60 | }\r | |
61 | \r | |
62 | NextSwapLocation = 0;\r | |
63 | \r | |
64 | //\r | |
65 | // pick a pivot (we choose last element)\r | |
66 | //\r | |
67 | Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));\r | |
68 | \r | |
69 | //\r | |
70 | // Now get the pivot such that all on "left" are below it\r | |
71 | // and everything "right" are above it\r | |
72 | //\r | |
73 | for ( LoopCount = 0\r | |
1e6e84c7 | 74 | ; LoopCount < Count -1\r |
4983ca93 | 75 | ; LoopCount++\r |
a405b86d | 76 | ){\r |
4983ca93 | 77 | //\r |
78 | // if the element is less than the pivot\r | |
79 | //\r | |
80 | if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r | |
81 | //\r | |
1e6e84c7 | 82 | // swap\r |
4983ca93 | 83 | //\r |
84 | CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r | |
85 | CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);\r | |
86 | CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);\r | |
87 | \r | |
88 | //\r | |
89 | // increment NextSwapLocation\r | |
1e6e84c7 | 90 | //\r |
4983ca93 | 91 | NextSwapLocation++;\r |
92 | }\r | |
93 | }\r | |
94 | //\r | |
95 | // swap pivot to it's final position (NextSwapLocaiton)\r | |
96 | //\r | |
97 | CopyMem (Buffer, Pivot, ElementSize);\r | |
98 | CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r | |
99 | CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);\r | |
100 | \r | |
101 | //\r | |
1e6e84c7 | 102 | // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element\r |
4983ca93 | 103 | // IE list is sorted left half, pivot element, sorted right half...\r |
104 | //\r | |
5dcb5355 | 105 | if (NextSwapLocation >= 2) {\r |
106 | QuickSortWorker(\r | |
107 | BufferToSort,\r | |
108 | NextSwapLocation,\r | |
109 | ElementSize,\r | |
110 | CompareFunction,\r | |
111 | Buffer);\r | |
112 | }\r | |
4983ca93 | 113 | \r |
5dcb5355 | 114 | if ((Count - NextSwapLocation - 1) >= 2) {\r |
115 | QuickSortWorker(\r | |
116 | (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,\r | |
117 | Count - NextSwapLocation - 1,\r | |
118 | ElementSize,\r | |
119 | CompareFunction,\r | |
120 | Buffer);\r | |
121 | }\r | |
4983ca93 | 122 | return;\r |
123 | }\r | |
124 | /**\r | |
125 | Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r | |
126 | \r | |
127 | Each element must be equal sized.\r | |
128 | \r | |
129 | if BufferToSort is NULL, then ASSERT.\r | |
130 | if CompareFunction is NULL, then ASSERT.\r | |
131 | \r | |
132 | if Count is < 2 then perform no action.\r | |
133 | if Size is < 1 then perform no action.\r | |
134 | \r | |
4ff7e37b ED |
135 | @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r |
136 | on return a buffer of sorted elements\r | |
137 | @param[in] Count the number of elements in the buffer to sort\r | |
138 | @param[in] ElementSize Size of an element in bytes\r | |
139 | @param[in] CompareFunction The function to call to perform the comparison\r | |
140 | of any 2 elements\r | |
4983ca93 | 141 | **/\r |
142 | VOID\r | |
143 | EFIAPI\r | |
144 | PerformQuickSort (\r | |
145 | IN OUT VOID *BufferToSort,\r | |
146 | IN CONST UINTN Count,\r | |
147 | IN CONST UINTN ElementSize,\r | |
148 | IN SORT_COMPARE CompareFunction\r | |
125c2cf4 | 149 | )\r |
150 | {\r | |
4983ca93 | 151 | VOID *Buffer;\r |
152 | \r | |
153 | ASSERT(BufferToSort != NULL);\r | |
154 | ASSERT(CompareFunction != NULL);\r | |
155 | \r | |
5a0fe66e | 156 | Buffer = AllocateZeroPool(ElementSize);\r |
4983ca93 | 157 | ASSERT(Buffer != NULL);\r |
158 | \r | |
159 | QuickSortWorker(\r | |
160 | BufferToSort,\r | |
161 | Count,\r | |
162 | ElementSize,\r | |
163 | CompareFunction,\r | |
164 | Buffer);\r | |
165 | \r | |
166 | FreePool(Buffer);\r | |
167 | return;\r | |
168 | }\r | |
125c2cf4 | 169 | \r |
170 | /**\r | |
171 | Not supported in Base version.\r | |
1e6e84c7 | 172 | \r |
a405b86d | 173 | @param[in] Buffer1 Ignored.\r |
174 | @param[in] Buffer2 Ignored.\r | |
175 | \r | |
125c2cf4 | 176 | ASSERT and return 0.\r |
177 | **/\r | |
178 | INTN\r | |
21ecdf15 | 179 | EFIAPI\r |
125c2cf4 | 180 | DevicePathCompare (\r |
b3011f40 | 181 | IN CONST VOID *Buffer1,\r |
182 | IN CONST VOID *Buffer2\r | |
125c2cf4 | 183 | )\r |
184 | {\r | |
185 | ASSERT(FALSE);\r | |
186 | return 0;\r | |
70328967 | 187 | }\r |
11d2decf | 188 | \r |
189 | /**\r | |
a653a525 | 190 | Not supported in Base version.\r |
11d2decf | 191 | \r |
a653a525 JC |
192 | @param[in] Buffer1 Ignored.\r |
193 | @param[in] Buffer2 Ignored.\r | |
11d2decf | 194 | \r |
a653a525 | 195 | ASSERT and return 0.\r |
11d2decf | 196 | **/\r |
197 | INTN\r | |
198 | EFIAPI\r | |
199 | StringNoCaseCompare (\r | |
b3011f40 | 200 | IN CONST VOID *Buffer1,\r |
201 | IN CONST VOID *Buffer2\r | |
11d2decf | 202 | )\r |
203 | {\r | |
204 | ASSERT(FALSE);\r | |
205 | return 0;\r | |
206 | }\r | |
207 | \r | |
208 | \r | |
a405b86d | 209 | /**\r |
a653a525 | 210 | Not supported in Base version.\r |
a405b86d | 211 | \r |
a653a525 JC |
212 | @param[in] Buffer1 Ignored.\r |
213 | @param[in] Buffer2 Ignored.\r | |
a405b86d | 214 | \r |
a653a525 | 215 | ASSERT and return 0.\r |
a405b86d | 216 | **/\r |
217 | INTN\r | |
218 | EFIAPI\r | |
219 | StringCompare (\r | |
220 | IN CONST VOID *Buffer1,\r | |
221 | IN CONST VOID *Buffer2\r | |
222 | )\r | |
223 | {\r | |
224 | ASSERT(FALSE);\r | |
225 | return 0;\r | |
226 | }\r | |
227 | \r | |
228 | \r |