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.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 *Entry1BackLink; 216 EFI_LIST_ENTRY *Entry2ForwardLink; 217 EFI_LIST_ENTRY *Entry2BackLink; 218 219 Entry2ForwardLink = Entry2->ForwardLink; 220 Entry2BackLink = Entry2->BackLink; 221 Entry1BackLink = Entry1->BackLink; 222 Entry2BackLink->ForwardLink = Entry2ForwardLink; 223 Entry2ForwardLink->BackLink = Entry2BackLink; 224 Entry2->ForwardLink = Entry1; 225 Entry2->BackLink = Entry1BackLink; 226 Entry1BackLink->ForwardLink = Entry2; 227 Entry1->BackLink = Entry2; 228 } 229 230 231 EFI_LIST_ENTRY * 232 GetFirstNode ( 233 EFI_LIST_ENTRY *List 234 ) 235 /*++ 236 237 Routine Description: 238 239 Return the first node pointed to by the list head. 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 doubly linked list. 246 247 Returns: 248 249 Pointer to the first node, if the list contains nodes. The list will 250 return a null value--that is, the value of List--when the list is empty. 251 See the description of IsNull for more information. 252 253 254 --*/ 255 { 256 return List->ForwardLink; 257 } 258 259 260 EFI_LIST_ENTRY * 261 GetNextNode ( 262 EFI_LIST_ENTRY *List, 263 EFI_LIST_ENTRY *Node 264 ) 265 /*++ 266 267 Routine Description: 268 269 Returns the node following Node in the list. The list must 270 have been initialized with InitializeListHead () before using this 271 function and must contain data. 272 273 Arguments: 274 275 List - The head of the list. MUST NOT be the literal value NULL. 276 Node - The node in the list. This value MUST NOT be the literal value NULL. 277 See the description of IsNull for more information. 278 279 Returns: 280 281 Pointer to the next node, if one exists. Otherwise, returns a null value, 282 which is actually a pointer to List. 283 See the description of IsNull for more information. 284 285 --*/ 286 { 287 if (Node == List) { 288 return List; 289 } 290 return Node->ForwardLink; 291 } 292 293 294 BOOLEAN 295 IsNull ( 296 EFI_LIST_ENTRY *List, 297 EFI_LIST_ENTRY *Node 298 ) 299 /*++ 300 301 Routine Description: 302 303 Determines whether the given node is null. Note that Node is null 304 when its value is equal to the value of List. It is an error for 305 Node to be the literal value NULL [(VOID*)0x0]. 306 307 Arguments: 308 309 List - The head of the list. MUST NOT be the literal value NULL. 310 Node - The node to test. MUST NOT be the literal value NULL. See 311 the description above. 312 313 Returns: 314 315 Returns true if the node is null. 316 317 --*/ 318 { 319 return (BOOLEAN)(Node == List); 320 } 321 322 323 BOOLEAN 324 IsNodeAtEnd ( 325 EFI_LIST_ENTRY *List, 326 EFI_LIST_ENTRY *Node 327 ) 328 /*++ 329 330 Routine Description: 331 332 Determines whether the given node is at the end of the list. Used 333 to walk the list. The list must have been initialized with 334 InitializeListHead () before using this function and must contain 335 data. 336 337 Arguments: 338 339 List - The head of the list. MUST NOT be the literal value NULL. 340 Node - The node to test. MUST NOT be the literal value NULL. 341 See the description of IsNull for more information. 342 343 Returns: 344 345 Returns true if the list is the tail. 346 347 --*/ 348 { 349 if (IsNull (List, Node)) { 350 return FALSE; 351 } 352 return (BOOLEAN)(List->BackLink == Node); 353 } 354 355
