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

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