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