]>
Commit | Line | Data |
---|---|---|
e1f414b6 | 1 | /** @file\r |
2 | Linked List Library Functions.\r | |
3 | \r | |
127010dd | 4 | Copyright (c) 2006 - 2010, Intel Corporation. All rights reserved.<BR>\r |
bb817c56 | 5 | This program and the accompanying materials\r |
e1f414b6 | 6 | are licensed and made available under the terms and conditions of the BSD License\r |
7 | which accompanies this distribution. The full text of the license may be found at\r | |
127010dd | 8 | http://opensource.org/licenses/bsd-license.php.\r |
e1f414b6 | 9 | \r |
10 | THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r | |
11 | WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r | |
12 | \r | |
e1f414b6 | 13 | **/\r |
14 | \r | |
e1f414b6 | 15 | #include "BaseLibInternals.h"\r |
16 | \r | |
17 | /**\r | |
2fc60b70 | 18 | Worker function that locates the Node in the List.\r |
e1f414b6 | 19 | \r |
20 | By searching the List, finds the location of the Node in List. At the same time,\r | |
21 | verifies the validity of this list.\r | |
22 | \r | |
23 | If List is NULL, then ASSERT().\r | |
24 | If List->ForwardLink is NULL, then ASSERT().\r | |
2fc60b70 | 25 | If List->backLink is NULL, then ASSERT().\r |
1081f624 | 26 | If Node is NULL, then ASSERT().\r |
27 | If PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE and Node \r | |
28 | is in not a member of List, then return FALSE\r | |
29 | If PcdMaximumLinkedListLenth is not zero, and List contains more than\r | |
30 | PcdMaximumLinkedListLenth nodes, then ASSERT().\r | |
e1f414b6 | 31 | \r |
1081f624 | 32 | @param List A pointer to a node in a linked list.\r |
33 | @param Node A pointer to a node in a linked list.\r | |
34 | @param VerifyNodeInList TRUE if a check should be made to see if Node is a \r | |
35 | member of List. FALSE if no membership test should \r | |
36 | be performed.\r | |
e1f414b6 | 37 | \r |
1081f624 | 38 | @retval TRUE if PcdVerifyNodeInList is FALSE\r |
39 | @retval TRUE if DoMembershipCheck is FALSE\r | |
40 | @retval TRUE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE \r | |
41 | and Node is a member of List.\r | |
42 | @retval FALSE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE \r | |
43 | and Node is in not a member of List.\r | |
e1f414b6 | 44 | \r |
45 | **/\r | |
46 | BOOLEAN\r | |
38bbd3d9 | 47 | EFIAPI\r |
80151e53 | 48 | InternalBaseLibIsNodeInList (\r |
1081f624 | 49 | IN CONST LIST_ENTRY *List,\r |
50 | IN CONST LIST_ENTRY *Node,\r | |
51 | IN BOOLEAN VerifyNodeInList\r | |
e1f414b6 | 52 | )\r |
53 | {\r | |
1081f624 | 54 | UINTN Count;\r |
55 | CONST LIST_ENTRY *Ptr;\r | |
e1f414b6 | 56 | \r |
57 | //\r | |
58 | // Test the validity of List and Node\r | |
59 | //\r | |
60 | ASSERT (List != NULL);\r | |
61 | ASSERT (List->ForwardLink != NULL);\r | |
62 | ASSERT (List->BackLink != NULL);\r | |
63 | ASSERT (Node != NULL);\r | |
64 | \r | |
1081f624 | 65 | Count = 0;\r |
66 | Ptr = List;\r | |
e1f414b6 | 67 | \r |
1081f624 | 68 | if (FeaturePcdGet (PcdVerifyNodeInList) && VerifyNodeInList) {\r |
69 | //\r | |
70 | // Check to see if Node is a member of List. \r | |
71 | // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength\r | |
72 | //\r | |
73 | do {\r | |
74 | Ptr = Ptr->ForwardLink;\r | |
75 | if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {\r | |
76 | Count++;\r | |
77 | //\r | |
78 | // ASSERT() if the linked list is too long\r | |
79 | //\r | |
80 | ASSERT (Count < PcdGet32 (PcdMaximumLinkedListLength));\r | |
81 | \r | |
82 | //\r | |
83 | // Return if the linked list is too long\r | |
84 | //\r | |
85 | if (Count >= PcdGet32 (PcdMaximumLinkedListLength)) {\r | |
86 | return (BOOLEAN)(Ptr == Node);\r | |
87 | }\r | |
88 | }\r | |
89 | } while ((Ptr != List) && (Ptr != Node)); \r | |
90 | \r | |
91 | if (Ptr != Node) {\r | |
92 | return FALSE;\r | |
93 | }\r | |
94 | }\r | |
e1f414b6 | 95 | \r |
96 | if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {\r | |
1081f624 | 97 | //\r |
98 | // Count the total number of nodes in List.\r | |
99 | // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength\r | |
100 | //\r | |
101 | do {\r | |
e1f414b6 | 102 | Ptr = Ptr->ForwardLink;\r |
1081f624 | 103 | Count++;\r |
104 | } while ((Ptr != List) && (Count < PcdGet32 (PcdMaximumLinkedListLength)));\r | |
105 | \r | |
106 | //\r | |
107 | // ASSERT() if the linked list is too long\r | |
108 | //\r | |
109 | ASSERT (Count < PcdGet32 (PcdMaximumLinkedListLength));\r | |
e1f414b6 | 110 | }\r |
111 | \r | |
1081f624 | 112 | return TRUE;\r |
e1f414b6 | 113 | }\r |
114 | \r | |
115 | /**\r | |
127010dd | 116 | Initializes the head node of a doubly-linked list, and returns the pointer to\r |
117 | the head node of the doubly-linked list.\r | |
e1f414b6 | 118 | \r |
119 | Initializes the forward and backward links of a new linked list. After\r | |
120 | initializing a linked list with this function, the other linked list\r | |
121 | functions may be used to add and remove nodes from the linked list. It is up\r | |
122 | to the caller of this function to allocate the memory for ListHead.\r | |
123 | \r | |
124 | If ListHead is NULL, then ASSERT().\r | |
125 | \r | |
127010dd | 126 | @param ListHead A pointer to the head node of a new doubly-linked list.\r |
e1f414b6 | 127 | \r |
128 | @return ListHead\r | |
129 | \r | |
130 | **/\r | |
131 | LIST_ENTRY *\r | |
132 | EFIAPI\r | |
133 | InitializeListHead (\r | |
2fc60b70 | 134 | IN OUT LIST_ENTRY *ListHead\r |
e1f414b6 | 135 | )\r |
136 | \r | |
137 | {\r | |
2fc60b70 | 138 | ASSERT (ListHead != NULL);\r |
e1f414b6 | 139 | \r |
2fc60b70 | 140 | ListHead->ForwardLink = ListHead;\r |
141 | ListHead->BackLink = ListHead;\r | |
142 | return ListHead;\r | |
e1f414b6 | 143 | }\r |
144 | \r | |
145 | /**\r | |
127010dd | 146 | Adds a node to the beginning of a doubly-linked list, and returns the pointer\r |
147 | to the head node of the doubly-linked list.\r | |
e1f414b6 | 148 | \r |
127010dd | 149 | Adds the node Entry at the beginning of the doubly-linked list denoted by\r |
e1f414b6 | 150 | ListHead, and returns ListHead.\r |
151 | \r | |
152 | If ListHead is NULL, then ASSERT().\r | |
153 | If Entry is NULL, then ASSERT().\r | |
9aa049d9 | 154 | If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or\r |
155 | InitializeListHead(), then ASSERT().\r | |
e1f414b6 | 156 | If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number\r |
157 | of nodes in ListHead, including the ListHead node, is greater than or\r | |
158 | equal to PcdMaximumLinkedListLength, then ASSERT().\r | |
159 | \r | |
127010dd | 160 | @param ListHead A pointer to the head node of a doubly-linked list.\r |
e1f414b6 | 161 | @param Entry A pointer to a node that is to be inserted at the beginning\r |
127010dd | 162 | of a doubly-linked list.\r |
e1f414b6 | 163 | \r |
164 | @return ListHead\r | |
165 | \r | |
166 | **/\r | |
167 | LIST_ENTRY *\r | |
168 | EFIAPI\r | |
169 | InsertHeadList (\r | |
2fc60b70 | 170 | IN OUT LIST_ENTRY *ListHead,\r |
171 | IN OUT LIST_ENTRY *Entry\r | |
e1f414b6 | 172 | )\r |
173 | {\r | |
174 | //\r | |
175 | // ASSERT List not too long and Entry is not one of the nodes of List\r | |
176 | //\r | |
1081f624 | 177 | ASSERT (InternalBaseLibIsNodeInList (ListHead, Entry, FALSE));\r |
178 | \r | |
2fc60b70 | 179 | Entry->ForwardLink = ListHead->ForwardLink;\r |
180 | Entry->BackLink = ListHead;\r | |
e1f414b6 | 181 | Entry->ForwardLink->BackLink = Entry;\r |
2fc60b70 | 182 | ListHead->ForwardLink = Entry;\r |
183 | return ListHead;\r | |
e1f414b6 | 184 | }\r |
185 | \r | |
186 | /**\r | |
127010dd | 187 | Adds a node to the end of a doubly-linked list, and returns the pointer to\r |
188 | the head node of the doubly-linked list.\r | |
e1f414b6 | 189 | \r |
127010dd | 190 | Adds the node Entry to the end of the doubly-linked list denoted by ListHead,\r |
e1f414b6 | 191 | and returns ListHead.\r |
192 | \r | |
193 | If ListHead is NULL, then ASSERT().\r | |
194 | If Entry is NULL, then ASSERT().\r | |
9aa049d9 | 195 | If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r |
196 | InitializeListHead(), then ASSERT().\r | |
e1f414b6 | 197 | If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number\r |
198 | of nodes in ListHead, including the ListHead node, is greater than or\r | |
199 | equal to PcdMaximumLinkedListLength, then ASSERT().\r | |
200 | \r | |
127010dd | 201 | @param ListHead A pointer to the head node of a doubly-linked list.\r |
e1f414b6 | 202 | @param Entry A pointer to a node that is to be added at the end of the\r |
127010dd | 203 | doubly-linked list.\r |
e1f414b6 | 204 | \r |
205 | @return ListHead\r | |
206 | \r | |
207 | **/\r | |
208 | LIST_ENTRY *\r | |
209 | EFIAPI\r | |
210 | InsertTailList (\r | |
2fc60b70 | 211 | IN OUT LIST_ENTRY *ListHead,\r |
212 | IN OUT LIST_ENTRY *Entry\r | |
e1f414b6 | 213 | )\r |
214 | {\r | |
215 | //\r | |
216 | // ASSERT List not too long and Entry is not one of the nodes of List\r | |
217 | //\r | |
1081f624 | 218 | ASSERT (InternalBaseLibIsNodeInList (ListHead, Entry, FALSE));\r |
219 | \r | |
2fc60b70 | 220 | Entry->ForwardLink = ListHead;\r |
221 | Entry->BackLink = ListHead->BackLink;\r | |
e1f414b6 | 222 | Entry->BackLink->ForwardLink = Entry;\r |
2fc60b70 | 223 | ListHead->BackLink = Entry;\r |
224 | return ListHead;\r | |
e1f414b6 | 225 | }\r |
226 | \r | |
227 | /**\r | |
127010dd | 228 | Retrieves the first node of a doubly-linked list.\r |
e1f414b6 | 229 | \r |
127010dd | 230 | Returns the first node of a doubly-linked list. List must have been \r |
9aa049d9 | 231 | initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().\r |
232 | If List is empty, then List is returned.\r | |
e1f414b6 | 233 | \r |
234 | If List is NULL, then ASSERT().\r | |
9aa049d9 | 235 | If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r |
236 | InitializeListHead(), then ASSERT().\r | |
e1f414b6 | 237 | If PcdMaximumLinkedListLenth is not zero, and the number of nodes\r |
238 | in List, including the List node, is greater than or equal to\r | |
239 | PcdMaximumLinkedListLength, then ASSERT().\r | |
240 | \r | |
127010dd | 241 | @param List A pointer to the head node of a doubly-linked list.\r |
e1f414b6 | 242 | \r |
127010dd | 243 | @return The first node of a doubly-linked list.\r |
e1f414b6 | 244 | @retval NULL The list is empty.\r |
245 | \r | |
246 | **/\r | |
247 | LIST_ENTRY *\r | |
248 | EFIAPI\r | |
249 | GetFirstNode (\r | |
2fc60b70 | 250 | IN CONST LIST_ENTRY *List\r |
e1f414b6 | 251 | )\r |
252 | {\r | |
253 | //\r | |
254 | // ASSERT List not too long\r | |
255 | //\r | |
1081f624 | 256 | ASSERT (InternalBaseLibIsNodeInList (List, List, FALSE));\r |
e1f414b6 | 257 | \r |
258 | return List->ForwardLink;\r | |
259 | }\r | |
260 | \r | |
261 | /**\r | |
127010dd | 262 | Retrieves the next node of a doubly-linked list.\r |
e1f414b6 | 263 | \r |
127010dd | 264 | Returns the node of a doubly-linked list that follows Node. \r |
9aa049d9 | 265 | List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()\r |
266 | or InitializeListHead(). If List is empty, then List is returned.\r | |
e1f414b6 | 267 | \r |
268 | If List is NULL, then ASSERT().\r | |
269 | If Node is NULL, then ASSERT().\r | |
9aa049d9 | 270 | If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r |
271 | InitializeListHead(), then ASSERT().\r | |
e1f414b6 | 272 | If PcdMaximumLinkedListLenth is not zero, and List contains more than\r |
273 | PcdMaximumLinkedListLenth nodes, then ASSERT().\r | |
1081f624 | 274 | If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().\r |
e1f414b6 | 275 | \r |
127010dd | 276 | @param List A pointer to the head node of a doubly-linked list.\r |
277 | @param Node A pointer to a node in the doubly-linked list.\r | |
e1f414b6 | 278 | \r |
127010dd | 279 | @return A pointer to the next node if one exists. Otherwise List is returned.\r |
e1f414b6 | 280 | \r |
281 | **/\r | |
282 | LIST_ENTRY *\r | |
283 | EFIAPI\r | |
284 | GetNextNode (\r | |
2fc60b70 | 285 | IN CONST LIST_ENTRY *List,\r |
286 | IN CONST LIST_ENTRY *Node\r | |
e1f414b6 | 287 | )\r |
288 | {\r | |
289 | //\r | |
290 | // ASSERT List not too long and Node is one of the nodes of List\r | |
291 | //\r | |
1081f624 | 292 | ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));\r |
e1f414b6 | 293 | \r |
294 | return Node->ForwardLink;\r | |
295 | }\r | |
296 | \r | |
cbca8de5 | 297 | /**\r |
127010dd | 298 | Retrieves the previous node of a doubly-linked list.\r |
cbca8de5 | 299 | \r |
127010dd | 300 | Returns the node of a doubly-linked list that precedes Node. \r |
cbca8de5 | 301 | List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()\r |
302 | or InitializeListHead(). If List is empty, then List is returned.\r | |
303 | \r | |
304 | If List is NULL, then ASSERT().\r | |
305 | If Node is NULL, then ASSERT().\r | |
306 | If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r | |
307 | InitializeListHead(), then ASSERT().\r | |
308 | If PcdMaximumLinkedListLenth is not zero, and List contains more than\r | |
309 | PcdMaximumLinkedListLenth nodes, then ASSERT().\r | |
310 | If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().\r | |
311 | \r | |
127010dd | 312 | @param List A pointer to the head node of a doubly-linked list.\r |
313 | @param Node A pointer to a node in the doubly-linked list.\r | |
cbca8de5 | 314 | \r |
127010dd | 315 | @return A pointer to the previous node if one exists. Otherwise List is returned.\r |
cbca8de5 | 316 | \r |
317 | **/\r | |
318 | LIST_ENTRY *\r | |
319 | EFIAPI\r | |
320 | GetPreviousNode (\r | |
321 | IN CONST LIST_ENTRY *List,\r | |
322 | IN CONST LIST_ENTRY *Node\r | |
323 | )\r | |
324 | {\r | |
325 | //\r | |
326 | // ASSERT List not too long and Node is one of the nodes of List\r | |
327 | //\r | |
328 | ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));\r | |
329 | \r | |
330 | return Node->BackLink;\r | |
331 | }\r | |
332 | \r | |
e1f414b6 | 333 | /**\r |
127010dd | 334 | Checks to see if a doubly-linked list is empty or not.\r |
e1f414b6 | 335 | \r |
127010dd | 336 | Checks to see if the doubly-linked list is empty. If the linked list contains\r |
e1f414b6 | 337 | zero nodes, this function returns TRUE. Otherwise, it returns FALSE.\r |
338 | \r | |
339 | If ListHead is NULL, then ASSERT().\r | |
9aa049d9 | 340 | If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r |
341 | InitializeListHead(), then ASSERT().\r | |
e1f414b6 | 342 | If PcdMaximumLinkedListLenth is not zero, and the number of nodes\r |
343 | in List, including the List node, is greater than or equal to\r | |
344 | PcdMaximumLinkedListLength, then ASSERT().\r | |
345 | \r | |
127010dd | 346 | @param ListHead A pointer to the head node of a doubly-linked list.\r |
e1f414b6 | 347 | \r |
348 | @retval TRUE The linked list is empty.\r | |
349 | @retval FALSE The linked list is not empty.\r | |
350 | \r | |
351 | **/\r | |
352 | BOOLEAN\r | |
353 | EFIAPI\r | |
354 | IsListEmpty (\r | |
2fc60b70 | 355 | IN CONST LIST_ENTRY *ListHead\r |
e1f414b6 | 356 | )\r |
357 | {\r | |
358 | //\r | |
359 | // ASSERT List not too long\r | |
360 | //\r | |
1081f624 | 361 | ASSERT (InternalBaseLibIsNodeInList (ListHead, ListHead, FALSE));\r |
362 | \r | |
2fc60b70 | 363 | return (BOOLEAN)(ListHead->ForwardLink == ListHead);\r |
e1f414b6 | 364 | }\r |
365 | \r | |
366 | /**\r | |
127010dd | 367 | Determines if a node in a doubly-linked list is the head node of a the same\r |
368 | doubly-linked list. This function is typically used to terminate a loop that\r | |
369 | traverses all the nodes in a doubly-linked list starting with the head node.\r | |
e1f414b6 | 370 | \r |
aa0583c7 | 371 | Returns TRUE if Node is equal to List. Returns FALSE if Node is one of the\r |
127010dd | 372 | nodes in the doubly-linked list specified by List. List must have been\r |
9aa049d9 | 373 | initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().\r |
e1f414b6 | 374 | \r |
375 | If List is NULL, then ASSERT().\r | |
376 | If Node is NULL, then ASSERT().\r | |
9aa049d9 | 377 | If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(), \r |
378 | then ASSERT().\r | |
e1f414b6 | 379 | If PcdMaximumLinkedListLenth is not zero, and the number of nodes\r |
380 | in List, including the List node, is greater than or equal to\r | |
381 | PcdMaximumLinkedListLength, then ASSERT().\r | |
1081f624 | 382 | If PcdVerifyNodeInList is TRUE and Node is not a node in List and Node is not \r |
383 | equal to List, then ASSERT().\r | |
e1f414b6 | 384 | \r |
127010dd | 385 | @param List A pointer to the head node of a doubly-linked list.\r |
386 | @param Node A pointer to a node in the doubly-linked list.\r | |
e1f414b6 | 387 | \r |
127010dd | 388 | @retval TRUE Node is one of the nodes in the doubly-linked list.\r |
389 | @retval FALSE Node is not one of the nodes in the doubly-linked list.\r | |
e1f414b6 | 390 | \r |
391 | **/\r | |
392 | BOOLEAN\r | |
393 | EFIAPI\r | |
394 | IsNull (\r | |
2fc60b70 | 395 | IN CONST LIST_ENTRY *List,\r |
396 | IN CONST LIST_ENTRY *Node\r | |
e1f414b6 | 397 | )\r |
398 | {\r | |
399 | //\r | |
400 | // ASSERT List not too long and Node is one of the nodes of List\r | |
401 | //\r | |
1081f624 | 402 | ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));\r |
403 | \r | |
e1f414b6 | 404 | return (BOOLEAN)(Node == List);\r |
405 | }\r | |
406 | \r | |
407 | /**\r | |
127010dd | 408 | Determines if a node the last node in a doubly-linked list.\r |
e1f414b6 | 409 | \r |
127010dd | 410 | Returns TRUE if Node is the last node in the doubly-linked list specified by\r |
e1f414b6 | 411 | List. Otherwise, FALSE is returned. List must have been initialized with\r |
9aa049d9 | 412 | INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().\r |
e1f414b6 | 413 | \r |
414 | If List is NULL, then ASSERT().\r | |
415 | If Node is NULL, then ASSERT().\r | |
9aa049d9 | 416 | If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or\r |
417 | InitializeListHead(), then ASSERT().\r | |
e1f414b6 | 418 | If PcdMaximumLinkedListLenth is not zero, and the number of nodes\r |
419 | in List, including the List node, is greater than or equal to\r | |
420 | PcdMaximumLinkedListLength, then ASSERT().\r | |
1081f624 | 421 | If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().\r |
e1f414b6 | 422 | \r |
127010dd | 423 | @param List A pointer to the head node of a doubly-linked list.\r |
424 | @param Node A pointer to a node in the doubly-linked list.\r | |
e1f414b6 | 425 | \r |
426 | @retval TRUE Node is the last node in the linked list.\r | |
427 | @retval FALSE Node is not the last node in the linked list.\r | |
428 | \r | |
429 | **/\r | |
430 | BOOLEAN\r | |
431 | EFIAPI\r | |
432 | IsNodeAtEnd (\r | |
2fc60b70 | 433 | IN CONST LIST_ENTRY *List,\r |
434 | IN CONST LIST_ENTRY *Node\r | |
e1f414b6 | 435 | )\r |
436 | {\r | |
437 | //\r | |
438 | // ASSERT List not too long and Node is one of the nodes of List\r | |
439 | //\r | |
1081f624 | 440 | ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));\r |
441 | \r | |
e1f414b6 | 442 | return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);\r |
443 | }\r | |
444 | \r | |
445 | /**\r | |
127010dd | 446 | Swaps the location of two nodes in a doubly-linked list, and returns the\r |
e1f414b6 | 447 | first node after the swap.\r |
448 | \r | |
449 | If FirstEntry is identical to SecondEntry, then SecondEntry is returned.\r | |
450 | Otherwise, the location of the FirstEntry node is swapped with the location\r | |
127010dd | 451 | of the SecondEntry node in a doubly-linked list. SecondEntry must be in the\r |
e1f414b6 | 452 | same double linked list as FirstEntry and that double linked list must have\r |
9aa049d9 | 453 | been initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(). \r |
454 | SecondEntry is returned after the nodes are swapped.\r | |
e1f414b6 | 455 | \r |
456 | If FirstEntry is NULL, then ASSERT().\r | |
457 | If SecondEntry is NULL, then ASSERT().\r | |
1081f624 | 458 | If PcdVerifyNodeInList is TRUE and SecondEntry and FirstEntry are not in the \r |
459 | same linked list, then ASSERT().\r | |
e1f414b6 | 460 | If PcdMaximumLinkedListLength is not zero, and the number of nodes in the\r |
461 | linked list containing the FirstEntry and SecondEntry nodes, including\r | |
462 | the FirstEntry and SecondEntry nodes, is greater than or equal to\r | |
463 | PcdMaximumLinkedListLength, then ASSERT().\r | |
464 | \r | |
465 | @param FirstEntry A pointer to a node in a linked list.\r | |
466 | @param SecondEntry A pointer to another node in the same linked list.\r | |
2fc60b70 | 467 | \r |
9aa049d9 | 468 | @return SecondEntry.\r |
e1f414b6 | 469 | \r |
470 | **/\r | |
471 | LIST_ENTRY *\r | |
472 | EFIAPI\r | |
473 | SwapListEntries (\r | |
2fc60b70 | 474 | IN OUT LIST_ENTRY *FirstEntry,\r |
475 | IN OUT LIST_ENTRY *SecondEntry\r | |
e1f414b6 | 476 | )\r |
477 | {\r | |
478 | LIST_ENTRY *Ptr;\r | |
479 | \r | |
480 | if (FirstEntry == SecondEntry) {\r | |
481 | return SecondEntry;\r | |
482 | }\r | |
483 | \r | |
484 | //\r | |
485 | // ASSERT Entry1 and Entry2 are in the same linked list\r | |
486 | //\r | |
1081f624 | 487 | ASSERT (InternalBaseLibIsNodeInList (FirstEntry, SecondEntry, TRUE));\r |
488 | \r | |
e1f414b6 | 489 | //\r |
490 | // Ptr is the node pointed to by FirstEntry->ForwardLink\r | |
491 | //\r | |
492 | Ptr = RemoveEntryList (FirstEntry);\r | |
493 | \r | |
494 | //\r | |
24dcb5e5 | 495 | // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed\r |
e1f414b6 | 496 | // immediately in front of SecondEntry\r |
497 | //\r | |
498 | if (Ptr->BackLink == SecondEntry) {\r | |
499 | return InsertTailList (SecondEntry, FirstEntry);\r | |
500 | }\r | |
501 | \r | |
502 | //\r | |
503 | // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,\r | |
504 | // then there are no further steps necessary\r | |
505 | //\r | |
506 | if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {\r | |
507 | return Ptr;\r | |
508 | }\r | |
509 | \r | |
510 | //\r | |
511 | // Move SecondEntry to the front of Ptr\r | |
512 | //\r | |
513 | RemoveEntryList (SecondEntry);\r | |
514 | InsertTailList (Ptr, SecondEntry);\r | |
515 | return SecondEntry;\r | |
516 | }\r | |
517 | \r | |
518 | /**\r | |
127010dd | 519 | Removes a node from a doubly-linked list, and returns the node that follows\r |
e1f414b6 | 520 | the removed node.\r |
521 | \r | |
127010dd | 522 | Removes the node Entry from a doubly-linked list. It is up to the caller of\r |
e1f414b6 | 523 | this function to release the memory used by this node if that is required. On\r |
127010dd | 524 | exit, the node following Entry in the doubly-linked list is returned. If\r |
e1f414b6 | 525 | Entry is the only node in the linked list, then the head node of the linked\r |
526 | list is returned.\r | |
527 | \r | |
528 | If Entry is NULL, then ASSERT().\r | |
529 | If Entry is the head node of an empty list, then ASSERT().\r | |
530 | If PcdMaximumLinkedListLength is not zero, and the number of nodes in the\r | |
531 | linked list containing Entry, including the Entry node, is greater than\r | |
532 | or equal to PcdMaximumLinkedListLength, then ASSERT().\r | |
533 | \r | |
9aa049d9 | 534 | @param Entry A pointer to a node in a linked list.\r |
e1f414b6 | 535 | \r |
9aa049d9 | 536 | @return Entry.\r |
e1f414b6 | 537 | \r |
538 | **/\r | |
539 | LIST_ENTRY *\r | |
540 | EFIAPI\r | |
541 | RemoveEntryList (\r | |
2fc60b70 | 542 | IN CONST LIST_ENTRY *Entry\r |
e1f414b6 | 543 | )\r |
544 | {\r | |
545 | ASSERT (!IsListEmpty (Entry));\r | |
1081f624 | 546 | \r |
e1f414b6 | 547 | Entry->ForwardLink->BackLink = Entry->BackLink;\r |
548 | Entry->BackLink->ForwardLink = Entry->ForwardLink;\r | |
549 | return Entry->ForwardLink;\r | |
550 | }\r |