]>
Commit | Line | Data |
---|---|---|
a4ee2a4f | 1 | /** @file\r |
2 | Library used for sorting routines.\r | |
3 | \r | |
99325a8b | 4 | Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>\r |
9d510e61 | 5 | SPDX-License-Identifier: BSD-2-Clause-Patent\r |
a4ee2a4f | 6 | \r |
7 | **/\r | |
8 | \r | |
9 | #include <Uefi.h>\r | |
10 | \r | |
11 | #include <Protocol/UnicodeCollation.h>\r | |
12 | #include <Protocol/DevicePath.h>\r | |
a4ee2a4f | 13 | \r |
14 | #include <Library/UefiBootServicesTableLib.h>\r | |
15 | #include <Library/BaseLib.h>\r | |
16 | #include <Library/BaseMemoryLib.h>\r | |
17 | #include <Library/DebugLib.h>\r | |
18 | #include <Library/MemoryAllocationLib.h>\r | |
1e6e84c7 | 19 | #include <Library/SortLib.h>\r |
863986b3 | 20 | #include <Library/DevicePathLib.h>\r |
a4ee2a4f | 21 | \r |
1436aea4 | 22 | STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation = NULL;\r |
11d2decf | 23 | \r |
ae591c14 DM |
24 | #define USL_FREE_NON_NULL(Pointer) \\r |
25 | { \\r | |
26 | if ((Pointer) != NULL) { \\r | |
27 | FreePool((Pointer)); \\r | |
28 | (Pointer) = NULL; \\r | |
29 | } \\r | |
30 | }\r | |
11d2decf | 31 | \r |
a4ee2a4f | 32 | /**\r |
33 | Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r | |
34 | \r | |
35 | Each element must be equal sized.\r | |
36 | \r | |
37 | if BufferToSort is NULL, then ASSERT.\r | |
38 | if CompareFunction is NULL, then ASSERT.\r | |
39 | \r | |
40 | if Count is < 2 then perform no action.\r | |
41 | if Size is < 1 then perform no action.\r | |
42 | \r | |
4ff7e37b ED |
43 | @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r |
44 | on return a buffer of sorted elements\r | |
45 | @param[in] Count the number of elements in the buffer to sort\r | |
46 | @param[in] ElementSize Size of an element in bytes\r | |
47 | @param[in] CompareFunction The function to call to perform the comparison\r | |
48 | of any 2 elements\r | |
a4ee2a4f | 49 | **/\r |
50 | VOID\r | |
51 | EFIAPI\r | |
52 | PerformQuickSort (\r | |
1436aea4 MK |
53 | IN OUT VOID *BufferToSort,\r |
54 | IN CONST UINTN Count,\r | |
55 | IN CONST UINTN ElementSize,\r | |
56 | IN SORT_COMPARE CompareFunction\r | |
125c2cf4 | 57 | )\r |
58 | {\r | |
a4ee2a4f | 59 | VOID *Buffer;\r |
60 | \r | |
1436aea4 MK |
61 | ASSERT (BufferToSort != NULL);\r |
62 | ASSERT (CompareFunction != NULL);\r | |
a4ee2a4f | 63 | \r |
1436aea4 MK |
64 | Buffer = AllocateZeroPool (ElementSize);\r |
65 | ASSERT (Buffer != NULL);\r | |
a4ee2a4f | 66 | \r |
99325a8b | 67 | QuickSort (\r |
a4ee2a4f | 68 | BufferToSort,\r |
69 | Count,\r | |
70 | ElementSize,\r | |
71 | CompareFunction,\r | |
99325a8b IK |
72 | Buffer\r |
73 | );\r | |
a4ee2a4f | 74 | \r |
1436aea4 | 75 | FreePool (Buffer);\r |
a4ee2a4f | 76 | return;\r |
77 | }\r | |
78 | \r | |
79 | /**\r | |
da70d025 | 80 | Function to compare 2 device paths for use in QuickSort.\r |
a4ee2a4f | 81 | \r |
82 | @param[in] Buffer1 pointer to Device Path poiner to compare\r | |
83 | @param[in] Buffer2 pointer to second DevicePath pointer to compare\r | |
84 | \r | |
85 | @retval 0 Buffer1 equal to Buffer2\r | |
ae591c14 DM |
86 | @retval <0 Buffer1 is less than Buffer2\r |
87 | @retval >0 Buffer1 is greater than Buffer2\r | |
a4ee2a4f | 88 | **/\r |
89 | INTN\r | |
e26d7b59 | 90 | EFIAPI\r |
a4ee2a4f | 91 | DevicePathCompare (\r |
1436aea4 MK |
92 | IN CONST VOID *Buffer1,\r |
93 | IN CONST VOID *Buffer2\r | |
125c2cf4 | 94 | )\r |
95 | {\r | |
a4ee2a4f | 96 | EFI_DEVICE_PATH_PROTOCOL *DevicePath1;\r |
97 | EFI_DEVICE_PATH_PROTOCOL *DevicePath2;\r | |
98 | CHAR16 *TextPath1;\r | |
99 | CHAR16 *TextPath2;\r | |
100 | EFI_STATUS Status;\r | |
101 | INTN RetVal;\r | |
1e6e84c7 | 102 | \r |
1436aea4 MK |
103 | DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL **)Buffer1;\r |
104 | DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL **)Buffer2;\r | |
a4ee2a4f | 105 | \r |
106 | if (DevicePath1 == NULL) {\r | |
107 | if (DevicePath2 == NULL) {\r | |
108 | return 0;\r | |
109 | }\r | |
110 | \r | |
111 | return -1;\r | |
112 | }\r | |
113 | \r | |
114 | if (DevicePath2 == NULL) {\r | |
115 | return 1;\r | |
116 | }\r | |
1e6e84c7 | 117 | \r |
11d2decf | 118 | if (mUnicodeCollation == NULL) {\r |
1436aea4 MK |
119 | Status = gBS->LocateProtocol (\r |
120 | &gEfiUnicodeCollation2ProtocolGuid,\r | |
121 | NULL,\r | |
122 | (VOID **)&mUnicodeCollation\r | |
123 | );\r | |
a4ee2a4f | 124 | \r |
1436aea4 | 125 | ASSERT_EFI_ERROR (Status);\r |
a4ee2a4f | 126 | }\r |
127 | \r | |
1436aea4 MK |
128 | TextPath1 = ConvertDevicePathToText (\r |
129 | DevicePath1,\r | |
130 | FALSE,\r | |
131 | FALSE\r | |
132 | );\r | |
a4ee2a4f | 133 | \r |
1436aea4 MK |
134 | TextPath2 = ConvertDevicePathToText (\r |
135 | DevicePath2,\r | |
136 | FALSE,\r | |
137 | FALSE\r | |
138 | );\r | |
1e6e84c7 | 139 | \r |
eca218a7 | 140 | if (TextPath1 == NULL) {\r |
141 | RetVal = -1;\r | |
142 | } else if (TextPath2 == NULL) {\r | |
143 | RetVal = 1;\r | |
144 | } else {\r | |
1436aea4 MK |
145 | RetVal = mUnicodeCollation->StriColl (\r |
146 | mUnicodeCollation,\r | |
147 | TextPath1,\r | |
148 | TextPath2\r | |
149 | );\r | |
eca218a7 | 150 | }\r |
a4ee2a4f | 151 | \r |
1436aea4 MK |
152 | USL_FREE_NON_NULL (TextPath1);\r |
153 | USL_FREE_NON_NULL (TextPath2);\r | |
a4ee2a4f | 154 | \r |
155 | return (RetVal);\r | |
11d2decf | 156 | }\r |
157 | \r | |
158 | /**\r | |
159 | Function to compare 2 strings without regard to case of the characters.\r | |
160 | \r | |
161 | @param[in] Buffer1 Pointer to String to compare.\r | |
162 | @param[in] Buffer2 Pointer to second String to compare.\r | |
163 | \r | |
164 | @retval 0 Buffer1 equal to Buffer2.\r | |
ae591c14 DM |
165 | @retval <0 Buffer1 is less than Buffer2.\r |
166 | @retval >0 Buffer1 is greater than Buffer2.\r | |
11d2decf | 167 | **/\r |
168 | INTN\r | |
169 | EFIAPI\r | |
170 | StringNoCaseCompare (\r | |
1436aea4 MK |
171 | IN CONST VOID *Buffer1,\r |
172 | IN CONST VOID *Buffer2\r | |
11d2decf | 173 | )\r |
174 | {\r | |
1436aea4 MK |
175 | EFI_STATUS Status;\r |
176 | \r | |
11d2decf | 177 | if (mUnicodeCollation == NULL) {\r |
1436aea4 MK |
178 | Status = gBS->LocateProtocol (\r |
179 | &gEfiUnicodeCollation2ProtocolGuid,\r | |
180 | NULL,\r | |
181 | (VOID **)&mUnicodeCollation\r | |
182 | );\r | |
11d2decf | 183 | \r |
1436aea4 | 184 | ASSERT_EFI_ERROR (Status);\r |
11d2decf | 185 | }\r |
186 | \r | |
1436aea4 MK |
187 | return (mUnicodeCollation->StriColl (\r |
188 | mUnicodeCollation,\r | |
189 | *(CHAR16 **)Buffer1,\r | |
190 | *(CHAR16 **)Buffer2\r | |
191 | ));\r | |
11d2decf | 192 | }\r |
193 | \r | |
a405b86d | 194 | /**\r |
195 | Function to compare 2 strings.\r | |
196 | \r | |
197 | @param[in] Buffer1 Pointer to String to compare (CHAR16**).\r | |
198 | @param[in] Buffer2 Pointer to second String to compare (CHAR16**).\r | |
199 | \r | |
200 | @retval 0 Buffer1 equal to Buffer2.\r | |
ae591c14 DM |
201 | @retval <0 Buffer1 is less than Buffer2.\r |
202 | @retval >0 Buffer1 is greater than Buffer2.\r | |
a405b86d | 203 | **/\r |
204 | INTN\r | |
205 | EFIAPI\r | |
206 | StringCompare (\r | |
1436aea4 MK |
207 | IN CONST VOID *Buffer1,\r |
208 | IN CONST VOID *Buffer2\r | |
a405b86d | 209 | )\r |
210 | {\r | |
1436aea4 MK |
211 | return (StrCmp (\r |
212 | *(CHAR16 **)Buffer1,\r | |
213 | *(CHAR16 **)Buffer2\r | |
214 | ));\r | |
a405b86d | 215 | }\r |