MdePkg/Library/BaseLib/LinkedList.c

   1 /** @file
   2   Linked List Library Functions.
   3
   4   Copyright (c) 2006 - 2008, 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 PcdMaximumLinkedListLenth is not zero, and List contains more than
  30   PcdMaximumLinkedListLenth 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 **/
  46 BOOLEAN
  47 EFIAPI
  48 InternalBaseLibIsNodeInList (
  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 **/
 131 LIST_ENTRY *
 132 EFIAPI
 133 InitializeListHead (
 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 PcdMaximumLinkedListLenth 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 **/
 167 LIST_ENTRY *
 168 EFIAPI
 169 InsertHeadList (
 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 PcdMaximumLinkedListLenth 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 **/
 208 LIST_ENTRY *
 209 EFIAPI
 210 InsertTailList (
 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 PcdMaximumLinkedListLenth 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 NULL  The list is empty.
 245
 246 **/
 247 LIST_ENTRY *
 248 EFIAPI
 249 GetFirstNode (
 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 PcdMaximumLinkedListLenth is not zero, and List contains more than
 273   PcdMaximumLinkedListLenth 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 Pointer to the next node if one exists. Otherwise List is returned.
 280
 281 **/
 282 LIST_ENTRY *
 283 EFIAPI
 284 GetNextNode (
 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 PcdMaximumLinkedListLenth is not zero, and List contains more than
 309   PcdMaximumLinkedListLenth 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 Pointer to the previous node if one exists. Otherwise List is returned.
 316
 317 **/
 318 LIST_ENTRY *
 319 EFIAPI
 320 GetPreviousNode (
 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 PcdMaximumLinkedListLenth 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 **/
 352 BOOLEAN
 353 EFIAPI
 354 IsListEmpty (
 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 PcdMaximumLinkedListLenth 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 one of the nodes in the doubly linked list.
 389   @retval FALSE Node is not one of the nodes in the doubly linked list.
 390
 391 **/
 392 BOOLEAN
 393 EFIAPI
 394 IsNull (
 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 PcdMaximumLinkedListLenth 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 **/
 430 BOOLEAN
 431 EFIAPI
 432 IsNodeAtEnd (
 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 **/
 471 LIST_ENTRY *
 472 EFIAPI
 473 SwapListEntries (
 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 **/
 539 LIST_ENTRY *
 540 EFIAPI
 541 RemoveEntryList (
 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 }