1/** @file
2  Linked List Library Functions.
3
4  Copyright (c) 2006 - 2013, 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.
9
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.
12
13**/
14
15#include "BaseLibInternals.h"
16
17/**
18  Worker function that locates the Node in the List.
19
20  By searching the List, finds the location of the Node in List. At the same time,
21  verifies the validity of this list.
22
23  If List is NULL, then ASSERT().
24  If List->ForwardLink is NULL, then ASSERT().
25  If List->backLink is NULL, then ASSERT().
26  If Node is NULL, then ASSERT().
27  If PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE and Node
28  is in not a member of List, then return FALSE
29  If PcdMaximumLinkedListLength is not zero, and List contains more than
30  PcdMaximumLinkedListLength nodes, then ASSERT().
31
32  @param  List              A pointer to a node in a linked list.
33  @param  Node              A pointer to a node in a linked list.
34  @param  VerifyNodeInList  TRUE if a check should be made to see if Node is a
35                            member of List.  FALSE if no membership test should
36                            be performed.
37
38  @retval   TRUE if PcdVerifyNodeInList is FALSE
39  @retval   TRUE if DoMembershipCheck is FALSE
40  @retval   TRUE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE
41            and Node is a member of List.
42  @retval   FALSE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE
43            and Node is in not a member of List.
44
45**/
46BOOLEAN
47EFIAPI
48InternalBaseLibIsNodeInList (
49  IN CONST LIST_ENTRY  *List,
50  IN CONST LIST_ENTRY  *Node,
51  IN BOOLEAN           VerifyNodeInList
52  )
53{
54  UINTN             Count;
55  CONST LIST_ENTRY  *Ptr;
56
57  //
58  // Test the validity of List and Node
59  //
60  ASSERT (List != NULL);
61  ASSERT (List->ForwardLink != NULL);
62  ASSERT (List->BackLink != NULL);
63  ASSERT (Node != NULL);
64
65  Count = 0;
66  Ptr   = List;
67
68  if (FeaturePcdGet (PcdVerifyNodeInList) && VerifyNodeInList) {
69    //
70    // Check to see if Node is a member of List.
71    // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
72    //
73    do {
74      Ptr = Ptr->ForwardLink;
75      if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
76        Count++;
77        //
78        // ASSERT() if the linked list is too long
79        //
80        ASSERT (Count < PcdGet32 (PcdMaximumLinkedListLength));
81
82        //
83        // Return if the linked list is too long
84        //
85        if (Count >= PcdGet32 (PcdMaximumLinkedListLength)) {
86          return (BOOLEAN)(Ptr == Node);
87        }
88      }
89    } while ((Ptr != List) && (Ptr != Node));
90
91    if (Ptr != Node) {
92      return FALSE;
93    }
94  }
95
96  if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
97    //
98    // Count the total number of nodes in List.
99    // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
100    //
101    do {
102      Ptr = Ptr->ForwardLink;
103      Count++;
104    } while ((Ptr != List) && (Count < PcdGet32 (PcdMaximumLinkedListLength)));
105
106    //
107    // ASSERT() if the linked list is too long
108    //
109    ASSERT (Count < PcdGet32 (PcdMaximumLinkedListLength));
110  }
111
112  return TRUE;
113}
114
115/**
116  Initializes the head node of a doubly-linked list, and returns the pointer to
117  the head node of the doubly-linked list.
118
119  Initializes the forward and backward links of a new linked list. After
120  initializing a linked list with this function, the other linked list
121  functions may be used to add and remove nodes from the linked list. It is up
122  to the caller of this function to allocate the memory for ListHead.
123
124  If ListHead is NULL, then ASSERT().
125
126  @param  ListHead  A pointer to the head node of a new doubly-linked list.
127
128  @return ListHead
129
130**/
131LIST_ENTRY *
132EFIAPI
133InitializeListHead (
134  IN OUT  LIST_ENTRY                *ListHead
135  )
136
137{
138  ASSERT (ListHead != NULL);
139
140  ListHead->ForwardLink = ListHead;
141  ListHead->BackLink = ListHead;
142  return ListHead;
143}
144
145/**
146  Adds a node to the beginning of a doubly-linked list, and returns the pointer
147  to the head node of the doubly-linked list.
148
149  Adds the node Entry at the beginning of the doubly-linked list denoted by
150  ListHead, and returns ListHead.
151
152  If ListHead is NULL, then ASSERT().
153  If Entry is NULL, then ASSERT().
154  If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
155  InitializeListHead(), then ASSERT().
156  If PcdMaximumLinkedListLength is not zero, and prior to insertion the number
157  of nodes in ListHead, including the ListHead node, is greater than or
158  equal to PcdMaximumLinkedListLength, then ASSERT().
159
160  @param  ListHead  A pointer to the head node of a doubly-linked list.
161  @param  Entry     A pointer to a node that is to be inserted at the beginning
162                    of a doubly-linked list.
163
164  @return ListHead
165
166**/
167LIST_ENTRY *
168EFIAPI
169InsertHeadList (
170  IN OUT  LIST_ENTRY                *ListHead,
171  IN OUT  LIST_ENTRY                *Entry
172  )
173{
174  //
175  // ASSERT List not too long and Entry is not one of the nodes of List
176  //
177  ASSERT (InternalBaseLibIsNodeInList (ListHead, Entry, FALSE));
178
179  Entry->ForwardLink = ListHead->ForwardLink;
180  Entry->BackLink = ListHead;
181  Entry->ForwardLink->BackLink = Entry;
182  ListHead->ForwardLink = Entry;
183  return ListHead;
184}
185
186/**
187  Adds a node to the end of a doubly-linked list, and returns the pointer to
188  the head node of the doubly-linked list.
189
190  Adds the node Entry to the end of the doubly-linked list denoted by ListHead,
191  and returns ListHead.
192
193  If ListHead is NULL, then ASSERT().
194  If Entry is NULL, then ASSERT().
195  If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
196  InitializeListHead(), then ASSERT().
197  If PcdMaximumLinkedListLength is not zero, and prior to insertion the number
198  of nodes in ListHead, including the ListHead node, is greater than or
199  equal to PcdMaximumLinkedListLength, then ASSERT().
200
201  @param  ListHead  A pointer to the head node of a doubly-linked list.
202  @param  Entry     A pointer to a node that is to be added at the end of the
203                    doubly-linked list.
204
205  @return ListHead
206
207**/
208LIST_ENTRY *
209EFIAPI
210InsertTailList (
211  IN OUT  LIST_ENTRY                *ListHead,
212  IN OUT  LIST_ENTRY                *Entry
213  )
214{
215  //
216  // ASSERT List not too long and Entry is not one of the nodes of List
217  //
218  ASSERT (InternalBaseLibIsNodeInList (ListHead, Entry, FALSE));
219
220  Entry->ForwardLink = ListHead;
221  Entry->BackLink = ListHead->BackLink;
222  Entry->BackLink->ForwardLink = Entry;
223  ListHead->BackLink = Entry;
224  return ListHead;
225}
226
227/**
228  Retrieves the first node of a doubly-linked list.
229
230  Returns the first node of a doubly-linked list.  List must have been
231  initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
232  If List is empty, then List is returned.
233
234  If List is NULL, then ASSERT().
235  If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
236  InitializeListHead(), then ASSERT().
237  If PcdMaximumLinkedListLength is not zero, and the number of nodes
238  in List, including the List node, is greater than or equal to
239  PcdMaximumLinkedListLength, then ASSERT().
240
241  @param  List  A pointer to the head node of a doubly-linked list.
242
243  @return The first node of a doubly-linked list.
244  @retval List  The list is empty.
245
246**/
247LIST_ENTRY *
248EFIAPI
249GetFirstNode (
250  IN      CONST LIST_ENTRY          *List
251  )
252{
253  //
254  // ASSERT List not too long
255  //
256  ASSERT (InternalBaseLibIsNodeInList (List, List, FALSE));
257
258  return List->ForwardLink;
259}
260
261/**
262  Retrieves the next node of a doubly-linked list.
263
264  Returns the node of a doubly-linked list that follows Node.
265  List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()
266  or InitializeListHead().  If List is empty, then List is returned.
267
268  If List is NULL, then ASSERT().
269  If Node is NULL, then ASSERT().
270  If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
271  InitializeListHead(), then ASSERT().
272  If PcdMaximumLinkedListLength is not zero, and List contains more than
273  PcdMaximumLinkedListLength nodes, then ASSERT().
274  If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
275
276  @param  List  A pointer to the head node of a doubly-linked list.
277  @param  Node  A pointer to a node in the doubly-linked list.
278
279  @return A pointer to the next node if one exists. Otherwise List is returned.
280
281**/
282LIST_ENTRY *
283EFIAPI
284GetNextNode (
285  IN      CONST LIST_ENTRY          *List,
286  IN      CONST LIST_ENTRY          *Node
287  )
288{
289  //
290  // ASSERT List not too long and Node is one of the nodes of List
291  //
292  ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));
293
294  return Node->ForwardLink;
295}
296
297/**
298  Retrieves the previous node of a doubly-linked list.
299
300  Returns the node of a doubly-linked list that precedes Node.
301  List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()
302  or InitializeListHead().  If List is empty, then List is returned.
303
304  If List is NULL, then ASSERT().
305  If Node is NULL, then ASSERT().
306  If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
307  InitializeListHead(), then ASSERT().
308  If PcdMaximumLinkedListLength is not zero, and List contains more than
309  PcdMaximumLinkedListLength nodes, then ASSERT().
310  If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
311
312  @param  List  A pointer to the head node of a doubly-linked list.
313  @param  Node  A pointer to a node in the doubly-linked list.
314
315  @return A pointer to the previous node if one exists. Otherwise List is returned.
316
317**/
318LIST_ENTRY *
319EFIAPI
320GetPreviousNode (
321  IN      CONST LIST_ENTRY          *List,
322  IN      CONST LIST_ENTRY          *Node
323  )
324{
325  //
326  // ASSERT List not too long and Node is one of the nodes of List
327  //
328  ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));
329
330  return Node->BackLink;
331}
332
333/**
334  Checks to see if a doubly-linked list is empty or not.
335
336  Checks to see if the doubly-linked list is empty. If the linked list contains
337  zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
338
339  If ListHead is NULL, then ASSERT().
340  If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
341  InitializeListHead(), then ASSERT().
342  If PcdMaximumLinkedListLength is not zero, and the number of nodes
343  in List, including the List node, is greater than or equal to
344  PcdMaximumLinkedListLength, then ASSERT().
345
346  @param  ListHead  A pointer to the head node of a doubly-linked list.
347
348  @retval TRUE  The linked list is empty.
349  @retval FALSE The linked list is not empty.
350
351**/
352BOOLEAN
353EFIAPI
354IsListEmpty (
355  IN      CONST LIST_ENTRY          *ListHead
356  )
357{
358  //
359  // ASSERT List not too long
360  //
361  ASSERT (InternalBaseLibIsNodeInList (ListHead, ListHead, FALSE));
362
363  return (BOOLEAN)(ListHead->ForwardLink == ListHead);
364}
365
366/**
367  Determines if a node in a doubly-linked list is the head node of a the same
368  doubly-linked list.  This function is typically used to terminate a loop that
369  traverses all the nodes in a doubly-linked list starting with the head node.
370
371  Returns TRUE if Node is equal to List.  Returns FALSE if Node is one of the
372  nodes in the doubly-linked list specified by List.  List must have been
373  initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
374
375  If List is NULL, then ASSERT().
376  If Node is NULL, then ASSERT().
377  If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(),
378  then ASSERT().
379  If PcdMaximumLinkedListLength is not zero, and the number of nodes
380  in List, including the List node, is greater than or equal to
381  PcdMaximumLinkedListLength, then ASSERT().
382  If PcdVerifyNodeInList is TRUE and Node is not a node in List and Node is not
383  equal to List, then ASSERT().
384
385  @param  List  A pointer to the head node of a doubly-linked list.
386  @param  Node  A pointer to a node in the doubly-linked list.
387
388  @retval TRUE  Node is the head of the doubly-linked list pointed by List.
389  @retval FALSE Node is not the head of the doubly-linked list pointed by List.
390
391**/
392BOOLEAN
393EFIAPI
394IsNull (
395  IN      CONST LIST_ENTRY          *List,
396  IN      CONST LIST_ENTRY          *Node
397  )
398{
399  //
400  // ASSERT List not too long and Node is one of the nodes of List
401  //
402  ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));
403
404  return (BOOLEAN)(Node == List);
405}
406
407/**
408  Determines if a node the last node in a doubly-linked list.
409
410  Returns TRUE if Node is the last node in the doubly-linked list specified by
411  List. Otherwise, FALSE is returned. List must have been initialized with
412  INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
413
414  If List is NULL, then ASSERT().
415  If Node is NULL, then ASSERT().
416  If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
417  InitializeListHead(), then ASSERT().
418  If PcdMaximumLinkedListLength is not zero, and the number of nodes
419  in List, including the List node, is greater than or equal to
420  PcdMaximumLinkedListLength, then ASSERT().
421  If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
422
423  @param  List  A pointer to the head node of a doubly-linked list.
424  @param  Node  A pointer to a node in the doubly-linked list.
425
426  @retval TRUE  Node is the last node in the linked list.
427  @retval FALSE Node is not the last node in the linked list.
428
429**/
430BOOLEAN
431EFIAPI
432IsNodeAtEnd (
433  IN      CONST LIST_ENTRY          *List,
434  IN      CONST LIST_ENTRY          *Node
435  )
436{
437  //
438  // ASSERT List not too long and Node is one of the nodes of List
439  //
440  ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));
441
442  return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
443}
444
445/**
446  Swaps the location of two nodes in a doubly-linked list, and returns the
447  first node after the swap.
448
449  If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
450  Otherwise, the location of the FirstEntry node is swapped with the location
451  of the SecondEntry node in a doubly-linked list. SecondEntry must be in the
452  same double linked list as FirstEntry and that double linked list must have
453  been initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
454  SecondEntry is returned after the nodes are swapped.
455
456  If FirstEntry is NULL, then ASSERT().
457  If SecondEntry is NULL, then ASSERT().
458  If PcdVerifyNodeInList is TRUE and SecondEntry and FirstEntry are not in the
459  same linked list, then ASSERT().
460  If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
461  linked list containing the FirstEntry and SecondEntry nodes, including
462  the FirstEntry and SecondEntry nodes, is greater than or equal to
463  PcdMaximumLinkedListLength, then ASSERT().
464
465  @param  FirstEntry  A pointer to a node in a linked list.
466  @param  SecondEntry A pointer to another node in the same linked list.
467
468  @return SecondEntry.
469
470**/
471LIST_ENTRY *
472EFIAPI
473SwapListEntries (
474  IN OUT  LIST_ENTRY                *FirstEntry,
475  IN OUT  LIST_ENTRY                *SecondEntry
476  )
477{
478  LIST_ENTRY                    *Ptr;
479
480  if (FirstEntry == SecondEntry) {
481    return SecondEntry;
482  }
483
484  //
485  // ASSERT Entry1 and Entry2 are in the same linked list
486  //
487  ASSERT (InternalBaseLibIsNodeInList (FirstEntry, SecondEntry, TRUE));
488
489  //
490  // Ptr is the node pointed to by FirstEntry->ForwardLink
491  //
492  Ptr = RemoveEntryList (FirstEntry);
493
494  //
495  // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
496  // immediately in front of SecondEntry
497  //
498  if (Ptr->BackLink == SecondEntry) {
499    return InsertTailList (SecondEntry, FirstEntry);
500  }
501
502  //
503  // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
504  // then there are no further steps necessary
505  //
506  if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
507    return Ptr;
508  }
509
510  //
511  // Move SecondEntry to the front of Ptr
512  //
513  RemoveEntryList (SecondEntry);
514  InsertTailList (Ptr, SecondEntry);
515  return SecondEntry;
516}
517
518/**
519  Removes a node from a doubly-linked list, and returns the node that follows
520  the removed node.
521
522  Removes the node Entry from a doubly-linked list. It is up to the caller of
523  this function to release the memory used by this node if that is required. On
524  exit, the node following Entry in the doubly-linked list is returned. If
525  Entry is the only node in the linked list, then the head node of the linked
526  list is returned.
527
528  If Entry is NULL, then ASSERT().
529  If Entry is the head node of an empty list, then ASSERT().
530  If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
531  linked list containing Entry, including the Entry node, is greater than
532  or equal to PcdMaximumLinkedListLength, then ASSERT().
533
534  @param  Entry A pointer to a node in a linked list.
535
536  @return Entry.
537
538**/
539LIST_ENTRY *
540EFIAPI
541RemoveEntryList (
542  IN      CONST LIST_ENTRY          *Entry
543  )
544{
545  ASSERT (!IsListEmpty (Entry));
546
547  Entry->ForwardLink->BackLink = Entry->BackLink;
548  Entry->BackLink->ForwardLink = Entry->ForwardLink;
549  return Entry->ForwardLink;
550}
551