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

/** @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 <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
  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
\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
  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
	4	Copyright (c) 2009, Intel Corporation\r
	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
	58	){\r
	59	VOID *Pivot;\r
	60	UINTN LoopCount;\r
	61	UINTN NextSwapLocation;\r
	62	\r
	63	ASSERT(BufferToSort != NULL);\r
	64	ASSERT(CompareFunction != NULL);\r
65	ASSERT(Buffer != NULL);\r
66	\r
67	if ( Count < 2 \r
68	\|\| ElementSize < 1\r
69	){\r
70	return;\r
71	}\r
72	\r
73	NextSwapLocation = 0;\r
74	\r
75	//\r
76	// pick a pivot (we choose last element)\r
77	//\r
78	Pivot = ((UINT8)BufferToSort+((Count-1)ElementSize));\r
79	\r
80	//\r
81	// Now get the pivot such that all on "left" are below it\r
82	// and everything "right" are above it\r
83	//\r
84	for ( LoopCount = 0\r
85	; LoopCount < Count -1 \r
86	; LoopCount++\r
87	){\r
88	//\r
89	// if the element is less than the pivot\r
90	//\r
91	if (CompareFunction((VOID)((UINT8)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r
92	//\r
93	// swap \r
94	//\r
95	CopyMem (Buffer, (UINT8)BufferToSort+(NextSwapLocationElementSize), ElementSize);\r
96	CopyMem ((UINT8)BufferToSort+(NextSwapLocationElementSize), (UINT8)BufferToSort+((LoopCount)ElementSize), ElementSize);\r
97	CopyMem ((UINT8)BufferToSort+((LoopCount)ElementSize), Buffer, ElementSize);\r
98	\r
99	//\r
100	// increment NextSwapLocation\r
101	// \r
102	NextSwapLocation++;\r
103	}\r
104	}\r
105	//\r
106	// swap pivot to it's final position (NextSwapLocaiton)\r
107	//\r
108	CopyMem (Buffer, Pivot, ElementSize);\r
109	CopyMem (Pivot, (UINT8)BufferToSort+(NextSwapLocationElementSize), ElementSize);\r
110	CopyMem ((UINT8)BufferToSort+(NextSwapLocationElementSize), Buffer, ElementSize);\r
111	\r
112	//\r
113	// Now recurse on 2 paritial lists. neither of these will have the 'pivot' element \r
114	// IE list is sorted left half, pivot element, sorted right half...\r
115	//\r
116	QuickSortWorker(\r
117	BufferToSort, \r
118	NextSwapLocation, \r
119	ElementSize, \r
120	CompareFunction,\r
121	Buffer);\r
122	\r
123	QuickSortWorker(\r
124	(UINT8 )BufferToSort + (NextSwapLocation+1) ElementSize,\r
125	Count - NextSwapLocation - 1, \r
126	ElementSize, \r
127	CompareFunction,\r
128	Buffer);\r
129	\r
130	return;\r
131	}\r
132	/**\r
133	Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r
134	\r
135	Each element must be equal sized.\r
136	\r
137	if BufferToSort is NULL, then ASSERT.\r
138	if CompareFunction is NULL, then ASSERT.\r
139	\r
140	if Count is < 2 then perform no action.\r
141	if Size is < 1 then perform no action.\r
142	\r
143	@param[in,out] BufferToSort on call a Buffer of (possibly sorted) elements\r
144	on return a buffer of sorted elements\r
145	@param[in] Count the number of elements in the buffer to sort\r
146	@param[in] ElementSize Size of an element in bytes\r
147	@param[in] CompareFunction The function to call to perform the comparison \r
148	of any 2 elements\r
149	**/\r
150	VOID\r
151	EFIAPI\r
152	PerformQuickSort (\r
153	IN OUT VOID *BufferToSort,\r
154	IN CONST UINTN Count,\r
155	IN CONST UINTN ElementSize,\r
156	IN SORT_COMPARE CompareFunction\r
157	){\r
158	VOID *Buffer;\r
159	\r
160	ASSERT(BufferToSort != NULL);\r
161	ASSERT(CompareFunction != NULL);\r
162	\r
163	Buffer = AllocatePool(ElementSize);\r
164	ASSERT(Buffer != NULL);\r
165	\r
166	QuickSortWorker(\r
167	BufferToSort,\r
168	Count,\r
169	ElementSize,\r
170	CompareFunction,\r
171	Buffer);\r
172	\r
173	FreePool(Buffer);\r
174	return;\r
175	}\r
176	\r
177	/**\r
178	function to compare 2 device paths for use in QuickSort\r
179	\r
180	@param[in] Buffer1 pointer to Device Path poiner to compare\r
181	@param[in] Buffer2 pointer to second DevicePath pointer to compare\r
182	\r
183	@retval 0 Buffer1 equal to Buffer2\r
184	@return < 0 Buffer1 is less than Buffer2\r
185	@return > 0 Buffer1 is greater than Buffer2 \r
186	**/\r
187	INTN\r
188	DevicePathCompare (\r
189	IN VOID *Buffer1,\r
190	IN VOID *Buffer2\r
191	){\r
192	EFI_DEVICE_PATH_PROTOCOL *DevicePath1;\r
193	EFI_DEVICE_PATH_PROTOCOL *DevicePath2;\r
194	CHAR16 *TextPath1;\r
195	CHAR16 *TextPath2;\r
196	EFI_STATUS Status;\r
197	INTN RetVal;\r
198	\r
199	STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL *DevicePathToText = NULL;\r
200	STATIC EFI_UNICODE_COLLATION_PROTOCOL *UnicodeCollation = NULL;\r
201	\r
202	DevicePath1 = (EFI_DEVICE_PATH_PROTOCOL*)Buffer1;\r
203	DevicePath2 = (EFI_DEVICE_PATH_PROTOCOL*)Buffer2;\r
204	\r
205	if (DevicePath1 == NULL) {\r
206	if (DevicePath2 == NULL) {\r
207	return 0;\r
208	}\r
209	\r
210	return -1;\r
211	}\r
212	\r
213	if (DevicePath2 == NULL) {\r
214	return 1;\r
215	}\r
216	\r
217	if (DevicePathToText == NULL) {\r
218	Status = gBS->LocateProtocol(\r
219	&gEfiDevicePathToTextProtocolGuid,\r
220	NULL,\r
221	(VOID**)&DevicePathToText);\r
222	\r
223	ASSERT_EFI_ERROR(Status);\r
224	}\r
225	\r
226	if (UnicodeCollation == NULL) {\r
227	Status = gBS->LocateProtocol(\r
228	&gEfiUnicodeCollation2ProtocolGuid,\r
229	NULL,\r
230	(VOID**)&UnicodeCollation);\r
231	\r
232	ASSERT_EFI_ERROR(Status);\r
233	}\r
234	\r
235	TextPath1 = DevicePathToText->ConvertDevicePathToText(\r
236	DevicePath1,\r
237	FALSE,\r
238	FALSE);\r
239	\r
240	TextPath2 = DevicePathToText->ConvertDevicePathToText(\r
241	DevicePath2,\r
242	FALSE,\r
243	FALSE);\r
244	\r
245	RetVal = UnicodeCollation->StriColl(\r
246	UnicodeCollation,\r
247	TextPath1,\r
248	TextPath2);\r
249	\r
250	FreePool(TextPath1);\r
251	FreePool(TextPath2);\r
252	\r
253	return (RetVal);\r
254	}