From a4ee2a4f9296f00dbda066817b5bdba4f437097e Mon Sep 17 00:00:00 2001 From: jcarsey Date: Mon, 9 Nov 2009 23:33:11 +0000 Subject: [PATCH] Adding new library instance for SortLib with built in function for sorting device paths. git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@9399 6f19259b-4bc3-4df7-8a09-765794883524 --- ShellPkg/Library/UefiSortLib/UefiSortLib.c | 254 +++++++++++++++++++ ShellPkg/Library/UefiSortLib/UefiSortLib.inf | 49 ++++ 2 files changed, 303 insertions(+) create mode 100644 ShellPkg/Library/UefiSortLib/UefiSortLib.c create mode 100644 ShellPkg/Library/UefiSortLib/UefiSortLib.inf diff --git a/ShellPkg/Library/UefiSortLib/UefiSortLib.c b/ShellPkg/Library/UefiSortLib/UefiSortLib.c new file mode 100644 index 0000000000..e7a8d1e952 --- /dev/null +++ b/ShellPkg/Library/UefiSortLib/UefiSortLib.c @@ -0,0 +1,254 @@ +/** @file + Library used for sorting routines. + +Copyright (c) 2009, Intel Corporation +All rights reserved. This program and the accompanying materials +are licensed and made available under the terms and conditions of the BSD License +which accompanies this distribution. The full text of the license may be found at +http://opensource.org/licenses/bsd-license.php + +THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, +WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. + +**/ + +#include + +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +/** + Worker function for QuickSorting. This function is identical to PerformQuickSort, + except that is uses the pre-allocated buffer so the in place sorting does not need to + allocate and free buffers constantly. + + Each element must be equal sized. + + if BufferToSort is NULL, then ASSERT. + if CompareFunction is NULL, then ASSERT. + if Buffer is NULL, then ASSERT. + + if Count is < 2 then perform no action. + if Size is < 1 then perform no action. + + @param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements + on return a buffer of sorted elements + @param[in] Count the number of elements in the buffer to sort + @param[in] ElementSize Size of an element in bytes + @param[in] CompareFunction The function to call to perform the comparison + of any 2 elements + @param[in] Buffer Buffer of size ElementSize for use in swapping +**/ +VOID +EFIAPI +QuickSortWorker ( + IN OUT VOID *BufferToSort, + IN CONST UINTN Count, + IN CONST UINTN ElementSize, + IN SORT_COMPARE CompareFunction, + IN VOID *Buffer + ){ + VOID *Pivot; + UINTN LoopCount; + UINTN NextSwapLocation; + + ASSERT(BufferToSort != NULL); + ASSERT(CompareFunction != NULL); + ASSERT(Buffer != NULL); + + if ( Count < 2 + || ElementSize < 1 + ){ + return; + } + + NextSwapLocation = 0; + + // + // pick a pivot (we choose last element) + // + Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize)); + + // + // Now get the pivot such that all on "left" are below it + // and everything "right" are above it + // + for ( LoopCount = 0 + ; LoopCount < Count -1 + ; LoopCount++ + ){ + // + // if the element is less than the pivot + // + if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){ + // + // swap + // + CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize); + CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize); + CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize); + + // + // increment NextSwapLocation + // + NextSwapLocation++; + } + } + // + // swap pivot to it's final position (NextSwapLocaiton) + // + CopyMem (Buffer, Pivot, ElementSize); + CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize); + CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize); + + // + // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element + // IE list is sorted left half, pivot element, sorted right half... + // + QuickSortWorker( + BufferToSort, + NextSwapLocation, + ElementSize, + CompareFunction, + Buffer); + + QuickSortWorker( + (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize, + Count - NextSwapLocation - 1, + ElementSize, + CompareFunction, + Buffer); + + return; +} +/** + Function to perform a Quick Sort alogrithm on a buffer of comparable elements. + + Each element must be equal sized. + + if BufferToSort is NULL, then ASSERT. + if CompareFunction is NULL, then ASSERT. + + if Count is < 2 then perform no action. + if Size is < 1 then perform no action. + + @param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements + on return a buffer of sorted elements + @param[in] Count the number of elements in the buffer to sort + @param[in] ElementSize Size of an element in bytes + @param[in] CompareFunction The function to call to perform the comparison + of any 2 elements +**/ +VOID +EFIAPI +PerformQuickSort ( + IN OUT VOID *BufferToSort, + IN CONST UINTN Count, + IN CONST UINTN ElementSize, + IN SORT_COMPARE CompareFunction + ){ + VOID *Buffer; + + ASSERT(BufferToSort != NULL); + ASSERT(CompareFunction != NULL); + + Buffer = AllocatePool(ElementSize); + ASSERT(Buffer != NULL); + + QuickSortWorker( + BufferToSort, + Count, + ElementSize, + CompareFunction, + Buffer); + + FreePool(Buffer); + return; +} + +/** + function to compare 2 device paths for use in QuickSort + + @param[in] Buffer1 pointer to Device Path poiner to compare + @param[in] Buffer2 pointer to second DevicePath pointer to compare + + @retval 0 Buffer1 equal to Buffer2 + @return < 0 Buffer1 is less than Buffer2 + @return > 0 Buffer1 is greater than Buffer2 +**/ +INTN +DevicePathCompare ( + IN VOID *Buffer1, + IN VOID *Buffer2 + ){ + EFI_DEVICE_PATH_PROTOCOL *DevicePath1; + EFI_DEVICE_PATH_PROTOCOL *DevicePath2; + CHAR16 *TextPath1; + CHAR16 *TextPath2; + EFI_STATUS Status; + INTN RetVal; + + STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL *DevicePathToText = NULL; + STATIC EFI_UNICODE_COLLATION_PROTOCOL *UnicodeCollation = NULL; + + DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1; + DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2; + + if (DevicePath1 == NULL) { + if (DevicePath2 == NULL) { + return 0; + } + + return -1; + } + + if (DevicePath2 == NULL) { + return 1; + } + + if (DevicePathToText == NULL) { + Status = gBS->LocateProtocol( + &gEfiDevicePathToTextProtocolGuid, + NULL, + (VOID**)&DevicePathToText); + + ASSERT_EFI_ERROR(Status); + } + + if (UnicodeCollation == NULL) { + Status = gBS->LocateProtocol( + &gEfiUnicodeCollation2ProtocolGuid, + NULL, + (VOID**)&UnicodeCollation); + + ASSERT_EFI_ERROR(Status); + } + + TextPath1 = DevicePathToText->ConvertDevicePathToText( + DevicePath1, + FALSE, + FALSE); + + TextPath2 = DevicePathToText->ConvertDevicePathToText( + DevicePath2, + FALSE, + FALSE); + + RetVal = UnicodeCollation->StriColl( + UnicodeCollation, + TextPath1, + TextPath2); + + FreePool(TextPath1); + FreePool(TextPath2); + + return (RetVal); +} \ No newline at end of file diff --git a/ShellPkg/Library/UefiSortLib/UefiSortLib.inf b/ShellPkg/Library/UefiSortLib/UefiSortLib.inf new file mode 100644 index 0000000000..a93c42dab0 --- /dev/null +++ b/ShellPkg/Library/UefiSortLib/UefiSortLib.inf @@ -0,0 +1,49 @@ +#/** @file +# Library used for sorting routines. +# +# Copyright (c) 2009, Intel Corporation. +# +# All rights reserved. This program and the accompanying materials +# are licensed and made available under the terms and conditions of the BSD License +# which accompanies this distribution. The full text of the license may be found at +# http://opensource.org/licenses/bsd-license.php +# THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, +# WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. +# +# +#**/ + +[Defines] + INF_VERSION = 0x00010006 + BASE_NAME = UefiSortLib + FILE_GUID = 4264A823-45A3-42db-B92C-AA078555CBD3 + MODULE_TYPE = UEFI_DRIVER + VERSION_STRING = 1.0 + LIBRARY_CLASS = SORTLib|UEFI_APPLICATION UEFI_DRIVER + +# +# VALID_ARCHITECTURES = IA32 X64 IPF EBC +# + +[Sources.common] + UefiSortLib.c + +[Packages] + MdePkg/MdePkg.dec + ShellPkg/ShellPkg.dec + +[LibraryClasses] + MemoryAllocationLib + BaseLib + BaseMemoryLib + DebugLib + UefiBootServicesTableLib + +[Protocols] + gEfiUnicodeCollation2ProtocolGuid # ALWAYS_CONSUMED + gEfiDevicePathProtocolGuid # ALWAYS_CONSUMED + gEfiDevicePathToTextProtocolGuid # ALWAYS_CONSUMED + +[Guids] + +[Pcd.common] -- 2.39.2