2 Library used for sorting routines.
4 Copyright (c) 2009, Intel Corporation
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
,
61 UINTN NextSwapLocation
;
63 ASSERT(BufferToSort
!= NULL
);
64 ASSERT(CompareFunction
!= NULL
);
65 ASSERT(Buffer
!= NULL
);
76 // pick a pivot (we choose last element)
78 Pivot
= ((UINT8
*)BufferToSort
+((Count
-1)*ElementSize
));
81 // Now get the pivot such that all on "left" are below it
82 // and everything "right" are above it
85 ; LoopCount
< Count
-1
89 // if the element is less than the pivot
91 if (CompareFunction((VOID
*)((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
)),Pivot
) <= 0){
95 CopyMem (Buffer
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
96 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), (UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), ElementSize
);
97 CopyMem ((UINT8
*)BufferToSort
+((LoopCount
)*ElementSize
), Buffer
, ElementSize
);
100 // increment NextSwapLocation
106 // swap pivot to it's final position (NextSwapLocaiton)
108 CopyMem (Buffer
, Pivot
, ElementSize
);
109 CopyMem (Pivot
, (UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), ElementSize
);
110 CopyMem ((UINT8
*)BufferToSort
+(NextSwapLocation
*ElementSize
), Buffer
, ElementSize
);
113 // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
114 // IE list is sorted left half, pivot element, sorted right half...
124 (UINT8
*)BufferToSort
+ (NextSwapLocation
+1) * ElementSize
,
125 Count
- NextSwapLocation
- 1,
133 Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
135 Each element must be equal sized.
137 if BufferToSort is NULL, then ASSERT.
138 if CompareFunction is NULL, then ASSERT.
140 if Count is < 2 then perform no action.
141 if Size is < 1 then perform no action.
143 @param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements
144 on return a buffer of sorted elements
145 @param[in] Count the number of elements in the buffer to sort
146 @param[in] ElementSize Size of an element in bytes
147 @param[in] CompareFunction The function to call to perform the comparison
153 IN OUT VOID
*BufferToSort
,
154 IN CONST UINTN Count
,
155 IN CONST UINTN ElementSize
,
156 IN SORT_COMPARE CompareFunction
160 ASSERT(BufferToSort
!= NULL
);
161 ASSERT(CompareFunction
!= NULL
);
163 Buffer
= AllocatePool(ElementSize
);
164 ASSERT(Buffer
!= NULL
);
178 function to compare 2 device paths for use in QuickSort
180 @param[in] Buffer1 pointer to Device Path poiner to compare
181 @param[in] Buffer2 pointer to second DevicePath pointer to compare
183 @retval 0 Buffer1 equal to Buffer2
184 @return < 0 Buffer1 is less than Buffer2
185 @return > 0 Buffer1 is greater than Buffer2
192 EFI_DEVICE_PATH_PROTOCOL
*DevicePath1
;
193 EFI_DEVICE_PATH_PROTOCOL
*DevicePath2
;
199 STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL
*DevicePathToText
= NULL
;
200 STATIC EFI_UNICODE_COLLATION_PROTOCOL
*UnicodeCollation
= NULL
;
202 DevicePath1
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer1
;
203 DevicePath2
= *(EFI_DEVICE_PATH_PROTOCOL
**)Buffer2
;
205 if (DevicePath1
== NULL
) {
206 if (DevicePath2
== NULL
) {
213 if (DevicePath2
== NULL
) {
217 if (DevicePathToText
== NULL
) {
218 Status
= gBS
->LocateProtocol(
219 &gEfiDevicePathToTextProtocolGuid
,
221 (VOID
**)&DevicePathToText
);
223 ASSERT_EFI_ERROR(Status
);
226 if (UnicodeCollation
== NULL
) {
227 Status
= gBS
->LocateProtocol(
228 &gEfiUnicodeCollation2ProtocolGuid
,
230 (VOID
**)&UnicodeCollation
);
232 ASSERT_EFI_ERROR(Status
);
235 TextPath1
= DevicePathToText
->ConvertDevicePathToText(
240 TextPath2
= DevicePathToText
->ConvertDevicePathToText(
245 RetVal
= UnicodeCollation
->StriColl(