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 ListHead contains more than
 100   PcdMaximumLinkedListLenth nodes, then ASSERT().
 101
 102   @param  ListHead  A pointer to the head node of a doubly linked list.
 103   @param  Entry     A pointer to a node that is to be inserted at the beginning
 104                     of a doubly linked list.
 105
 106   @return ListHead
 107
 108 **/
 109 LIST_ENTRY *
 110 EFIAPI
 111 InsertHeadList (
 112   IN OUT  LIST_ENTRY            *List,
 113   IN OUT  LIST_ENTRY            *Entry
 114   )
 115 {
 116   //
 117   // ASSERT List not too long and Entry is not one of the nodes of List
 118   //
 119   ASSERT (!IsNodeInList (List, Entry));
 120
 121   Entry->ForwardLink = List->ForwardLink;
 122   Entry->BackLink = List;
 123   Entry->ForwardLink->BackLink = Entry;
 124   List->ForwardLink = Entry;
 125   return List;
 126 }
 127
 128 /**
 129   Adds a node to the end of a doubly linked list, and returns the pointer to
 130   the head node of the doubly linked list.
 131
 132   Adds the node Entry to the end of the doubly linked list denoted by ListHead,
 133   and returns ListHead.
 134
 135   If ListHead is NULL, then ASSERT().
 136   If Entry is NULL, then ASSERT().
 137   If ListHead was not initialized with InitializeListHead(), then ASSERT().
 138   If PcdMaximumLinkedListLenth is not zero, and ListHead contains more than
 139   PcdMaximumLinkedListLenth nodes, then ASSERT().
 140
 141   @param  ListHead  A pointer to the head node of a doubly linked list.
 142   @param  Entry     A pointer to a node that is to be added at the end of the
 143                     doubly linked list.
 144
 145   @return ListHead
 146
 147 **/
 148 LIST_ENTRY *
 149 EFIAPI
 150 InsertTailList (
 151   IN OUT  LIST_ENTRY            *List,
 152   IN OUT  LIST_ENTRY            *Entry
 153   )
 154 {
 155   //
 156   // ASSERT List not too long and Entry is not one of the nodes of List
 157   //
 158   ASSERT (!IsNodeInList (List, Entry));
 159
 160   Entry->ForwardLink = List;
 161   Entry->BackLink = List->BackLink;
 162   Entry->BackLink->ForwardLink = Entry;
 163   List->BackLink = Entry;
 164   return List;
 165 }
 166
 167 /**
 168   Retrieves the first node of a doubly linked list.
 169
 170   Returns the first node of a doubly linked list. List must have been
 171   initialized with InitializeListHead(). If List is empty, then NULL is
 172   returned.
 173
 174   If List is NULL, then ASSERT().
 175   If List was not initialized with InitializeListHead(), then ASSERT().
 176   If PcdMaximumLinkedListLenth is not zero, and List contains more than
 177   PcdMaximumLinkedListLenth nodes, 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 List contains more than
 244   PcdMaximumLinkedListLenth nodes, then ASSERT().
 245
 246   @param  ListHead  A pointer to the head node of a doubly linked list.
 247
 248   @retval TRUE  The linked list is empty.
 249   @retval FALSE The linked list is not empty.
 250
 251 **/
 252 BOOLEAN
 253 EFIAPI
 254 IsListEmpty (
 255   IN      CONST LIST_ENTRY      *List
 256   )
 257 {
 258   //
 259   // ASSERT List not too long
 260   //
 261   ASSERT (IsNodeInList (List, List));
 262
 263   return (BOOLEAN)(List->ForwardLink == List);
 264 }
 265
 266 /**
 267   Determines if a node in a doubly linked list is null.
 268
 269   Returns FALSE if Node is one of the nodes in the doubly linked list specified
 270   by List. Otherwise, TRUE is returned. List must have been initialized with
 271   InitializeListHead().
 272
 273   If List is NULL, then ASSERT().
 274   If Node is NULL, then ASSERT().
 275   If List was not initialized with InitializeListHead(), then ASSERT().
 276   If PcdMaximumLinkedListLenth is not zero, and List contains more than
 277   PcdMaximumLinkedListLenth nodes, then ASSERT().
 278   If Node is not a node in List and Node is not equal to List, then ASSERT().
 279
 280   @param  List  A pointer to the head node of a doubly linked list.
 281   @param  Node  A pointer to a node in the doubly linked list.
 282
 283   @retval TRUE  Node is one of the nodes in the doubly linked list.
 284   @retval FALSE Node is not one of the nodes in the doubly linked list.
 285
 286 **/
 287 BOOLEAN
 288 EFIAPI
 289 IsNull (
 290   IN      CONST LIST_ENTRY      *List,
 291   IN      CONST LIST_ENTRY      *Node
 292   )
 293 {
 294   //
 295   // ASSERT List not too long and Node is one of the nodes of List
 296   //
 297   ASSERT (IsNodeInList (List, Node));
 298
 299   return (BOOLEAN)(Node == List);
 300 }
 301
 302 /**
 303   Determines if a node the last node in a doubly linked list.
 304
 305   Returns TRUE if Node is the last node in the doubly linked list specified by
 306   List. Otherwise, FALSE is returned. List must have been initialized with
 307   InitializeListHead().
 308
 309   If List is NULL, then ASSERT().
 310   If Node is NULL, then ASSERT().
 311   If List was not initialized with InitializeListHead(), then ASSERT().
 312   If PcdMaximumLinkedListLenth is not zero, and List contains more than
 313   PcdMaximumLinkedListLenth nodes, then ASSERT().
 314   If Node is not a node in List, then ASSERT().
 315
 316   @param  List  A pointer to the head node of a doubly linked list.
 317   @param  Node  A pointer to a node in the doubly linked list.
 318
 319   @retval TRUE  Node is the last node in the linked list.
 320   @retval FALSE Node is not the last node in the linked list.
 321
 322 **/
 323 BOOLEAN
 324 EFIAPI
 325 IsNodeAtEnd (
 326   IN      CONST LIST_ENTRY      *List,
 327   IN      CONST LIST_ENTRY      *Node
 328   )
 329 {
 330   //
 331   // ASSERT List not too long and Node is one of the nodes of List
 332   //
 333   ASSERT (IsNodeInList (List, Node));
 334
 335   return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
 336 }
 337
 338 /**
 339   Swaps the location of two nodes in a doubly linked list, and returns the
 340   first node after the swap.
 341
 342   If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
 343   Otherwise, the location of the FirstEntry node is swapped with the location
 344   of the SecondEntry node in a doubly linked list. SecondEntry must be in the
 345   same double linked list as FirstEntry and that double linked list must have
 346   been initialized with InitializeListHead(). SecondEntry is returned after the
 347   nodes are swapped.
 348
 349   If FirstEntry is NULL, then ASSERT().
 350   If SecondEntry is NULL, then ASSERT().
 351   If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
 352   If PcdMaximumLinkedListLenth is not zero, and the linked list containing
 353   FirstEntry and SecondEntry contains more than PcdMaximumLinkedListLenth
 354   nodes, then ASSERT().
 355
 356   @param  FirstEntry  A pointer to a node in a linked list.
 357   @param  SecondEntry A pointer to another node in the same linked list.
 358
 359 **/
 360 LIST_ENTRY *
 361 EFIAPI
 362 SwapListEntries (
 363   IN OUT  LIST_ENTRY            *FirstEntry,
 364   IN OUT  LIST_ENTRY            *SecondEntry
 365   )
 366 {
 367   LIST_ENTRY                    *Ptr;
 368
 369   if (FirstEntry == SecondEntry) {
 370     return SecondEntry;
 371   }
 372
 373   //
 374   // ASSERT Entry1 and Entry2 are in the same linked list
 375   //
 376   ASSERT (IsNodeInList (FirstEntry, SecondEntry));
 377
 378   //
 379   // Ptr is the node pointed to by FirstEntry->ForwardLink
 380   //
 381   Ptr = RemoveEntryList (FirstEntry);
 382
 383   //
 384   // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
 385   // immediately in front of SecondEntry
 386   //
 387   if (Ptr->BackLink == SecondEntry) {
 388     return InsertTailList (SecondEntry, FirstEntry);
 389   }
 390
 391   //
 392   // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
 393   // then there are no further steps necessary
 394   //
 395   if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
 396     return Ptr;
 397   }
 398
 399   //
 400   // Move SecondEntry to the front of Ptr
 401   //
 402   RemoveEntryList (SecondEntry);
 403   InsertTailList (Ptr, SecondEntry);
 404   return SecondEntry;
 405 }
 406
 407 /**
 408   Removes a node from a doubly linked list, and returns the node that follows
 409   the removed node.
 410
 411   Removes the node Entry from a doubly linked list. It is up to the caller of
 412   this function to release the memory used by this node if that is required. On
 413   exit, the node following Entry in the doubly linked list is returned. If
 414   Entry is the only node in the linked list, then the head node of the linked
 415   list is returned.
 416
 417   If Entry is NULL, then ASSERT().
 418   If Entry is the head node of an empty list, then ASSERT().
 419   If PcdMaximumLinkedListLenth is not zero, and the linked list containing
 420   Entry contains more than PcdMaximumLinkedListLenth nodes, then ASSERT().
 421
 422   @param  Entry A pointer to a node in a linked list
 423
 424   @return Entry
 425
 426 **/
 427 LIST_ENTRY *
 428 EFIAPI
 429 RemoveEntryList (
 430   IN      CONST LIST_ENTRY      *Entry
 431   )
 432 {
 433   ASSERT (!IsListEmpty (Entry));
 434
 435   Entry->ForwardLink->BackLink = Entry->BackLink;
 436   Entry->BackLink->ForwardLink = Entry->ForwardLink;
 437   return Entry->ForwardLink;
 438 }