MdePkg/Library/BaseLib/LinkedList.c

   1 /** @file
   2   Linked List Library Functions.
   3
   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.
   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   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
  21   valid list.
  22
  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().
  29
  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.
  34
  35 **/
  36 #if !defined (MDEPKG_NDEBUG)
  37   #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList)  \
  38     do {                                                                     \
  39       if (FeaturePcdGet (PcdVerifyNodeInList)) {                             \
  40         ASSERT (InList == IsNodeInList ((FirstEntry), (SecondEntry)));       \
  41       } else {                                                               \
  42         ASSERT (InternalBaseLibIsListValid (FirstEntry));                    \
  43       }                                                                      \
  44     } while (FALSE)
  45 #else
  46   #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList)
  47 #endif
  48
  49 /**
  50   Worker function that verifies the validity of this list.
  51
  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().
  57
  58   @param  List              A pointer to a node in a linked list.
  59
  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.
  66
  67 **/
  68 BOOLEAN
  69 EFIAPI
  70 InternalBaseLibIsListValid (
  71   IN CONST LIST_ENTRY  *List
  72   )
  73 {
  74   UINTN             Count;
  75   CONST LIST_ENTRY  *Ptr;
  76
  77   //
  78   // Test the validity of List and Node
  79   //
  80   ASSERT (List != NULL);
  81   ASSERT (List->ForwardLink != NULL);
  82   ASSERT (List->BackLink != NULL);
  83
  84   if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
  85     Count = 0;
  86     Ptr   = List;
  87
  88     //
  89     // Count the total number of nodes in List.
  90     // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
  91     //
  92     do {
  93       Ptr = Ptr->ForwardLink;
  94       Count++;
  95     } while ((Ptr != List) && (Count < PcdGet32 (PcdMaximumLinkedListLength)));
  96
  97     //
  98     // return whether linked list is too long
  99     //
 100     return (BOOLEAN)(Count < PcdGet32 (PcdMaximumLinkedListLength));
 101   }
 102
 103   return TRUE;
 104 }
 105
 106 /**
 107   Checks whether FirstEntry and SecondEntry are part of the same doubly-linked
 108   list.
 109
 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().
 116
 117   @param  FirstEntry   A pointer to a node in a linked list.
 118   @param  SecondEntry  A pointer to the node to locate.
 119
 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.
 123
 124 **/
 125 BOOLEAN
 126 EFIAPI
 127 IsNodeInList (
 128   IN      CONST LIST_ENTRY      *FirstEntry,
 129   IN      CONST LIST_ENTRY      *SecondEntry
 130   )
 131 {
 132   UINTN             Count;
 133   CONST LIST_ENTRY  *Ptr;
 134
 135   //
 136   // ASSERT List not too long
 137   //
 138   ASSERT (InternalBaseLibIsListValid (FirstEntry));
 139
 140   ASSERT (SecondEntry != NULL);
 141
 142   Count = 0;
 143   Ptr   = FirstEntry;
 144
 145   //
 146   // Check to see if SecondEntry is a member of FirstEntry.
 147   // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
 148   //
 149   do {
 150     Ptr = Ptr->ForwardLink;
 151     if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
 152       Count++;
 153
 154       //
 155       // Return if the linked list is too long
 156       //
 157       if (Count == PcdGet32 (PcdMaximumLinkedListLength)) {
 158         return (BOOLEAN)(Ptr == SecondEntry);
 159       }
 160     }
 161
 162     if (Ptr == SecondEntry) {
 163       return TRUE;
 164     }
 165   } while (Ptr != FirstEntry);
 166
 167   return FALSE;
 168 }
 169
 170 /**
 171   Initializes the head node of a doubly-linked list, and returns the pointer to
 172   the head node of the doubly-linked list.
 173
 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.
 178
 179   If ListHead is NULL, then ASSERT().
 180
 181   @param  ListHead  A pointer to the head node of a new doubly-linked list.
 182
 183   @return ListHead
 184
 185 **/
 186 LIST_ENTRY *
 187 EFIAPI
 188 InitializeListHead (
 189   IN OUT  LIST_ENTRY                *ListHead
 190   )
 191
 192 {
 193   ASSERT (ListHead != NULL);
 194
 195   ListHead->ForwardLink = ListHead;
 196   ListHead->BackLink = ListHead;
 197   return ListHead;
 198 }
 199
 200 /**
 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.
 203
 204   Adds the node Entry at the beginning of the doubly-linked list denoted by
 205   ListHead, and returns ListHead.
 206
 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().
 214
 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.
 218
 219   @return ListHead
 220
 221 **/
 222 LIST_ENTRY *
 223 EFIAPI
 224 InsertHeadList (
 225   IN OUT  LIST_ENTRY                *ListHead,
 226   IN OUT  LIST_ENTRY                *Entry
 227   )
 228 {
 229   //
 230   // ASSERT List not too long and Entry is not one of the nodes of List
 231   //
 232   ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead, Entry, FALSE);
 233
 234   Entry->ForwardLink = ListHead->ForwardLink;
 235   Entry->BackLink = ListHead;
 236   Entry->ForwardLink->BackLink = Entry;
 237   ListHead->ForwardLink = Entry;
 238   return ListHead;
 239 }
 240
 241 /**
 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.
 244
 245   Adds the node Entry to the end of the doubly-linked list denoted by ListHead,
 246   and returns ListHead.
 247
 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().
 255
 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
 258                     doubly-linked list.
 259
 260   @return ListHead
 261
 262 **/
 263 LIST_ENTRY *
 264 EFIAPI
 265 InsertTailList (
 266   IN OUT  LIST_ENTRY                *ListHead,
 267   IN OUT  LIST_ENTRY                *Entry
 268   )
 269 {
 270   //
 271   // ASSERT List not too long and Entry is not one of the nodes of List
 272   //
 273   ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead, Entry, FALSE);
 274
 275   Entry->ForwardLink = ListHead;
 276   Entry->BackLink = ListHead->BackLink;
 277   Entry->BackLink->ForwardLink = Entry;
 278   ListHead->BackLink = Entry;
 279   return ListHead;
 280 }
 281
 282 /**
 283   Retrieves the first node of a doubly-linked list.
 284
 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.
 288
 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().
 295
 296   @param  List  A pointer to the head node of a doubly-linked list.
 297
 298   @return The first node of a doubly-linked list.
 299   @retval List  The list is empty.
 300
 301 **/
 302 LIST_ENTRY *
 303 EFIAPI
 304 GetFirstNode (
 305   IN      CONST LIST_ENTRY          *List
 306   )
 307 {
 308   //
 309   // ASSERT List not too long
 310   //
 311   ASSERT (InternalBaseLibIsListValid (List));
 312
 313   return List->ForwardLink;
 314 }
 315
 316 /**
 317   Retrieves the next node of a doubly-linked list.
 318
 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.
 322
 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().
 330
 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.
 333
 334   @return A pointer to the next node if one exists. Otherwise List is returned.
 335
 336 **/
 337 LIST_ENTRY *
 338 EFIAPI
 339 GetNextNode (
 340   IN      CONST LIST_ENTRY          *List,
 341   IN      CONST LIST_ENTRY          *Node
 342   )
 343 {
 344   //
 345   // ASSERT List not too long and Node is one of the nodes of List
 346   //
 347   ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
 348
 349   return Node->ForwardLink;
 350 }
 351
 352 /**
 353   Retrieves the previous node of a doubly-linked list.
 354
 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.
 358
 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().
 366
 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.
 369
 370   @return A pointer to the previous node if one exists. Otherwise List is returned.
 371
 372 **/
 373 LIST_ENTRY *
 374 EFIAPI
 375 GetPreviousNode (
 376   IN      CONST LIST_ENTRY          *List,
 377   IN      CONST LIST_ENTRY          *Node
 378   )
 379 {
 380   //
 381   // ASSERT List not too long and Node is one of the nodes of List
 382   //
 383   ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
 384
 385   return Node->BackLink;
 386 }
 387
 388 /**
 389   Checks to see if a doubly-linked list is empty or not.
 390
 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.
 393
 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().
 400
 401   @param  ListHead  A pointer to the head node of a doubly-linked list.
 402
 403   @retval TRUE  The linked list is empty.
 404   @retval FALSE The linked list is not empty.
 405
 406 **/
 407 BOOLEAN
 408 EFIAPI
 409 IsListEmpty (
 410   IN      CONST LIST_ENTRY          *ListHead
 411   )
 412 {
 413   //
 414   // ASSERT List not too long
 415   //
 416   ASSERT (InternalBaseLibIsListValid (ListHead));
 417
 418   return (BOOLEAN)(ListHead->ForwardLink == ListHead);
 419 }
 420
 421 /**
 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.
 425
 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().
 429
 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(),
 433   then ASSERT().
 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().
 439
 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.
 442
 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.
 445
 446 **/
 447 BOOLEAN
 448 EFIAPI
 449 IsNull (
 450   IN      CONST LIST_ENTRY          *List,
 451   IN      CONST LIST_ENTRY          *Node
 452   )
 453 {
 454   //
 455   // ASSERT List not too long and Node is one of the nodes of List
 456   //
 457   ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
 458
 459   return (BOOLEAN)(Node == List);
 460 }
 461
 462 /**
 463   Determines if a node the last node in a doubly-linked list.
 464
 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().
 468
 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().
 477
 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.
 480
 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.
 483
 484 **/
 485 BOOLEAN
 486 EFIAPI
 487 IsNodeAtEnd (
 488   IN      CONST LIST_ENTRY          *List,
 489   IN      CONST LIST_ENTRY          *Node
 490   )
 491 {
 492   //
 493   // ASSERT List not too long and Node is one of the nodes of List
 494   //
 495   ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
 496
 497   return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
 498 }
 499
 500 /**
 501   Swaps the location of two nodes in a doubly-linked list, and returns the
 502   first node after the swap.
 503
 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.
 510
 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().
 519
 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.
 522
 523   @return SecondEntry.
 524
 525 **/
 526 LIST_ENTRY *
 527 EFIAPI
 528 SwapListEntries (
 529   IN OUT  LIST_ENTRY                *FirstEntry,
 530   IN OUT  LIST_ENTRY                *SecondEntry
 531   )
 532 {
 533   LIST_ENTRY                    *Ptr;
 534
 535   if (FirstEntry == SecondEntry) {
 536     return SecondEntry;
 537   }
 538
 539   //
 540   // ASSERT Entry1 and Entry2 are in the same linked list
 541   //
 542   ASSERT_VERIFY_NODE_IN_VALID_LIST (FirstEntry, SecondEntry, TRUE);
 543
 544   //
 545   // Ptr is the node pointed to by FirstEntry->ForwardLink
 546   //
 547   Ptr = RemoveEntryList (FirstEntry);
 548
 549   //
 550   // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
 551   // immediately in front of SecondEntry
 552   //
 553   if (Ptr->BackLink == SecondEntry) {
 554     return InsertTailList (SecondEntry, FirstEntry);
 555   }
 556
 557   //
 558   // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
 559   // then there are no further steps necessary
 560   //
 561   if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
 562     return Ptr;
 563   }
 564
 565   //
 566   // Move SecondEntry to the front of Ptr
 567   //
 568   RemoveEntryList (SecondEntry);
 569   InsertTailList (Ptr, SecondEntry);
 570   return SecondEntry;
 571 }
 572
 573 /**
 574   Removes a node from a doubly-linked list, and returns the node that follows
 575   the removed node.
 576
 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
 581   list is returned.
 582
 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().
 588
 589   @param  Entry A pointer to a node in a linked list.
 590
 591   @return Entry.
 592
 593 **/
 594 LIST_ENTRY *
 595 EFIAPI
 596 RemoveEntryList (
 597   IN      CONST LIST_ENTRY          *Entry
 598   )
 599 {
 600   ASSERT (!IsListEmpty (Entry));
 601
 602   Entry->ForwardLink->BackLink = Entry->BackLink;
 603   Entry->BackLink->ForwardLink = Entry->ForwardLink;
 604   return Entry->ForwardLink;
 605 }