MdePkg/Library/BaseLib/LinkedList.c

   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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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 }