2 Linked List Library Functions.
4 Copyright (c) 2006 - 2017, Intel Corporation. All rights reserved.<BR>
5 This program and the accompanying materials
6 are licensed and made available under the terms and conditions of the BSD License
7 which accompanies this distribution. The full text of the license may be found at
8 http://opensource.org/licenses/bsd-license.php.
10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
15 #include "BaseLibInternals.h"
18 If PcdVerifyNodeInList is TRUE, ASSERTs when SecondEntry is or is not part of
19 the same doubly-linked list as FirstEntry depending on the value of InList.
20 Independent of PcdVerifyNodeInList, ASSERTs when FirstEntry is not part of a
23 If FirstEntry is NULL, then ASSERT().
24 If FirstEntry->ForwardLink is NULL, then ASSERT().
25 If FirstEntry->BackLink is NULL, then ASSERT().
26 If PcdMaximumLinkedListLength is not zero, and List contains more than
27 PcdMaximumLinkedListLength nodes, then ASSERT().
28 If PcdVerifyNodeInList is TRUE and SecondEntry is NULL, then ASSERT().
30 @param FirstEntry A pointer to a node in a linked list.
31 @param SecondEntry A pointer to the node to locate.
32 @param InList Defines whether to check if SecondEntry is or is not part
33 of the same doubly-linked list as FirstEntry.
36 #if !defined (MDEPKG_NDEBUG)
37 #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList) \
39 if (FeaturePcdGet (PcdVerifyNodeInList)) { \
40 ASSERT (InList == IsNodeInList ((FirstEntry), (SecondEntry))); \
42 ASSERT (InternalBaseLibIsListValid (FirstEntry)); \
46 #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList)
50 Worker function that verifies the validity of this list.
52 If List is NULL, then ASSERT().
53 If List->ForwardLink is NULL, then ASSERT().
54 If List->BackLink is NULL, then ASSERT().
55 If PcdMaximumLinkedListLength is not zero, and List contains more than
56 PcdMaximumLinkedListLength nodes, then ASSERT().
58 @param List A pointer to a node in a linked list.
60 @retval TRUE if PcdVerifyNodeInList is FALSE
61 @retval TRUE if DoMembershipCheck is FALSE
62 @retval TRUE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE
63 and Node is a member of List.
64 @retval FALSE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE
65 and Node is in not a member of List.
70 InternalBaseLibIsListValid (
71 IN CONST LIST_ENTRY
*List
75 CONST LIST_ENTRY
*Ptr
;
78 // Test the validity of List and Node
80 ASSERT (List
!= NULL
);
81 ASSERT (List
->ForwardLink
!= NULL
);
82 ASSERT (List
->BackLink
!= NULL
);
84 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
89 // Count the total number of nodes in List.
90 // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
93 Ptr
= Ptr
->ForwardLink
;
95 } while ((Ptr
!= List
) && (Count
< PcdGet32 (PcdMaximumLinkedListLength
)));
98 // return whether linked list is too long
100 return (BOOLEAN
)(Count
< PcdGet32 (PcdMaximumLinkedListLength
));
107 Checks whether FirstEntry and SecondEntry are part of the same doubly-linked
110 If FirstEntry is NULL, then ASSERT().
111 If FirstEntry->ForwardLink is NULL, then ASSERT().
112 If FirstEntry->BackLink is NULL, then ASSERT().
113 If SecondEntry is NULL, then ASSERT();
114 If PcdMaximumLinkedListLength is not zero, and List contains more than
115 PcdMaximumLinkedListLength nodes, then ASSERT().
117 @param FirstEntry A pointer to a node in a linked list.
118 @param SecondEntry A pointer to the node to locate.
120 @retval TRUE SecondEntry is in the same doubly-linked list as FirstEntry.
121 @retval FALSE SecondEntry isn't in the same doubly-linked list as FirstEntry,
122 or FirstEntry is invalid.
128 IN CONST LIST_ENTRY
*FirstEntry
,
129 IN CONST LIST_ENTRY
*SecondEntry
133 CONST LIST_ENTRY
*Ptr
;
136 // ASSERT List not too long
138 ASSERT (InternalBaseLibIsListValid (FirstEntry
));
140 ASSERT (SecondEntry
!= NULL
);
146 // Check to see if SecondEntry is a member of FirstEntry.
147 // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
150 Ptr
= Ptr
->ForwardLink
;
151 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
155 // Return if the linked list is too long
157 if (Count
== PcdGet32 (PcdMaximumLinkedListLength
)) {
158 return (BOOLEAN
)(Ptr
== SecondEntry
);
162 if (Ptr
== SecondEntry
) {
165 } while (Ptr
!= FirstEntry
);
171 Initializes the head node of a doubly-linked list, and returns the pointer to
172 the head node of the doubly-linked list.
174 Initializes the forward and backward links of a new linked list. After
175 initializing a linked list with this function, the other linked list
176 functions may be used to add and remove nodes from the linked list. It is up
177 to the caller of this function to allocate the memory for ListHead.
179 If ListHead is NULL, then ASSERT().
181 @param ListHead A pointer to the head node of a new doubly-linked list.
189 IN OUT LIST_ENTRY
*ListHead
193 ASSERT (ListHead
!= NULL
);
195 ListHead
->ForwardLink
= ListHead
;
196 ListHead
->BackLink
= ListHead
;
201 Adds a node to the beginning of a doubly-linked list, and returns the pointer
202 to the head node of the doubly-linked list.
204 Adds the node Entry at the beginning of the doubly-linked list denoted by
205 ListHead, and returns ListHead.
207 If ListHead is NULL, then ASSERT().
208 If Entry is NULL, then ASSERT().
209 If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
210 InitializeListHead(), then ASSERT().
211 If PcdMaximumLinkedListLength is not zero, and prior to insertion the number
212 of nodes in ListHead, including the ListHead node, is greater than or
213 equal to PcdMaximumLinkedListLength, then ASSERT().
215 @param ListHead A pointer to the head node of a doubly-linked list.
216 @param Entry A pointer to a node that is to be inserted at the beginning
217 of a doubly-linked list.
225 IN OUT LIST_ENTRY
*ListHead
,
226 IN OUT LIST_ENTRY
*Entry
230 // ASSERT List not too long and Entry is not one of the nodes of List
232 ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead
, Entry
, FALSE
);
234 Entry
->ForwardLink
= ListHead
->ForwardLink
;
235 Entry
->BackLink
= ListHead
;
236 Entry
->ForwardLink
->BackLink
= Entry
;
237 ListHead
->ForwardLink
= Entry
;
242 Adds a node to the end of a doubly-linked list, and returns the pointer to
243 the head node of the doubly-linked list.
245 Adds the node Entry to the end of the doubly-linked list denoted by ListHead,
246 and returns ListHead.
248 If ListHead is NULL, then ASSERT().
249 If Entry is NULL, then ASSERT().
250 If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
251 InitializeListHead(), then ASSERT().
252 If PcdMaximumLinkedListLength is not zero, and prior to insertion the number
253 of nodes in ListHead, including the ListHead node, is greater than or
254 equal to PcdMaximumLinkedListLength, then ASSERT().
256 @param ListHead A pointer to the head node of a doubly-linked list.
257 @param Entry A pointer to a node that is to be added at the end of the
266 IN OUT LIST_ENTRY
*ListHead
,
267 IN OUT LIST_ENTRY
*Entry
271 // ASSERT List not too long and Entry is not one of the nodes of List
273 ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead
, Entry
, FALSE
);
275 Entry
->ForwardLink
= ListHead
;
276 Entry
->BackLink
= ListHead
->BackLink
;
277 Entry
->BackLink
->ForwardLink
= Entry
;
278 ListHead
->BackLink
= Entry
;
283 Retrieves the first node of a doubly-linked list.
285 Returns the first node of a doubly-linked list. List must have been
286 initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
287 If List is empty, then List is returned.
289 If List is NULL, then ASSERT().
290 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
291 InitializeListHead(), then ASSERT().
292 If PcdMaximumLinkedListLength is not zero, and the number of nodes
293 in List, including the List node, is greater than or equal to
294 PcdMaximumLinkedListLength, then ASSERT().
296 @param List A pointer to the head node of a doubly-linked list.
298 @return The first node of a doubly-linked list.
299 @retval List The list is empty.
305 IN CONST LIST_ENTRY
*List
309 // ASSERT List not too long
311 ASSERT (InternalBaseLibIsListValid (List
));
313 return List
->ForwardLink
;
317 Retrieves the next node of a doubly-linked list.
319 Returns the node of a doubly-linked list that follows Node.
320 List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()
321 or InitializeListHead(). If List is empty, then List is returned.
323 If List is NULL, then ASSERT().
324 If Node is NULL, then ASSERT().
325 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
326 InitializeListHead(), then ASSERT().
327 If PcdMaximumLinkedListLength is not zero, and List contains more than
328 PcdMaximumLinkedListLength nodes, then ASSERT().
329 If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
331 @param List A pointer to the head node of a doubly-linked list.
332 @param Node A pointer to a node in the doubly-linked list.
334 @return A pointer to the next node if one exists. Otherwise List is returned.
340 IN CONST LIST_ENTRY
*List
,
341 IN CONST LIST_ENTRY
*Node
345 // ASSERT List not too long and Node is one of the nodes of List
347 ASSERT_VERIFY_NODE_IN_VALID_LIST (List
, Node
, TRUE
);
349 return Node
->ForwardLink
;
353 Retrieves the previous node of a doubly-linked list.
355 Returns the node of a doubly-linked list that precedes Node.
356 List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()
357 or InitializeListHead(). If List is empty, then List is returned.
359 If List is NULL, then ASSERT().
360 If Node is NULL, then ASSERT().
361 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
362 InitializeListHead(), then ASSERT().
363 If PcdMaximumLinkedListLength is not zero, and List contains more than
364 PcdMaximumLinkedListLength nodes, then ASSERT().
365 If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
367 @param List A pointer to the head node of a doubly-linked list.
368 @param Node A pointer to a node in the doubly-linked list.
370 @return A pointer to the previous node if one exists. Otherwise List is returned.
376 IN CONST LIST_ENTRY
*List
,
377 IN CONST LIST_ENTRY
*Node
381 // ASSERT List not too long and Node is one of the nodes of List
383 ASSERT_VERIFY_NODE_IN_VALID_LIST (List
, Node
, TRUE
);
385 return Node
->BackLink
;
389 Checks to see if a doubly-linked list is empty or not.
391 Checks to see if the doubly-linked list is empty. If the linked list contains
392 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
394 If ListHead is NULL, then ASSERT().
395 If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
396 InitializeListHead(), then ASSERT().
397 If PcdMaximumLinkedListLength is not zero, and the number of nodes
398 in List, including the List node, is greater than or equal to
399 PcdMaximumLinkedListLength, then ASSERT().
401 @param ListHead A pointer to the head node of a doubly-linked list.
403 @retval TRUE The linked list is empty.
404 @retval FALSE The linked list is not empty.
410 IN CONST LIST_ENTRY
*ListHead
414 // ASSERT List not too long
416 ASSERT (InternalBaseLibIsListValid (ListHead
));
418 return (BOOLEAN
)(ListHead
->ForwardLink
== ListHead
);
422 Determines if a node in a doubly-linked list is the head node of a the same
423 doubly-linked list. This function is typically used to terminate a loop that
424 traverses all the nodes in a doubly-linked list starting with the head node.
426 Returns TRUE if Node is equal to List. Returns FALSE if Node is one of the
427 nodes in the doubly-linked list specified by List. List must have been
428 initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
430 If List is NULL, then ASSERT().
431 If Node is NULL, then ASSERT().
432 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(),
434 If PcdMaximumLinkedListLength is not zero, and the number of nodes
435 in List, including the List node, is greater than or equal to
436 PcdMaximumLinkedListLength, then ASSERT().
437 If PcdVerifyNodeInList is TRUE and Node is not a node in List and Node is not
438 equal to List, then ASSERT().
440 @param List A pointer to the head node of a doubly-linked list.
441 @param Node A pointer to a node in the doubly-linked list.
443 @retval TRUE Node is the head of the doubly-linked list pointed by List.
444 @retval FALSE Node is not the head of the doubly-linked list pointed by List.
450 IN CONST LIST_ENTRY
*List
,
451 IN CONST LIST_ENTRY
*Node
455 // ASSERT List not too long and Node is one of the nodes of List
457 ASSERT_VERIFY_NODE_IN_VALID_LIST (List
, Node
, TRUE
);
459 return (BOOLEAN
)(Node
== List
);
463 Determines if a node the last node in a doubly-linked list.
465 Returns TRUE if Node is the last node in the doubly-linked list specified by
466 List. Otherwise, FALSE is returned. List must have been initialized with
467 INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
469 If List is NULL, then ASSERT().
470 If Node is NULL, then ASSERT().
471 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
472 InitializeListHead(), then ASSERT().
473 If PcdMaximumLinkedListLength is not zero, and the number of nodes
474 in List, including the List node, is greater than or equal to
475 PcdMaximumLinkedListLength, then ASSERT().
476 If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
478 @param List A pointer to the head node of a doubly-linked list.
479 @param Node A pointer to a node in the doubly-linked list.
481 @retval TRUE Node is the last node in the linked list.
482 @retval FALSE Node is not the last node in the linked list.
488 IN CONST LIST_ENTRY
*List
,
489 IN CONST LIST_ENTRY
*Node
493 // ASSERT List not too long and Node is one of the nodes of List
495 ASSERT_VERIFY_NODE_IN_VALID_LIST (List
, Node
, TRUE
);
497 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
501 Swaps the location of two nodes in a doubly-linked list, and returns the
502 first node after the swap.
504 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
505 Otherwise, the location of the FirstEntry node is swapped with the location
506 of the SecondEntry node in a doubly-linked list. SecondEntry must be in the
507 same double linked list as FirstEntry and that double linked list must have
508 been initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
509 SecondEntry is returned after the nodes are swapped.
511 If FirstEntry is NULL, then ASSERT().
512 If SecondEntry is NULL, then ASSERT().
513 If PcdVerifyNodeInList is TRUE and SecondEntry and FirstEntry are not in the
514 same linked list, then ASSERT().
515 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
516 linked list containing the FirstEntry and SecondEntry nodes, including
517 the FirstEntry and SecondEntry nodes, is greater than or equal to
518 PcdMaximumLinkedListLength, then ASSERT().
520 @param FirstEntry A pointer to a node in a linked list.
521 @param SecondEntry A pointer to another node in the same linked list.
529 IN OUT LIST_ENTRY
*FirstEntry
,
530 IN OUT LIST_ENTRY
*SecondEntry
535 if (FirstEntry
== SecondEntry
) {
540 // ASSERT Entry1 and Entry2 are in the same linked list
542 ASSERT_VERIFY_NODE_IN_VALID_LIST (FirstEntry
, SecondEntry
, TRUE
);
545 // Ptr is the node pointed to by FirstEntry->ForwardLink
547 Ptr
= RemoveEntryList (FirstEntry
);
550 // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
551 // immediately in front of SecondEntry
553 if (Ptr
->BackLink
== SecondEntry
) {
554 return InsertTailList (SecondEntry
, FirstEntry
);
558 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
559 // then there are no further steps necessary
561 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
566 // Move SecondEntry to the front of Ptr
568 RemoveEntryList (SecondEntry
);
569 InsertTailList (Ptr
, SecondEntry
);
574 Removes a node from a doubly-linked list, and returns the node that follows
577 Removes the node Entry from a doubly-linked list. It is up to the caller of
578 this function to release the memory used by this node if that is required. On
579 exit, the node following Entry in the doubly-linked list is returned. If
580 Entry is the only node in the linked list, then the head node of the linked
583 If Entry is NULL, then ASSERT().
584 If Entry is the head node of an empty list, then ASSERT().
585 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
586 linked list containing Entry, including the Entry node, is greater than
587 or equal to PcdMaximumLinkedListLength, then ASSERT().
589 @param Entry A pointer to a node in a linked list.
597 IN CONST LIST_ENTRY
*Entry
600 ASSERT (!IsListEmpty (Entry
));
602 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
603 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
604 return Entry
->ForwardLink
;