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