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
  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 null.
 293
 294   Returns FALSE if Node is one of the nodes in the doubly linked list specified
 295   by List. Otherwise, TRUE is returned. List must have been initialized with
 296   InitializeListHead().
 297
 298   If List is NULL, then ASSERT().
 299   If Node is NULL, then ASSERT().
 300   If List was not initialized with InitializeListHead(), then ASSERT().
 301   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 302   in List, including the List node, is greater than or equal to
 303   PcdMaximumLinkedListLength, then ASSERT().
 304   If Node is not a node in List and Node is not equal to List, then ASSERT().
 305
 306   @param  List  A pointer to the head node of a doubly linked list.
 307   @param  Node  A pointer to a node in the doubly linked list.
 308
 309   @retval TRUE  Node is one of the nodes in the doubly linked list.
 310   @retval FALSE Node is not one of the nodes in the doubly linked list.
 311
 312 **/
 313 BOOLEAN
 314 EFIAPI
 315 IsNull (
 316   IN      CONST LIST_ENTRY      *List,
 317   IN      CONST LIST_ENTRY      *Node
 318   )
 319 {
 320   //
 321   // ASSERT List not too long and Node is one of the nodes of List
 322   //
 323   ASSERT (IsNodeInList (List, Node));
 324
 325   return (BOOLEAN)(Node == List);
 326 }
 327
 328 /**
 329   Determines if a node the last node in a doubly linked list.
 330
 331   Returns TRUE if Node is the last node in the doubly linked list specified by
 332   List. Otherwise, FALSE is returned. List must have been initialized with
 333   InitializeListHead().
 334
 335   If List is NULL, then ASSERT().
 336   If Node is NULL, then ASSERT().
 337   If List was not initialized with InitializeListHead(), then ASSERT().
 338   If PcdMaximumLinkedListLenth is not zero, and the number of nodes
 339   in List, including the List node, is greater than or equal to
 340   PcdMaximumLinkedListLength, then ASSERT().
 341   If Node is not a node in List, then ASSERT().
 342
 343   @param  List  A pointer to the head node of a doubly linked list.
 344   @param  Node  A pointer to a node in the doubly linked list.
 345
 346   @retval TRUE  Node is the last node in the linked list.
 347   @retval FALSE Node is not the last node in the linked list.
 348
 349 **/
 350 BOOLEAN
 351 EFIAPI
 352 IsNodeAtEnd (
 353   IN      CONST LIST_ENTRY      *List,
 354   IN      CONST LIST_ENTRY      *Node
 355   )
 356 {
 357   //
 358   // ASSERT List not too long and Node is one of the nodes of List
 359   //
 360   ASSERT (IsNodeInList (List, Node));
 361
 362   return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
 363 }
 364
 365 /**
 366   Swaps the location of two nodes in a doubly linked list, and returns the
 367   first node after the swap.
 368
 369   If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
 370   Otherwise, the location of the FirstEntry node is swapped with the location
 371   of the SecondEntry node in a doubly linked list. SecondEntry must be in the
 372   same double linked list as FirstEntry and that double linked list must have
 373   been initialized with InitializeListHead(). SecondEntry is returned after the
 374   nodes are swapped.
 375
 376   If FirstEntry is NULL, then ASSERT().
 377   If SecondEntry is NULL, then ASSERT().
 378   If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
 379   If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
 380   linked list containing the FirstEntry and SecondEntry nodes, including
 381   the FirstEntry and SecondEntry nodes, is greater than or equal to
 382   PcdMaximumLinkedListLength, then ASSERT().
 383
 384   @param  FirstEntry  A pointer to a node in a linked list.
 385   @param  SecondEntry A pointer to another node in the same linked list.
 386
 387   @return SecondEntry
 388
 389 **/
 390 LIST_ENTRY *
 391 EFIAPI
 392 SwapListEntries (
 393   IN OUT  LIST_ENTRY            *FirstEntry,
 394   IN OUT  LIST_ENTRY            *SecondEntry
 395   )
 396 {
 397   LIST_ENTRY                    *Ptr;
 398
 399   if (FirstEntry == SecondEntry) {
 400     return SecondEntry;
 401   }
 402
 403   //
 404   // ASSERT Entry1 and Entry2 are in the same linked list
 405   //
 406   ASSERT (IsNodeInList (FirstEntry, SecondEntry));
 407
 408   //
 409   // Ptr is the node pointed to by FirstEntry->ForwardLink
 410   //
 411   Ptr = RemoveEntryList (FirstEntry);
 412
 413   //
 414   // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
 415   // immediately in front of SecondEntry
 416   //
 417   if (Ptr->BackLink == SecondEntry) {
 418     return InsertTailList (SecondEntry, FirstEntry);
 419   }
 420
 421   //
 422   // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
 423   // then there are no further steps necessary
 424   //
 425   if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
 426     return Ptr;
 427   }
 428
 429   //
 430   // Move SecondEntry to the front of Ptr
 431   //
 432   RemoveEntryList (SecondEntry);
 433   InsertTailList (Ptr, SecondEntry);
 434   return SecondEntry;
 435 }
 436
 437 /**
 438   Removes a node from a doubly linked list, and returns the node that follows
 439   the removed node.
 440
 441   Removes the node Entry from a doubly linked list. It is up to the caller of
 442   this function to release the memory used by this node if that is required. On
 443   exit, the node following Entry in the doubly linked list is returned. If
 444   Entry is the only node in the linked list, then the head node of the linked
 445   list is returned.
 446
 447   If Entry is NULL, then ASSERT().
 448   If Entry is the head node of an empty list, then ASSERT().
 449   If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
 450   linked list containing Entry, including the Entry node, is greater than
 451   or equal to PcdMaximumLinkedListLength, then ASSERT().
 452
 453   @param  Entry A pointer to a node in a linked list
 454
 455   @return Entry
 456
 457 **/
 458 LIST_ENTRY *
 459 EFIAPI
 460 RemoveEntryList (
 461   IN      CONST LIST_ENTRY      *Entry
 462   )
 463 {
 464   ASSERT (!IsListEmpty (Entry));
 465
 466   Entry->ForwardLink->BackLink = Entry->BackLink;
 467   Entry->BackLink->ForwardLink = Entry->ForwardLink;
 468   return Entry->ForwardLink;
 469 }