1.Updated some functions header of BaseLib with new MWG spec
[mirror_edk2.git] / MdePkg / Library / BaseLib / LinkedList.c
CommitLineData
878ddf1f 1/** @file\r
2 Linked List Library Functions.\r
3\r
4 Copyright (c) 2006, Intel Corporation<BR>\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 Module Name: LinkedList.c\r
14\r
15**/\r
16\r
17BOOLEAN\r
18EFIAPI\r
19IsNodeInList (\r
20 IN CONST LIST_ENTRY *List,\r
21 IN CONST LIST_ENTRY *Node\r
22 )\r
23{\r
24 UINTN Count;\r
25 CONST LIST_ENTRY *Ptr;\r
26 BOOLEAN Found;\r
27\r
28 //\r
29 // Test the validity of List and Node\r
30 //\r
31 ASSERT (List != NULL);\r
32 ASSERT (List->ForwardLink != NULL);\r
33 ASSERT (List->BackLink != NULL);\r
34 ASSERT (Node != NULL);\r
35\r
dc530c7b 36 Count = PcdGet32 (PcdMaximumLinkedListLength);\r
7d7c2b46 37 if (Count != 0) {\r
38 Count++;\r
39 }\r
40\r
878ddf1f 41 Ptr = List;\r
42 do {\r
43 Ptr = Ptr->ForwardLink;\r
44 Count--;\r
45 } while ((Ptr != List) && (Ptr != Node) && (Count > 0));\r
46 Found = (BOOLEAN)(Ptr == Node);\r
47\r
dc530c7b 48 if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {\r
878ddf1f 49 while ((Count > 0) && (Ptr != List)) {\r
50 Ptr = Ptr->ForwardLink;\r
7d7c2b46 51 Count--;\r
878ddf1f 52 }\r
53 ASSERT (Count > 0);\r
54 }\r
55\r
56 return Found;\r
57}\r
58\r
59/**\r
60 Initializes the head node of a doubly linked list, and returns the pointer to\r
61 the head node of the doubly linked list.\r
62\r
63 Initializes the forward and backward links of a new linked list. After\r
64 initializing a linked list with this function, the other linked list\r
65 functions may be used to add and remove nodes from the linked list. It is up\r
66 to the caller of this function to allocate the memory for ListHead.\r
67\r
68 If ListHead is NULL, then ASSERT().\r
69\r
70 @param ListHead A pointer to the head node of a new doubly linked list.\r
71\r
72 @return ListHead\r
73\r
74**/\r
75LIST_ENTRY *\r
76EFIAPI\r
77InitializeListHead (\r
78 IN OUT LIST_ENTRY *List\r
79 )\r
80\r
81{\r
82 ASSERT (List != NULL);\r
83\r
84 List->ForwardLink = List;\r
85 List->BackLink = List;\r
86 return List;\r
87}\r
88\r
89/**\r
90 Adds a node to the beginning of a doubly linked list, and returns the pointer\r
91 to the head node of the doubly linked list.\r
92\r
93 Adds the node Entry at the beginning of the doubly linked list denoted by\r
94 ListHead, and returns ListHead.\r
95\r
96 If ListHead is NULL, then ASSERT().\r
97 If Entry is NULL, then ASSERT().\r
98 If ListHead was not initialized with InitializeListHead(), then ASSERT().\r
30817eb4 99 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number\r
100 of nodes in ListHead, including the ListHead node, is greater than or \r
101 equal to PcdMaximumLinkedListLength, then ASSERT().\r
878ddf1f 102\r
103 @param ListHead A pointer to the head node of a doubly linked list.\r
104 @param Entry A pointer to a node that is to be inserted at the beginning\r
105 of a doubly linked list.\r
106\r
107 @return ListHead\r
108\r
109**/\r
110LIST_ENTRY *\r
111EFIAPI\r
112InsertHeadList (\r
113 IN OUT LIST_ENTRY *List,\r
114 IN OUT LIST_ENTRY *Entry\r
115 )\r
116{\r
117 //\r
118 // ASSERT List not too long and Entry is not one of the nodes of List\r
119 //\r
120 ASSERT (!IsNodeInList (List, Entry));\r
121\r
122 Entry->ForwardLink = List->ForwardLink;\r
123 Entry->BackLink = List;\r
124 Entry->ForwardLink->BackLink = Entry;\r
125 List->ForwardLink = Entry;\r
126 return List;\r
127}\r
128\r
129/**\r
130 Adds a node to the end of a doubly linked list, and returns the pointer to\r
131 the head node of the doubly linked list.\r
132\r
133 Adds the node Entry to the end of the doubly linked list denoted by ListHead,\r
134 and returns ListHead.\r
135\r
136 If ListHead is NULL, then ASSERT().\r
137 If Entry is NULL, then ASSERT().\r
138 If ListHead was not initialized with InitializeListHead(), then ASSERT().\r
30817eb4 139 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number\r
140 of nodes in ListHead, including the ListHead node, is greater than or \r
141 equal to PcdMaximumLinkedListLength, then ASSERT().\r
878ddf1f 142\r
143 @param ListHead A pointer to the head node of a doubly linked list.\r
144 @param Entry A pointer to a node that is to be added at the end of the\r
145 doubly linked list.\r
146\r
147 @return ListHead\r
148\r
149**/\r
150LIST_ENTRY *\r
151EFIAPI\r
152InsertTailList (\r
153 IN OUT LIST_ENTRY *List,\r
154 IN OUT LIST_ENTRY *Entry\r
155 )\r
156{\r
157 //\r
158 // ASSERT List not too long and Entry is not one of the nodes of List\r
159 //\r
160 ASSERT (!IsNodeInList (List, Entry));\r
161\r
162 Entry->ForwardLink = List;\r
163 Entry->BackLink = List->BackLink;\r
164 Entry->BackLink->ForwardLink = Entry;\r
165 List->BackLink = Entry;\r
166 return List;\r
167}\r
168\r
169/**\r
170 Retrieves the first node of a doubly linked list.\r
171\r
172 Returns the first node of a doubly linked list. List must have been\r
173 initialized with InitializeListHead(). If List is empty, then NULL is\r
174 returned.\r
175\r
176 If List is NULL, then ASSERT().\r
177 If List was not initialized with InitializeListHead(), then ASSERT().\r
30817eb4 178 If PcdMaximumLinkedListLenth is not zero, and the number of nodes \r
179 in List, including the List node, is greater than or equal to \r
180 PcdMaximumLinkedListLength, then ASSERT().\r
878ddf1f 181\r
182 @param List A pointer to the head node of a doubly linked list.\r
183\r
184 @return The first node of a doubly linked list.\r
185 @retval NULL The list is empty.\r
186\r
187**/\r
188LIST_ENTRY *\r
189EFIAPI\r
190GetFirstNode (\r
191 IN CONST LIST_ENTRY *List\r
192 )\r
193{\r
194 //\r
195 // ASSERT List not too long\r
196 //\r
197 ASSERT (IsNodeInList (List, List));\r
198\r
199 return List->ForwardLink;\r
200}\r
201\r
202/**\r
203 Retrieves the next node of a doubly linked list.\r
204\r
205 Returns the node of a doubly linked list that follows Node. List must have\r
206 been initialized with InitializeListHead(). If List is empty, then List is\r
207 returned.\r
208\r
209 If List is NULL, then ASSERT().\r
210 If Node is NULL, then ASSERT().\r
211 If List was not initialized with InitializeListHead(), then ASSERT().\r
212 If PcdMaximumLinkedListLenth is not zero, and List contains more than\r
213 PcdMaximumLinkedListLenth nodes, then ASSERT().\r
214 If Node is not a node in List, then ASSERT().\r
215\r
216 @param List A pointer to the head node of a doubly linked list.\r
217 @param Node A pointer to a node in the doubly linked list.\r
218\r
219 @return Pointer to the next node if one exists. Otherwise a null value which\r
220 is actually List is returned.\r
221\r
222**/\r
223LIST_ENTRY *\r
224EFIAPI\r
225GetNextNode (\r
226 IN CONST LIST_ENTRY *List,\r
227 IN CONST LIST_ENTRY *Node\r
228 )\r
229{\r
230 //\r
231 // ASSERT List not too long and Node is one of the nodes of List\r
232 //\r
233 ASSERT (IsNodeInList (List, Node));\r
234\r
235 return Node->ForwardLink;\r
236}\r
237\r
238/**\r
239 Checks to see if a doubly linked list is empty or not.\r
240\r
241 Checks to see if the doubly linked list is empty. If the linked list contains\r
242 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.\r
243\r
244 If ListHead is NULL, then ASSERT().\r
245 If ListHead was not initialized with InitializeListHead(), then ASSERT().\r
30817eb4 246 If PcdMaximumLinkedListLenth is not zero, and the number of nodes \r
247 in List, including the List node, is greater than or equal to \r
248 PcdMaximumLinkedListLength, then ASSERT().\r
878ddf1f 249\r
250 @param ListHead A pointer to the head node of a doubly linked list.\r
251\r
252 @retval TRUE The linked list is empty.\r
253 @retval FALSE The linked list is not empty.\r
254\r
255**/\r
256BOOLEAN\r
257EFIAPI\r
258IsListEmpty (\r
259 IN CONST LIST_ENTRY *List\r
260 )\r
261{\r
262 //\r
263 // ASSERT List not too long\r
264 //\r
265 ASSERT (IsNodeInList (List, List));\r
266\r
267 return (BOOLEAN)(List->ForwardLink == List);\r
268}\r
269\r
270/**\r
271 Determines if a node in a doubly linked list is null.\r
272\r
273 Returns FALSE if Node is one of the nodes in the doubly linked list specified\r
274 by List. Otherwise, TRUE is returned. List must have been initialized with\r
275 InitializeListHead().\r
276\r
277 If List is NULL, then ASSERT().\r
278 If Node is NULL, then ASSERT().\r
279 If List was not initialized with InitializeListHead(), then ASSERT().\r
30817eb4 280 If PcdMaximumLinkedListLenth is not zero, and the number of nodes \r
281 in List, including the List node, is greater than or equal to \r
282 PcdMaximumLinkedListLength, then ASSERT().\r
878ddf1f 283 If Node is not a node in List and Node is not equal to List, then ASSERT().\r
284\r
285 @param List A pointer to the head node of a doubly linked list.\r
24e25d11 286 @param Node A pointer to a node in the doubly linked list.\r
878ddf1f 287\r
288 @retval TRUE Node is one of the nodes in the doubly linked list.\r
289 @retval FALSE Node is not one of the nodes in the doubly linked list.\r
290\r
291**/\r
292BOOLEAN\r
293EFIAPI\r
294IsNull (\r
295 IN CONST LIST_ENTRY *List,\r
296 IN CONST LIST_ENTRY *Node\r
297 )\r
298{\r
299 //\r
300 // ASSERT List not too long and Node is one of the nodes of List\r
301 //\r
302 ASSERT (IsNodeInList (List, Node));\r
303\r
304 return (BOOLEAN)(Node == List);\r
305}\r
306\r
307/**\r
308 Determines if a node the last node in a doubly linked list.\r
309\r
310 Returns TRUE if Node is the last node in the doubly linked list specified by\r
311 List. Otherwise, FALSE is returned. List must have been initialized with\r
312 InitializeListHead().\r
313\r
314 If List is NULL, then ASSERT().\r
315 If Node is NULL, then ASSERT().\r
316 If List was not initialized with InitializeListHead(), then ASSERT().\r
30817eb4 317 If PcdMaximumLinkedListLenth is not zero, and the number of nodes \r
318 in List, including the List node, is greater than or equal to \r
319 PcdMaximumLinkedListLength, then ASSERT().\r
878ddf1f 320 If Node is not a node in List, then ASSERT().\r
321\r
322 @param List A pointer to the head node of a doubly linked list.\r
24e25d11 323 @param Node A pointer to a node in the doubly linked list.\r
878ddf1f 324\r
325 @retval TRUE Node is the last node in the linked list.\r
326 @retval FALSE Node is not the last node in the linked list.\r
327\r
328**/\r
329BOOLEAN\r
330EFIAPI\r
331IsNodeAtEnd (\r
332 IN CONST LIST_ENTRY *List,\r
333 IN CONST LIST_ENTRY *Node\r
334 )\r
335{\r
336 //\r
337 // ASSERT List not too long and Node is one of the nodes of List\r
338 //\r
339 ASSERT (IsNodeInList (List, Node));\r
340\r
341 return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);\r
342}\r
343\r
344/**\r
345 Swaps the location of two nodes in a doubly linked list, and returns the\r
346 first node after the swap.\r
347\r
348 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.\r
349 Otherwise, the location of the FirstEntry node is swapped with the location\r
350 of the SecondEntry node in a doubly linked list. SecondEntry must be in the\r
351 same double linked list as FirstEntry and that double linked list must have\r
352 been initialized with InitializeListHead(). SecondEntry is returned after the\r
353 nodes are swapped.\r
354\r
355 If FirstEntry is NULL, then ASSERT().\r
356 If SecondEntry is NULL, then ASSERT().\r
357 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().\r
30817eb4 358 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the\r
359 linked list containing the FirstEntry and SecondEntry nodes, including\r
360 the FirstEntry and SecondEntry nodes, is greater than or equal to \r
361 PcdMaximumLinkedListLength, then ASSERT().\r
878ddf1f 362\r
363 @param FirstEntry A pointer to a node in a linked list.\r
364 @param SecondEntry A pointer to another node in the same linked list.\r
365\r
366**/\r
367LIST_ENTRY *\r
368EFIAPI\r
369SwapListEntries (\r
370 IN OUT LIST_ENTRY *FirstEntry,\r
371 IN OUT LIST_ENTRY *SecondEntry\r
372 )\r
373{\r
374 LIST_ENTRY *Ptr;\r
375\r
376 if (FirstEntry == SecondEntry) {\r
377 return SecondEntry;\r
378 }\r
379\r
380 //\r
381 // ASSERT Entry1 and Entry2 are in the same linked list\r
382 //\r
383 ASSERT (IsNodeInList (FirstEntry, SecondEntry));\r
384\r
385 //\r
386 // Ptr is the node pointed to by FirstEntry->ForwardLink\r
387 //\r
388 Ptr = RemoveEntryList (FirstEntry);\r
389\r
390 //\r
391 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed\r
392 // immediately in front of SecondEntry\r
393 //\r
394 if (Ptr->BackLink == SecondEntry) {\r
395 return InsertTailList (SecondEntry, FirstEntry);\r
396 }\r
397\r
398 //\r
399 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,\r
400 // then there are no further steps necessary\r
401 //\r
402 if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {\r
403 return Ptr;\r
404 }\r
405\r
406 //\r
407 // Move SecondEntry to the front of Ptr\r
408 //\r
409 RemoveEntryList (SecondEntry);\r
410 InsertTailList (Ptr, SecondEntry);\r
411 return SecondEntry;\r
412}\r
413\r
414/**\r
415 Removes a node from a doubly linked list, and returns the node that follows\r
416 the removed node.\r
417\r
418 Removes the node Entry from a doubly linked list. It is up to the caller of\r
419 this function to release the memory used by this node if that is required. On\r
420 exit, the node following Entry in the doubly linked list is returned. If\r
421 Entry is the only node in the linked list, then the head node of the linked\r
422 list is returned.\r
423\r
424 If Entry is NULL, then ASSERT().\r
425 If Entry is the head node of an empty list, then ASSERT().\r
30817eb4 426 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the \r
427 linked list containing Entry, including the Entry node, is greater than \r
428 or equal to PcdMaximumLinkedListLength, then ASSERT().\r
878ddf1f 429\r
430 @param Entry A pointer to a node in a linked list\r
431\r
432 @return Entry\r
433\r
434**/\r
435LIST_ENTRY *\r
436EFIAPI\r
437RemoveEntryList (\r
438 IN CONST LIST_ENTRY *Entry\r
439 )\r
440{\r
441 ASSERT (!IsListEmpty (Entry));\r
442\r
443 Entry->ForwardLink->BackLink = Entry->BackLink;\r
444 Entry->BackLink->ForwardLink = Entry->ForwardLink;\r
445 return Entry->ForwardLink;\r
446}\r