[mirror_edk2.git] / ShellPkg / Library / UefiSortLib / UefiSortLib.c

/** @file\r
  Library used for sorting routines.\r
\r
Copyright (c) 2009, Intel Corporation<BR>\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 <Protocol/UnicodeCollation.h>\r
#include <Protocol/DevicePath.h>\r
#include <Protocol/DevicePathToText.h>\r
\r
#include <Library/UefiBootServicesTableLib.h>\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
{\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
{\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
\r
/**\r
  function to compare 2 device paths for use in QuickSort\r
\r
  @param[in] Buffer1            pointer to Device Path poiner to compare\r
  @param[in] Buffer2            pointer to second DevicePath pointer to compare\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
INTN\r
DevicePathCompare (\r
  IN  VOID             *Buffer1,\r
  IN  VOID             *Buffer2\r
  )\r
{\r
  EFI_DEVICE_PATH_PROTOCOL  *DevicePath1;\r
  EFI_DEVICE_PATH_PROTOCOL  *DevicePath2;\r
  CHAR16                    *TextPath1;\r
  CHAR16                    *TextPath2;\r
  EFI_STATUS                Status;\r
  INTN                      RetVal;\r
   \r
  STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL *DevicePathToText = NULL;\r
  STATIC EFI_UNICODE_COLLATION_PROTOCOL   *UnicodeCollation = NULL;\r
\r
  DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;\r
  DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;\r
\r
  if (DevicePath1 == NULL) {\r
    if (DevicePath2 == NULL) {\r
      return 0;\r
    }\r
\r
    return -1;\r
  }\r
\r
  if (DevicePath2 == NULL) {\r
    return 1;\r
  }\r
  \r
  if (DevicePathToText == NULL) {\r
    Status = gBS->LocateProtocol(\r
      &gEfiDevicePathToTextProtocolGuid,\r
      NULL,\r
      (VOID**)&DevicePathToText);\r
\r
    ASSERT_EFI_ERROR(Status);\r
  }\r
\r
  if (UnicodeCollation == NULL) {\r
    Status = gBS->LocateProtocol(\r
      &gEfiUnicodeCollation2ProtocolGuid,\r
      NULL,\r
      (VOID**)&UnicodeCollation);\r
\r
    ASSERT_EFI_ERROR(Status);\r
  }\r
\r
  TextPath1 = DevicePathToText->ConvertDevicePathToText(\r
    DevicePath1,\r
    FALSE,\r
    FALSE);\r
\r
  TextPath2 = DevicePathToText->ConvertDevicePathToText(\r
    DevicePath2,\r
    FALSE,\r
    FALSE);\r
  \r
  RetVal = UnicodeCollation->StriColl(\r
    UnicodeCollation,\r
    TextPath1,\r
    TextPath2);\r
\r
  FreePool(TextPath1);\r
  FreePool(TextPath2);\r
\r
  return (RetVal);\r
}
Commit	Line	Data
a4ee2a4f	1	/** @file\r
	2	Library used for sorting routines.\r
	3	\r
a31bd33c	4	Copyright (c) 2009, Intel Corporation<BR>\r
a4ee2a4f	5	All rights reserved. This program and the accompanying materials\r
	6	are licensed and made available under the terms and conditions of the BSD License\r
	7	which accompanies this distribution. The full text of the license may be found at\r
	8	http://opensource.org/licenses/bsd-license.php\r
	9	\r
	10	THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
	11	WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
	12	\r
	13	**/\r
	14	\r
	15	#include <Uefi.h>\r
	16	\r
	17	#include <Protocol/UnicodeCollation.h>\r
	18	#include <Protocol/DevicePath.h>\r
	19	#include <Protocol/DevicePathToText.h>\r
	20	\r
	21	#include <Library/UefiBootServicesTableLib.h>\r
	22	#include <Library/BaseLib.h>\r
	23	#include <Library/BaseMemoryLib.h>\r
	24	#include <Library/DebugLib.h>\r
	25	#include <Library/MemoryAllocationLib.h>\r
	26	#include <Library/SortLib.h> \r
	27	\r
	28	/**\r
	29	Worker function for QuickSorting. This function is identical to PerformQuickSort, \r
	30	except that is uses the pre-allocated buffer so the in place sorting does not need to \r
	31	allocate and free buffers constantly.\r
	32	\r
	33	Each element must be equal sized.\r
	34	\r
	35	if BufferToSort is NULL, then ASSERT.\r
	36	if CompareFunction is NULL, then ASSERT.\r
	37	if Buffer is NULL, then ASSERT.\r
	38	\r
	39	if Count is < 2 then perform no action.\r
	40	if Size is < 1 then perform no action.\r
	41	\r
	42	@param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements\r
	43	on return a buffer of sorted elements\r
	44	@param[in] Count the number of elements in the buffer to sort\r
	45	@param[in] ElementSize Size of an element in bytes\r
	46	@param[in] CompareFunction The function to call to perform the comparison \r
	47	of any 2 elements\r
	48	@param[in] Buffer Buffer of size ElementSize for use in swapping\r
	49	**/\r
	50	VOID\r
	51	EFIAPI\r
	52	QuickSortWorker (\r
	53	IN OUT VOID *BufferToSort,\r
	54	IN CONST UINTN Count,\r
	55	IN CONST UINTN ElementSize,\r
	56	IN SORT_COMPARE CompareFunction,\r
	57	IN VOID *Buffer\r
125c2cf4	58	)\r
125c2cf4	59	{\r
a4ee2a4f	60	VOID *Pivot;\r
	61	UINTN LoopCount;\r
	62	UINTN NextSwapLocation;\r
	63	\r
	64	ASSERT(BufferToSort != NULL);\r
	65	ASSERT(CompareFunction != NULL);\r
	66	ASSERT(Buffer != NULL);\r
	67	\r
	68	if ( Count < 2 \r
	69	\|\| ElementSize < 1\r
	70	){\r
	71	return;\r
	72	}\r
	73	\r
	74	NextSwapLocation = 0;\r
	75	\r
	76	//\r
	77	// pick a pivot (we choose last element)\r
	78	//\r
	79	Pivot = ((UINT8)BufferToSort+((Count-1)ElementSize));\r
	80	\r
	81	//\r
	82	// Now get the pivot such that all on "left" are below it\r
	83	// and everything "right" are above it\r
	84	//\r
	85	for ( LoopCount = 0\r
	86	; LoopCount < Count -1 \r
	87	; LoopCount++\r
	88	){\r
	89	//\r
	90	// if the element is less than the pivot\r
	91	//\r
	92	if (CompareFunction((VOID)((UINT8)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r
	93	//\r
	94	// swap \r
	95	//\r
	96	CopyMem (Buffer, (UINT8)BufferToSort+(NextSwapLocationElementSize), ElementSize);\r
	97	CopyMem ((UINT8)BufferToSort+(NextSwapLocationElementSize), (UINT8)BufferToSort+((LoopCount)ElementSize), ElementSize);\r
	98	CopyMem ((UINT8)BufferToSort+((LoopCount)ElementSize), Buffer, ElementSize);\r
	99	\r
	100	//\r
	101	// increment NextSwapLocation\r
	102	// \r
	103	NextSwapLocation++;\r
	104	}\r
	105	}\r
	106	//\r
	107	// swap pivot to it's final position (NextSwapLocaiton)\r
	108	//\r
	109	CopyMem (Buffer, Pivot, ElementSize);\r
	110	CopyMem (Pivot, (UINT8)BufferToSort+(NextSwapLocationElementSize), ElementSize);\r
	111	CopyMem ((UINT8)BufferToSort+(NextSwapLocationElementSize), Buffer, ElementSize);\r
	112	\r
	113	//\r
	114	// Now recurse on 2 paritial lists. neither of these will have the 'pivot' element \r
	115	// IE list is sorted left half, pivot element, sorted right half...\r
	116	//\r
	117	QuickSortWorker(\r
	118	BufferToSort, \r
	119	NextSwapLocation, \r
	120	ElementSize, \r
	121	CompareFunction,\r
	122	Buffer);\r
	123	\r
124	QuickSortWorker(\r
125	(UINT8 )BufferToSort + (NextSwapLocation+1) ElementSize,\r
126	Count - NextSwapLocation - 1, \r
127	ElementSize, \r
128	CompareFunction,\r
129	Buffer);\r
130	\r
131	return;\r
132	}\r
133	/**\r
134	Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r
135	\r
136	Each element must be equal sized.\r
137	\r
138	if BufferToSort is NULL, then ASSERT.\r
139	if CompareFunction is NULL, then ASSERT.\r
140	\r
141	if Count is < 2 then perform no action.\r
142	if Size is < 1 then perform no action.\r
143	\r
144	@param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements\r
145	on return a buffer of sorted elements\r
146	@param[in] Count the number of elements in the buffer to sort\r
147	@param[in] ElementSize Size of an element in bytes\r
148	@param[in] CompareFunction The function to call to perform the comparison \r
149	of any 2 elements\r
150	**/\r
151	VOID\r
152	EFIAPI\r
153	PerformQuickSort (\r
154	IN OUT VOID *BufferToSort,\r
155	IN CONST UINTN Count,\r
156	IN CONST UINTN ElementSize,\r
157	IN SORT_COMPARE CompareFunction\r
125c2cf4	158	)\r
125c2cf4	159	{\r
a4ee2a4f	160	VOID *Buffer;\r
	161	\r
	162	ASSERT(BufferToSort != NULL);\r
	163	ASSERT(CompareFunction != NULL);\r
	164	\r
	165	Buffer = AllocatePool(ElementSize);\r
	166	ASSERT(Buffer != NULL);\r
	167	\r
	168	QuickSortWorker(\r
	169	BufferToSort,\r
	170	Count,\r
	171	ElementSize,\r
	172	CompareFunction,\r
	173	Buffer);\r
	174	\r
	175	FreePool(Buffer);\r
	176	return;\r
	177	}\r
	178	\r
	179	/**\r
	180	function to compare 2 device paths for use in QuickSort\r
	181	\r
	182	@param[in] Buffer1 pointer to Device Path poiner to compare\r
	183	@param[in] Buffer2 pointer to second DevicePath pointer to compare\r
	184	\r
	185	@retval 0 Buffer1 equal to Buffer2\r
	186	@return < 0 Buffer1 is less than Buffer2\r
	187	@return > 0 Buffer1 is greater than Buffer2 \r
	188	**/\r
	189	INTN\r
	190	DevicePathCompare (\r
	191	IN VOID *Buffer1,\r
	192	IN VOID *Buffer2\r
125c2cf4	193	)\r
125c2cf4	194	{\r
a4ee2a4f	195	EFI_DEVICE_PATH_PROTOCOL *DevicePath1;\r
	196	EFI_DEVICE_PATH_PROTOCOL *DevicePath2;\r
	197	CHAR16 *TextPath1;\r
	198	CHAR16 *TextPath2;\r
	199	EFI_STATUS Status;\r
	200	INTN RetVal;\r
	201	\r
	202	STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL *DevicePathToText = NULL;\r
	203	STATIC EFI_UNICODE_COLLATION_PROTOCOL *UnicodeCollation = NULL;\r
	204	\r
	205	DevicePath1 = (EFI_DEVICE_PATH_PROTOCOL*)Buffer1;\r
	206	DevicePath2 = (EFI_DEVICE_PATH_PROTOCOL*)Buffer2;\r
	207	\r
	208	if (DevicePath1 == NULL) {\r
	209	if (DevicePath2 == NULL) {\r
	210	return 0;\r
	211	}\r
	212	\r
	213	return -1;\r
	214	}\r
	215	\r
	216	if (DevicePath2 == NULL) {\r
	217	return 1;\r
	218	}\r
	219	\r
	220	if (DevicePathToText == NULL) {\r
	221	Status = gBS->LocateProtocol(\r
	222	&gEfiDevicePathToTextProtocolGuid,\r
	223	NULL,\r
	224	(VOID**)&DevicePathToText);\r
	225	\r
	226	ASSERT_EFI_ERROR(Status);\r
	227	}\r
	228	\r
	229	if (UnicodeCollation == NULL) {\r
	230	Status = gBS->LocateProtocol(\r
	231	&gEfiUnicodeCollation2ProtocolGuid,\r
	232	NULL,\r
	233	(VOID**)&UnicodeCollation);\r
	234	\r
	235	ASSERT_EFI_ERROR(Status);\r
	236	}\r
	237	\r
	238	TextPath1 = DevicePathToText->ConvertDevicePathToText(\r
	239	DevicePath1,\r
	240	FALSE,\r
	241	FALSE);\r
	242	\r
	243	TextPath2 = DevicePathToText->ConvertDevicePathToText(\r
	244	DevicePath2,\r
	245	FALSE,\r
	246	FALSE);\r
	247	\r
	248	RetVal = UnicodeCollation->StriColl(\r
	249	UnicodeCollation,\r
	250	TextPath1,\r
	251	TextPath2);\r
	252	\r
	253	FreePool(TextPath1);\r
	254	FreePool(TextPath2);\r
	255	\r
	256	return (RetVal);\r
	257	}