]>
Commit | Line | Data |
---|---|---|
4983ca93 | 1 | /** @file\r |
2 | Library used for sorting routines.\r | |
3 | \r | |
ae591c14 | 4 | Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>\r |
1e6e84c7 | 5 | This program and the accompanying materials\r |
6 | are licensed and made available under the terms and conditions of the BSD License\r | |
7 | which accompanies this distribution. The full text of the license may be found at\r | |
8 | http://opensource.org/licenses/bsd-license.php\r | |
4983ca93 | 9 | \r |
1e6e84c7 | 10 | THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r |
11 | WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r | |
4983ca93 | 12 | \r |
13 | **/\r | |
4983ca93 | 14 | #include <Uefi.h>\r |
15 | \r | |
16 | #include <Library/BaseLib.h>\r | |
17 | #include <Library/BaseMemoryLib.h>\r | |
18 | #include <Library/DebugLib.h>\r | |
19 | #include <Library/MemoryAllocationLib.h>\r | |
1e6e84c7 | 20 | #include <Library/SortLib.h>\r |
4983ca93 | 21 | \r |
22 | /**\r | |
1e6e84c7 | 23 | Worker function for QuickSorting. This function is identical to PerformQuickSort,\r |
24 | except that is uses the pre-allocated buffer so the in place sorting does not need to\r | |
4983ca93 | 25 | allocate and free buffers constantly.\r |
26 | \r | |
27 | Each element must be equal sized.\r | |
28 | \r | |
29 | if BufferToSort is NULL, then ASSERT.\r | |
30 | if CompareFunction is NULL, then ASSERT.\r | |
31 | if Buffer is NULL, then ASSERT.\r | |
32 | \r | |
33 | if Count is < 2 then perform no action.\r | |
34 | if Size is < 1 then perform no action.\r | |
35 | \r | |
4ff7e37b ED |
36 | @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r |
37 | on return a buffer of sorted elements\r | |
38 | @param[in] Count the number of elements in the buffer to sort\r | |
39 | @param[in] ElementSize Size of an element in bytes\r | |
40 | @param[in] CompareFunction The function to call to perform the comparison\r | |
41 | of any 2 elements\r | |
42 | @param[in] Buffer Buffer of size ElementSize for use in swapping\r | |
4983ca93 | 43 | **/\r |
44 | VOID\r | |
45 | EFIAPI\r | |
46 | QuickSortWorker (\r | |
47 | IN OUT VOID *BufferToSort,\r | |
48 | IN CONST UINTN Count,\r | |
49 | IN CONST UINTN ElementSize,\r | |
50 | IN SORT_COMPARE CompareFunction,\r | |
51 | IN VOID *Buffer\r | |
125c2cf4 | 52 | )\r |
53 | {\r | |
4983ca93 | 54 | VOID *Pivot;\r |
55 | UINTN LoopCount;\r | |
56 | UINTN NextSwapLocation;\r | |
57 | \r | |
58 | ASSERT(BufferToSort != NULL);\r | |
59 | ASSERT(CompareFunction != NULL);\r | |
60 | ASSERT(Buffer != NULL);\r | |
61 | \r | |
1e6e84c7 | 62 | if ( Count < 2\r |
4983ca93 | 63 | || ElementSize < 1\r |
a405b86d | 64 | ){\r |
4983ca93 | 65 | return;\r |
66 | }\r | |
67 | \r | |
68 | NextSwapLocation = 0;\r | |
69 | \r | |
70 | //\r | |
71 | // pick a pivot (we choose last element)\r | |
72 | //\r | |
73 | Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));\r | |
74 | \r | |
75 | //\r | |
76 | // Now get the pivot such that all on "left" are below it\r | |
77 | // and everything "right" are above it\r | |
78 | //\r | |
79 | for ( LoopCount = 0\r | |
1e6e84c7 | 80 | ; LoopCount < Count -1\r |
4983ca93 | 81 | ; LoopCount++\r |
a405b86d | 82 | ){\r |
4983ca93 | 83 | //\r |
84 | // if the element is less than the pivot\r | |
85 | //\r | |
86 | if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r | |
87 | //\r | |
1e6e84c7 | 88 | // swap\r |
4983ca93 | 89 | //\r |
90 | CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r | |
91 | CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);\r | |
92 | CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);\r | |
93 | \r | |
94 | //\r | |
95 | // increment NextSwapLocation\r | |
1e6e84c7 | 96 | //\r |
4983ca93 | 97 | NextSwapLocation++;\r |
98 | }\r | |
99 | }\r | |
100 | //\r | |
101 | // swap pivot to it's final position (NextSwapLocaiton)\r | |
102 | //\r | |
103 | CopyMem (Buffer, Pivot, ElementSize);\r | |
104 | CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r | |
105 | CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);\r | |
106 | \r | |
107 | //\r | |
1e6e84c7 | 108 | // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element\r |
4983ca93 | 109 | // IE list is sorted left half, pivot element, sorted right half...\r |
110 | //\r | |
5dcb5355 | 111 | if (NextSwapLocation >= 2) {\r |
112 | QuickSortWorker(\r | |
113 | BufferToSort,\r | |
114 | NextSwapLocation,\r | |
115 | ElementSize,\r | |
116 | CompareFunction,\r | |
117 | Buffer);\r | |
118 | }\r | |
4983ca93 | 119 | \r |
5dcb5355 | 120 | if ((Count - NextSwapLocation - 1) >= 2) {\r |
121 | QuickSortWorker(\r | |
122 | (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,\r | |
123 | Count - NextSwapLocation - 1,\r | |
124 | ElementSize,\r | |
125 | CompareFunction,\r | |
126 | Buffer);\r | |
127 | }\r | |
4983ca93 | 128 | return;\r |
129 | }\r | |
130 | /**\r | |
131 | Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r | |
132 | \r | |
133 | Each element must be equal sized.\r | |
134 | \r | |
135 | if BufferToSort is NULL, then ASSERT.\r | |
136 | if CompareFunction is NULL, then ASSERT.\r | |
137 | \r | |
138 | if Count is < 2 then perform no action.\r | |
139 | if Size is < 1 then perform no action.\r | |
140 | \r | |
4ff7e37b ED |
141 | @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r |
142 | on return a buffer of sorted elements\r | |
143 | @param[in] Count the number of elements in the buffer to sort\r | |
144 | @param[in] ElementSize Size of an element in bytes\r | |
145 | @param[in] CompareFunction The function to call to perform the comparison\r | |
146 | of any 2 elements\r | |
4983ca93 | 147 | **/\r |
148 | VOID\r | |
149 | EFIAPI\r | |
150 | PerformQuickSort (\r | |
151 | IN OUT VOID *BufferToSort,\r | |
152 | IN CONST UINTN Count,\r | |
153 | IN CONST UINTN ElementSize,\r | |
154 | IN SORT_COMPARE CompareFunction\r | |
125c2cf4 | 155 | )\r |
156 | {\r | |
4983ca93 | 157 | VOID *Buffer;\r |
158 | \r | |
159 | ASSERT(BufferToSort != NULL);\r | |
160 | ASSERT(CompareFunction != NULL);\r | |
161 | \r | |
5a0fe66e | 162 | Buffer = AllocateZeroPool(ElementSize);\r |
4983ca93 | 163 | ASSERT(Buffer != NULL);\r |
164 | \r | |
165 | QuickSortWorker(\r | |
166 | BufferToSort,\r | |
167 | Count,\r | |
168 | ElementSize,\r | |
169 | CompareFunction,\r | |
170 | Buffer);\r | |
171 | \r | |
172 | FreePool(Buffer);\r | |
173 | return;\r | |
174 | }\r | |
125c2cf4 | 175 | \r |
176 | /**\r | |
177 | Not supported in Base version.\r | |
1e6e84c7 | 178 | \r |
a405b86d | 179 | @param[in] Buffer1 Ignored.\r |
180 | @param[in] Buffer2 Ignored.\r | |
181 | \r | |
125c2cf4 | 182 | ASSERT and return 0.\r |
183 | **/\r | |
184 | INTN\r | |
21ecdf15 | 185 | EFIAPI\r |
125c2cf4 | 186 | DevicePathCompare (\r |
b3011f40 | 187 | IN CONST VOID *Buffer1,\r |
188 | IN CONST VOID *Buffer2\r | |
125c2cf4 | 189 | )\r |
190 | {\r | |
191 | ASSERT(FALSE);\r | |
192 | return 0;\r | |
70328967 | 193 | }\r |
11d2decf | 194 | \r |
195 | /**\r | |
196 | Function to compare 2 strings without regard to case of the characters.\r | |
197 | \r | |
198 | @param[in] Buffer1 Pointer to String to compare.\r | |
199 | @param[in] Buffer2 Pointer to second String to compare.\r | |
200 | \r | |
201 | @retval 0 Buffer1 equal to Buffer2.\r | |
202 | @return < 0 Buffer1 is less than Buffer2.\r | |
1e6e84c7 | 203 | @return > 0 Buffer1 is greater than Buffer2.\r |
11d2decf | 204 | **/\r |
205 | INTN\r | |
206 | EFIAPI\r | |
207 | StringNoCaseCompare (\r | |
b3011f40 | 208 | IN CONST VOID *Buffer1,\r |
209 | IN CONST VOID *Buffer2\r | |
11d2decf | 210 | )\r |
211 | {\r | |
212 | ASSERT(FALSE);\r | |
213 | return 0;\r | |
214 | }\r | |
215 | \r | |
216 | \r | |
a405b86d | 217 | /**\r |
218 | Function to compare 2 strings.\r | |
219 | \r | |
220 | @param[in] Buffer1 Pointer to String to compare (CHAR16**).\r | |
221 | @param[in] Buffer2 Pointer to second String to compare (CHAR16**).\r | |
222 | \r | |
223 | @retval 0 Buffer1 equal to Buffer2.\r | |
224 | @return < 0 Buffer1 is less than Buffer2.\r | |
225 | @return > 0 Buffer1 is greater than Buffer2.\r | |
226 | **/\r | |
227 | INTN\r | |
228 | EFIAPI\r | |
229 | StringCompare (\r | |
230 | IN CONST VOID *Buffer1,\r | |
231 | IN CONST VOID *Buffer2\r | |
232 | )\r | |
233 | {\r | |
234 | ASSERT(FALSE);\r | |
235 | return 0;\r | |
236 | }\r | |
237 | \r | |
238 | \r |