TianoCore EDK2 master
LinkedList.c
Go to the documentation of this file.
1
9#include "BaseLibInternals.h"
10
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
62BOOLEAN
63EFIAPI
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
119BOOLEAN
120EFIAPI
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
181EFIAPI
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
217EFIAPI
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
258EFIAPI
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
297EFIAPI
299 IN CONST LIST_ENTRY *List
300 )
301{
302 //
303 // ASSERT List not too long
304 //
306
307 return List->ForwardLink;
308}
309
332EFIAPI
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 //
342
343 return Node->ForwardLink;
344}
345
368EFIAPI
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 //
378
379 return Node->BackLink;
380}
381
401BOOLEAN
402EFIAPI
404 IN CONST LIST_ENTRY *ListHead
405 )
406{
407 //
408 // ASSERT List not too long
409 //
411
412 return (BOOLEAN)(ListHead->ForwardLink == ListHead);
413}
414
441BOOLEAN
442EFIAPI
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 //
452
453 return (BOOLEAN)(Node == List);
454}
455
479BOOLEAN
480EFIAPI
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 //
490
491 return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
492}
493
521EFIAPI
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
589EFIAPI
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}
UINT64 UINTN
#define NULL
Definition: Base.h:312
#define CONST
Definition: Base.h:259
#define TRUE
Definition: Base.h:301
#define FALSE
Definition: Base.h:307
#define IN
Definition: Base.h:279
#define OUT
Definition: Base.h:284
#define ASSERT(Expression)
Definition: DebugLib.h:391
BOOLEAN EFIAPI IsNull(IN CONST LIST_ENTRY *List, IN CONST LIST_ENTRY *Node)
Definition: LinkedList.c:443
LIST_ENTRY *EFIAPI GetPreviousNode(IN CONST LIST_ENTRY *List, IN CONST LIST_ENTRY *Node)
Definition: LinkedList.c:369
BOOLEAN EFIAPI IsListEmpty(IN CONST LIST_ENTRY *ListHead)
Definition: LinkedList.c:403
BOOLEAN EFIAPI InternalBaseLibIsListValid(IN CONST LIST_ENTRY *List)
Definition: LinkedList.c:64
LIST_ENTRY *EFIAPI GetNextNode(IN CONST LIST_ENTRY *List, IN CONST LIST_ENTRY *Node)
Definition: LinkedList.c:333
BOOLEAN EFIAPI IsNodeAtEnd(IN CONST LIST_ENTRY *List, IN CONST LIST_ENTRY *Node)
Definition: LinkedList.c:481
LIST_ENTRY *EFIAPI InsertHeadList(IN OUT LIST_ENTRY *ListHead, IN OUT LIST_ENTRY *Entry)
Definition: LinkedList.c:218
#define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList)
Definition: LinkedList.c:31
LIST_ENTRY *EFIAPI GetFirstNode(IN CONST LIST_ENTRY *List)
Definition: LinkedList.c:298
LIST_ENTRY *EFIAPI SwapListEntries(IN OUT LIST_ENTRY *FirstEntry, IN OUT LIST_ENTRY *SecondEntry)
Definition: LinkedList.c:522
LIST_ENTRY *EFIAPI RemoveEntryList(IN CONST LIST_ENTRY *Entry)
Definition: LinkedList.c:590
LIST_ENTRY *EFIAPI InitializeListHead(IN OUT LIST_ENTRY *ListHead)
Definition: LinkedList.c:182
BOOLEAN EFIAPI IsNodeInList(IN CONST LIST_ENTRY *FirstEntry, IN CONST LIST_ENTRY *SecondEntry)
Definition: LinkedList.c:121
LIST_ENTRY *EFIAPI InsertTailList(IN OUT LIST_ENTRY *ListHead, IN OUT LIST_ENTRY *Entry)
Definition: LinkedList.c:259
#define PcdGet32(TokenName)
Definition: PcdLib.h:362