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