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