--- /dev/null
+/** @file\r
+ This is a test application that demonstrates how to use the sorting functions.\r
+\r
+ Copyright (c) 2009, Intel Corporation \r
+ All rights reserved. This program and the accompanying materials \r
+ are licensed and made available under the terms and conditions of the BSD License \r
+ which accompanies this distribution. The full text of the license may be found at \r
+ http://opensource.org/licenses/bsd-license.php \r
+\r
+ THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, \r
+ WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. \r
+\r
+**/\r
+\r
+#include <Uefi.h>\r
+#include <Library/UefiLib.h>\r
+#include <Library/DebugLib.h>\r
+#include <Library/ShellCEntryLib.h>\r
+#include <Library/SortLib.h>\r
+\r
+INTN Test(VOID*b1, VOID*b2)\r
+{\r
+ if (*(INTN*)b1 == *(INTN*)b2) {\r
+ return (0);\r
+ }\r
+ if (*(INTN*)b1 < *(INTN*)b2) {\r
+ return(-1);\r
+ }\r
+ return (1);\r
+}\r
+\r
+/**\r
+ UEFI application entry point which has an interface similar to a\r
+ standard C main function.\r
+\r
+ The ShellCEntryLib library instance wrappers the actual UEFI application\r
+ entry point and calls this ShellAppMain function.\r
+\r
+ @param ImageHandle The image handle of the UEFI Application.\r
+ @param SystemTable A pointer to the EFI System Table.\r
+\r
+ @retval 0 The application exited normally.\r
+ @retval Other An error occurred.\r
+\r
+**/\r
+INTN \r
+EFIAPI \r
+ShellAppMain (\r
+ IN UINTN Argc, \r
+ IN CHAR16 **Argv\r
+ ){\r
+ INTN Array[10] = {2,3,4,1,5,6,7,8,1,5};\r
+ 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]);\r
+ PerformQuickSort(Array, 10, sizeof(INTN), Test);\r
+ Print(L"POST-SORT\r\n");\r
+ 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]);\r
+ return 0;\r
+}\r
--- /dev/null
+#/** @file\r
+# This is the shell sorting testing application\r
+#\r
+# Copyright (c) 2009, Intel Corporation.\r
+#\r
+# All rights reserved. This program and the accompanying materials\r
+# are licensed and made available under the terms and conditions of the BSD License\r
+# which accompanies this distribution. The full text of the license may be found at\r
+# http://opensource.org/licenses/bsd-license.php\r
+# THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
+# WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
+#\r
+#\r
+#**/\r
+\r
+[Defines]\r
+ INF_VERSION = 0x00010006\r
+ BASE_NAME = ShellSortTestApp\r
+ FILE_GUID = 079E8E98-AE93-4b9a-8A71-1DC869F23E09\r
+ MODULE_TYPE = UEFI_APPLICATION\r
+ VERSION_STRING = 1.0\r
+ ENTRY_POINT = ShellCEntryLib\r
+\r
+#\r
+# The following information is for reference only and not required by the build tools.\r
+#\r
+# VALID_ARCHITECTURES = IA32 X64 IPF EBC\r
+#\r
+\r
+[Sources]\r
+ ShellSortTestApp.c\r
+\r
+[Packages]\r
+ MdePkg/MdePkg.dec\r
+ ShellPkg/ShellPkg.dec\r
+ \r
+[LibraryClasses]\r
+ ShellCEntryLib\r
+ UefiLib\r
+ SortLib\r
+ \r
+[Guids]\r
+\r
+[Protocols]\r
+\r
+\r
+[Pcd]\r
--- /dev/null
+/** @file\r
+ Library used for sorting routines.\r
+\r
+Copyright (c) 2009, Intel Corporation\r
+All rights reserved. This program and the accompanying materials\r
+are licensed and made available under the terms and conditions of the BSD License\r
+which accompanies this distribution. The full text of the license may be found at\r
+http://opensource.org/licenses/bsd-license.php\r
+\r
+THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
+WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
+\r
+**/\r
+\r
+#if !defined(__SORT_LIB_H__)\r
+#define __SORT_LIB_H__\r
+\r
+/**\r
+ Prototype for comparison function for any 2 element types.\r
+\r
+ @param[in] Buffer1 pointer to first buffer\r
+ @param[in] Buffer2 pointer to second buffer \r
+\r
+ @retval 0 Buffer1 equal to Buffer2\r
+ @return < 0 Buffer1 is less than Buffer2\r
+ @return > 0 Buffer1 is greater than Buffer2\r
+**/\r
+typedef\r
+INTN\r
+(EFIAPI *SORT_COMPARE)(\r
+ IN VOID *Buffer1,\r
+ IN VOID *Buffer2\r
+ );\r
+\r
+/**\r
+ Function to perform a Quick Sort on a buffer of comparable elements.\r
+\r
+ Each element must be equally sized.\r
+\r
+ if BufferToSort is NULL, then ASSERT.\r
+ if CompareFunction is NULL, then ASSERT.\r
+\r
+ if Count is < 2 then perform no action.\r
+ if Size is < 1 then perform no action.\r
+\r
+ @param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements\r
+ on return a buffer of sorted elements\r
+ @param[in] Count the number of elements in the buffer to sort\r
+ @param[in] ElementSize Size of an element in bytes\r
+ @param[in] CompareFunction The function to call to perform the comparison \r
+ of any 2 elements\r
+**/\r
+VOID\r
+EFIAPI\r
+PerformQuickSort (\r
+ IN OUT VOID *BufferToSort,\r
+ IN CONST UINTN Count,\r
+ IN CONST UINTN ElementSize,\r
+ IN SORT_COMPARE CompareFunction\r
+ );\r
+\r
+#endif //__SORT_LIB_H__\r
--- /dev/null
+/** @file\r
+ Library used for sorting routines.\r
+\r
+Copyright (c) 2009, Intel Corporation\r
+All rights reserved. This program and the accompanying materials\r
+are licensed and made available under the terms and conditions of the BSD License\r
+which accompanies this distribution. The full text of the license may be found at\r
+http://opensource.org/licenses/bsd-license.php\r
+\r
+THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
+WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
+\r
+**/\r
+\r
+#include <Uefi.h>\r
+\r
+#include <Library/BaseLib.h>\r
+#include <Library/BaseMemoryLib.h>\r
+#include <Library/DebugLib.h>\r
+#include <Library/MemoryAllocationLib.h>\r
+#include <Library/SortLib.h> \r
+\r
+/**\r
+ Worker function for QuickSorting. This function is identical to PerformQuickSort, \r
+ except that is uses the pre-allocated buffer so the in place sorting does not need to \r
+ allocate and free buffers constantly.\r
+\r
+ Each element must be equal sized.\r
+\r
+ if BufferToSort is NULL, then ASSERT.\r
+ if CompareFunction is NULL, then ASSERT.\r
+ if Buffer is NULL, then ASSERT.\r
+\r
+ if Count is < 2 then perform no action.\r
+ if Size is < 1 then perform no action.\r
+\r
+ @param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements\r
+ on return a buffer of sorted elements\r
+ @param[in] Count the number of elements in the buffer to sort\r
+ @param[in] ElementSize Size of an element in bytes\r
+ @param[in] CompareFunction The function to call to perform the comparison \r
+ of any 2 elements\r
+ @param[in] Buffer Buffer of size ElementSize for use in swapping\r
+**/\r
+VOID\r
+EFIAPI\r
+QuickSortWorker (\r
+ IN OUT VOID *BufferToSort,\r
+ IN CONST UINTN Count,\r
+ IN CONST UINTN ElementSize,\r
+ IN SORT_COMPARE CompareFunction,\r
+ IN VOID *Buffer\r
+ ){\r
+ VOID *Pivot;\r
+ UINTN LoopCount;\r
+ UINTN NextSwapLocation;\r
+\r
+ ASSERT(BufferToSort != NULL);\r
+ ASSERT(CompareFunction != NULL);\r
+ ASSERT(Buffer != NULL);\r
+\r
+ if ( Count < 2 \r
+ || ElementSize < 1\r
+ ){\r
+ return;\r
+ }\r
+\r
+ NextSwapLocation = 0;\r
+\r
+ //\r
+ // pick a pivot (we choose last element)\r
+ //\r
+ Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));\r
+\r
+ //\r
+ // Now get the pivot such that all on "left" are below it\r
+ // and everything "right" are above it\r
+ //\r
+ for ( LoopCount = 0\r
+ ; LoopCount < Count -1 \r
+ ; LoopCount++\r
+ ){\r
+ //\r
+ // if the element is less than the pivot\r
+ //\r
+ if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r
+ //\r
+ // swap \r
+ //\r
+ CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
+ CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);\r
+ CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);\r
+\r
+ //\r
+ // increment NextSwapLocation\r
+ // \r
+ NextSwapLocation++;\r
+ }\r
+ }\r
+ //\r
+ // swap pivot to it's final position (NextSwapLocaiton)\r
+ //\r
+ CopyMem (Buffer, Pivot, ElementSize);\r
+ CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
+ CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);\r
+\r
+ //\r
+ // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element \r
+ // IE list is sorted left half, pivot element, sorted right half...\r
+ //\r
+ QuickSortWorker(\r
+ BufferToSort, \r
+ NextSwapLocation, \r
+ ElementSize, \r
+ CompareFunction,\r
+ Buffer);\r
+\r
+ QuickSortWorker(\r
+ (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,\r
+ Count - NextSwapLocation - 1, \r
+ ElementSize, \r
+ CompareFunction,\r
+ Buffer);\r
+\r
+ return;\r
+}\r
+/**\r
+ Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r
+\r
+ Each element must be equal sized.\r
+\r
+ if BufferToSort is NULL, then ASSERT.\r
+ if CompareFunction is NULL, then ASSERT.\r
+\r
+ if Count is < 2 then perform no action.\r
+ if Size is < 1 then perform no action.\r
+\r
+ @param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements\r
+ on return a buffer of sorted elements\r
+ @param[in] Count the number of elements in the buffer to sort\r
+ @param[in] ElementSize Size of an element in bytes\r
+ @param[in] CompareFunction The function to call to perform the comparison \r
+ of any 2 elements\r
+**/\r
+VOID\r
+EFIAPI\r
+PerformQuickSort (\r
+ IN OUT VOID *BufferToSort,\r
+ IN CONST UINTN Count,\r
+ IN CONST UINTN ElementSize,\r
+ IN SORT_COMPARE CompareFunction\r
+ ){\r
+ VOID *Buffer;\r
+\r
+ ASSERT(BufferToSort != NULL);\r
+ ASSERT(CompareFunction != NULL);\r
+\r
+ Buffer = AllocatePool(ElementSize);\r
+ ASSERT(Buffer != NULL);\r
+\r
+ QuickSortWorker(\r
+ BufferToSort,\r
+ Count,\r
+ ElementSize,\r
+ CompareFunction,\r
+ Buffer);\r
+\r
+ FreePool(Buffer);\r
+ return;\r
+}\r
--- /dev/null
+#/** @file\r
+# Library used for sorting routines.\r
+#\r
+# Copyright (c) 2009, Intel Corporation.\r
+#\r
+# All rights reserved. This program and the accompanying materials\r
+# are licensed and made available under the terms and conditions of the BSD License\r
+# which accompanies this distribution. The full text of the license may be found at\r
+# http://opensource.org/licenses/bsd-license.php\r
+# THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
+# WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
+#\r
+#\r
+#**/\r
+\r
+[Defines]\r
+ INF_VERSION = 0x00010006\r
+ BASE_NAME = BaseSortLib\r
+ FILE_GUID = 03F3331B-F12D-494f-BF37-E55A657F2497\r
+ MODULE_TYPE = UEFI_DRIVER\r
+ VERSION_STRING = 1.0\r
+ LIBRARY_CLASS = SORTLib|UEFI_APPLICATION UEFI_DRIVER\r
+\r
+#\r
+# VALID_ARCHITECTURES = IA32 X64 IPF EBC\r
+#\r
+\r
+[Sources.common]\r
+ BaseSortLib.c\r
+\r
+[Packages]\r
+ MdePkg/MdePkg.dec\r
+ ShellPkg/ShellPkg.dec\r
+\r
+[LibraryClasses]\r
+ MemoryAllocationLib\r
+ BaseLib\r
+ BaseMemoryLib\r
+ DebugLib\r
+\r
+[Protocols]\r
+\r
+[Guids]\r
+\r
+[Pcd.common]\r
##\r
FileHandleLib|Include/Library/FileHandleLib.h\r
\r
- ## Allows for a shell application to have a C style entry point\r
+ ## @libraryclass Allows for a shell application to have a C style entry point\r
+ ##\r
ShellCEntryLib|Include/Library/ShellCEntryLib.h\r
\r
+ ## @libraryclass Provides sorting functions\r
+ ##\r
+ SortLib|Include/Library/Sortlib.h\r
+\r
\r
[Guids.common]\r
gEfiShellEnvironment2ExtGuid = {0xd2c18636, 0x40e5, 0x4eb5, {0xa3, 0x1b, 0x36, 0x69, 0x5f, 0xd4, 0x2c, 0x87}}\r
ShellLib|ShellPkg/Library/UefiShellLib/UefiShellLib.inf\r
FileHandleLib|ShellPkg/Library/BaseFileHandleLib/BaseFileHandleLib.inf\r
ShellCEntryLib|ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf\r
+ SortLib|ShellPkg/Library/BaseSortLib/BaseSortLib.inf\r
+\r
[PcdsFixedAtBuild.common]\r
\r
[Components.common]\r
ShellPkg/Library/BaseFileHandleLib/BaseFileHandleLib.inf\r
ShellPkg/Library/UefiShellLib/UefiShellLib.inf\r
ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf\r
- ShellPkg/Application/ShellCTestApp/ShellCTestApp.inf
\ No newline at end of file
+ ShellPkg/Library/BaseSortLib/BaseSortLib.inf\r
+ ShellPkg/Application/ShellCTestApp/ShellCTestApp.inf\r
+ ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.inf
\ No newline at end of file