[mirror_edk2.git] / EdkCompatibilityPkg / Foundation / Library / EfiCommonLib / LinkedList.c

/*++\r
\r
Copyright (c) 2004, 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
Module Name:\r
\r
  LinkedList.c\r
\r
Abstract:\r
\r
  Linked List Library Functions\r
\r
--*/\r
\r
#include "Tiano.h"\r
#include "EfiDriverLib.h"\r
\r
\r
VOID\r
InitializeListHead (\r
  EFI_LIST_ENTRY       *List\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Initialize the head of the List.  The caller must allocate the memory \r
  for the EFI_LIST. This function must be called before the other linked\r
  list macros can be used.\r
    \r
Arguments:\r
\r
  List - Pointer to list head to initialize\r
   \r
Returns:\r
\r
  None.\r
\r
--*/\r
\r
{\r
  List->ForwardLink = List;\r
  List->BackLink    = List;\r
}\r
\r
\r
BOOLEAN\r
IsListEmpty (\r
  EFI_LIST_ENTRY  *List\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Return TRUE is the list contains zero nodes. Otherzise return FALSE.\r
  The list must have been initialized with InitializeListHead () before using \r
  this function.\r
    \r
Arguments:\r
\r
  List - Pointer to list head to test\r
\r
   \r
Returns:\r
\r
  Return TRUE is the list contains zero nodes. Otherzise return FALSE.\r
\r
--*/\r
{\r
  return (BOOLEAN)(List->ForwardLink == List);\r
}\r
\r
\r
VOID\r
RemoveEntryList (\r
  EFI_LIST_ENTRY  *Entry\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Remove Node from the doubly linked list. It is the caller's responsibility\r
  to free any memory used by the entry if needed. The list must have been \r
  initialized with InitializeListHead () before using this function.\r
    \r
Arguments:\r
\r
  Entry - Element to remove from the list.\r
   \r
Returns:\r
  \r
  None\r
\r
--*/\r
{\r
  EFI_LIST_ENTRY  *_ForwardLink;\r
  EFI_LIST_ENTRY  *_BackLink;\r
\r
  _ForwardLink           = Entry->ForwardLink;\r
  _BackLink              = Entry->BackLink;      \r
  _BackLink->ForwardLink = _ForwardLink;\r
  _ForwardLink->BackLink = _BackLink;   \r
\r
  DEBUG_CODE (\r
    Entry->ForwardLink = (EFI_LIST_ENTRY *) EFI_BAD_POINTER;\r
    Entry->BackLink    = (EFI_LIST_ENTRY *) EFI_BAD_POINTER;\r
  )\r
}\r
\r
\r
VOID\r
InsertTailList (\r
  EFI_LIST_ENTRY  *ListHead,\r
  EFI_LIST_ENTRY  *Entry\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Insert a Node into the end of a doubly linked list. The list must have \r
  been initialized with InitializeListHead () before using this function.\r
    \r
Arguments:\r
\r
  ListHead - Head of doubly linked list\r
\r
  Entry    - Element to insert at the end of the list.\r
   \r
Returns:\r
  \r
  None\r
\r
--*/\r
{\r
  EFI_LIST_ENTRY *_ListHead;\r
  EFI_LIST_ENTRY *_BackLink;\r
\r
  _ListHead              = ListHead;              \r
  _BackLink              = _ListHead->BackLink;     \r
  Entry->ForwardLink     = _ListHead;    \r
  Entry->BackLink        = _BackLink;       \r
  _BackLink->ForwardLink = Entry;    \r
  _ListHead->BackLink    = Entry;       \r
}\r
\r
\r
\r
VOID\r
InsertHeadList (\r
  EFI_LIST_ENTRY  *ListHead,\r
  EFI_LIST_ENTRY  *Entry\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Insert a Node into the start of a doubly linked list. The list must have \r
  been initialized with InitializeListHead () before using this function.\r
    \r
Arguments:\r
\r
  ListHead - Head of doubly linked list\r
\r
  Entry    - Element to insert to beginning of list\r
   \r
Returns:\r
  \r
  None\r
\r
--*/\r
{\r
  EFI_LIST_ENTRY  *_ListHead;\r
  EFI_LIST_ENTRY  *_ForwardLink;\r
\r
  _ListHead               = ListHead;                 \r
  _ForwardLink            = _ListHead->ForwardLink;  \r
  Entry->ForwardLink      = _ForwardLink;    \r
  Entry->BackLink         = _ListHead;          \r
  _ForwardLink->BackLink  = Entry;       \r
  _ListHead->ForwardLink  = Entry;       \r
}\r
\r
VOID\r
SwapListEntries (\r
  EFI_LIST_ENTRY  *Entry1,\r
  EFI_LIST_ENTRY  *Entry2\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Swap the location of the two elements of a doubly linked list. Node2 \r
  is placed in front of Node1. The list must have been initialized with \r
  InitializeListHead () before using this function.\r
    \r
Arguments:\r
\r
  Entry1 - Element in the doubly linked list in front of Node2. \r
\r
  Entry2 - Element in the doubly linked list behind Node1.\r
   \r
Returns:\r
  \r
  None\r
\r
--*/\r
{\r
  EFI_LIST_ENTRY *Entry1ForwardLink;\r
  EFI_LIST_ENTRY *Entry1BackLink;\r
  EFI_LIST_ENTRY *Entry2ForwardLink;\r
  EFI_LIST_ENTRY *Entry2BackLink;\r
\r
  Entry2ForwardLink           = Entry2->ForwardLink;          \r
  Entry2BackLink              = Entry2->BackLink;                \r
  Entry1ForwardLink           = Entry1->ForwardLink;          \r
  Entry1BackLink              = Entry1->BackLink;                \r
  Entry2BackLink->ForwardLink = Entry2ForwardLink;    \r
  Entry2ForwardLink->BackLink = Entry2BackLink;       \r
  Entry2->ForwardLink         = Entry1;                     \r
  Entry2->BackLink            = Entry1BackLink;                \r
  Entry1BackLink->ForwardLink = Entry2;             \r
  Entry1->BackLink            = Entry2;                      \r
}\r
\r
\r
EFI_LIST_ENTRY *\r
GetFirstNode (\r
  EFI_LIST_ENTRY  *List \r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Return the first node pointed to by the list head.  The list must \r
  have been initialized with InitializeListHead () before using this \r
  function and must contain data.\r
    \r
Arguments:\r
\r
  List - The head of the doubly linked list.\r
   \r
Returns:\r
  \r
  Pointer to the first node, if the list contains nodes.  The list will\r
  return a null value--that is, the value of List--when the list is empty.\r
    See the description of IsNull for more information.\r
\r
\r
--*/\r
{\r
  return List->ForwardLink;\r
}\r
\r
\r
EFI_LIST_ENTRY *\r
GetNextNode (\r
  EFI_LIST_ENTRY  *List,\r
  EFI_LIST_ENTRY  *Node\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Returns the node following Node in the list. The list must \r
  have been initialized with InitializeListHead () before using this \r
  function and must contain data.\r
    \r
Arguments:\r
\r
  List - The head of the list.  MUST NOT be the literal value NULL.\r
  Node - The node in the list.  This value MUST NOT be the literal value NULL.\r
    See the description of IsNull for more information.\r
   \r
Returns:\r
  \r
  Pointer to the next node, if one exists.  Otherwise, returns a null value,\r
  which is actually a pointer to List.\r
    See the description of IsNull for more information.\r
\r
--*/\r
{\r
  if (Node == List) {\r
    return List;\r
  } \r
  return Node->ForwardLink;\r
}\r
\r
\r
BOOLEAN \r
IsNull ( \r
  EFI_LIST_ENTRY  *List,\r
  EFI_LIST_ENTRY  *Node \r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Determines whether the given node is null.  Note that Node is null\r
  when its value is equal to the value of List.  It is an error for\r
  Node to be the literal value NULL [(VOID*)0x0].\r
\r
Arguments:\r
\r
  List - The head of the list.  MUST NOT be the literal value NULL.\r
  Node - The node to test.  MUST NOT be the literal value NULL.  See\r
    the description above.\r
   \r
Returns:\r
  \r
  Returns true if the node is null.\r
\r
--*/\r
{\r
  return (BOOLEAN)(Node == List);\r
}\r
\r
\r
BOOLEAN \r
IsNodeAtEnd ( \r
  EFI_LIST_ENTRY  *List, \r
  EFI_LIST_ENTRY  *Node \r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Determines whether the given node is at the end of the list.  Used\r
  to walk the list.  The list must have been initialized with \r
  InitializeListHead () before using this function and must contain \r
  data.\r
\r
Arguments:\r
\r
  List - The head of the list.  MUST NOT be the literal value NULL.\r
  Node - The node to test.  MUST NOT be the literal value NULL.\r
    See the description of IsNull for more information.\r
   \r
Returns:\r
  \r
  Returns true if the list is the tail.\r
\r
--*/\r
{\r
  if (IsNull (List, Node)) {\r
    return FALSE;\r
  }\r
  return (BOOLEAN)(List->BackLink == Node);\r
}\r
\r
Commit	Line	Data
3eb9473e	1	/*++\r
3eb9473e	2	\r
4ea9375a HT	3	Copyright (c) 2004, Intel Corporation. All rights reserved.<BR>\r
4ea9375a HT	4	This program and the accompanying materials \r
3eb9473e	5	are licensed and made available under the terms and conditions of the BSD License \r
	6	which accompanies this distribution. The full text of the license may be found at \r
	7	http://opensource.org/licenses/bsd-license.php \r
	8	\r
	9	THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, \r
	10	WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. \r
	11	\r
	12	Module Name:\r
	13	\r
	14	LinkedList.c\r
	15	\r
	16	Abstract:\r
	17	\r
	18	Linked List Library Functions\r
	19	\r
	20	--*/\r
	21	\r
	22	#include "Tiano.h"\r
	23	#include "EfiDriverLib.h"\r
	24	\r
	25	\r
	26	VOID\r
	27	InitializeListHead (\r
	28	EFI_LIST_ENTRY *List\r
	29	)\r
	30	/*++\r
	31	\r
	32	Routine Description:\r
	33	\r
	34	Initialize the head of the List. The caller must allocate the memory \r
	35	for the EFI_LIST. This function must be called before the other linked\r
	36	list macros can be used.\r
	37	\r
	38	Arguments:\r
	39	\r
	40	List - Pointer to list head to initialize\r
	41	\r
	42	Returns:\r
	43	\r
	44	None.\r
	45	\r
	46	--*/\r
	47	\r
	48	{\r
	49	List->ForwardLink = List;\r
	50	List->BackLink = List;\r
	51	}\r
	52	\r
	53	\r
	54	BOOLEAN\r
	55	IsListEmpty (\r
	56	EFI_LIST_ENTRY *List\r
	57	)\r
	58	/*++\r
	59	\r
	60	Routine Description:\r
	61	\r
	62	Return TRUE is the list contains zero nodes. Otherzise return FALSE.\r
	63	The list must have been initialized with InitializeListHead () before using \r
	64	this function.\r
	65	\r
	66	Arguments:\r
	67	\r
	68	List - Pointer to list head to test\r
69	\r
70	\r
71	Returns:\r
72	\r
73	Return TRUE is the list contains zero nodes. Otherzise return FALSE.\r
74	\r
75	--*/\r
76	{\r
77	return (BOOLEAN)(List->ForwardLink == List);\r
78	}\r
79	\r
80	\r
81	VOID\r
82	RemoveEntryList (\r
83	EFI_LIST_ENTRY *Entry\r
84	)\r
85	/*++\r
86	\r
87	Routine Description:\r
88	\r
89	Remove Node from the doubly linked list. It is the caller's responsibility\r
90	to free any memory used by the entry if needed. The list must have been \r
91	initialized with InitializeListHead () before using this function.\r
92	\r
93	Arguments:\r
94	\r
95	Entry - Element to remove from the list.\r
96	\r
97	Returns:\r
98	\r
99	None\r
100	\r
101	--*/\r
102	{\r
103	EFI_LIST_ENTRY *_ForwardLink;\r
104	EFI_LIST_ENTRY *_BackLink;\r
105	\r
106	_ForwardLink = Entry->ForwardLink;\r
107	_BackLink = Entry->BackLink; \r
108	_BackLink->ForwardLink = _ForwardLink;\r
109	_ForwardLink->BackLink = _BackLink; \r
110	\r
111	DEBUG_CODE (\r
112	Entry->ForwardLink = (EFI_LIST_ENTRY *) EFI_BAD_POINTER;\r
113	Entry->BackLink = (EFI_LIST_ENTRY *) EFI_BAD_POINTER;\r
114	)\r
115	}\r
116	\r
117	\r
118	VOID\r
119	InsertTailList (\r
120	EFI_LIST_ENTRY *ListHead,\r
121	EFI_LIST_ENTRY *Entry\r
122	)\r
123	/*++\r
124	\r
125	Routine Description:\r
126	\r
127	Insert a Node into the end of a doubly linked list. The list must have \r
128	been initialized with InitializeListHead () before using this function.\r
129	\r
130	Arguments:\r
131	\r
132	ListHead - Head of doubly linked list\r
133	\r
134	Entry - Element to insert at the end of the list.\r
135	\r
136	Returns:\r
137	\r
138	None\r
139	\r
140	--*/\r
141	{\r
142	EFI_LIST_ENTRY *_ListHead;\r
143	EFI_LIST_ENTRY *_BackLink;\r
144	\r
145	_ListHead = ListHead; \r
146	_BackLink = _ListHead->BackLink; \r
147	Entry->ForwardLink = _ListHead; \r
148	Entry->BackLink = _BackLink; \r
149	_BackLink->ForwardLink = Entry; \r
150	_ListHead->BackLink = Entry; \r
151	}\r
152	\r
153	\r
154	\r
155	VOID\r
156	InsertHeadList (\r
157	EFI_LIST_ENTRY *ListHead,\r
158	EFI_LIST_ENTRY *Entry\r
159	)\r
160	/*++\r
161	\r
162	Routine Description:\r
163	\r
164	Insert a Node into the start of a doubly linked list. The list must have \r
165	been initialized with InitializeListHead () before using this function.\r
166	\r
167	Arguments:\r
168	\r
169	ListHead - Head of doubly linked list\r
170	\r
171	Entry - Element to insert to beginning of list\r
172	\r
173	Returns:\r
174	\r
175	None\r
176	\r
177	--*/\r
178	{\r
179	EFI_LIST_ENTRY *_ListHead;\r
180	EFI_LIST_ENTRY *_ForwardLink;\r
181	\r
182	_ListHead = ListHead; \r
183	_ForwardLink = _ListHead->ForwardLink; \r
184	Entry->ForwardLink = _ForwardLink; \r
185	Entry->BackLink = _ListHead; \r
186	_ForwardLink->BackLink = Entry; \r
187	_ListHead->ForwardLink = Entry; \r
188	}\r
189	\r
190	VOID\r
191	SwapListEntries (\r
192	EFI_LIST_ENTRY *Entry1,\r
193	EFI_LIST_ENTRY *Entry2\r
194	)\r
195	/*++\r
196	\r
197	Routine Description:\r
198	\r
199	Swap the location of the two elements of a doubly linked list. Node2 \r
200	is placed in front of Node1. The list must have been initialized with \r
201	InitializeListHead () before using this function.\r
202	\r
203	Arguments:\r
204	\r
205	Entry1 - Element in the doubly linked list in front of Node2. \r
206	\r
207	Entry2 - Element in the doubly linked list behind Node1.\r
208	\r
209	Returns:\r
210	\r
211	None\r
212	\r
213	--*/\r
214	{\r
215	EFI_LIST_ENTRY *Entry1ForwardLink;\r
216	EFI_LIST_ENTRY *Entry1BackLink;\r
217	EFI_LIST_ENTRY *Entry2ForwardLink;\r
218	EFI_LIST_ENTRY *Entry2BackLink;\r
219	\r
220	Entry2ForwardLink = Entry2->ForwardLink; \r
221	Entry2BackLink = Entry2->BackLink; \r
222	Entry1ForwardLink = Entry1->ForwardLink; \r
223	Entry1BackLink = Entry1->BackLink; \r
224	Entry2BackLink->ForwardLink = Entry2ForwardLink; \r
225	Entry2ForwardLink->BackLink = Entry2BackLink; \r
226	Entry2->ForwardLink = Entry1; \r
227	Entry2->BackLink = Entry1BackLink; \r
228	Entry1BackLink->ForwardLink = Entry2; \r
229	Entry1->BackLink = Entry2; \r
230	}\r
231	\r
232	\r
233	EFI_LIST_ENTRY *\r
234	GetFirstNode (\r
235	EFI_LIST_ENTRY *List \r
236	)\r
237	/*++\r
238	\r
239	Routine Description:\r
240	\r
241	Return the first node pointed to by the list head. The list must \r
242	have been initialized with InitializeListHead () before using this \r
243	function and must contain data.\r
244	\r
245	Arguments:\r
246	\r
247	List - The head of the doubly linked list.\r
248	\r
249	Returns:\r
250	\r
251	Pointer to the first node, if the list contains nodes. The list will\r
252	return a null value--that is, the value of List--when the list is empty.\r
253	See the description of IsNull for more information.\r
254	\r
255	\r
256	--*/\r
257	{\r
258	return List->ForwardLink;\r
259	}\r
260	\r
261	\r
262	EFI_LIST_ENTRY *\r
263	GetNextNode (\r
264	EFI_LIST_ENTRY *List,\r
265	EFI_LIST_ENTRY *Node\r
266	)\r
267	/*++\r
268	\r
269	Routine Description:\r
270	\r
271	Returns the node following Node in the list. The list must \r
272	have been initialized with InitializeListHead () before using this \r
273	function and must contain data.\r
274	\r
275	Arguments:\r
276	\r
277	List - The head of the list. MUST NOT be the literal value NULL.\r
278	Node - The node in the list. This value MUST NOT be the literal value NULL.\r
279	See the description of IsNull for more information.\r
280	\r
281	Returns:\r
282	\r
283	Pointer to the next node, if one exists. Otherwise, returns a null value,\r
284	which is actually a pointer to List.\r
285	See the description of IsNull for more information.\r
286	\r
287	--*/\r
288	{\r
289	if (Node == List) {\r
290	return List;\r
291	} \r
292	return Node->ForwardLink;\r
293	}\r
294	\r
295	\r
296	BOOLEAN \r
297	IsNull ( \r
298	EFI_LIST_ENTRY *List,\r
299	EFI_LIST_ENTRY *Node \r
300	)\r
301	/*++\r
302	\r
303	Routine Description:\r
304	\r
305	Determines whether the given node is null. Note that Node is null\r
306	when its value is equal to the value of List. It is an error for\r
307	Node to be the literal value NULL [(VOID*)0x0].\r
308	\r
309	Arguments:\r
310	\r
311	List - The head of the list. MUST NOT be the literal value NULL.\r
312	Node - The node to test. MUST NOT be the literal value NULL. See\r
313	the description above.\r
314	\r
315	Returns:\r
316	\r
317	Returns true if the node is null.\r
318	\r
319	--*/\r
320	{\r
321	return (BOOLEAN)(Node == List);\r
322	}\r
323	\r
324	\r
325	BOOLEAN \r
326	IsNodeAtEnd ( \r
327	EFI_LIST_ENTRY *List, \r
328	EFI_LIST_ENTRY *Node \r
329	)\r
330	/*++\r
331	\r
332	Routine Description:\r
333	\r
334	Determines whether the given node is at the end of the list. Used\r
335	to walk the list. The list must have been initialized with \r
336	InitializeListHead () before using this function and must contain \r
337	data.\r
338	\r
339	Arguments:\r
340	\r
341	List - The head of the list. MUST NOT be the literal value NULL.\r
342	Node - The node to test. MUST NOT be the literal value NULL.\r
343	See the description of IsNull for more information.\r
344	\r
345	Returns:\r
346	\r
347	Returns true if the list is the tail.\r
348	\r
349	--*/\r
350	{\r
351	if (IsNull (List, Node)) {\r
352	return FALSE;\r
353	}\r
354	return (BOOLEAN)(List->BackLink == Node);\r
355	}\r
356	\r