EdkCompatibilityPkg/Foundation/Library/EdkIIGlueLib/Library/BaseLib/LinkedList.c

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