1 /** @file
2 Linked List Library Functions.
3
4 Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.<BR>
5 SPDX-License-Identifier: BSD-2-Clause-Patent
6
7 **/
8
9 #include "BaseLibInternals.h"
10
11 /**
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
15 valid list.
16
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().
23
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.
28
29 **/
30 #if !defined (MDEPKG_NDEBUG)
31 #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList) \
32 do { \
33 if (FeaturePcdGet (PcdVerifyNodeInList)) { \
34 ASSERT (InList == IsNodeInList ((FirstEntry), (SecondEntry))); \
35 } else { \
36 ASSERT (InternalBaseLibIsListValid (FirstEntry)); \
37 } \
38 } while (FALSE)
39 #else
40 #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList)
41 #endif
42
43 /**
44 Worker function that verifies the validity of this list.
45
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().
51
52 @param List A pointer to a node in a linked list.
53
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.
60
61 **/
62 BOOLEAN
63 EFIAPI
InternalBaseLibIsListValid(IN CONST LIST_ENTRY * List)64 InternalBaseLibIsListValid (
65 IN CONST LIST_ENTRY *List
66 )
67 {
68 UINTN Count;
69 CONST LIST_ENTRY *Ptr;
70
71 //
72 // Test the validity of List and Node
73 //
74 ASSERT (List != NULL);
75 ASSERT (List->ForwardLink != NULL);
76 ASSERT (List->BackLink != NULL);
77
78 if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
79 Count = 0;
80 Ptr = List;
81
82 //
83 // Count the total number of nodes in List.
84 // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
85 //
86 do {
87 Ptr = Ptr->ForwardLink;
88 Count++;
89 } while ((Ptr != List) && (Count < PcdGet32 (PcdMaximumLinkedListLength)));
90
91 //
92 // return whether linked list is too long
93 //
94 return (BOOLEAN)(Count < PcdGet32 (PcdMaximumLinkedListLength));
95 }
96
97 return TRUE;
98 }
99
100 /**
101 Checks whether FirstEntry and SecondEntry are part of the same doubly-linked
102 list.
103
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().
110
111 @param FirstEntry A pointer to a node in a linked list.
112 @param SecondEntry A pointer to the node to locate.
113
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.
117
118 **/
119 BOOLEAN
120 EFIAPI
IsNodeInList(IN CONST LIST_ENTRY * FirstEntry,IN CONST LIST_ENTRY * SecondEntry)121 IsNodeInList (
122 IN CONST LIST_ENTRY *FirstEntry,
123 IN CONST LIST_ENTRY *SecondEntry
124 )
125 {
126 UINTN Count;
127 CONST LIST_ENTRY *Ptr;
128
129 //
130 // ASSERT List not too long
131 //
132 ASSERT (InternalBaseLibIsListValid (FirstEntry));
133
134 ASSERT (SecondEntry != NULL);
135
136 Count = 0;
137 Ptr = FirstEntry;
138
139 //
140 // Check to see if SecondEntry is a member of FirstEntry.
141 // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
142 //
143 do {
144 Ptr = Ptr->ForwardLink;
145 if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
146 Count++;
147
148 //
149 // Return if the linked list is too long
150 //
151 if (Count == PcdGet32 (PcdMaximumLinkedListLength)) {
152 return (BOOLEAN)(Ptr == SecondEntry);
153 }
154 }
155
156 if (Ptr == SecondEntry) {
157 return TRUE;
158 }
159 } while (Ptr != FirstEntry);
160
161 return FALSE;
162 }
163
164 /**
165 Initializes the head node of a doubly-linked list, and returns the pointer to
166 the head node of the doubly-linked list.
167
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.
172
173 If ListHead is NULL, then ASSERT().
174
175 @param ListHead A pointer to the head node of a new doubly-linked list.
176
177 @return ListHead
178
179 **/
180 LIST_ENTRY *
181 EFIAPI
InitializeListHead(IN OUT LIST_ENTRY * ListHead)182 InitializeListHead (
183 IN OUT LIST_ENTRY *ListHead
184 )
185
186 {
187 ASSERT (ListHead != NULL);
188
189 ListHead->ForwardLink = ListHead;
190 ListHead->BackLink = ListHead;
191 return ListHead;
192 }
193
194 /**
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.
197
198 Adds the node Entry at the beginning of the doubly-linked list denoted by
199 ListHead, and returns ListHead.
200
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().
208
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.
212
213 @return ListHead
214
215 **/
216 LIST_ENTRY *
217 EFIAPI
InsertHeadList(IN OUT LIST_ENTRY * ListHead,IN OUT LIST_ENTRY * Entry)218 InsertHeadList (
219 IN OUT LIST_ENTRY *ListHead,
220 IN OUT LIST_ENTRY *Entry
221 )
222 {
223 //
224 // ASSERT List not too long and Entry is not one of the nodes of List
225 //
226 ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead, Entry, FALSE);
227
228 Entry->ForwardLink = ListHead->ForwardLink;
229 Entry->BackLink = ListHead;
230 Entry->ForwardLink->BackLink = Entry;
231 ListHead->ForwardLink = Entry;
232 return ListHead;
233 }
234
235 /**
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.
238
239 Adds the node Entry to the end of the doubly-linked list denoted by ListHead,
240 and returns ListHead.
241
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().
249
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
252 doubly-linked list.
253
254 @return ListHead
255
256 **/
257 LIST_ENTRY *
258 EFIAPI
InsertTailList(IN OUT LIST_ENTRY * ListHead,IN OUT LIST_ENTRY * Entry)259 InsertTailList (
260 IN OUT LIST_ENTRY *ListHead,
261 IN OUT LIST_ENTRY *Entry
262 )
263 {
264 //
265 // ASSERT List not too long and Entry is not one of the nodes of List
266 //
267 ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead, Entry, FALSE);
268
269 Entry->ForwardLink = ListHead;
270 Entry->BackLink = ListHead->BackLink;
271 Entry->BackLink->ForwardLink = Entry;
272 ListHead->BackLink = Entry;
273 return ListHead;
274 }
275
276 /**
277 Retrieves the first node of a doubly-linked list.
278
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.
282
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().
289
290 @param List A pointer to the head node of a doubly-linked list.
291
292 @return The first node of a doubly-linked list.
293 @retval List The list is empty.
294
295 **/
296 LIST_ENTRY *
297 EFIAPI
GetFirstNode(IN CONST LIST_ENTRY * List)298 GetFirstNode (
299 IN CONST LIST_ENTRY *List
300 )
301 {
302 //
303 // ASSERT List not too long
304 //
305 ASSERT (InternalBaseLibIsListValid (List));
306
307 return List->ForwardLink;
308 }
309
310 /**
311 Retrieves the next node of a doubly-linked list.
312
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.
316
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().
324
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.
327
328 @return A pointer to the next node if one exists. Otherwise List is returned.
329
330 **/
331 LIST_ENTRY *
332 EFIAPI
GetNextNode(IN CONST LIST_ENTRY * List,IN CONST LIST_ENTRY * Node)333 GetNextNode (
334 IN CONST LIST_ENTRY *List,
335 IN CONST LIST_ENTRY *Node
336 )
337 {
338 //
339 // ASSERT List not too long and Node is one of the nodes of List
340 //
341 ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
342
343 return Node->ForwardLink;
344 }
345
346 /**
347 Retrieves the previous node of a doubly-linked list.
348
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.
352
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().
360
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.
363
364 @return A pointer to the previous node if one exists. Otherwise List is returned.
365
366 **/
367 LIST_ENTRY *
368 EFIAPI
GetPreviousNode(IN CONST LIST_ENTRY * List,IN CONST LIST_ENTRY * Node)369 GetPreviousNode (
370 IN CONST LIST_ENTRY *List,
371 IN CONST LIST_ENTRY *Node
372 )
373 {
374 //
375 // ASSERT List not too long and Node is one of the nodes of List
376 //
377 ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
378
379 return Node->BackLink;
380 }
381
382 /**
383 Checks to see if a doubly-linked list is empty or not.
384
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.
387
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().
394
395 @param ListHead A pointer to the head node of a doubly-linked list.
396
397 @retval TRUE The linked list is empty.
398 @retval FALSE The linked list is not empty.
399
400 **/
401 BOOLEAN
402 EFIAPI
IsListEmpty(IN CONST LIST_ENTRY * ListHead)403 IsListEmpty (
404 IN CONST LIST_ENTRY *ListHead
405 )
406 {
407 //
408 // ASSERT List not too long
409 //
410 ASSERT (InternalBaseLibIsListValid (ListHead));
411
412 return (BOOLEAN)(ListHead->ForwardLink == ListHead);
413 }
414
415 /**
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.
419
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().
423
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(),
427 then ASSERT().
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().
433
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.
436
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.
439
440 **/
441 BOOLEAN
442 EFIAPI
IsNull(IN CONST LIST_ENTRY * List,IN CONST LIST_ENTRY * Node)443 IsNull (
444 IN CONST LIST_ENTRY *List,
445 IN CONST LIST_ENTRY *Node
446 )
447 {
448 //
449 // ASSERT List not too long and Node is one of the nodes of List
450 //
451 ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
452
453 return (BOOLEAN)(Node == List);
454 }
455
456 /**
457 Determines if a node the last node in a doubly-linked list.
458
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().
462
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().
471
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.
474
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.
477
478 **/
479 BOOLEAN
480 EFIAPI
IsNodeAtEnd(IN CONST LIST_ENTRY * List,IN CONST LIST_ENTRY * Node)481 IsNodeAtEnd (
482 IN CONST LIST_ENTRY *List,
483 IN CONST LIST_ENTRY *Node
484 )
485 {
486 //
487 // ASSERT List not too long and Node is one of the nodes of List
488 //
489 ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
490
491 return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
492 }
493
494 /**
495 Swaps the location of two nodes in a doubly-linked list, and returns the
496 first node after the swap.
497
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.
504
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().
513
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.
516
517 @return SecondEntry.
518
519 **/
520 LIST_ENTRY *
521 EFIAPI
SwapListEntries(IN OUT LIST_ENTRY * FirstEntry,IN OUT LIST_ENTRY * SecondEntry)522 SwapListEntries (
523 IN OUT LIST_ENTRY *FirstEntry,
524 IN OUT LIST_ENTRY *SecondEntry
525 )
526 {
527 LIST_ENTRY *Ptr;
528
529 if (FirstEntry == SecondEntry) {
530 return SecondEntry;
531 }
532
533 //
534 // ASSERT Entry1 and Entry2 are in the same linked list
535 //
536 ASSERT_VERIFY_NODE_IN_VALID_LIST (FirstEntry, SecondEntry, TRUE);
537
538 //
539 // Ptr is the node pointed to by FirstEntry->ForwardLink
540 //
541 Ptr = RemoveEntryList (FirstEntry);
542
543 //
544 // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
545 // immediately in front of SecondEntry
546 //
547 if (Ptr->BackLink == SecondEntry) {
548 return InsertTailList (SecondEntry, FirstEntry);
549 }
550
551 //
552 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
553 // then there are no further steps necessary
554 //
555 if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
556 return Ptr;
557 }
558
559 //
560 // Move SecondEntry to the front of Ptr
561 //
562 RemoveEntryList (SecondEntry);
563 InsertTailList (Ptr, SecondEntry);
564 return SecondEntry;
565 }
566
567 /**
568 Removes a node from a doubly-linked list, and returns the node that follows
569 the removed node.
570
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
575 list is returned.
576
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().
582
583 @param Entry A pointer to a node in a linked list.
584
585 @return Entry.
586
587 **/
588 LIST_ENTRY *
589 EFIAPI
RemoveEntryList(IN CONST LIST_ENTRY * Entry)590 RemoveEntryList (
591 IN CONST LIST_ENTRY *Entry
592 )
593 {
594 ASSERT (!IsListEmpty (Entry));
595
596 Entry->ForwardLink->BackLink = Entry->BackLink;
597 Entry->BackLink->ForwardLink = Entry->ForwardLink;
598 return Entry->ForwardLink;
599 }
600