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>
21 #include <Library/UefiBootServicesTableLib.h>
22 #include <Library/BaseLib.h>
23 #include <Library/BaseMemoryLib.h>
24 #include <Library/DebugLib.h>
25 #include <Library/MemoryAllocationLib.h>
26 #include <Library/SortLib.h>
27 #include <Library/DevicePathLib.h>
29 STATIC EFI_UNICODE_COLLATION_PROTOCOL
*mUnicodeCollation
= NULL
;
33 Worker function for QuickSorting. This function is identical to PerformQuickSort,
34 except that is uses the pre-allocated buffer so the in place sorting does not need to
35 allocate and free buffers constantly.
37 Each element must be equal sized.
39 if BufferToSort is NULL, then ASSERT.
40 if CompareFunction is NULL, then ASSERT.
41 if Buffer is NULL, then ASSERT.
43 if Count is < 2 then perform no action.
44 if Size is < 1 then perform no action.
46 @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
47 on return a buffer of sorted elements
48 @param[in] Count the number of elements in the buffer to sort
49 @param[in] ElementSize Size of an element in bytes
50 @param[in] CompareFunction The function to call to perform the comparison
52 @param[in] Buffer Buffer of size ElementSize for use in swapping
57 IN OUT VOID
*BufferToSort
,
59 IN CONST UINTN ElementSize
,
60 IN SORT_COMPARE CompareFunction
,
66 UINTN NextSwapLocation
;
68 ASSERT(BufferToSort
!= NULL
);
69 ASSERT(CompareFunction
!= NULL
);
70 ASSERT(Buffer
!= NULL
);
81 // pick a pivot (we choose last element)
83 Pivot
= ((UINT8
*)BufferToSort
+((Count
-1)*ElementSize
));
86 // Now get the pivot such that all on "left" are below it
87 // and everything "right" are above it
90 ; LoopCount
< Count
-1
94 // if the element is less than the pivot
96 if (CompareFunction((VOID
*)((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
)),Pivot
) <= 0){
100 CopyMem (Buffer
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
101 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), (UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), ElementSize
);
102 CopyMem ((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), Buffer
, ElementSize
);
105 // increment NextSwapLocation
111 // swap pivot to it's final position (NextSwapLocaiton)
113 CopyMem (Buffer
, Pivot
, ElementSize
);
114 CopyMem (Pivot
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
115 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), Buffer
, ElementSize
);
118 // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
119 // IE list is sorted left half, pivot element, sorted right half...
121 if (NextSwapLocation
>= 2) {
130 if ((Count
- NextSwapLocation
- 1) >= 2) {
132 (UINT8
*)BufferToSort
+ (NextSwapLocation
+1) * ElementSize
,
133 Count
- NextSwapLocation
- 1,
142 Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
144 Each element must be equal sized.
146 if BufferToSort is NULL, then ASSERT.
147 if CompareFunction is NULL, then ASSERT.
149 if Count is < 2 then perform no action.
150 if Size is < 1 then perform no action.
152 @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
153 on return a buffer of sorted elements
154 @param[in] Count the number of elements in the buffer to sort
155 @param[in] ElementSize Size of an element in bytes
156 @param[in] CompareFunction The function to call to perform the comparison
162 IN OUT VOID
*BufferToSort
,
163 IN CONST UINTN Count
,
164 IN CONST UINTN ElementSize
,
165 IN SORT_COMPARE CompareFunction
170 ASSERT(BufferToSort
!= NULL
);
171 ASSERT(CompareFunction
!= NULL
);
173 Buffer
= AllocateZeroPool(ElementSize
);
174 ASSERT(Buffer
!= NULL
);
188 Function to compare 2 device paths for use in QuickSort.
190 @param[in] Buffer1 pointer to Device Path poiner to compare
191 @param[in] Buffer2 pointer to second DevicePath pointer to compare
193 @retval 0 Buffer1 equal to Buffer2
194 @return < 0 Buffer1 is less than Buffer2
195 @return > 0 Buffer1 is greater than Buffer2
200 IN CONST VOID
*Buffer1
,
201 IN CONST VOID
*Buffer2
204 EFI_DEVICE_PATH_PROTOCOL
*DevicePath1
;
205 EFI_DEVICE_PATH_PROTOCOL
*DevicePath2
;
211 DevicePath1
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer1
;
212 DevicePath2
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer2
;
214 if (DevicePath1
== NULL
) {
215 if (DevicePath2
== NULL
) {
222 if (DevicePath2
== NULL
) {
226 if (mUnicodeCollation
== NULL
) {
227 Status
= gBS
->LocateProtocol(
228 &gEfiUnicodeCollation2ProtocolGuid
,
230 (VOID
**)&mUnicodeCollation
);
232 ASSERT_EFI_ERROR(Status
);
235 TextPath1
= ConvertDevicePathToText(
240 TextPath2
= ConvertDevicePathToText(
245 if (TextPath1
== NULL
) {
247 } else if (TextPath2
== NULL
) {
250 RetVal
= mUnicodeCollation
->StriColl(
256 SHELL_FREE_NON_NULL(TextPath1
);
257 SHELL_FREE_NON_NULL(TextPath2
);
263 Function to compare 2 strings without regard to case of the characters.
265 @param[in] Buffer1 Pointer to String to compare.
266 @param[in] Buffer2 Pointer to second String to compare.
268 @retval 0 Buffer1 equal to Buffer2.
269 @return < 0 Buffer1 is less than Buffer2.
270 @return > 0 Buffer1 is greater than Buffer2.
274 StringNoCaseCompare (
275 IN CONST VOID
*Buffer1
,
276 IN CONST VOID
*Buffer2
280 if (mUnicodeCollation
== NULL
) {
281 Status
= gBS
->LocateProtocol(
282 &gEfiUnicodeCollation2ProtocolGuid
,
284 (VOID
**)&mUnicodeCollation
);
286 ASSERT_EFI_ERROR(Status
);
289 return (mUnicodeCollation
->StriColl(
292 *(CHAR16
**)Buffer2
));
297 Function to compare 2 strings.
299 @param[in] Buffer1 Pointer to String to compare (CHAR16**).
300 @param[in] Buffer2 Pointer to second String to compare (CHAR16**).
302 @retval 0 Buffer1 equal to Buffer2.
303 @return < 0 Buffer1 is less than Buffer2.
304 @return > 0 Buffer1 is greater than Buffer2.
309 IN CONST VOID
*Buffer1
,
310 IN CONST VOID
*Buffer2
315 *(CHAR16
**)Buffer2
));