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