EdkCompatibilityPkg/Foundation/Library/EfiCommonLib/LinkedList.c

   1 /*++
   2
   3 Copyright (c) 2004, Intel Corporation
   4 All rights reserved. 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 Module Name:
  13
  14   LinkedList.c
  15
  16 Abstract:
  17
  18   Linked List Library Functions
  19
  20 --*/
  21
  22 #include "Tiano.h"
  23 #include "EfiDriverLib.h"
  24
  25
  26 VOID
  27 InitializeListHead (
  28   EFI_LIST_ENTRY       *List
  29   )
  30 /*++
  31
  32 Routine Description:
  33
  34   Initialize the head of the List.  The caller must allocate the memory
  35   for the EFI_LIST. This function must be called before the other linked
  36   list macros can be used.
  37
  38 Arguments:
  39
  40   List - Pointer to list head to initialize
  41
  42 Returns:
  43
  44   None.
  45
  46 --*/
  47
  48 {
  49   List->ForwardLink = List;
  50   List->BackLink    = List;
  51 }
  52
  53
  54 BOOLEAN
  55 IsListEmpty (
  56   EFI_LIST_ENTRY  *List
  57   )
  58 /*++
  59
  60 Routine Description:
  61
  62   Return TRUE is the list contains zero nodes. Otherzise return FALSE.
  63   The list must have been initialized with InitializeListHead () before using
  64   this function.
  65
  66 Arguments:
  67
  68   List - Pointer to list head to test
  69
  70
  71 Returns:
  72
  73   Return TRUE is the list contains zero nodes. Otherzise return FALSE.
  74
  75 --*/
  76 {
  77   return (BOOLEAN)(List->ForwardLink == List);
  78 }
  79
  80
  81 VOID
  82 RemoveEntryList (
  83   EFI_LIST_ENTRY  *Entry
  84   )
  85 /*++
  86
  87 Routine Description:
  88
  89   Remove Node from the doubly linked list. It is the caller's responsibility
  90   to free any memory used by the entry if needed. The list must have been
  91   initialized with InitializeListHead () before using this function.
  92
  93 Arguments:
  94
  95   Entry - Element to remove from the list.
  96
  97 Returns:
  98
  99   None
 100
 101 --*/
 102 {
 103   EFI_LIST_ENTRY  *_ForwardLink;
 104   EFI_LIST_ENTRY  *_BackLink;
 105
 106   _ForwardLink           = Entry->ForwardLink;
 107   _BackLink              = Entry->BackLink;
 108   _BackLink->ForwardLink = _ForwardLink;
 109   _ForwardLink->BackLink = _BackLink;
 110
 111   DEBUG_CODE (
 112     Entry->ForwardLink = (EFI_LIST_ENTRY *) EFI_BAD_POINTER;
 113     Entry->BackLink    = (EFI_LIST_ENTRY *) EFI_BAD_POINTER;
 114   )
 115 }
 116
 117
 118 VOID
 119 InsertTailList (
 120   EFI_LIST_ENTRY  *ListHead,
 121   EFI_LIST_ENTRY  *Entry
 122   )
 123 /*++
 124
 125 Routine Description:
 126
 127   Insert a Node into the end of a doubly linked list. The list must have
 128   been initialized with InitializeListHead () before using this function.
 129
 130 Arguments:
 131
 132   ListHead - Head of doubly linked list
 133
 134   Entry    - Element to insert at the end of the list.
 135
 136 Returns:
 137
 138   None
 139
 140 --*/
 141 {
 142   EFI_LIST_ENTRY *_ListHead;
 143   EFI_LIST_ENTRY *_BackLink;
 144
 145   _ListHead              = ListHead;
 146   _BackLink              = _ListHead->BackLink;
 147   Entry->ForwardLink     = _ListHead;
 148   Entry->BackLink        = _BackLink;
 149   _BackLink->ForwardLink = Entry;
 150   _ListHead->BackLink    = Entry;
 151 }
 152
 153
 154
 155 VOID
 156 InsertHeadList (
 157   EFI_LIST_ENTRY  *ListHead,
 158   EFI_LIST_ENTRY  *Entry
 159   )
 160 /*++
 161
 162 Routine Description:
 163
 164   Insert a Node into the start of a doubly linked list. The list must have
 165   been initialized with InitializeListHead () before using this function.
 166
 167 Arguments:
 168
 169   ListHead - Head of doubly linked list
 170
 171   Entry    - Element to insert to beginning of list
 172
 173 Returns:
 174
 175   None
 176
 177 --*/
 178 {
 179   EFI_LIST_ENTRY  *_ListHead;
 180   EFI_LIST_ENTRY  *_ForwardLink;
 181
 182   _ListHead               = ListHead;
 183   _ForwardLink            = _ListHead->ForwardLink;
 184   Entry->ForwardLink      = _ForwardLink;
 185   Entry->BackLink         = _ListHead;
 186   _ForwardLink->BackLink  = Entry;
 187   _ListHead->ForwardLink  = Entry;
 188 }
 189
 190 VOID
 191 SwapListEntries (
 192   EFI_LIST_ENTRY  *Entry1,
 193   EFI_LIST_ENTRY  *Entry2
 194   )
 195 /*++
 196
 197 Routine Description:
 198
 199   Swap the location of the two elements of a doubly linked list. Node2
 200   is placed in front of Node1. The list must have been initialized with
 201   InitializeListHead () before using this function.
 202
 203 Arguments:
 204
 205   Entry1 - Element in the doubly linked list in front of Node2.
 206
 207   Entry2 - Element in the doubly linked list behind Node1.
 208
 209 Returns:
 210
 211   None
 212
 213 --*/
 214 {
 215   EFI_LIST_ENTRY *Entry1ForwardLink;
 216   EFI_LIST_ENTRY *Entry1BackLink;
 217   EFI_LIST_ENTRY *Entry2ForwardLink;
 218   EFI_LIST_ENTRY *Entry2BackLink;
 219
 220   Entry2ForwardLink           = Entry2->ForwardLink;
 221   Entry2BackLink              = Entry2->BackLink;
 222   Entry1ForwardLink           = Entry1->ForwardLink;
 223   Entry1BackLink              = Entry1->BackLink;
 224   Entry2BackLink->ForwardLink = Entry2ForwardLink;
 225   Entry2ForwardLink->BackLink = Entry2BackLink;
 226   Entry2->ForwardLink         = Entry1;
 227   Entry2->BackLink            = Entry1BackLink;
 228   Entry1BackLink->ForwardLink = Entry2;
 229   Entry1->BackLink            = Entry2;
 230 }
 231
 232
 233 EFI_LIST_ENTRY *
 234 GetFirstNode (
 235   EFI_LIST_ENTRY  *List
 236   )
 237 /*++
 238
 239 Routine Description:
 240
 241   Return the first node pointed to by the list head.  The list must
 242   have been initialized with InitializeListHead () before using this
 243   function and must contain data.
 244
 245 Arguments:
 246
 247   List - The head of the doubly linked list.
 248
 249 Returns:
 250
 251   Pointer to the first node, if the list contains nodes.  The list will
 252   return a null value--that is, the value of List--when the list is empty.
 253     See the description of IsNull for more information.
 254
 255
 256 --*/
 257 {
 258   return List->ForwardLink;
 259 }
 260
 261
 262 EFI_LIST_ENTRY *
 263 GetNextNode (
 264   EFI_LIST_ENTRY  *List,
 265   EFI_LIST_ENTRY  *Node
 266   )
 267 /*++
 268
 269 Routine Description:
 270
 271   Returns the node following Node in the list. The list must
 272   have been initialized with InitializeListHead () before using this
 273   function and must contain data.
 274
 275 Arguments:
 276
 277   List - The head of the list.  MUST NOT be the literal value NULL.
 278   Node - The node in the list.  This value MUST NOT be the literal value NULL.
 279     See the description of IsNull for more information.
 280
 281 Returns:
 282
 283   Pointer to the next node, if one exists.  Otherwise, returns a null value,
 284   which is actually a pointer to List.
 285     See the description of IsNull for more information.
 286
 287 --*/
 288 {
 289   if (Node == List) {
 290     return List;
 291   }
 292   return Node->ForwardLink;
 293 }
 294
 295
 296 BOOLEAN
 297 IsNull (
 298   EFI_LIST_ENTRY  *List,
 299   EFI_LIST_ENTRY  *Node
 300   )
 301 /*++
 302
 303 Routine Description:
 304
 305   Determines whether the given node is null.  Note that Node is null
 306   when its value is equal to the value of List.  It is an error for
 307   Node to be the literal value NULL [(VOID*)0x0].
 308
 309 Arguments:
 310
 311   List - The head of the list.  MUST NOT be the literal value NULL.
 312   Node - The node to test.  MUST NOT be the literal value NULL.  See
 313     the description above.
 314
 315 Returns:
 316
 317   Returns true if the node is null.
 318
 319 --*/
 320 {
 321   return (BOOLEAN)(Node == List);
 322 }
 323
 324
 325 BOOLEAN
 326 IsNodeAtEnd (
 327   EFI_LIST_ENTRY  *List,
 328   EFI_LIST_ENTRY  *Node
 329   )
 330 /*++
 331
 332 Routine Description:
 333
 334   Determines whether the given node is at the end of the list.  Used
 335   to walk the list.  The list must have been initialized with
 336   InitializeListHead () before using this function and must contain
 337   data.
 338
 339 Arguments:
 340
 341   List - The head of the list.  MUST NOT be the literal value NULL.
 342   Node - The node to test.  MUST NOT be the literal value NULL.
 343     See the description of IsNull for more information.
 344
 345 Returns:
 346
 347   Returns true if the list is the tail.
 348
 349 --*/
 350 {
 351   if (IsNull (List, Node)) {
 352     return FALSE;
 353   }
 354   return (BOOLEAN)(List->BackLink == Node);
 355 }
 356