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