MdePkg/Library/BaseLib/LinkedList.c

   1 /** @file
   2   Linked List Library Functions.
   3
   4   Copyright (c) 2006 - 2008, Intel Corporation<BR>
   5   All rights reserved. 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 a null value which
 280           is actually List is returned.
 281
 282 **/
 283 LIST_ENTRY *
 284 EFIAPI
 285 GetNextNode (
 286   IN      CONST LIST_ENTRY          *List,
 287   IN      CONST LIST_ENTRY          *Node
 288   )
 289 {
 290   //
 291   // ASSERT List not too long and Node is one of the nodes of List
 292   //
 293   ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));
 294
 295   return Node->ForwardLink;
 296 }
 297
 298 /**
 299   Checks to see if a doubly linked list is empty or not.
 300
 301   Checks to see if the doubly linked list is empty. If the linked list contains
 302   zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
 303
 304   If ListHead is NULL, then ASSERT().
 305   If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
 306   InitializeListHead(), then ASSERT().
 307   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 308   in List, including the List node, is greater than or equal to
 309   PcdMaximumLinkedListLength, then ASSERT().
 310
 311   @param  ListHead  A pointer to the head node of a doubly linked list.
 312
 313   @retval TRUE  The linked list is empty.
 314   @retval FALSE The linked list is not empty.
 315
 316 **/
 317 BOOLEAN
 318 EFIAPI
 319 IsListEmpty (
 320   IN      CONST LIST_ENTRY          *ListHead
 321   )
 322 {
 323   //
 324   // ASSERT List not too long
 325   //
 326   ASSERT (InternalBaseLibIsNodeInList (ListHead, ListHead, FALSE));
 327
 328   return (BOOLEAN)(ListHead->ForwardLink == ListHead);
 329 }
 330
 331 /**
 332   Determines if a node in a doubly linked list is the head node of a the same
 333   doubly linked list.  This function is typically used to terminate a loop that
 334   traverses all the nodes in a doubly linked list starting with the head node.
 335
 336   Returns TRUE if Node is equal to List.  Returns FALSE if Node is one of the
 337   nodes in the doubly linked list specified by List.  List must have been
 338   initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
 339
 340   If List is NULL, then ASSERT().
 341   If Node is NULL, then ASSERT().
 342   If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(),
 343   then ASSERT().
 344   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 345   in List, including the List node, is greater than or equal to
 346   PcdMaximumLinkedListLength, then ASSERT().
 347   If PcdVerifyNodeInList is TRUE and Node is not a node in List and Node is not
 348   equal to List, then ASSERT().
 349
 350   @param  List  A pointer to the head node of a doubly linked list.
 351   @param  Node  A pointer to a node in the doubly linked list.
 352
 353   @retval TRUE  Node is one of the nodes in the doubly linked list.
 354   @retval FALSE Node is not one of the nodes in the doubly linked list.
 355
 356 **/
 357 BOOLEAN
 358 EFIAPI
 359 IsNull (
 360   IN      CONST LIST_ENTRY          *List,
 361   IN      CONST LIST_ENTRY          *Node
 362   )
 363 {
 364   //
 365   // ASSERT List not too long and Node is one of the nodes of List
 366   //
 367   ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));
 368
 369   return (BOOLEAN)(Node == List);
 370 }
 371
 372 /**
 373   Determines if a node the last node in a doubly linked list.
 374
 375   Returns TRUE if Node is the last node in the doubly linked list specified by
 376   List. Otherwise, FALSE is returned. List must have been initialized with
 377   INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
 378
 379   If List is NULL, then ASSERT().
 380   If Node is NULL, then ASSERT().
 381   If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
 382   InitializeListHead(), then ASSERT().
 383   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 384   in List, including the List node, is greater than or equal to
 385   PcdMaximumLinkedListLength, then ASSERT().
 386   If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().
 387
 388   @param  List  A pointer to the head node of a doubly linked list.
 389   @param  Node  A pointer to a node in the doubly linked list.
 390
 391   @retval TRUE  Node is the last node in the linked list.
 392   @retval FALSE Node is not the last node in the linked list.
 393
 394 **/
 395 BOOLEAN
 396 EFIAPI
 397 IsNodeAtEnd (
 398   IN      CONST LIST_ENTRY          *List,
 399   IN      CONST LIST_ENTRY          *Node
 400   )
 401 {
 402   //
 403   // ASSERT List not too long and Node is one of the nodes of List
 404   //
 405   ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));
 406
 407   return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
 408 }
 409
 410 /**
 411   Swaps the location of two nodes in a doubly linked list, and returns the
 412   first node after the swap.
 413
 414   If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
 415   Otherwise, the location of the FirstEntry node is swapped with the location
 416   of the SecondEntry node in a doubly linked list. SecondEntry must be in the
 417   same double linked list as FirstEntry and that double linked list must have
 418   been initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
 419   SecondEntry is returned after the nodes are swapped.
 420
 421   If FirstEntry is NULL, then ASSERT().
 422   If SecondEntry is NULL, then ASSERT().
 423   If PcdVerifyNodeInList is TRUE and SecondEntry and FirstEntry are not in the
 424   same linked list, then ASSERT().
 425   If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
 426   linked list containing the FirstEntry and SecondEntry nodes, including
 427   the FirstEntry and SecondEntry nodes, is greater than or equal to
 428   PcdMaximumLinkedListLength, then ASSERT().
 429
 430   @param  FirstEntry  A pointer to a node in a linked list.
 431   @param  SecondEntry A pointer to another node in the same linked list.
 432
 433   @return SecondEntry.
 434
 435 **/
 436 LIST_ENTRY *
 437 EFIAPI
 438 SwapListEntries (
 439   IN OUT  LIST_ENTRY                *FirstEntry,
 440   IN OUT  LIST_ENTRY                *SecondEntry
 441   )
 442 {
 443   LIST_ENTRY                    *Ptr;
 444
 445   if (FirstEntry == SecondEntry) {
 446     return SecondEntry;
 447   }
 448
 449   //
 450   // ASSERT Entry1 and Entry2 are in the same linked list
 451   //
 452   ASSERT (InternalBaseLibIsNodeInList (FirstEntry, SecondEntry, TRUE));
 453
 454   //
 455   // Ptr is the node pointed to by FirstEntry->ForwardLink
 456   //
 457   Ptr = RemoveEntryList (FirstEntry);
 458
 459   //
 460   // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
 461   // immediately in front of SecondEntry
 462   //
 463   if (Ptr->BackLink == SecondEntry) {
 464     return InsertTailList (SecondEntry, FirstEntry);
 465   }
 466
 467   //
 468   // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
 469   // then there are no further steps necessary
 470   //
 471   if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
 472     return Ptr;
 473   }
 474
 475   //
 476   // Move SecondEntry to the front of Ptr
 477   //
 478   RemoveEntryList (SecondEntry);
 479   InsertTailList (Ptr, SecondEntry);
 480   return SecondEntry;
 481 }
 482
 483 /**
 484   Removes a node from a doubly linked list, and returns the node that follows
 485   the removed node.
 486
 487   Removes the node Entry from a doubly linked list. It is up to the caller of
 488   this function to release the memory used by this node if that is required. On
 489   exit, the node following Entry in the doubly linked list is returned. If
 490   Entry is the only node in the linked list, then the head node of the linked
 491   list is returned.
 492
 493   If Entry is NULL, then ASSERT().
 494   If Entry is the head node of an empty list, then ASSERT().
 495   If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
 496   linked list containing Entry, including the Entry node, is greater than
 497   or equal to PcdMaximumLinkedListLength, then ASSERT().
 498
 499   @param  Entry A pointer to a node in a linked list.
 500
 501   @return Entry.
 502
 503 **/
 504 LIST_ENTRY *
 505 EFIAPI
 506 RemoveEntryList (
 507   IN      CONST LIST_ENTRY          *Entry
 508   )
 509 {
 510   ASSERT (!IsListEmpty (Entry));
 511
 512   Entry->ForwardLink->BackLink = Entry->BackLink;
 513   Entry->BackLink->ForwardLink = Entry->ForwardLink;
 514   return Entry->ForwardLink;
 515 }