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 313