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 PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
  28   of nodes in ListHead, including the ListHead node, is greater than or
  29   equal to PcdMaximumLinkedListLength, then ASSERT().
  30
  31   @param  List  A pointer to a node in a linked list.
  32   @param  Node  A pointer to one nod.
  33
  34   @retval TRUE   Node is in List
  35   @retval FALSE  Node isn't in List, or List is invalid
  36
  37 **/
  38 BOOLEAN
  39 EFIAPI
  40 InternalBaseLibIsNodeInList (
  41   IN      CONST LIST_ENTRY      *List,
  42   IN      CONST LIST_ENTRY      *Node
  43   )
  44 {
  45   UINTN                         Count;
  46   CONST LIST_ENTRY              *Ptr;
  47   BOOLEAN                       Found;
  48
  49   //
  50   // Test the validity of List and Node
  51   //
  52   ASSERT (List != NULL);
  53   ASSERT (List->ForwardLink != NULL);
  54   ASSERT (List->BackLink != NULL);
  55   ASSERT (Node != NULL);
  56
  57   Count = PcdGet32 (PcdMaximumLinkedListLength);
  58
  59   Ptr = List;
  60   do {
  61     Ptr = Ptr->ForwardLink;
  62     Count--;
  63   } while ((Ptr != List) && (Ptr != Node) && (Count > 0));
  64   Found = (BOOLEAN)(Ptr == Node);
  65
  66   if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
  67     while ((Count > 0) && (Ptr != List)) {
  68       Ptr = Ptr->ForwardLink;
  69       Count--;
  70     }
  71     ASSERT (Count > 0);
  72   }
  73
  74   return Found;
  75 }
  76
  77 /**
  78   Initializes the head node of a doubly linked list, and returns the pointer to
  79   the head node of the doubly linked list.
  80
  81   Initializes the forward and backward links of a new linked list. After
  82   initializing a linked list with this function, the other linked list
  83   functions may be used to add and remove nodes from the linked list. It is up
  84   to the caller of this function to allocate the memory for ListHead.
  85
  86   If ListHead is NULL, then ASSERT().
  87
  88   @param  ListHead  A pointer to the head node of a new doubly linked list.
  89
  90   @return ListHead
  91
  92 **/
  93 LIST_ENTRY *
  94 EFIAPI
  95 InitializeListHead (
  96   IN OUT  LIST_ENTRY                *ListHead
  97   )
  98
  99 {
 100   ASSERT (ListHead != NULL);
 101
 102   ListHead->ForwardLink = ListHead;
 103   ListHead->BackLink = ListHead;
 104   return ListHead;
 105 }
 106
 107 /**
 108   Adds a node to the beginning of a doubly linked list, and returns the pointer
 109   to the head node of the doubly linked list.
 110
 111   Adds the node Entry at the beginning of the doubly linked list denoted by
 112   ListHead, and returns ListHead.
 113
 114   If ListHead is NULL, then ASSERT().
 115   If Entry is NULL, then ASSERT().
 116   If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
 117   InitializeListHead(), then ASSERT().
 118   If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
 119   of nodes in ListHead, including the ListHead node, is greater than or
 120   equal to PcdMaximumLinkedListLength, then ASSERT().
 121
 122   @param  ListHead  A pointer to the head node of a doubly linked list.
 123   @param  Entry     A pointer to a node that is to be inserted at the beginning
 124                     of a doubly linked list.
 125
 126   @return ListHead
 127
 128 **/
 129 LIST_ENTRY *
 130 EFIAPI
 131 InsertHeadList (
 132   IN OUT  LIST_ENTRY                *ListHead,
 133   IN OUT  LIST_ENTRY                *Entry
 134   )
 135 {
 136   //
 137   // ASSERT List not too long and Entry is not one of the nodes of List
 138   //
 139   ASSERT (!InternalBaseLibIsNodeInList (ListHead, Entry));
 140
 141   Entry->ForwardLink = ListHead->ForwardLink;
 142   Entry->BackLink = ListHead;
 143   Entry->ForwardLink->BackLink = Entry;
 144   ListHead->ForwardLink = Entry;
 145   return ListHead;
 146 }
 147
 148 /**
 149   Adds a node to the end of a doubly linked list, and returns the pointer to
 150   the head node of the doubly linked list.
 151
 152   Adds the node Entry to the end of the doubly linked list denoted by ListHead,
 153   and returns ListHead.
 154
 155   If ListHead is NULL, then ASSERT().
 156   If Entry is NULL, then ASSERT().
 157   If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
 158   InitializeListHead(), then ASSERT().
 159   If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
 160   of nodes in ListHead, including the ListHead node, is greater than or
 161   equal to PcdMaximumLinkedListLength, then ASSERT().
 162
 163   @param  ListHead  A pointer to the head node of a doubly linked list.
 164   @param  Entry     A pointer to a node that is to be added at the end of the
 165                     doubly linked list.
 166
 167   @return ListHead
 168
 169 **/
 170 LIST_ENTRY *
 171 EFIAPI
 172 InsertTailList (
 173   IN OUT  LIST_ENTRY                *ListHead,
 174   IN OUT  LIST_ENTRY                *Entry
 175   )
 176 {
 177   //
 178   // ASSERT List not too long and Entry is not one of the nodes of List
 179   //
 180   ASSERT (!InternalBaseLibIsNodeInList (ListHead, Entry));
 181
 182   Entry->ForwardLink = ListHead;
 183   Entry->BackLink = ListHead->BackLink;
 184   Entry->BackLink->ForwardLink = Entry;
 185   ListHead->BackLink = Entry;
 186   return ListHead;
 187 }
 188
 189 /**
 190   Retrieves the first node of a doubly linked list.
 191
 192   Returns the first node of a doubly linked list.  List must have been
 193   initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
 194   If List is empty, then List is returned.
 195
 196   If List is NULL, then ASSERT().
 197   If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
 198   InitializeListHead(), then ASSERT().
 199   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 200   in List, including the List node, is greater than or equal to
 201   PcdMaximumLinkedListLength, then ASSERT().
 202
 203   @param  List  A pointer to the head node of a doubly linked list.
 204
 205   @return The first node of a doubly linked list.
 206   @retval NULL  The list is empty.
 207
 208 **/
 209 LIST_ENTRY *
 210 EFIAPI
 211 GetFirstNode (
 212   IN      CONST LIST_ENTRY          *List
 213   )
 214 {
 215   //
 216   // ASSERT List not too long
 217   //
 218   ASSERT (InternalBaseLibIsNodeInList (List, List));
 219
 220   return List->ForwardLink;
 221 }
 222
 223 /**
 224   Retrieves the next node of a doubly linked list.
 225
 226   Returns the node of a doubly linked list that follows Node.
 227   List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()
 228   or InitializeListHead().  If List is empty, then List is returned.
 229
 230   If List is NULL, then ASSERT().
 231   If Node is NULL, then ASSERT().
 232   If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
 233   InitializeListHead(), then ASSERT().
 234   If PcdMaximumLinkedListLenth is not zero, and List contains more than
 235   PcdMaximumLinkedListLenth nodes, then ASSERT().
 236   If Node is not a node in List, then ASSERT().
 237
 238   @param  List  A pointer to the head node of a doubly linked list.
 239   @param  Node  A pointer to a node in the doubly linked list.
 240
 241   @return Pointer to the next node if one exists. Otherwise a null value which
 242           is actually List is returned.
 243
 244 **/
 245 LIST_ENTRY *
 246 EFIAPI
 247 GetNextNode (
 248   IN      CONST LIST_ENTRY          *List,
 249   IN      CONST LIST_ENTRY          *Node
 250   )
 251 {
 252   //
 253   // ASSERT List not too long and Node is one of the nodes of List
 254   //
 255   ASSERT (InternalBaseLibIsNodeInList (List, Node));
 256
 257   return Node->ForwardLink;
 258 }
 259
 260 /**
 261   Checks to see if a doubly linked list is empty or not.
 262
 263   Checks to see if the doubly linked list is empty. If the linked list contains
 264   zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
 265
 266   If ListHead is NULL, then ASSERT().
 267   If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
 268   InitializeListHead(), then ASSERT().
 269   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 270   in List, including the List node, is greater than or equal to
 271   PcdMaximumLinkedListLength, then ASSERT().
 272
 273   @param  ListHead  A pointer to the head node of a doubly linked list.
 274
 275   @retval TRUE  The linked list is empty.
 276   @retval FALSE The linked list is not empty.
 277
 278 **/
 279 BOOLEAN
 280 EFIAPI
 281 IsListEmpty (
 282   IN      CONST LIST_ENTRY          *ListHead
 283   )
 284 {
 285   //
 286   // ASSERT List not too long
 287   //
 288   ASSERT (InternalBaseLibIsNodeInList (ListHead, ListHead));
 289
 290   return (BOOLEAN)(ListHead->ForwardLink == ListHead);
 291 }
 292
 293 /**
 294   Determines if a node in a doubly linked list is the head node of a the same
 295   doubly linked list.  This function is typically used to terminate a loop that
 296   traverses all the nodes in a doubly linked list starting with the head node.
 297
 298   Returns TRUE if Node is equal to List.  Returns FALSE if Node is one of the
 299   nodes in the doubly linked list specified by List.  List must have been
 300   initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
 301
 302   If List is NULL, then ASSERT().
 303   If Node is NULL, then ASSERT().
 304   If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(),
 305   then ASSERT().
 306   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 307   in List, including the List node, is greater than or equal to
 308   PcdMaximumLinkedListLength, then ASSERT().
 309   If Node is not a node in List and Node is not equal to List, then ASSERT().
 310
 311   @param  List  A pointer to the head node of a doubly linked list.
 312   @param  Node  A pointer to a node in the doubly linked list.
 313
 314   @retval TRUE  Node is one of the nodes in the doubly linked list.
 315   @retval FALSE Node is not one of the nodes in the doubly linked list.
 316
 317 **/
 318 BOOLEAN
 319 EFIAPI
 320 IsNull (
 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));
 329
 330   return (BOOLEAN)(Node == List);
 331 }
 332
 333 /**
 334   Determines if a node the last node in a doubly linked list.
 335
 336   Returns TRUE if Node is the last node in the doubly linked list specified by
 337   List. Otherwise, FALSE is returned. List must have been initialized with
 338   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
 343   InitializeListHead(), 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 Node is not a node in List, then ASSERT().
 348
 349   @param  List  A pointer to the head node of a doubly linked list.
 350   @param  Node  A pointer to a node in the doubly linked list.
 351
 352   @retval TRUE  Node is the last node in the linked list.
 353   @retval FALSE Node is not the last node in the linked list.
 354
 355 **/
 356 BOOLEAN
 357 EFIAPI
 358 IsNodeAtEnd (
 359   IN      CONST LIST_ENTRY          *List,
 360   IN      CONST LIST_ENTRY          *Node
 361   )
 362 {
 363   //
 364   // ASSERT List not too long and Node is one of the nodes of List
 365   //
 366   ASSERT (InternalBaseLibIsNodeInList (List, Node));
 367
 368   return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
 369 }
 370
 371 /**
 372   Swaps the location of two nodes in a doubly linked list, and returns the
 373   first node after the swap.
 374
 375   If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
 376   Otherwise, the location of the FirstEntry node is swapped with the location
 377   of the SecondEntry node in a doubly linked list. SecondEntry must be in the
 378   same double linked list as FirstEntry and that double linked list must have
 379   been initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
 380   SecondEntry is returned after the nodes are swapped.
 381
 382   If FirstEntry is NULL, then ASSERT().
 383   If SecondEntry is NULL, then ASSERT().
 384   If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
 385   If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
 386   linked list containing the FirstEntry and SecondEntry nodes, including
 387   the FirstEntry and SecondEntry nodes, is greater than or equal to
 388   PcdMaximumLinkedListLength, then ASSERT().
 389
 390   @param  FirstEntry  A pointer to a node in a linked list.
 391   @param  SecondEntry A pointer to another node in the same linked list.
 392
 393   @return SecondEntry.
 394
 395 **/
 396 LIST_ENTRY *
 397 EFIAPI
 398 SwapListEntries (
 399   IN OUT  LIST_ENTRY                *FirstEntry,
 400   IN OUT  LIST_ENTRY                *SecondEntry
 401   )
 402 {
 403   LIST_ENTRY                    *Ptr;
 404
 405   if (FirstEntry == SecondEntry) {
 406     return SecondEntry;
 407   }
 408
 409   //
 410   // ASSERT Entry1 and Entry2 are in the same linked list
 411   //
 412   ASSERT (InternalBaseLibIsNodeInList (FirstEntry, SecondEntry));
 413
 414   //
 415   // Ptr is the node pointed to by FirstEntry->ForwardLink
 416   //
 417   Ptr = RemoveEntryList (FirstEntry);
 418
 419   //
 420   // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
 421   // immediately in front of SecondEntry
 422   //
 423   if (Ptr->BackLink == SecondEntry) {
 424     return InsertTailList (SecondEntry, FirstEntry);
 425   }
 426
 427   //
 428   // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
 429   // then there are no further steps necessary
 430   //
 431   if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
 432     return Ptr;
 433   }
 434
 435   //
 436   // Move SecondEntry to the front of Ptr
 437   //
 438   RemoveEntryList (SecondEntry);
 439   InsertTailList (Ptr, SecondEntry);
 440   return SecondEntry;
 441 }
 442
 443 /**
 444   Removes a node from a doubly linked list, and returns the node that follows
 445   the removed node.
 446
 447   Removes the node Entry from a doubly linked list. It is up to the caller of
 448   this function to release the memory used by this node if that is required. On
 449   exit, the node following Entry in the doubly linked list is returned. If
 450   Entry is the only node in the linked list, then the head node of the linked
 451   list is returned.
 452
 453   If Entry is NULL, then ASSERT().
 454   If Entry is the head node of an empty list, then ASSERT().
 455   If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
 456   linked list containing Entry, including the Entry node, is greater than
 457   or equal to PcdMaximumLinkedListLength, then ASSERT().
 458
 459   @param  Entry A pointer to a node in a linked list.
 460
 461   @return Entry.
 462
 463 **/
 464 LIST_ENTRY *
 465 EFIAPI
 466 RemoveEntryList (
 467   IN      CONST LIST_ENTRY          *Entry
 468   )
 469 {
 470   ASSERT (!IsListEmpty (Entry));
 471
 472   Entry->ForwardLink->BackLink = Entry->BackLink;
 473   Entry->BackLink->ForwardLink = Entry->ForwardLink;
 474   return Entry->ForwardLink;
 475 }