2 Library used for sorting routines.
4 Copyright (c) 2009 - 2014, 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.
17 #include <Protocol/UnicodeCollation.h>
18 #include <Protocol/DevicePath.h>
20 #include <Library/UefiBootServicesTableLib.h>
21 #include <Library/BaseLib.h>
22 #include <Library/BaseMemoryLib.h>
23 #include <Library/DebugLib.h>
24 #include <Library/MemoryAllocationLib.h>
25 #include <Library/SortLib.h>
26 #include <Library/DevicePathLib.h>
28 STATIC EFI_UNICODE_COLLATION_PROTOCOL
*mUnicodeCollation
= NULL
;
30 #define USL_FREE_NON_NULL(Pointer) \
32 if ((Pointer) != NULL) { \
33 FreePool((Pointer)); \
39 Worker function for QuickSorting. This function is identical to PerformQuickSort,
40 except that is uses the pre-allocated buffer so the in place sorting does not need to
41 allocate and free buffers constantly.
43 Each element must be equal sized.
45 if BufferToSort is NULL, then ASSERT.
46 if CompareFunction is NULL, then ASSERT.
47 if Buffer is NULL, then ASSERT.
49 if Count is < 2 then perform no action.
50 if Size is < 1 then perform no action.
52 @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
53 on return a buffer of sorted elements
54 @param[in] Count the number of elements in the buffer to sort
55 @param[in] ElementSize Size of an element in bytes
56 @param[in] CompareFunction The function to call to perform the comparison
58 @param[in] Buffer Buffer of size ElementSize for use in swapping
63 IN OUT VOID
*BufferToSort
,
65 IN CONST UINTN ElementSize
,
66 IN SORT_COMPARE CompareFunction
,
72 UINTN NextSwapLocation
;
74 ASSERT(BufferToSort
!= NULL
);
75 ASSERT(CompareFunction
!= NULL
);
76 ASSERT(Buffer
!= NULL
);
87 // pick a pivot (we choose last element)
89 Pivot
= ((UINT8
*)BufferToSort
+((Count
-1)*ElementSize
));
92 // Now get the pivot such that all on "left" are below it
93 // and everything "right" are above it
96 ; LoopCount
< Count
-1
100 // if the element is less than the pivot
102 if (CompareFunction((VOID
*)((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
)),Pivot
) <= 0){
106 CopyMem (Buffer
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
107 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), (UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), ElementSize
);
108 CopyMem ((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), Buffer
, ElementSize
);
111 // increment NextSwapLocation
117 // swap pivot to it's final position (NextSwapLocaiton)
119 CopyMem (Buffer
, Pivot
, ElementSize
);
120 CopyMem (Pivot
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
121 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), Buffer
, ElementSize
);
124 // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
125 // IE list is sorted left half, pivot element, sorted right half...
127 if (NextSwapLocation
>= 2) {
136 if ((Count
- NextSwapLocation
- 1) >= 2) {
138 (UINT8
*)BufferToSort
+ (NextSwapLocation
+1) * ElementSize
,
139 Count
- NextSwapLocation
- 1,
148 Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
150 Each element must be equal sized.
152 if BufferToSort is NULL, then ASSERT.
153 if CompareFunction is NULL, then ASSERT.
155 if Count is < 2 then perform no action.
156 if Size is < 1 then perform no action.
158 @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
159 on return a buffer of sorted elements
160 @param[in] Count the number of elements in the buffer to sort
161 @param[in] ElementSize Size of an element in bytes
162 @param[in] CompareFunction The function to call to perform the comparison
168 IN OUT VOID
*BufferToSort
,
169 IN CONST UINTN Count
,
170 IN CONST UINTN ElementSize
,
171 IN SORT_COMPARE CompareFunction
176 ASSERT(BufferToSort
!= NULL
);
177 ASSERT(CompareFunction
!= NULL
);
179 Buffer
= AllocateZeroPool(ElementSize
);
180 ASSERT(Buffer
!= NULL
);
194 Function to compare 2 device paths for use in QuickSort.
196 @param[in] Buffer1 pointer to Device Path poiner to compare
197 @param[in] Buffer2 pointer to second DevicePath pointer to compare
199 @retval 0 Buffer1 equal to Buffer2
200 @retval <0 Buffer1 is less than Buffer2
201 @retval >0 Buffer1 is greater than Buffer2
206 IN CONST VOID
*Buffer1
,
207 IN CONST VOID
*Buffer2
210 EFI_DEVICE_PATH_PROTOCOL
*DevicePath1
;
211 EFI_DEVICE_PATH_PROTOCOL
*DevicePath2
;
217 DevicePath1
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer1
;
218 DevicePath2
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer2
;
220 if (DevicePath1
== NULL
) {
221 if (DevicePath2
== NULL
) {
228 if (DevicePath2
== NULL
) {
232 if (mUnicodeCollation
== NULL
) {
233 Status
= gBS
->LocateProtocol(
234 &gEfiUnicodeCollation2ProtocolGuid
,
236 (VOID
**)&mUnicodeCollation
);
238 ASSERT_EFI_ERROR(Status
);
241 TextPath1
= ConvertDevicePathToText(
246 TextPath2
= ConvertDevicePathToText(
251 if (TextPath1
== NULL
) {
253 } else if (TextPath2
== NULL
) {
256 RetVal
= mUnicodeCollation
->StriColl(
262 USL_FREE_NON_NULL(TextPath1
);
263 USL_FREE_NON_NULL(TextPath2
);
269 Function to compare 2 strings without regard to case of the characters.
271 @param[in] Buffer1 Pointer to String to compare.
272 @param[in] Buffer2 Pointer to second String to compare.
274 @retval 0 Buffer1 equal to Buffer2.
275 @retval <0 Buffer1 is less than Buffer2.
276 @retval >0 Buffer1 is greater than Buffer2.
280 StringNoCaseCompare (
281 IN CONST VOID
*Buffer1
,
282 IN CONST VOID
*Buffer2
286 if (mUnicodeCollation
== NULL
) {
287 Status
= gBS
->LocateProtocol(
288 &gEfiUnicodeCollation2ProtocolGuid
,
290 (VOID
**)&mUnicodeCollation
);
292 ASSERT_EFI_ERROR(Status
);
295 return (mUnicodeCollation
->StriColl(
298 *(CHAR16
**)Buffer2
));
303 Function to compare 2 strings.
305 @param[in] Buffer1 Pointer to String to compare (CHAR16**).
306 @param[in] Buffer2 Pointer to second String to compare (CHAR16**).
308 @retval 0 Buffer1 equal to Buffer2.
309 @retval <0 Buffer1 is less than Buffer2.
310 @retval >0 Buffer1 is greater than Buffer2.
315 IN CONST VOID
*Buffer1
,
316 IN CONST VOID
*Buffer2
321 *(CHAR16
**)Buffer2
));