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