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