2 Library used for sorting routines.
4 Copyright (c) 2009, Intel Corporation<BR>
5 All rights reserved. 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>
19 #include <Protocol/DevicePathToText.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>
29 Worker function for QuickSorting. This function is identical to PerformQuickSort,
30 except that is uses the pre-allocated buffer so the in place sorting does not need to
31 allocate and free buffers constantly.
33 Each element must be equal sized.
35 if BufferToSort is NULL, then ASSERT.
36 if CompareFunction is NULL, then ASSERT.
37 if Buffer is NULL, then ASSERT.
39 if Count is < 2 then perform no action.
40 if Size is < 1 then perform no action.
42 @param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements
43 on return a buffer of sorted elements
44 @param[in] Count the number of elements in the buffer to sort
45 @param[in] ElementSize Size of an element in bytes
46 @param[in] CompareFunction The function to call to perform the comparison
48 @param[in] Buffer Buffer of size ElementSize for use in swapping
53 IN OUT VOID
*BufferToSort
,
55 IN CONST UINTN ElementSize
,
56 IN SORT_COMPARE CompareFunction
,
62 UINTN NextSwapLocation
;
64 ASSERT(BufferToSort
!= NULL
);
65 ASSERT(CompareFunction
!= NULL
);
66 ASSERT(Buffer
!= NULL
);
77 // pick a pivot (we choose last element)
79 Pivot
= ((UINT8
*)BufferToSort
+((Count
-1)*ElementSize
));
82 // Now get the pivot such that all on "left" are below it
83 // and everything "right" are above it
86 ; LoopCount
< Count
-1
90 // if the element is less than the pivot
92 if (CompareFunction((VOID
*)((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
)),Pivot
) <= 0){
96 CopyMem (Buffer
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
97 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), (UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), ElementSize
);
98 CopyMem ((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), Buffer
, ElementSize
);
101 // increment NextSwapLocation
107 // swap pivot to it's final position (NextSwapLocaiton)
109 CopyMem (Buffer
, Pivot
, ElementSize
);
110 CopyMem (Pivot
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
111 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), Buffer
, ElementSize
);
114 // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
115 // IE list is sorted left half, pivot element, sorted right half...
125 (UINT8
*)BufferToSort
+ (NextSwapLocation
+1) * ElementSize
,
126 Count
- NextSwapLocation
- 1,
134 Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
136 Each element must be equal sized.
138 if BufferToSort is NULL, then ASSERT.
139 if CompareFunction is NULL, then ASSERT.
141 if Count is < 2 then perform no action.
142 if Size is < 1 then perform no action.
144 @param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements
145 on return a buffer of sorted elements
146 @param[in] Count the number of elements in the buffer to sort
147 @param[in] ElementSize Size of an element in bytes
148 @param[in] CompareFunction The function to call to perform the comparison
154 IN OUT VOID
*BufferToSort
,
155 IN CONST UINTN Count
,
156 IN CONST UINTN ElementSize
,
157 IN SORT_COMPARE CompareFunction
162 ASSERT(BufferToSort
!= NULL
);
163 ASSERT(CompareFunction
!= NULL
);
165 Buffer
= AllocatePool(ElementSize
);
166 ASSERT(Buffer
!= NULL
);
180 function to compare 2 device paths for use in QuickSort
182 @param[in] Buffer1 pointer to Device Path poiner to compare
183 @param[in] Buffer2 pointer to second DevicePath pointer to compare
185 @retval 0 Buffer1 equal to Buffer2
186 @return < 0 Buffer1 is less than Buffer2
187 @return > 0 Buffer1 is greater than Buffer2
195 EFI_DEVICE_PATH_PROTOCOL
*DevicePath1
;
196 EFI_DEVICE_PATH_PROTOCOL
*DevicePath2
;
202 STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL
*DevicePathToText
= NULL
;
203 STATIC EFI_UNICODE_COLLATION_PROTOCOL
*UnicodeCollation
= NULL
;
205 DevicePath1
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer1
;
206 DevicePath2
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer2
;
208 if (DevicePath1
== NULL
) {
209 if (DevicePath2
== NULL
) {
216 if (DevicePath2
== NULL
) {
220 if (DevicePathToText
== NULL
) {
221 Status
= gBS
->LocateProtocol(
222 &gEfiDevicePathToTextProtocolGuid
,
224 (VOID
**)&DevicePathToText
);
226 ASSERT_EFI_ERROR(Status
);
229 if (UnicodeCollation
== NULL
) {
230 Status
= gBS
->LocateProtocol(
231 &gEfiUnicodeCollation2ProtocolGuid
,
233 (VOID
**)&UnicodeCollation
);
235 ASSERT_EFI_ERROR(Status
);
238 TextPath1
= DevicePathToText
->ConvertDevicePathToText(
243 TextPath2
= DevicePathToText
->ConvertDevicePathToText(
248 RetVal
= UnicodeCollation
->StriColl(