2 Linked List Library Functions.
4 Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.<BR>
5 SPDX-License-Identifier: BSD-2-Clause-Patent
9 #include "BaseLibInternals.h"
12 If PcdVerifyNodeInList is TRUE, ASSERTs when SecondEntry is or is not part of
13 the same doubly-linked list as FirstEntry depending on the value of InList.
14 Independent of PcdVerifyNodeInList, ASSERTs when FirstEntry is not part of a
17 If FirstEntry is NULL, then ASSERT().
18 If FirstEntry->ForwardLink is NULL, then ASSERT().
19 If FirstEntry->BackLink is NULL, then ASSERT().
20 If PcdMaximumLinkedListLength is not zero, and List contains more than
21 PcdMaximumLinkedListLength nodes, then ASSERT().
22 If PcdVerifyNodeInList is TRUE and SecondEntry is NULL, then ASSERT().
24 @param FirstEntry A pointer to a node in a linked list.
25 @param SecondEntry A pointer to the node to locate.
26 @param InList Defines whether to check if SecondEntry is or is not part
27 of the same doubly-linked list as FirstEntry.
30 #if !defined (MDEPKG_NDEBUG)
31 #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList) \
33 if (FeaturePcdGet (PcdVerifyNodeInList)) { \
34 ASSERT (InList == IsNodeInList ((FirstEntry), (SecondEntry))); \
36 ASSERT (InternalBaseLibIsListValid (FirstEntry)); \
40 #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList)
44 Worker function that verifies the validity of this list.
46 If List is NULL, then ASSERT().
47 If List->ForwardLink is NULL, then ASSERT().
48 If List->BackLink is NULL, then ASSERT().
49 If PcdMaximumLinkedListLength is not zero, and List contains more than
50 PcdMaximumLinkedListLength nodes, then ASSERT().
52 @param List A pointer to a node in a linked list.
54 @retval TRUE if PcdVerifyNodeInList is FALSE
55 @retval TRUE if DoMembershipCheck is FALSE
56 @retval TRUE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE
57 and Node is a member of List.
58 @retval FALSE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE
59 and Node is in not a member of List.
64 InternalBaseLibIsListValid (
65 IN CONST LIST_ENTRY
*List
69 CONST LIST_ENTRY
*Ptr
;
72 // Test the validity of List and Node
74 ASSERT (List
!= NULL
);
75 ASSERT (List
->ForwardLink
!= NULL
);
76 ASSERT (List
->BackLink
!= NULL
);
78 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
83 // Count the total number of nodes in List.
84 // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
87 Ptr
= Ptr
->ForwardLink
;
89 } while ((Ptr
!= List
) && (Count
< PcdGet32 (PcdMaximumLinkedListLength
)));
92 // return whether linked list is too long
94 return (BOOLEAN
)(Count
< PcdGet32 (PcdMaximumLinkedListLength
));
101 Checks whether FirstEntry and SecondEntry are part of the same doubly-linked
104 If FirstEntry is NULL, then ASSERT().
105 If FirstEntry->ForwardLink is NULL, then ASSERT().
106 If FirstEntry->BackLink is NULL, then ASSERT().
107 If SecondEntry is NULL, then ASSERT();
108 If PcdMaximumLinkedListLength is not zero, and List contains more than
109 PcdMaximumLinkedListLength nodes, then ASSERT().
111 @param FirstEntry A pointer to a node in a linked list.
112 @param SecondEntry A pointer to the node to locate.
114 @retval TRUE SecondEntry is in the same doubly-linked list as FirstEntry.
115 @retval FALSE SecondEntry isn't in the same doubly-linked list as FirstEntry,
116 or FirstEntry is invalid.
122 IN CONST LIST_ENTRY
*FirstEntry
,
123 IN CONST LIST_ENTRY
*SecondEntry
127 CONST LIST_ENTRY
*Ptr
;
130 // ASSERT List not too long
132 ASSERT (InternalBaseLibIsListValid (FirstEntry
));
134 ASSERT (SecondEntry
!= NULL
);
140 // Check to see if SecondEntry is a member of FirstEntry.
141 // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
144 Ptr
= Ptr
->ForwardLink
;
145 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
149 // Return if the linked list is too long
151 if (Count
== PcdGet32 (PcdMaximumLinkedListLength
)) {
152 return (BOOLEAN
)(Ptr
== SecondEntry
);
156 if (Ptr
== SecondEntry
) {
159 } while (Ptr
!= FirstEntry
);
165 Initializes the head node of a doubly-linked list, and returns the pointer to
166 the head node of the doubly-linked list.
168 Initializes the forward and backward links of a new linked list. After
169 initializing a linked list with this function, the other linked list
170 functions may be used to add and remove nodes from the linked list. It is up
171 to the caller of this function to allocate the memory for ListHead.
173 If ListHead is NULL, then ASSERT().
175 @param ListHead A pointer to the head node of a new doubly-linked list.
183 IN OUT LIST_ENTRY
*ListHead
187 ASSERT (ListHead
!= NULL
);
189 ListHead
->ForwardLink
= ListHead
;
190 ListHead
->BackLink
= ListHead
;
195 Adds a node to the beginning of a doubly-linked list, and returns the pointer
196 to the head node of the doubly-linked list.
198 Adds the node Entry at the beginning of the doubly-linked list denoted by
199 ListHead, and returns ListHead.
201 If ListHead is NULL, then ASSERT().
202 If Entry is NULL, then ASSERT().
203 If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
204 InitializeListHead(), then ASSERT().
205 If PcdMaximumLinkedListLength is not zero, and prior to insertion the number
206 of nodes in ListHead, including the ListHead node, is greater than or
207 equal to PcdMaximumLinkedListLength, then ASSERT().
209 @param ListHead A pointer to the head node of a doubly-linked list.
210 @param Entry A pointer to a node that is to be inserted at the beginning
211 of a doubly-linked list.
219 IN OUT LIST_ENTRY
*ListHead
,
220 IN OUT LIST_ENTRY
*Entry
224 // ASSERT List not too long and Entry is not one of the nodes of List
226 ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead
, Entry
, FALSE
);
228 Entry
->ForwardLink
= ListHead
->ForwardLink
;
229 Entry
->BackLink
= ListHead
;
230 Entry
->ForwardLink
->BackLink
= Entry
;
231 ListHead
->ForwardLink
= Entry
;
236 Adds a node to the end of a doubly-linked list, and returns the pointer to
237 the head node of the doubly-linked list.
239 Adds the node Entry to the end of the doubly-linked list denoted by ListHead,
240 and returns ListHead.
242 If ListHead is NULL, then ASSERT().
243 If Entry is NULL, then ASSERT().
244 If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
245 InitializeListHead(), then ASSERT().
246 If PcdMaximumLinkedListLength is not zero, and prior to insertion the number
247 of nodes in ListHead, including the ListHead node, is greater than or
248 equal to PcdMaximumLinkedListLength, then ASSERT().
250 @param ListHead A pointer to the head node of a doubly-linked list.
251 @param Entry A pointer to a node that is to be added at the end of the
260 IN OUT LIST_ENTRY
*ListHead
,
261 IN OUT LIST_ENTRY
*Entry
265 // ASSERT List not too long and Entry is not one of the nodes of List
267 ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead
, Entry
, FALSE
);
269 Entry
->ForwardLink
= ListHead
;
270 Entry
->BackLink
= ListHead
->BackLink
;
271 Entry
->BackLink
->ForwardLink
= Entry
;
272 ListHead
->BackLink
= Entry
;
277 Retrieves the first node of a doubly-linked list.
279 Returns the first node of a doubly-linked list. List must have been
280 initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
281 If List is empty, then List is returned.
283 If List is NULL, then ASSERT().
284 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
285 InitializeListHead(), then ASSERT().
286 If PcdMaximumLinkedListLength is not zero, and the number of nodes
287 in List, including the List node, is greater than or equal to
288 PcdMaximumLinkedListLength, then ASSERT().
290 @param List A pointer to the head node of a doubly-linked list.
292 @return The first node of a doubly-linked list.
293 @retval List The list is empty.
299 IN CONST LIST_ENTRY
*List
303 // ASSERT List not too long
305 ASSERT (InternalBaseLibIsListValid (List
));
307 return List
->ForwardLink
;
311 Retrieves the next node of a doubly-linked list.
313 Returns the node of a doubly-linked list that follows Node.
314 List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()
315 or InitializeListHead(). If List is empty, then List is returned.
317 If List is NULL, then ASSERT().
318 If Node is NULL, then ASSERT().
319 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
320 InitializeListHead(), then ASSERT().
321 If PcdMaximumLinkedListLength is not zero, and List contains more than
322 PcdMaximumLinkedListLength nodes, then ASSERT().
323 If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
325 @param List A pointer to the head node of a doubly-linked list.
326 @param Node A pointer to a node in the doubly-linked list.
328 @return A pointer to the next node if one exists. Otherwise List is returned.
334 IN CONST LIST_ENTRY
*List
,
335 IN CONST LIST_ENTRY
*Node
339 // ASSERT List not too long and Node is one of the nodes of List
341 ASSERT_VERIFY_NODE_IN_VALID_LIST (List
, Node
, TRUE
);
343 return Node
->ForwardLink
;
347 Retrieves the previous node of a doubly-linked list.
349 Returns the node of a doubly-linked list that precedes Node.
350 List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()
351 or InitializeListHead(). If List is empty, then List is returned.
353 If List is NULL, then ASSERT().
354 If Node is NULL, then ASSERT().
355 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
356 InitializeListHead(), then ASSERT().
357 If PcdMaximumLinkedListLength is not zero, and List contains more than
358 PcdMaximumLinkedListLength nodes, then ASSERT().
359 If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
361 @param List A pointer to the head node of a doubly-linked list.
362 @param Node A pointer to a node in the doubly-linked list.
364 @return A pointer to the previous node if one exists. Otherwise List is returned.
370 IN CONST LIST_ENTRY
*List
,
371 IN CONST LIST_ENTRY
*Node
375 // ASSERT List not too long and Node is one of the nodes of List
377 ASSERT_VERIFY_NODE_IN_VALID_LIST (List
, Node
, TRUE
);
379 return Node
->BackLink
;
383 Checks to see if a doubly-linked list is empty or not.
385 Checks to see if the doubly-linked list is empty. If the linked list contains
386 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
388 If ListHead is NULL, then ASSERT().
389 If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
390 InitializeListHead(), then ASSERT().
391 If PcdMaximumLinkedListLength is not zero, and the number of nodes
392 in List, including the List node, is greater than or equal to
393 PcdMaximumLinkedListLength, then ASSERT().
395 @param ListHead A pointer to the head node of a doubly-linked list.
397 @retval TRUE The linked list is empty.
398 @retval FALSE The linked list is not empty.
404 IN CONST LIST_ENTRY
*ListHead
408 // ASSERT List not too long
410 ASSERT (InternalBaseLibIsListValid (ListHead
));
412 return (BOOLEAN
)(ListHead
->ForwardLink
== ListHead
);
416 Determines if a node in a doubly-linked list is the head node of a the same
417 doubly-linked list. This function is typically used to terminate a loop that
418 traverses all the nodes in a doubly-linked list starting with the head node.
420 Returns TRUE if Node is equal to List. Returns FALSE if Node is one of the
421 nodes in the doubly-linked list specified by List. List must have been
422 initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
424 If List is NULL, then ASSERT().
425 If Node is NULL, then ASSERT().
426 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(),
428 If PcdMaximumLinkedListLength is not zero, and the number of nodes
429 in List, including the List node, is greater than or equal to
430 PcdMaximumLinkedListLength, then ASSERT().
431 If PcdVerifyNodeInList is TRUE and Node is not a node in List and Node is not
432 equal to List, then ASSERT().
434 @param List A pointer to the head node of a doubly-linked list.
435 @param Node A pointer to a node in the doubly-linked list.
437 @retval TRUE Node is the head of the doubly-linked list pointed by List.
438 @retval FALSE Node is not the head of the doubly-linked list pointed by List.
444 IN CONST LIST_ENTRY
*List
,
445 IN CONST LIST_ENTRY
*Node
449 // ASSERT List not too long and Node is one of the nodes of List
451 ASSERT_VERIFY_NODE_IN_VALID_LIST (List
, Node
, TRUE
);
453 return (BOOLEAN
)(Node
== List
);
457 Determines if a node the last node in a doubly-linked list.
459 Returns TRUE if Node is the last node in the doubly-linked list specified by
460 List. Otherwise, FALSE is returned. List must have been initialized with
461 INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
463 If List is NULL, then ASSERT().
464 If Node is NULL, then ASSERT().
465 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
466 InitializeListHead(), then ASSERT().
467 If PcdMaximumLinkedListLength is not zero, and the number of nodes
468 in List, including the List node, is greater than or equal to
469 PcdMaximumLinkedListLength, then ASSERT().
470 If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
472 @param List A pointer to the head node of a doubly-linked list.
473 @param Node A pointer to a node in the doubly-linked list.
475 @retval TRUE Node is the last node in the linked list.
476 @retval FALSE Node is not the last node in the linked list.
482 IN CONST LIST_ENTRY
*List
,
483 IN CONST LIST_ENTRY
*Node
487 // ASSERT List not too long and Node is one of the nodes of List
489 ASSERT_VERIFY_NODE_IN_VALID_LIST (List
, Node
, TRUE
);
491 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
495 Swaps the location of two nodes in a doubly-linked list, and returns the
496 first node after the swap.
498 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
499 Otherwise, the location of the FirstEntry node is swapped with the location
500 of the SecondEntry node in a doubly-linked list. SecondEntry must be in the
501 same double linked list as FirstEntry and that double linked list must have
502 been initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
503 SecondEntry is returned after the nodes are swapped.
505 If FirstEntry is NULL, then ASSERT().
506 If SecondEntry is NULL, then ASSERT().
507 If PcdVerifyNodeInList is TRUE and SecondEntry and FirstEntry are not in the
508 same linked list, then ASSERT().
509 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
510 linked list containing the FirstEntry and SecondEntry nodes, including
511 the FirstEntry and SecondEntry nodes, is greater than or equal to
512 PcdMaximumLinkedListLength, then ASSERT().
514 @param FirstEntry A pointer to a node in a linked list.
515 @param SecondEntry A pointer to another node in the same linked list.
523 IN OUT LIST_ENTRY
*FirstEntry
,
524 IN OUT LIST_ENTRY
*SecondEntry
529 if (FirstEntry
== SecondEntry
) {
534 // ASSERT Entry1 and Entry2 are in the same linked list
536 ASSERT_VERIFY_NODE_IN_VALID_LIST (FirstEntry
, SecondEntry
, TRUE
);
539 // Ptr is the node pointed to by FirstEntry->ForwardLink
541 Ptr
= RemoveEntryList (FirstEntry
);
544 // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
545 // immediately in front of SecondEntry
547 if (Ptr
->BackLink
== SecondEntry
) {
548 return InsertTailList (SecondEntry
, FirstEntry
);
552 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
553 // then there are no further steps necessary
555 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
560 // Move SecondEntry to the front of Ptr
562 RemoveEntryList (SecondEntry
);
563 InsertTailList (Ptr
, SecondEntry
);
568 Removes a node from a doubly-linked list, and returns the node that follows
571 Removes the node Entry from a doubly-linked list. It is up to the caller of
572 this function to release the memory used by this node if that is required. On
573 exit, the node following Entry in the doubly-linked list is returned. If
574 Entry is the only node in the linked list, then the head node of the linked
577 If Entry is NULL, then ASSERT().
578 If Entry is the head node of an empty list, then ASSERT().
579 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
580 linked list containing Entry, including the Entry node, is greater than
581 or equal to PcdMaximumLinkedListLength, then ASSERT().
583 @param Entry A pointer to a node in a linked list.
591 IN CONST LIST_ENTRY
*Entry
594 ASSERT (!IsListEmpty (Entry
));
596 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
597 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
598 return Entry
->ForwardLink
;