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 IsNodeInList (
  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  List  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            *List
  97   )
  98
  99 {
 100   ASSERT (List != NULL);
 101
 102   List->ForwardLink = List;
 103   List->BackLink = List;
 104   return List;
 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 InitializeListHead(), then ASSERT().
 117   If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
 118   of nodes in ListHead, including the ListHead node, is greater than or
 119   equal to PcdMaximumLinkedListLength, then ASSERT().
 120
 121   @param  List      A pointer to the head node of a doubly linked list.
 122   @param  Entry     A pointer to a node that is to be inserted at the beginning
 123                     of a doubly linked list.
 124
 125   @return ListHead
 126
 127 **/
 128 LIST_ENTRY *
 129 EFIAPI
 130 InsertHeadList (
 131   IN OUT  LIST_ENTRY            *List,
 132   IN OUT  LIST_ENTRY            *Entry
 133   )
 134 {
 135   //
 136   // ASSERT List not too long and Entry is not one of the nodes of List
 137   //
 138   ASSERT (!IsNodeInList (List, Entry));
 139
 140   Entry->ForwardLink = List->ForwardLink;
 141   Entry->BackLink = List;
 142   Entry->ForwardLink->BackLink = Entry;
 143   List->ForwardLink = Entry;
 144   return List;
 145 }
 146
 147 /**
 148   Adds a node to the end of a doubly linked list, and returns the pointer to
 149   the head node of the doubly linked list.
 150
 151   Adds the node Entry to the end of the doubly linked list denoted by ListHead,
 152   and returns ListHead.
 153
 154   If ListHead is NULL, then ASSERT().
 155   If Entry is NULL, then ASSERT().
 156   If ListHead was not initialized with InitializeListHead(), then ASSERT().
 157   If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
 158   of nodes in ListHead, including the ListHead node, is greater than or
 159   equal to PcdMaximumLinkedListLength, then ASSERT().
 160
 161   @param  List      A pointer to the head node of a doubly linked list.
 162   @param  Entry     A pointer to a node that is to be added at the end of the
 163                     doubly linked list.
 164
 165   @return ListHead
 166
 167 **/
 168 LIST_ENTRY *
 169 EFIAPI
 170 InsertTailList (
 171   IN OUT  LIST_ENTRY            *List,
 172   IN OUT  LIST_ENTRY            *Entry
 173   )
 174 {
 175   //
 176   // ASSERT List not too long and Entry is not one of the nodes of List
 177   //
 178   ASSERT (!IsNodeInList (List, Entry));
 179
 180   Entry->ForwardLink = List;
 181   Entry->BackLink = List->BackLink;
 182   Entry->BackLink->ForwardLink = Entry;
 183   List->BackLink = Entry;
 184   return List;
 185 }
 186
 187 /**
 188   Retrieves the first node of a doubly linked list.
 189
 190   Returns the first node of a doubly linked list. List must have been
 191   initialized with InitializeListHead(). If List is empty, then NULL is
 192   returned.
 193
 194   If List is NULL, then ASSERT().
 195   If List was not initialized with InitializeListHead(), then ASSERT().
 196   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 197   in List, including the List node, is greater than or equal to
 198   PcdMaximumLinkedListLength, then ASSERT().
 199
 200   @param  List  A pointer to the head node of a doubly linked list.
 201
 202   @return The first node of a doubly linked list.
 203   @retval NULL  The list is empty.
 204
 205 **/
 206 LIST_ENTRY *
 207 EFIAPI
 208 GetFirstNode (
 209   IN CONST LIST_ENTRY  *List
 210   )
 211 {
 212   //
 213   // ASSERT List not too long
 214   //
 215   ASSERT (IsNodeInList (List, List));
 216
 217   return List->ForwardLink;
 218 }
 219
 220 /**
 221   Retrieves the next node of a doubly linked list.
 222
 223   Returns the node of a doubly linked list that follows Node. List must have
 224   been initialized with InitializeListHead(). If List is empty, then List is
 225   returned.
 226
 227   If List is NULL, then ASSERT().
 228   If Node is NULL, then ASSERT().
 229   If List was not initialized with InitializeListHead(), then ASSERT().
 230   If PcdMaximumLinkedListLenth is not zero, and List contains more than
 231   PcdMaximumLinkedListLenth nodes, then ASSERT().
 232   If Node is not a node in List, then ASSERT().
 233
 234   @param  List  A pointer to the head node of a doubly linked list.
 235   @param  Node  A pointer to a node in the doubly linked list.
 236
 237   @return Pointer to the next node if one exists. Otherwise a null value which
 238           is actually List is returned.
 239
 240 **/
 241 LIST_ENTRY *
 242 EFIAPI
 243 GetNextNode (
 244   IN CONST LIST_ENTRY  *List,
 245   IN CONST LIST_ENTRY  *Node
 246   )
 247 {
 248   //
 249   // ASSERT List not too long and Node is one of the nodes of List
 250   //
 251   ASSERT (IsNodeInList (List, Node));
 252
 253   return Node->ForwardLink;
 254 }
 255
 256 /**
 257   Checks to see if a doubly linked list is empty or not.
 258
 259   Checks to see if the doubly linked list is empty. If the linked list contains
 260   zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
 261
 262   If ListHead is NULL, then ASSERT().
 263   If ListHead was not initialized with InitializeListHead(), then ASSERT().
 264   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 265   in List, including the List node, is greater than or equal to
 266   PcdMaximumLinkedListLength, then ASSERT().
 267
 268   @param  List  A pointer to the head node of a doubly linked list.
 269
 270   @retval TRUE  The linked list is empty.
 271   @retval FALSE The linked list is not empty.
 272
 273 **/
 274 BOOLEAN
 275 EFIAPI
 276 IsListEmpty (
 277   IN      CONST LIST_ENTRY      *List
 278   )
 279 {
 280   //
 281   // ASSERT List not too long
 282   //
 283   ASSERT (IsNodeInList (List, List));
 284
 285   return (BOOLEAN)(List->ForwardLink == List);
 286 }
 287
 288 /**
 289   Determines if a node in a doubly linked list is the head node of a the same
 290   doubly linked list.  This function is typically used to terminate a loop that
 291   traverses all the nodes in a doubly linked list starting with the head node.
 292
 293   Returns TRUE if Node is equal to List.  Returns FALSE if Node is one of the
 294   nodes in the doubly linked list specified by List.  List must have been
 295   initialized with InitializeListHead().
 296
 297   If List is NULL, then ASSERT().
 298   If Node is NULL, then ASSERT().
 299   If List was not initialized with InitializeListHead(), then ASSERT().
 300   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 301   in List, including the List node, is greater than or equal to
 302   PcdMaximumLinkedListLength, then ASSERT().
 303   If Node is not a node in List and Node is not equal to List, then ASSERT().
 304
 305   @param  List  A pointer to the head node of a doubly linked list.
 306   @param  Node  A pointer to a node in the doubly linked list.
 307
 308   @retval TRUE  Node is one of the nodes in the doubly linked list.
 309   @retval FALSE Node is not one of the nodes in the doubly linked list.
 310
 311 **/
 312 BOOLEAN
 313 EFIAPI
 314 IsNull (
 315   IN      CONST LIST_ENTRY      *List,
 316   IN      CONST LIST_ENTRY      *Node
 317   )
 318 {
 319   //
 320   // ASSERT List not too long and Node is one of the nodes of List
 321   //
 322   ASSERT (IsNodeInList (List, Node));
 323
 324   return (BOOLEAN)(Node == List);
 325 }
 326
 327 /**
 328   Determines if a node the last node in a doubly linked list.
 329
 330   Returns TRUE if Node is the last node in the doubly linked list specified by
 331   List. Otherwise, FALSE is returned. List must have been initialized with
 332   InitializeListHead().
 333
 334   If List is NULL, then ASSERT().
 335   If Node is NULL, then ASSERT().
 336   If List was not initialized with InitializeListHead(), then ASSERT().
 337   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 338   in List, including the List node, is greater than or equal to
 339   PcdMaximumLinkedListLength, then ASSERT().
 340   If Node is not a node in List, then ASSERT().
 341
 342   @param  List  A pointer to the head node of a doubly linked list.
 343   @param  Node  A pointer to a node in the doubly linked list.
 344
 345   @retval TRUE  Node is the last node in the linked list.
 346   @retval FALSE Node is not the last node in the linked list.
 347
 348 **/
 349 BOOLEAN
 350 EFIAPI
 351 IsNodeAtEnd (
 352   IN      CONST LIST_ENTRY      *List,
 353   IN      CONST LIST_ENTRY      *Node
 354   )
 355 {
 356   //
 357   // ASSERT List not too long and Node is one of the nodes of List
 358   //
 359   ASSERT (IsNodeInList (List, Node));
 360
 361   return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
 362 }
 363
 364 /**
 365   Swaps the location of two nodes in a doubly linked list, and returns the
 366   first node after the swap.
 367
 368   If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
 369   Otherwise, the location of the FirstEntry node is swapped with the location
 370   of the SecondEntry node in a doubly linked list. SecondEntry must be in the
 371   same double linked list as FirstEntry and that double linked list must have
 372   been initialized with InitializeListHead(). SecondEntry is returned after the
 373   nodes are swapped.
 374
 375   If FirstEntry is NULL, then ASSERT().
 376   If SecondEntry is NULL, then ASSERT().
 377   If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
 378   If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
 379   linked list containing the FirstEntry and SecondEntry nodes, including
 380   the FirstEntry and SecondEntry nodes, is greater than or equal to
 381   PcdMaximumLinkedListLength, then ASSERT().
 382
 383   @param  FirstEntry  A pointer to a node in a linked list.
 384   @param  SecondEntry A pointer to another node in the same linked list.
 385
 386   @return SecondEntry after the nodes are swapped
 387
 388 **/
 389 LIST_ENTRY *
 390 EFIAPI
 391 SwapListEntries (
 392   IN OUT  LIST_ENTRY            *FirstEntry,
 393   IN OUT  LIST_ENTRY            *SecondEntry
 394   )
 395 {
 396   LIST_ENTRY                    *Ptr;
 397
 398   if (FirstEntry == SecondEntry) {
 399     return SecondEntry;
 400   }
 401
 402   //
 403   // ASSERT Entry1 and Entry2 are in the same linked list
 404   //
 405   ASSERT (IsNodeInList (FirstEntry, SecondEntry));
 406
 407   //
 408   // Ptr is the node pointed to by FirstEntry->ForwardLink
 409   //
 410   Ptr = RemoveEntryList (FirstEntry);
 411
 412   //
 413   // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
 414   // immediately in front of SecondEntry
 415   //
 416   if (Ptr->BackLink == SecondEntry) {
 417     return InsertTailList (SecondEntry, FirstEntry);
 418   }
 419
 420   //
 421   // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
 422   // then there are no further steps necessary
 423   //
 424   if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
 425     return Ptr;
 426   }
 427
 428   //
 429   // Move SecondEntry to the front of Ptr
 430   //
 431   RemoveEntryList (SecondEntry);
 432   InsertTailList (Ptr, SecondEntry);
 433   return SecondEntry;
 434 }
 435
 436 /**
 437   Removes a node from a doubly linked list, and returns the node that follows
 438   the removed node.
 439
 440   Removes the node Entry from a doubly linked list. It is up to the caller of
 441   this function to release the memory used by this node if that is required. On
 442   exit, the node following Entry in the doubly linked list is returned. If
 443   Entry is the only node in the linked list, then the head node of the linked
 444   list is returned.
 445
 446   If Entry is NULL, then ASSERT().
 447   If Entry is the head node of an empty list, then ASSERT().
 448   If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
 449   linked list containing Entry, including the Entry node, is greater than
 450   or equal to PcdMaximumLinkedListLength, then ASSERT().
 451
 452   @param  Entry A pointer to a node in a linked list
 453
 454   @return The node following Entry in the doubly linked list.
 455           If Entry is the only node in the linked list, then
 456           the head node of the linked list is returned.
 457
 458 **/
 459 LIST_ENTRY *
 460 EFIAPI
 461 RemoveEntryList (
 462   IN      CONST LIST_ENTRY      *Entry
 463   )
 464 {
 465   ASSERT (!IsListEmpty (Entry));
 466
 467   Entry->ForwardLink->BackLink = Entry->BackLink;
 468   Entry->BackLink->ForwardLink = Entry->ForwardLink;
 469   return Entry->ForwardLink;
 470 }