From 4983ca934c85ed80b15264d3a7ee10a4d3c0d51f Mon Sep 17 00:00:00 2001 From: jcarsey Date: Mon, 13 Jul 2009 19:33:35 +0000 Subject: [PATCH 1/1] add: 1) sorting library 2) sorting test Application/ShellSortTestApp update DEC and DSC for 2 additions git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@8938 6f19259b-4bc3-4df7-8a09-765794883524 --- .../ShellSortTestApp/ShellSortTestApp.c | 58 ++++++ .../ShellSortTestApp/ShellSortTestApp.inf | 47 +++++ ShellPkg/Include/Library/SortLib.h | 62 +++++++ ShellPkg/Library/BaseSortLib/BaseSortLib.c | 170 ++++++++++++++++++ ShellPkg/Library/BaseSortLib/BaseSortLib.inf | 45 +++++ ShellPkg/ShellPkg.dec | 7 +- ShellPkg/ShellPkg.dsc | 6 +- 7 files changed, 393 insertions(+), 2 deletions(-) create mode 100644 ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.c create mode 100644 ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.inf create mode 100644 ShellPkg/Include/Library/SortLib.h create mode 100644 ShellPkg/Library/BaseSortLib/BaseSortLib.c create mode 100644 ShellPkg/Library/BaseSortLib/BaseSortLib.inf diff --git a/ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.c b/ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.c new file mode 100644 index 0000000000..5a671e0395 --- /dev/null +++ b/ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.c @@ -0,0 +1,58 @@ +/** @file + This is a test application that demonstrates how to use the sorting functions. + + 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 + +INTN Test(VOID*b1, VOID*b2) +{ + if (*(INTN*)b1 == *(INTN*)b2) { + return (0); + } + if (*(INTN*)b1 < *(INTN*)b2) { + return(-1); + } + return (1); +} + +/** + UEFI application entry point which has an interface similar to a + standard C main function. + + The ShellCEntryLib library instance wrappers the actual UEFI application + entry point and calls this ShellAppMain function. + + @param ImageHandle The image handle of the UEFI Application. + @param SystemTable A pointer to the EFI System Table. + + @retval 0 The application exited normally. + @retval Other An error occurred. + +**/ +INTN +EFIAPI +ShellAppMain ( + IN UINTN Argc, + IN CHAR16 **Argv + ){ + INTN Array[10] = {2,3,4,1,5,6,7,8,1,5}; + Print(L"Array = %d, %d, %d, %d, %d, %d, %d, %d, %d, %d\r\n", Array[0],Array[1],Array[2],Array[3],Array[4],Array[5],Array[6],Array[7],Array[8],Array[9]); + PerformQuickSort(Array, 10, sizeof(INTN), Test); + Print(L"POST-SORT\r\n"); + Print(L"Array = %d, %d, %d, %d, %d, %d, %d, %d, %d, %d\r\n", Array[0],Array[1],Array[2],Array[3],Array[4],Array[5],Array[6],Array[7],Array[8],Array[9]); + return 0; +} diff --git a/ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.inf b/ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.inf new file mode 100644 index 0000000000..87b87983b8 --- /dev/null +++ b/ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.inf @@ -0,0 +1,47 @@ +#/** @file +# This is the shell sorting testing application +# +# 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 = ShellSortTestApp + FILE_GUID = 079E8E98-AE93-4b9a-8A71-1DC869F23E09 + MODULE_TYPE = UEFI_APPLICATION + VERSION_STRING = 1.0 + ENTRY_POINT = ShellCEntryLib + +# +# The following information is for reference only and not required by the build tools. +# +# VALID_ARCHITECTURES = IA32 X64 IPF EBC +# + +[Sources] + ShellSortTestApp.c + +[Packages] + MdePkg/MdePkg.dec + ShellPkg/ShellPkg.dec + +[LibraryClasses] + ShellCEntryLib + UefiLib + SortLib + +[Guids] + +[Protocols] + + +[Pcd] diff --git a/ShellPkg/Include/Library/SortLib.h b/ShellPkg/Include/Library/SortLib.h new file mode 100644 index 0000000000..ecc538e4b3 --- /dev/null +++ b/ShellPkg/Include/Library/SortLib.h @@ -0,0 +1,62 @@ +/** @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. + +**/ + +#if !defined(__SORT_LIB_H__) +#define __SORT_LIB_H__ + +/** + Prototype for comparison function for any 2 element types. + + @param[in] Buffer1 pointer to first buffer + @param[in] Buffer2 pointer to second buffer + + @retval 0 Buffer1 equal to Buffer2 + @return < 0 Buffer1 is less than Buffer2 + @return > 0 Buffer1 is greater than Buffer2 +**/ +typedef +INTN +(EFIAPI *SORT_COMPARE)( + IN VOID *Buffer1, + IN VOID *Buffer2 + ); + +/** + Function to perform a Quick Sort on a buffer of comparable elements. + + Each element must be equally 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 + ); + +#endif //__SORT_LIB_H__ diff --git a/ShellPkg/Library/BaseSortLib/BaseSortLib.c b/ShellPkg/Library/BaseSortLib/BaseSortLib.c new file mode 100644 index 0000000000..04d818efd1 --- /dev/null +++ b/ShellPkg/Library/BaseSortLib/BaseSortLib.c @@ -0,0 +1,170 @@ +/** @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 + +/** + 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; +} diff --git a/ShellPkg/Library/BaseSortLib/BaseSortLib.inf b/ShellPkg/Library/BaseSortLib/BaseSortLib.inf new file mode 100644 index 0000000000..3ce3b9f98d --- /dev/null +++ b/ShellPkg/Library/BaseSortLib/BaseSortLib.inf @@ -0,0 +1,45 @@ +#/** @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 = BaseSortLib + FILE_GUID = 03F3331B-F12D-494f-BF37-E55A657F2497 + MODULE_TYPE = UEFI_DRIVER + VERSION_STRING = 1.0 + LIBRARY_CLASS = SORTLib|UEFI_APPLICATION UEFI_DRIVER + +# +# VALID_ARCHITECTURES = IA32 X64 IPF EBC +# + +[Sources.common] + BaseSortLib.c + +[Packages] + MdePkg/MdePkg.dec + ShellPkg/ShellPkg.dec + +[LibraryClasses] + MemoryAllocationLib + BaseLib + BaseMemoryLib + DebugLib + +[Protocols] + +[Guids] + +[Pcd.common] diff --git a/ShellPkg/ShellPkg.dec b/ShellPkg/ShellPkg.dec index 7e0b1a07c5..4c7292b3b0 100644 --- a/ShellPkg/ShellPkg.dec +++ b/ShellPkg/ShellPkg.dec @@ -37,9 +37,14 @@ ## FileHandleLib|Include/Library/FileHandleLib.h - ## Allows for a shell application to have a C style entry point + ## @libraryclass Allows for a shell application to have a C style entry point + ## ShellCEntryLib|Include/Library/ShellCEntryLib.h + ## @libraryclass Provides sorting functions + ## + SortLib|Include/Library/Sortlib.h + [Guids.common] gEfiShellEnvironment2ExtGuid = {0xd2c18636, 0x40e5, 0x4eb5, {0xa3, 0x1b, 0x36, 0x69, 0x5f, 0xd4, 0x2c, 0x87}} diff --git a/ShellPkg/ShellPkg.dsc b/ShellPkg/ShellPkg.dsc index 97eb76e965..86c6c82829 100644 --- a/ShellPkg/ShellPkg.dsc +++ b/ShellPkg/ShellPkg.dsc @@ -41,6 +41,8 @@ ShellLib|ShellPkg/Library/UefiShellLib/UefiShellLib.inf FileHandleLib|ShellPkg/Library/BaseFileHandleLib/BaseFileHandleLib.inf ShellCEntryLib|ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf + SortLib|ShellPkg/Library/BaseSortLib/BaseSortLib.inf + [PcdsFixedAtBuild.common] [Components.common] @@ -49,4 +51,6 @@ ShellPkg/Library/BaseFileHandleLib/BaseFileHandleLib.inf ShellPkg/Library/UefiShellLib/UefiShellLib.inf ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf - ShellPkg/Application/ShellCTestApp/ShellCTestApp.inf \ No newline at end of file + ShellPkg/Library/BaseSortLib/BaseSortLib.inf + ShellPkg/Application/ShellCTestApp/ShellCTestApp.inf + ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.inf \ No newline at end of file -- 2.39.2