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 **/
  14
  15 //
  16 // Include common header file for this module.
  17 //
  18
  19
  20 #include "BaseLibInternals.h"
  21
  22 /**
  23   Worker function that locates the Node in the List
  24
  25   By searching the List, finds the location of the Node in List. At the same time,
  26   verifies the validity of this list.
  27
  28   If List is NULL, then ASSERT().
  29   If List->ForwardLink is NULL, then ASSERT().
  30   If List->backLink is NULL, then ASSERT().
  31   If Node is NULL, then ASSERT();
  32   If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
  33   of nodes in ListHead, including the ListHead node, is greater than or
  34   equal to PcdMaximumLinkedListLength, then ASSERT().
  35
  36   @param  List  A pointer to a node in a linked list.
  37   @param  Node  A pointer to one nod.
  38
  39   @retval TRUE   Node is in List
  40   @retval FALSE  Node isn't in List, or List is invalid
  41
  42 **/
  43 BOOLEAN
  44 IsNodeInList (
  45   IN      CONST LIST_ENTRY      *List,
  46   IN      CONST LIST_ENTRY      *Node
  47   )
  48 {
  49   UINTN                         Count;
  50   CONST LIST_ENTRY              *Ptr;
  51   BOOLEAN                       Found;
  52
  53   //
  54   // Test the validity of List and Node
  55   //
  56   ASSERT (List != NULL);
  57   ASSERT (List->ForwardLink != NULL);
  58   ASSERT (List->BackLink != NULL);
  59   ASSERT (Node != NULL);
  60
  61   Count = PcdGet32 (PcdMaximumLinkedListLength);
  62
  63   Ptr = List;
  64   do {
  65     Ptr = Ptr->ForwardLink;
  66     Count--;
  67   } while ((Ptr != List) && (Ptr != Node) && (Count > 0));
  68   Found = (BOOLEAN)(Ptr == Node);
  69
  70   if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
  71     while ((Count > 0) && (Ptr != List)) {
  72       Ptr = Ptr->ForwardLink;
  73       Count--;
  74     }
  75     ASSERT (Count > 0);
  76   }
  77
  78   return Found;
  79 }
  80
  81 /**
  82   Initializes the head node of a doubly linked list, and returns the pointer to
  83   the head node of the doubly linked list.
  84
  85   Initializes the forward and backward links of a new linked list. After
  86   initializing a linked list with this function, the other linked list
  87   functions may be used to add and remove nodes from the linked list. It is up
  88   to the caller of this function to allocate the memory for ListHead.
  89
  90   If ListHead is NULL, then ASSERT().
  91
  92   @param  ListHead  A pointer to the head node of a new doubly linked list.
  93
  94   @return ListHead
  95
  96 **/
  97 LIST_ENTRY *
  98 EFIAPI
  99 InitializeListHead (
 100   IN OUT  LIST_ENTRY            *List
 101   )
 102
 103 {
 104   ASSERT (List != NULL);
 105
 106   List->ForwardLink = List;
 107   List->BackLink = List;
 108   return List;
 109 }
 110
 111 /**
 112   Adds a node to the beginning of a doubly linked list, and returns the pointer
 113   to the head node of the doubly linked list.
 114
 115   Adds the node Entry at the beginning of the doubly linked list denoted by
 116   ListHead, and returns ListHead.
 117
 118   If ListHead is NULL, then ASSERT().
 119   If Entry is NULL, then ASSERT().
 120   If ListHead was not initialized with InitializeListHead(), then ASSERT().
 121   If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
 122   of nodes in ListHead, including the ListHead node, is greater than or
 123   equal to PcdMaximumLinkedListLength, then ASSERT().
 124
 125   @param  ListHead  A pointer to the head node of a doubly linked list.
 126   @param  Entry     A pointer to a node that is to be inserted at the beginning
 127                     of a doubly linked list.
 128
 129   @return ListHead
 130
 131 **/
 132 LIST_ENTRY *
 133 EFIAPI
 134 InsertHeadList (
 135   IN OUT  LIST_ENTRY            *List,
 136   IN OUT  LIST_ENTRY            *Entry
 137   )
 138 {
 139   //
 140   // ASSERT List not too long and Entry is not one of the nodes of List
 141   //
 142   ASSERT (!IsNodeInList (List, Entry));
 143
 144   Entry->ForwardLink = List->ForwardLink;
 145   Entry->BackLink = List;
 146   Entry->ForwardLink->BackLink = Entry;
 147   List->ForwardLink = Entry;
 148   return List;
 149 }
 150
 151 /**
 152   Adds a node to the end of a doubly linked list, and returns the pointer to
 153   the head node of the doubly linked list.
 154
 155   Adds the node Entry to the end of the doubly linked list denoted by ListHead,
 156   and returns ListHead.
 157
 158   If ListHead is NULL, then ASSERT().
 159   If Entry is NULL, then ASSERT().
 160   If ListHead was not initialized with InitializeListHead(), then ASSERT().
 161   If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
 162   of nodes in ListHead, including the ListHead node, is greater than or
 163   equal to PcdMaximumLinkedListLength, then ASSERT().
 164
 165   @param  ListHead  A pointer to the head node of a doubly linked list.
 166   @param  Entry     A pointer to a node that is to be added at the end of the
 167                     doubly linked list.
 168
 169   @return ListHead
 170
 171 **/
 172 LIST_ENTRY *
 173 EFIAPI
 174 InsertTailList (
 175   IN OUT  LIST_ENTRY            *List,
 176   IN OUT  LIST_ENTRY            *Entry
 177   )
 178 {
 179   //
 180   // ASSERT List not too long and Entry is not one of the nodes of List
 181   //
 182   ASSERT (!IsNodeInList (List, Entry));
 183
 184   Entry->ForwardLink = List;
 185   Entry->BackLink = List->BackLink;
 186   Entry->BackLink->ForwardLink = Entry;
 187   List->BackLink = Entry;
 188   return List;
 189 }
 190
 191 /**
 192   Retrieves the first node of a doubly linked list.
 193
 194   Returns the first node of a doubly linked list. List must have been
 195   initialized with InitializeListHead(). If List is empty, then NULL is
 196   returned.
 197
 198   If List is NULL, then ASSERT().
 199   If List was not initialized with InitializeListHead(), then ASSERT().
 200   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 201   in List, including the List node, is greater than or equal to
 202   PcdMaximumLinkedListLength, then ASSERT().
 203
 204   @param  List  A pointer to the head node of a doubly linked list.
 205
 206   @return The first node of a doubly linked list.
 207   @retval NULL  The list is empty.
 208
 209 **/
 210 LIST_ENTRY *
 211 EFIAPI
 212 GetFirstNode (
 213   IN CONST LIST_ENTRY  *List
 214   )
 215 {
 216   //
 217   // ASSERT List not too long
 218   //
 219   ASSERT (IsNodeInList (List, List));
 220
 221   return List->ForwardLink;
 222 }
 223
 224 /**
 225   Retrieves the next node of a doubly linked list.
 226
 227   Returns the node of a doubly linked list that follows Node. List must have
 228   been initialized with InitializeListHead(). If List is empty, then List is
 229   returned.
 230
 231   If List is NULL, then ASSERT().
 232   If Node is NULL, then ASSERT().
 233   If List was not initialized with 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 (IsNodeInList (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 InitializeListHead(), then ASSERT().
 268   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 269   in List, including the List node, is greater than or equal to
 270   PcdMaximumLinkedListLength, then ASSERT().
 271
 272   @param  ListHead  A pointer to the head node of a doubly linked list.
 273
 274   @retval TRUE  The linked list is empty.
 275   @retval FALSE The linked list is not empty.
 276
 277 **/
 278 BOOLEAN
 279 EFIAPI
 280 IsListEmpty (
 281   IN      CONST LIST_ENTRY      *List
 282   )
 283 {
 284   //
 285   // ASSERT List not too long
 286   //
 287   ASSERT (IsNodeInList (List, List));
 288
 289   return (BOOLEAN)(List->ForwardLink == List);
 290 }
 291
 292 /**
 293   Determines if a node in a doubly linked list is null.
 294
 295   Returns FALSE if Node is one of the nodes in the doubly linked list specified
 296   by List. Otherwise, TRUE is returned. List must have been initialized with
 297   InitializeListHead().
 298
 299   If List is NULL, then ASSERT().
 300   If Node is NULL, then ASSERT().
 301   If List was not initialized with InitializeListHead(), then ASSERT().
 302   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 303   in List, including the List node, is greater than or equal to
 304   PcdMaximumLinkedListLength, then ASSERT().
 305   If Node is not a node in List and Node is not equal to List, then ASSERT().
 306
 307   @param  List  A pointer to the head node of a doubly linked list.
 308   @param  Node  A pointer to a node in the doubly linked list.
 309
 310   @retval TRUE  Node is one of the nodes in the doubly linked list.
 311   @retval FALSE Node is not one of the nodes in the doubly linked list.
 312
 313 **/
 314 BOOLEAN
 315 EFIAPI
 316 IsNull (
 317   IN      CONST LIST_ENTRY      *List,
 318   IN      CONST LIST_ENTRY      *Node
 319   )
 320 {
 321   //
 322   // ASSERT List not too long and Node is one of the nodes of List
 323   //
 324   ASSERT (IsNodeInList (List, Node));
 325
 326   return (BOOLEAN)(Node == List);
 327 }
 328
 329 /**
 330   Determines if a node the last node in a doubly linked list.
 331
 332   Returns TRUE if Node is the last node in the doubly linked list specified by
 333   List. Otherwise, FALSE is returned. List must have been initialized with
 334   InitializeListHead().
 335
 336   If List is NULL, then ASSERT().
 337   If Node is NULL, then ASSERT().
 338   If List was not initialized with InitializeListHead(), then ASSERT().
 339   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 340   in List, including the List node, is greater than or equal to
 341   PcdMaximumLinkedListLength, then ASSERT().
 342   If Node is not a node in List, then ASSERT().
 343
 344   @param  List  A pointer to the head node of a doubly linked list.
 345   @param  Node  A pointer to a node in the doubly linked list.
 346
 347   @retval TRUE  Node is the last node in the linked list.
 348   @retval FALSE Node is not the last node in the linked list.
 349
 350 **/
 351 BOOLEAN
 352 EFIAPI
 353 IsNodeAtEnd (
 354   IN      CONST LIST_ENTRY      *List,
 355   IN      CONST LIST_ENTRY      *Node
 356   )
 357 {
 358   //
 359   // ASSERT List not too long and Node is one of the nodes of List
 360   //
 361   ASSERT (IsNodeInList (List, Node));
 362
 363   return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
 364 }
 365
 366 /**
 367   Swaps the location of two nodes in a doubly linked list, and returns the
 368   first node after the swap.
 369
 370   If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
 371   Otherwise, the location of the FirstEntry node is swapped with the location
 372   of the SecondEntry node in a doubly linked list. SecondEntry must be in the
 373   same double linked list as FirstEntry and that double linked list must have
 374   been initialized with InitializeListHead(). SecondEntry is returned after the
 375   nodes are swapped.
 376
 377   If FirstEntry is NULL, then ASSERT().
 378   If SecondEntry is NULL, then ASSERT().
 379   If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
 380   If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
 381   linked list containing the FirstEntry and SecondEntry nodes, including
 382   the FirstEntry and SecondEntry nodes, is greater than or equal to
 383   PcdMaximumLinkedListLength, then ASSERT().
 384
 385   @param  FirstEntry  A pointer to a node in a linked list.
 386   @param  SecondEntry A pointer to another node in the same linked list.
 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 willl 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 Entry
 455
 456 **/
 457 LIST_ENTRY *
 458 EFIAPI
 459 RemoveEntryList (
 460   IN      CONST LIST_ENTRY      *Entry
 461   )
 462 {
 463   ASSERT (!IsListEmpty (Entry));
 464
 465   Entry->ForwardLink->BackLink = Entry->BackLink;
 466   Entry->BackLink->ForwardLink = Entry->ForwardLink;
 467   return Entry->ForwardLink;
 468 }