]>
Commit | Line | Data |
---|---|---|
a4ee2a4f | 1 | /** @file\r |
2 | Library used for sorting routines.\r | |
3 | \r | |
9586a351 | 4 | Copyright (c) 2009 - 2011, Intel Corporation. All rights reserved. <BR>\r |
1e6e84c7 | 5 | This program and the accompanying materials\r |
6 | are licensed and made available under the terms and conditions of the BSD License\r | |
7 | which accompanies this distribution. The full text of the license may be found at\r | |
8 | http://opensource.org/licenses/bsd-license.php\r | |
a4ee2a4f | 9 | \r |
1e6e84c7 | 10 | THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r |
11 | WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r | |
a4ee2a4f | 12 | \r |
13 | **/\r | |
14 | \r | |
15 | #include <Uefi.h>\r | |
eca218a7 | 16 | #include <ShellBase.h>\r |
a4ee2a4f | 17 | \r |
18 | #include <Protocol/UnicodeCollation.h>\r | |
19 | #include <Protocol/DevicePath.h>\r | |
20 | #include <Protocol/DevicePathToText.h>\r | |
21 | \r | |
22 | #include <Library/UefiBootServicesTableLib.h>\r | |
23 | #include <Library/BaseLib.h>\r | |
24 | #include <Library/BaseMemoryLib.h>\r | |
25 | #include <Library/DebugLib.h>\r | |
26 | #include <Library/MemoryAllocationLib.h>\r | |
1e6e84c7 | 27 | #include <Library/SortLib.h>\r |
a4ee2a4f | 28 | \r |
11d2decf | 29 | STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL *mDevicePathToText = NULL;\r |
30 | STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation = NULL;\r | |
31 | \r | |
32 | \r | |
a4ee2a4f | 33 | /**\r |
1e6e84c7 | 34 | Worker function for QuickSorting. This function is identical to PerformQuickSort,\r |
35 | except that is uses the pre-allocated buffer so the in place sorting does not need to\r | |
a4ee2a4f | 36 | allocate and free buffers constantly.\r |
37 | \r | |
38 | Each element must be equal sized.\r | |
39 | \r | |
40 | if BufferToSort is NULL, then ASSERT.\r | |
41 | if CompareFunction is NULL, then ASSERT.\r | |
42 | if Buffer is NULL, then ASSERT.\r | |
43 | \r | |
44 | if Count is < 2 then perform no action.\r | |
45 | if Size is < 1 then perform no action.\r | |
46 | \r | |
4ff7e37b ED |
47 | @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r |
48 | on return a buffer of sorted elements\r | |
49 | @param[in] Count the number of elements in the buffer to sort\r | |
50 | @param[in] ElementSize Size of an element in bytes\r | |
51 | @param[in] CompareFunction The function to call to perform the comparison\r | |
52 | of any 2 elements\r | |
53 | @param[in] Buffer Buffer of size ElementSize for use in swapping\r | |
a4ee2a4f | 54 | **/\r |
55 | VOID\r | |
56 | EFIAPI\r | |
57 | QuickSortWorker (\r | |
58 | IN OUT VOID *BufferToSort,\r | |
59 | IN CONST UINTN Count,\r | |
60 | IN CONST UINTN ElementSize,\r | |
61 | IN SORT_COMPARE CompareFunction,\r | |
62 | IN VOID *Buffer\r | |
125c2cf4 | 63 | )\r |
64 | {\r | |
a4ee2a4f | 65 | VOID *Pivot;\r |
66 | UINTN LoopCount;\r | |
67 | UINTN NextSwapLocation;\r | |
68 | \r | |
69 | ASSERT(BufferToSort != NULL);\r | |
70 | ASSERT(CompareFunction != NULL);\r | |
71 | ASSERT(Buffer != NULL);\r | |
72 | \r | |
1e6e84c7 | 73 | if ( Count < 2\r |
a4ee2a4f | 74 | || ElementSize < 1\r |
a405b86d | 75 | ){\r |
a4ee2a4f | 76 | return;\r |
77 | }\r | |
78 | \r | |
79 | NextSwapLocation = 0;\r | |
80 | \r | |
81 | //\r | |
82 | // pick a pivot (we choose last element)\r | |
83 | //\r | |
84 | Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));\r | |
85 | \r | |
86 | //\r | |
87 | // Now get the pivot such that all on "left" are below it\r | |
88 | // and everything "right" are above it\r | |
89 | //\r | |
90 | for ( LoopCount = 0\r | |
1e6e84c7 | 91 | ; LoopCount < Count -1\r |
a4ee2a4f | 92 | ; LoopCount++\r |
a405b86d | 93 | ){\r |
a4ee2a4f | 94 | //\r |
95 | // if the element is less than the pivot\r | |
96 | //\r | |
97 | if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r | |
98 | //\r | |
1e6e84c7 | 99 | // swap\r |
a4ee2a4f | 100 | //\r |
101 | CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r | |
102 | CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);\r | |
103 | CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);\r | |
104 | \r | |
105 | //\r | |
106 | // increment NextSwapLocation\r | |
1e6e84c7 | 107 | //\r |
a4ee2a4f | 108 | NextSwapLocation++;\r |
109 | }\r | |
110 | }\r | |
111 | //\r | |
112 | // swap pivot to it's final position (NextSwapLocaiton)\r | |
113 | //\r | |
114 | CopyMem (Buffer, Pivot, ElementSize);\r | |
115 | CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r | |
116 | CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);\r | |
117 | \r | |
118 | //\r | |
1e6e84c7 | 119 | // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element\r |
a4ee2a4f | 120 | // IE list is sorted left half, pivot element, sorted right half...\r |
121 | //\r | |
5dcb5355 | 122 | if (NextSwapLocation >= 2) {\r |
123 | QuickSortWorker(\r | |
124 | BufferToSort,\r | |
125 | NextSwapLocation,\r | |
126 | ElementSize,\r | |
127 | CompareFunction,\r | |
128 | Buffer);\r | |
129 | }\r | |
130 | \r | |
131 | if ((Count - NextSwapLocation - 1) >= 2) {\r | |
132 | QuickSortWorker(\r | |
133 | (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,\r | |
134 | Count - NextSwapLocation - 1,\r | |
135 | ElementSize,\r | |
136 | CompareFunction,\r | |
137 | Buffer);\r | |
138 | }\r | |
a4ee2a4f | 139 | \r |
140 | return;\r | |
141 | }\r | |
142 | /**\r | |
143 | Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r | |
144 | \r | |
145 | Each element must be equal sized.\r | |
146 | \r | |
147 | if BufferToSort is NULL, then ASSERT.\r | |
148 | if CompareFunction is NULL, then ASSERT.\r | |
149 | \r | |
150 | if Count is < 2 then perform no action.\r | |
151 | if Size is < 1 then perform no action.\r | |
152 | \r | |
4ff7e37b ED |
153 | @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r |
154 | on return a buffer of sorted elements\r | |
155 | @param[in] Count the number of elements in the buffer to sort\r | |
156 | @param[in] ElementSize Size of an element in bytes\r | |
157 | @param[in] CompareFunction The function to call to perform the comparison\r | |
158 | of any 2 elements\r | |
a4ee2a4f | 159 | **/\r |
160 | VOID\r | |
161 | EFIAPI\r | |
162 | PerformQuickSort (\r | |
163 | IN OUT VOID *BufferToSort,\r | |
164 | IN CONST UINTN Count,\r | |
165 | IN CONST UINTN ElementSize,\r | |
166 | IN SORT_COMPARE CompareFunction\r | |
125c2cf4 | 167 | )\r |
168 | {\r | |
a4ee2a4f | 169 | VOID *Buffer;\r |
170 | \r | |
171 | ASSERT(BufferToSort != NULL);\r | |
172 | ASSERT(CompareFunction != NULL);\r | |
173 | \r | |
9586a351 | 174 | Buffer = AllocateZeroPool(ElementSize);\r |
a4ee2a4f | 175 | ASSERT(Buffer != NULL);\r |
176 | \r | |
177 | QuickSortWorker(\r | |
178 | BufferToSort,\r | |
179 | Count,\r | |
180 | ElementSize,\r | |
181 | CompareFunction,\r | |
182 | Buffer);\r | |
183 | \r | |
184 | FreePool(Buffer);\r | |
185 | return;\r | |
186 | }\r | |
187 | \r | |
188 | /**\r | |
da70d025 | 189 | Function to compare 2 device paths for use in QuickSort.\r |
a4ee2a4f | 190 | \r |
191 | @param[in] Buffer1 pointer to Device Path poiner to compare\r | |
192 | @param[in] Buffer2 pointer to second DevicePath pointer to compare\r | |
193 | \r | |
194 | @retval 0 Buffer1 equal to Buffer2\r | |
195 | @return < 0 Buffer1 is less than Buffer2\r | |
1e6e84c7 | 196 | @return > 0 Buffer1 is greater than Buffer2\r |
a4ee2a4f | 197 | **/\r |
198 | INTN\r | |
e26d7b59 | 199 | EFIAPI\r |
a4ee2a4f | 200 | DevicePathCompare (\r |
b3011f40 | 201 | IN CONST VOID *Buffer1,\r |
202 | IN CONST VOID *Buffer2\r | |
125c2cf4 | 203 | )\r |
204 | {\r | |
a4ee2a4f | 205 | EFI_DEVICE_PATH_PROTOCOL *DevicePath1;\r |
206 | EFI_DEVICE_PATH_PROTOCOL *DevicePath2;\r | |
207 | CHAR16 *TextPath1;\r | |
208 | CHAR16 *TextPath2;\r | |
209 | EFI_STATUS Status;\r | |
210 | INTN RetVal;\r | |
1e6e84c7 | 211 | \r |
a4ee2a4f | 212 | DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;\r |
213 | DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;\r | |
214 | \r | |
215 | if (DevicePath1 == NULL) {\r | |
216 | if (DevicePath2 == NULL) {\r | |
217 | return 0;\r | |
218 | }\r | |
219 | \r | |
220 | return -1;\r | |
221 | }\r | |
222 | \r | |
223 | if (DevicePath2 == NULL) {\r | |
224 | return 1;\r | |
225 | }\r | |
1e6e84c7 | 226 | \r |
11d2decf | 227 | if (mDevicePathToText == NULL) {\r |
a4ee2a4f | 228 | Status = gBS->LocateProtocol(\r |
229 | &gEfiDevicePathToTextProtocolGuid,\r | |
230 | NULL,\r | |
11d2decf | 231 | (VOID**)&mDevicePathToText);\r |
a4ee2a4f | 232 | \r |
233 | ASSERT_EFI_ERROR(Status);\r | |
234 | }\r | |
235 | \r | |
11d2decf | 236 | if (mUnicodeCollation == NULL) {\r |
a4ee2a4f | 237 | Status = gBS->LocateProtocol(\r |
238 | &gEfiUnicodeCollation2ProtocolGuid,\r | |
239 | NULL,\r | |
11d2decf | 240 | (VOID**)&mUnicodeCollation);\r |
a4ee2a4f | 241 | \r |
242 | ASSERT_EFI_ERROR(Status);\r | |
243 | }\r | |
244 | \r | |
11d2decf | 245 | TextPath1 = mDevicePathToText->ConvertDevicePathToText(\r |
a4ee2a4f | 246 | DevicePath1,\r |
247 | FALSE,\r | |
248 | FALSE);\r | |
249 | \r | |
11d2decf | 250 | TextPath2 = mDevicePathToText->ConvertDevicePathToText(\r |
a4ee2a4f | 251 | DevicePath2,\r |
252 | FALSE,\r | |
253 | FALSE);\r | |
1e6e84c7 | 254 | \r |
eca218a7 | 255 | if (TextPath1 == NULL) {\r |
256 | RetVal = -1;\r | |
257 | } else if (TextPath2 == NULL) {\r | |
258 | RetVal = 1;\r | |
259 | } else {\r | |
260 | RetVal = mUnicodeCollation->StriColl(\r | |
261 | mUnicodeCollation,\r | |
262 | TextPath1,\r | |
263 | TextPath2);\r | |
264 | }\r | |
a4ee2a4f | 265 | \r |
eca218a7 | 266 | SHELL_FREE_NON_NULL(TextPath1);\r |
267 | SHELL_FREE_NON_NULL(TextPath2);\r | |
a4ee2a4f | 268 | \r |
269 | return (RetVal);\r | |
11d2decf | 270 | }\r |
271 | \r | |
272 | /**\r | |
273 | Function to compare 2 strings without regard to case of the characters.\r | |
274 | \r | |
275 | @param[in] Buffer1 Pointer to String to compare.\r | |
276 | @param[in] Buffer2 Pointer to second String to compare.\r | |
277 | \r | |
278 | @retval 0 Buffer1 equal to Buffer2.\r | |
279 | @return < 0 Buffer1 is less than Buffer2.\r | |
1e6e84c7 | 280 | @return > 0 Buffer1 is greater than Buffer2.\r |
11d2decf | 281 | **/\r |
282 | INTN\r | |
283 | EFIAPI\r | |
284 | StringNoCaseCompare (\r | |
b3011f40 | 285 | IN CONST VOID *Buffer1,\r |
286 | IN CONST VOID *Buffer2\r | |
11d2decf | 287 | )\r |
288 | {\r | |
289 | EFI_STATUS Status;\r | |
290 | if (mUnicodeCollation == NULL) {\r | |
291 | Status = gBS->LocateProtocol(\r | |
292 | &gEfiUnicodeCollation2ProtocolGuid,\r | |
293 | NULL,\r | |
294 | (VOID**)&mUnicodeCollation);\r | |
295 | \r | |
296 | ASSERT_EFI_ERROR(Status);\r | |
297 | }\r | |
298 | \r | |
299 | return (mUnicodeCollation->StriColl(\r | |
300 | mUnicodeCollation,\r | |
301 | *(CHAR16**)Buffer1,\r | |
302 | *(CHAR16**)Buffer2));\r | |
303 | }\r | |
304 | \r | |
305 | \r | |
a405b86d | 306 | /**\r |
307 | Function to compare 2 strings.\r | |
308 | \r | |
309 | @param[in] Buffer1 Pointer to String to compare (CHAR16**).\r | |
310 | @param[in] Buffer2 Pointer to second String to compare (CHAR16**).\r | |
311 | \r | |
312 | @retval 0 Buffer1 equal to Buffer2.\r | |
313 | @return < 0 Buffer1 is less than Buffer2.\r | |
314 | @return > 0 Buffer1 is greater than Buffer2.\r | |
315 | **/\r | |
316 | INTN\r | |
317 | EFIAPI\r | |
318 | StringCompare (\r | |
319 | IN CONST VOID *Buffer1,\r | |
320 | IN CONST VOID *Buffer2\r | |
321 | )\r | |
322 | {\r | |
323 | return (StrCmp(\r | |
324 | *(CHAR16**)Buffer1,\r | |
325 | *(CHAR16**)Buffer2));\r | |
326 | }\r |