2 Library used for sorting routines.
4 Copyright (c) 2009 - 2011, Intel Corporation. All rights reserved. <BR>
5 This program and the accompanying materials
6 are licensed and made available under the terms and conditions of the BSD License
7 which accompanies this distribution. The full text of the license may be found at
8 http://opensource.org/licenses/bsd-license.php
10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
16 #include <ShellBase.h>
18 #include <Protocol/UnicodeCollation.h>
19 #include <Protocol/DevicePath.h>
20 #include <Protocol/DevicePathToText.h>
22 #include <Library/UefiBootServicesTableLib.h>
23 #include <Library/BaseLib.h>
24 #include <Library/BaseMemoryLib.h>
25 #include <Library/DebugLib.h>
26 #include <Library/MemoryAllocationLib.h>
27 #include <Library/SortLib.h>
29 STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL
*mDevicePathToText
= NULL
;
30 STATIC EFI_UNICODE_COLLATION_PROTOCOL
*mUnicodeCollation
= NULL
;
34 Worker function for QuickSorting. This function is identical to PerformQuickSort,
35 except that is uses the pre-allocated buffer so the in place sorting does not need to
36 allocate and free buffers constantly.
38 Each element must be equal sized.
40 if BufferToSort is NULL, then ASSERT.
41 if CompareFunction is NULL, then ASSERT.
42 if Buffer is NULL, then ASSERT.
44 if Count is < 2 then perform no action.
45 if Size is < 1 then perform no action.
47 @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
48 on return a buffer of sorted elements
49 @param[in] Count the number of elements in the buffer to sort
50 @param[in] ElementSize Size of an element in bytes
51 @param[in] CompareFunction The function to call to perform the comparison
53 @param[in] Buffer Buffer of size ElementSize for use in swapping
58 IN OUT VOID
*BufferToSort
,
60 IN CONST UINTN ElementSize
,
61 IN SORT_COMPARE CompareFunction
,
67 UINTN NextSwapLocation
;
69 ASSERT(BufferToSort
!= NULL
);
70 ASSERT(CompareFunction
!= NULL
);
71 ASSERT(Buffer
!= NULL
);
82 // pick a pivot (we choose last element)
84 Pivot
= ((UINT8
*)BufferToSort
+((Count
-1)*ElementSize
));
87 // Now get the pivot such that all on "left" are below it
88 // and everything "right" are above it
91 ; LoopCount
< Count
-1
95 // if the element is less than the pivot
97 if (CompareFunction((VOID
*)((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
)),Pivot
) <= 0){
101 CopyMem (Buffer
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
102 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), (UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), ElementSize
);
103 CopyMem ((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), Buffer
, ElementSize
);
106 // increment NextSwapLocation
112 // swap pivot to it's final position (NextSwapLocaiton)
114 CopyMem (Buffer
, Pivot
, ElementSize
);
115 CopyMem (Pivot
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
116 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), Buffer
, ElementSize
);
119 // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
120 // IE list is sorted left half, pivot element, sorted right half...
122 if (NextSwapLocation
>= 2) {
131 if ((Count
- NextSwapLocation
- 1) >= 2) {
133 (UINT8
*)BufferToSort
+ (NextSwapLocation
+1) * ElementSize
,
134 Count
- NextSwapLocation
- 1,
143 Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
145 Each element must be equal sized.
147 if BufferToSort is NULL, then ASSERT.
148 if CompareFunction is NULL, then ASSERT.
150 if Count is < 2 then perform no action.
151 if Size is < 1 then perform no action.
153 @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
154 on return a buffer of sorted elements
155 @param[in] Count the number of elements in the buffer to sort
156 @param[in] ElementSize Size of an element in bytes
157 @param[in] CompareFunction The function to call to perform the comparison
163 IN OUT VOID
*BufferToSort
,
164 IN CONST UINTN Count
,
165 IN CONST UINTN ElementSize
,
166 IN SORT_COMPARE CompareFunction
171 ASSERT(BufferToSort
!= NULL
);
172 ASSERT(CompareFunction
!= NULL
);
174 Buffer
= AllocateZeroPool(ElementSize
);
175 ASSERT(Buffer
!= NULL
);
189 Function to compare 2 device paths for use in QuickSort.
191 @param[in] Buffer1 pointer to Device Path poiner to compare
192 @param[in] Buffer2 pointer to second DevicePath pointer to compare
194 @retval 0 Buffer1 equal to Buffer2
195 @return < 0 Buffer1 is less than Buffer2
196 @return > 0 Buffer1 is greater than Buffer2
201 IN CONST VOID
*Buffer1
,
202 IN CONST VOID
*Buffer2
205 EFI_DEVICE_PATH_PROTOCOL
*DevicePath1
;
206 EFI_DEVICE_PATH_PROTOCOL
*DevicePath2
;
212 DevicePath1
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer1
;
213 DevicePath2
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer2
;
215 if (DevicePath1
== NULL
) {
216 if (DevicePath2
== NULL
) {
223 if (DevicePath2
== NULL
) {
227 if (mDevicePathToText
== NULL
) {
228 Status
= gBS
->LocateProtocol(
229 &gEfiDevicePathToTextProtocolGuid
,
231 (VOID
**)&mDevicePathToText
);
233 ASSERT_EFI_ERROR(Status
);
236 if (mUnicodeCollation
== NULL
) {
237 Status
= gBS
->LocateProtocol(
238 &gEfiUnicodeCollation2ProtocolGuid
,
240 (VOID
**)&mUnicodeCollation
);
242 ASSERT_EFI_ERROR(Status
);
245 TextPath1
= mDevicePathToText
->ConvertDevicePathToText(
250 TextPath2
= mDevicePathToText
->ConvertDevicePathToText(
255 if (TextPath1
== NULL
) {
257 } else if (TextPath2
== NULL
) {
260 RetVal
= mUnicodeCollation
->StriColl(
266 SHELL_FREE_NON_NULL(TextPath1
);
267 SHELL_FREE_NON_NULL(TextPath2
);
273 Function to compare 2 strings without regard to case of the characters.
275 @param[in] Buffer1 Pointer to String to compare.
276 @param[in] Buffer2 Pointer to second String to compare.
278 @retval 0 Buffer1 equal to Buffer2.
279 @return < 0 Buffer1 is less than Buffer2.
280 @return > 0 Buffer1 is greater than Buffer2.
284 StringNoCaseCompare (
285 IN CONST VOID
*Buffer1
,
286 IN CONST VOID
*Buffer2
290 if (mUnicodeCollation
== NULL
) {
291 Status
= gBS
->LocateProtocol(
292 &gEfiUnicodeCollation2ProtocolGuid
,
294 (VOID
**)&mUnicodeCollation
);
296 ASSERT_EFI_ERROR(Status
);
299 return (mUnicodeCollation
->StriColl(
302 *(CHAR16
**)Buffer2
));
307 Function to compare 2 strings.
309 @param[in] Buffer1 Pointer to String to compare (CHAR16**).
310 @param[in] Buffer2 Pointer to second String to compare (CHAR16**).
312 @retval 0 Buffer1 equal to Buffer2.
313 @return < 0 Buffer1 is less than Buffer2.
314 @return > 0 Buffer1 is greater than Buffer2.
319 IN CONST VOID
*Buffer1
,
320 IN CONST VOID
*Buffer2
325 *(CHAR16
**)Buffer2
));