MdePkg/Library/BaseLib/LinkedList.c

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