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 EFIAPI
  45 IsNodeInList (
  46   IN      CONST LIST_ENTRY      *List,
  47   IN      CONST LIST_ENTRY      *Node
  48   )
  49 {
  50   UINTN                         Count;
  51   CONST LIST_ENTRY              *Ptr;
  52   BOOLEAN                       Found;
  53
  54   //
  55   // Test the validity of List and Node
  56   //
  57   ASSERT (List != NULL);
  58   ASSERT (List->ForwardLink != NULL);
  59   ASSERT (List->BackLink != NULL);
  60   ASSERT (Node != NULL);
  61
  62   Count = PcdGet32 (PcdMaximumLinkedListLength);
  63
  64   Ptr = List;
  65   do {
  66     Ptr = Ptr->ForwardLink;
  67     Count--;
  68   } while ((Ptr != List) && (Ptr != Node) && (Count > 0));
  69   Found = (BOOLEAN)(Ptr == Node);
  70
  71   if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
  72     while ((Count > 0) && (Ptr != List)) {
  73       Ptr = Ptr->ForwardLink;
  74       Count--;
  75     }
  76     ASSERT (Count > 0);
  77   }
  78
  79   return Found;
  80 }
  81
  82 /**
  83   Initializes the head node of a doubly linked list, and returns the pointer to
  84   the head node of the doubly linked list.
  85
  86   Initializes the forward and backward links of a new linked list. After
  87   initializing a linked list with this function, the other linked list
  88   functions may be used to add and remove nodes from the linked list. It is up
  89   to the caller of this function to allocate the memory for ListHead.
  90
  91   If ListHead is NULL, then ASSERT().
  92
  93   @param  List  A pointer to the head node of a new doubly linked list.
  94
  95   @return ListHead
  96
  97 **/
  98 LIST_ENTRY *
  99 EFIAPI
 100 InitializeListHead (
 101   IN OUT  LIST_ENTRY            *List
 102   )
 103
 104 {
 105   ASSERT (List != NULL);
 106
 107   List->ForwardLink = List;
 108   List->BackLink = List;
 109   return List;
 110 }
 111
 112 /**
 113   Adds a node to the beginning of a doubly linked list, and returns the pointer
 114   to the head node of the doubly linked list.
 115
 116   Adds the node Entry at the beginning of the doubly linked list denoted by
 117   ListHead, and returns ListHead.
 118
 119   If ListHead is NULL, then ASSERT().
 120   If Entry is NULL, then ASSERT().
 121   If ListHead was not initialized with InitializeListHead(), then ASSERT().
 122   If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
 123   of nodes in ListHead, including the ListHead node, is greater than or
 124   equal to PcdMaximumLinkedListLength, then ASSERT().
 125
 126   @param  List      A pointer to the head node of a doubly linked list.
 127   @param  Entry     A pointer to a node that is to be inserted at the beginning
 128                     of a doubly linked list.
 129
 130   @return ListHead
 131
 132 **/
 133 LIST_ENTRY *
 134 EFIAPI
 135 InsertHeadList (
 136   IN OUT  LIST_ENTRY            *List,
 137   IN OUT  LIST_ENTRY            *Entry
 138   )
 139 {
 140   //
 141   // ASSERT List not too long and Entry is not one of the nodes of List
 142   //
 143   ASSERT (!IsNodeInList (List, Entry));
 144
 145   Entry->ForwardLink = List->ForwardLink;
 146   Entry->BackLink = List;
 147   Entry->ForwardLink->BackLink = Entry;
 148   List->ForwardLink = Entry;
 149   return List;
 150 }
 151
 152 /**
 153   Adds a node to the end of a doubly linked list, and returns the pointer to
 154   the head node of the doubly linked list.
 155
 156   Adds the node Entry to the end of the doubly linked list denoted by ListHead,
 157   and returns ListHead.
 158
 159   If ListHead is NULL, then ASSERT().
 160   If Entry is NULL, then ASSERT().
 161   If ListHead was not initialized with InitializeListHead(), then ASSERT().
 162   If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
 163   of nodes in ListHead, including the ListHead node, is greater than or
 164   equal to PcdMaximumLinkedListLength, then ASSERT().
 165
 166   @param  List      A pointer to the head node of a doubly linked list.
 167   @param  Entry     A pointer to a node that is to be added at the end of the
 168                     doubly linked list.
 169
 170   @return ListHead
 171
 172 **/
 173 LIST_ENTRY *
 174 EFIAPI
 175 InsertTailList (
 176   IN OUT  LIST_ENTRY            *List,
 177   IN OUT  LIST_ENTRY            *Entry
 178   )
 179 {
 180   //
 181   // ASSERT List not too long and Entry is not one of the nodes of List
 182   //
 183   ASSERT (!IsNodeInList (List, Entry));
 184
 185   Entry->ForwardLink = List;
 186   Entry->BackLink = List->BackLink;
 187   Entry->BackLink->ForwardLink = Entry;
 188   List->BackLink = Entry;
 189   return List;
 190 }
 191
 192 /**
 193   Retrieves the first node of a doubly linked list.
 194
 195   Returns the first node of a doubly linked list. List must have been
 196   initialized with InitializeListHead(). If List is empty, then NULL is
 197   returned.
 198
 199   If List is NULL, then ASSERT().
 200   If List was not initialized with InitializeListHead(), then ASSERT().
 201   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 202   in List, including the List node, is greater than or equal to
 203   PcdMaximumLinkedListLength, then ASSERT().
 204
 205   @param  List  A pointer to the head node of a doubly linked list.
 206
 207   @return The first node of a doubly linked list.
 208   @retval NULL  The list is empty.
 209
 210 **/
 211 LIST_ENTRY *
 212 EFIAPI
 213 GetFirstNode (
 214   IN CONST LIST_ENTRY  *List
 215   )
 216 {
 217   //
 218   // ASSERT List not too long
 219   //
 220   ASSERT (IsNodeInList (List, List));
 221
 222   return List->ForwardLink;
 223 }
 224
 225 /**
 226   Retrieves the next node of a doubly linked list.
 227
 228   Returns the node of a doubly linked list that follows Node. List must have
 229   been initialized with InitializeListHead(). If List is empty, then List is
 230   returned.
 231
 232   If List is NULL, then ASSERT().
 233   If Node is NULL, then ASSERT().
 234   If List was not initialized with InitializeListHead(), then ASSERT().
 235   If PcdMaximumLinkedListLenth is not zero, and List contains more than
 236   PcdMaximumLinkedListLenth nodes, then ASSERT().
 237   If Node is not a node in List, then ASSERT().
 238
 239   @param  List  A pointer to the head node of a doubly linked list.
 240   @param  Node  A pointer to a node in the doubly linked list.
 241
 242   @return Pointer to the next node if one exists. Otherwise a null value which
 243           is actually List is returned.
 244
 245 **/
 246 LIST_ENTRY *
 247 EFIAPI
 248 GetNextNode (
 249   IN CONST LIST_ENTRY  *List,
 250   IN CONST LIST_ENTRY  *Node
 251   )
 252 {
 253   //
 254   // ASSERT List not too long and Node is one of the nodes of List
 255   //
 256   ASSERT (IsNodeInList (List, Node));
 257
 258   return Node->ForwardLink;
 259 }
 260
 261 /**
 262   Checks to see if a doubly linked list is empty or not.
 263
 264   Checks to see if the doubly linked list is empty. If the linked list contains
 265   zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
 266
 267   If ListHead is NULL, then ASSERT().
 268   If ListHead was not initialized with 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  List  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      *List
 283   )
 284 {
 285   //
 286   // ASSERT List not too long
 287   //
 288   ASSERT (IsNodeInList (List, List));
 289
 290   return (BOOLEAN)(List->ForwardLink == List);
 291 }
 292
 293 /**
 294   Determines if a node in a doubly linked list is null.
 295
 296   Returns FALSE if Node is one of the nodes in the doubly linked list specified
 297   by List. Otherwise, TRUE is returned. List must have been initialized with
 298   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
 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 willl 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 Entry
 458
 459 **/
 460 LIST_ENTRY *
 461 EFIAPI
 462 RemoveEntryList (
 463   IN      CONST LIST_ENTRY      *Entry
 464   )
 465 {
 466   ASSERT (!IsListEmpty (Entry));
 467
 468   Entry->ForwardLink->BackLink = Entry->BackLink;
 469   Entry->BackLink->ForwardLink = Entry->ForwardLink;
 470   return Entry->ForwardLink;
 471 }