diff options
| -rw-r--r-- | ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.c | 58 | ||||
| -rw-r--r-- | ShellPkg/Application/ShellSortTestApp/ShellSortTestApp.inf | 47 | ||||
| -rw-r--r-- | ShellPkg/Include/Library/SortLib.h | 62 | ||||
| -rw-r--r-- | ShellPkg/Library/BaseSortLib/BaseSortLib.c | 170 | ||||
| -rw-r--r-- | ShellPkg/Library/BaseSortLib/BaseSortLib.inf | 45 | ||||
| -rw-r--r-- | ShellPkg/ShellPkg.dec | 7 | ||||
| -rw-r--r-- | ShellPkg/ShellPkg.dsc | 6 |
7 files changed, 393 insertions, 2 deletions
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 <Uefi.h>
+#include <Library/UefiLib.h>
+#include <Library/DebugLib.h>
+#include <Library/ShellCEntryLib.h>
+#include <Library/SortLib.h>
+
+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 <Uefi.h>
+
+#include <Library/BaseLib.h>
+#include <Library/BaseMemoryLib.h>
+#include <Library/DebugLib.h>
+#include <Library/MemoryAllocationLib.h>
+#include <Library/SortLib.h>
+
+/**
+ 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 |