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