EdkCompatibilityPkg/Foundation/Library/Dxe/Include/LinkedList.h

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