1 /** @file
2 Library used for sorting routines.
3
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
9
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.
12
13 **/
14
15 #include <Uefi.h>
16
17 #include <Protocol/UnicodeCollation.h>
18 #include <Protocol/DevicePath.h>
19
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>
27
28 STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation = NULL;
29
30 #define USL_FREE_NON_NULL(Pointer) \
31 { \
32 if ((Pointer) != NULL) { \
33 FreePool((Pointer)); \
34 (Pointer) = NULL; \
35 } \
36 }
37
38 /**
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.
42
43 Each element must be equal sized.
44
45 if BufferToSort is NULL, then ASSERT.
46 if CompareFunction is NULL, then ASSERT.
47 if Buffer is NULL, then ASSERT.
48
49 if Count is < 2 then perform no action.
50 if Size is < 1 then perform no action.
51
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
57 of any 2 elements
58 @param[in] Buffer Buffer of size ElementSize for use in swapping
59 **/
60 VOID
61 EFIAPI
QuickSortWorker(IN OUT VOID * BufferToSort,IN CONST UINTN Count,IN CONST UINTN ElementSize,IN SORT_COMPARE CompareFunction,IN VOID * Buffer)62 QuickSortWorker (
63 IN OUT VOID *BufferToSort,
64 IN CONST UINTN Count,
65 IN CONST UINTN ElementSize,
66 IN SORT_COMPARE CompareFunction,
67 IN VOID *Buffer
68 )
69 {
70 VOID *Pivot;
71 UINTN LoopCount;
72 UINTN NextSwapLocation;
73
74 ASSERT(BufferToSort != NULL);
75 ASSERT(CompareFunction != NULL);
76 ASSERT(Buffer != NULL);
77
78 if ( Count < 2
79 || ElementSize < 1
80 ){
81 return;
82 }
83
84 NextSwapLocation = 0;
85
86 //
87 // pick a pivot (we choose last element)
88 //
89 Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));
90
91 //
92 // Now get the pivot such that all on "left" are below it
93 // and everything "right" are above it
94 //
95 for ( LoopCount = 0
96 ; LoopCount < Count -1
97 ; LoopCount++
98 ){
99 //
100 // if the element is less than the pivot
101 //
102 if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
103 //
104 // swap
105 //
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);
109
110 //
111 // increment NextSwapLocation
112 //
113 NextSwapLocation++;
114 }
115 }
116 //
117 // swap pivot to it's final position (NextSwapLocaiton)
118 //
119 CopyMem (Buffer, Pivot, ElementSize);
120 CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
121 CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
122
123 //
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...
126 //
127 if (NextSwapLocation >= 2) {
128 QuickSortWorker(
129 BufferToSort,
130 NextSwapLocation,
131 ElementSize,
132 CompareFunction,
133 Buffer);
134 }
135
136 if ((Count - NextSwapLocation - 1) >= 2) {
137 QuickSortWorker(
138 (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
139 Count - NextSwapLocation - 1,
140 ElementSize,
141 CompareFunction,
142 Buffer);
143 }
144
145 return;
146 }
147 /**
148 Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
149
150 Each element must be equal sized.
151
152 if BufferToSort is NULL, then ASSERT.
153 if CompareFunction is NULL, then ASSERT.
154
155 if Count is < 2 then perform no action.
156 if Size is < 1 then perform no action.
157
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
163 of any 2 elements
164 **/
165 VOID
166 EFIAPI
PerformQuickSort(IN OUT VOID * BufferToSort,IN CONST UINTN Count,IN CONST UINTN ElementSize,IN SORT_COMPARE CompareFunction)167 PerformQuickSort (
168 IN OUT VOID *BufferToSort,
169 IN CONST UINTN Count,
170 IN CONST UINTN ElementSize,
171 IN SORT_COMPARE CompareFunction
172 )
173 {
174 VOID *Buffer;
175
176 ASSERT(BufferToSort != NULL);
177 ASSERT(CompareFunction != NULL);
178
179 Buffer = AllocateZeroPool(ElementSize);
180 ASSERT(Buffer != NULL);
181
182 QuickSortWorker(
183 BufferToSort,
184 Count,
185 ElementSize,
186 CompareFunction,
187 Buffer);
188
189 FreePool(Buffer);
190 return;
191 }
192
193 /**
194 Function to compare 2 device paths for use in QuickSort.
195
196 @param[in] Buffer1 pointer to Device Path poiner to compare
197 @param[in] Buffer2 pointer to second DevicePath pointer to compare
198
199 @retval 0 Buffer1 equal to Buffer2
200 @retval <0 Buffer1 is less than Buffer2
201 @retval >0 Buffer1 is greater than Buffer2
202 **/
203 INTN
204 EFIAPI
DevicePathCompare(IN CONST VOID * Buffer1,IN CONST VOID * Buffer2)205 DevicePathCompare (
206 IN CONST VOID *Buffer1,
207 IN CONST VOID *Buffer2
208 )
209 {
210 EFI_DEVICE_PATH_PROTOCOL *DevicePath1;
211 EFI_DEVICE_PATH_PROTOCOL *DevicePath2;
212 CHAR16 *TextPath1;
213 CHAR16 *TextPath2;
214 EFI_STATUS Status;
215 INTN RetVal;
216
217 DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;
218 DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;
219
220 if (DevicePath1 == NULL) {
221 if (DevicePath2 == NULL) {
222 return 0;
223 }
224
225 return -1;
226 }
227
228 if (DevicePath2 == NULL) {
229 return 1;
230 }
231
232 if (mUnicodeCollation == NULL) {
233 Status = gBS->LocateProtocol(
234 &gEfiUnicodeCollation2ProtocolGuid,
235 NULL,
236 (VOID**)&mUnicodeCollation);
237
238 ASSERT_EFI_ERROR(Status);
239 }
240
241 TextPath1 = ConvertDevicePathToText(
242 DevicePath1,
243 FALSE,
244 FALSE);
245
246 TextPath2 = ConvertDevicePathToText(
247 DevicePath2,
248 FALSE,
249 FALSE);
250
251 if (TextPath1 == NULL) {
252 RetVal = -1;
253 } else if (TextPath2 == NULL) {
254 RetVal = 1;
255 } else {
256 RetVal = mUnicodeCollation->StriColl(
257 mUnicodeCollation,
258 TextPath1,
259 TextPath2);
260 }
261
262 USL_FREE_NON_NULL(TextPath1);
263 USL_FREE_NON_NULL(TextPath2);
264
265 return (RetVal);
266 }
267
268 /**
269 Function to compare 2 strings without regard to case of the characters.
270
271 @param[in] Buffer1 Pointer to String to compare.
272 @param[in] Buffer2 Pointer to second String to compare.
273
274 @retval 0 Buffer1 equal to Buffer2.
275 @retval <0 Buffer1 is less than Buffer2.
276 @retval >0 Buffer1 is greater than Buffer2.
277 **/
278 INTN
279 EFIAPI
StringNoCaseCompare(IN CONST VOID * Buffer1,IN CONST VOID * Buffer2)280 StringNoCaseCompare (
281 IN CONST VOID *Buffer1,
282 IN CONST VOID *Buffer2
283 )
284 {
285 EFI_STATUS Status;
286 if (mUnicodeCollation == NULL) {
287 Status = gBS->LocateProtocol(
288 &gEfiUnicodeCollation2ProtocolGuid,
289 NULL,
290 (VOID**)&mUnicodeCollation);
291
292 ASSERT_EFI_ERROR(Status);
293 }
294
295 return (mUnicodeCollation->StriColl(
296 mUnicodeCollation,
297 *(CHAR16**)Buffer1,
298 *(CHAR16**)Buffer2));
299 }
300
301
302 /**
303 Function to compare 2 strings.
304
305 @param[in] Buffer1 Pointer to String to compare (CHAR16**).
306 @param[in] Buffer2 Pointer to second String to compare (CHAR16**).
307
308 @retval 0 Buffer1 equal to Buffer2.
309 @retval <0 Buffer1 is less than Buffer2.
310 @retval >0 Buffer1 is greater than Buffer2.
311 **/
312 INTN
313 EFIAPI
StringCompare(IN CONST VOID * Buffer1,IN CONST VOID * Buffer2)314 StringCompare (
315 IN CONST VOID *Buffer1,
316 IN CONST VOID *Buffer2
317 )
318 {
319 return (StrCmp(
320 *(CHAR16**)Buffer1,
321 *(CHAR16**)Buffer2));
322 }
323