2 Linked List Library Functions.
4 Copyright (c) 2006, Intel Corporation<BR>
5 All rights reserved. This program and the accompanying materials
6 are licensed and made available under the terms and conditions of the BSD License
7 which accompanies this distribution. The full text of the license may be found at
8 http://opensource.org/licenses/bsd-license.php
10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
16 // Include common header file for this module.
20 #include "BaseLibInternals.h"
23 Worker function that locates the Node in the List
25 By searching the List, finds the location of the Node in List. At the same time,
26 verifies the validity of this list.
28 If List is NULL, then ASSERT().
29 If List->ForwardLink is NULL, then ASSERT().
30 If List->backLink is NULL, then ASSERT().
31 If Node is NULL, then ASSERT();
32 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
33 of nodes in ListHead, including the ListHead node, is greater than or
34 equal to PcdMaximumLinkedListLength, then ASSERT().
36 @param List A pointer to a node in a linked list.
37 @param Node A pointer to one nod.
39 @retval TRUE Node is in List
40 @retval FALSE Node isn't in List, or List is invalid
46 IN CONST LIST_ENTRY
*List
,
47 IN CONST LIST_ENTRY
*Node
51 CONST LIST_ENTRY
*Ptr
;
55 // Test the validity of List and Node
57 ASSERT (List
!= NULL
);
58 ASSERT (List
->ForwardLink
!= NULL
);
59 ASSERT (List
->BackLink
!= NULL
);
60 ASSERT (Node
!= NULL
);
62 Count
= PcdGet32 (PcdMaximumLinkedListLength
);
66 Ptr
= Ptr
->ForwardLink
;
68 } while ((Ptr
!= List
) && (Ptr
!= Node
) && (Count
> 0));
69 Found
= (BOOLEAN
)(Ptr
== Node
);
71 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
72 while ((Count
> 0) && (Ptr
!= List
)) {
73 Ptr
= Ptr
->ForwardLink
;
83 Initializes the head node of a doubly linked list, and returns the pointer to
84 the head node of the doubly linked list.
86 Initializes the forward and backward links of a new linked list. After
87 initializing a linked list with this function, the other linked list
88 functions may be used to add and remove nodes from the linked list. It is up
89 to the caller of this function to allocate the memory for ListHead.
91 If ListHead is NULL, then ASSERT().
93 @param List A pointer to the head node of a new doubly linked list.
101 IN OUT LIST_ENTRY
*List
105 ASSERT (List
!= NULL
);
107 List
->ForwardLink
= List
;
108 List
->BackLink
= List
;
113 Adds a node to the beginning of a doubly linked list, and returns the pointer
114 to the head node of the doubly linked list.
116 Adds the node Entry at the beginning of the doubly linked list denoted by
117 ListHead, and returns ListHead.
119 If ListHead is NULL, then ASSERT().
120 If Entry is NULL, then ASSERT().
121 If ListHead was not initialized with InitializeListHead(), then ASSERT().
122 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
123 of nodes in ListHead, including the ListHead node, is greater than or
124 equal to PcdMaximumLinkedListLength, then ASSERT().
126 @param List A pointer to the head node of a doubly linked list.
127 @param Entry A pointer to a node that is to be inserted at the beginning
128 of a doubly linked list.
136 IN OUT LIST_ENTRY
*List
,
137 IN OUT LIST_ENTRY
*Entry
141 // ASSERT List not too long and Entry is not one of the nodes of List
143 ASSERT (!IsNodeInList (List
, Entry
));
145 Entry
->ForwardLink
= List
->ForwardLink
;
146 Entry
->BackLink
= List
;
147 Entry
->ForwardLink
->BackLink
= Entry
;
148 List
->ForwardLink
= Entry
;
153 Adds a node to the end of a doubly linked list, and returns the pointer to
154 the head node of the doubly linked list.
156 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
157 and returns ListHead.
159 If ListHead is NULL, then ASSERT().
160 If Entry is NULL, then ASSERT().
161 If ListHead was not initialized with InitializeListHead(), then ASSERT().
162 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
163 of nodes in ListHead, including the ListHead node, is greater than or
164 equal to PcdMaximumLinkedListLength, then ASSERT().
166 @param List A pointer to the head node of a doubly linked list.
167 @param Entry A pointer to a node that is to be added at the end of the
176 IN OUT LIST_ENTRY
*List
,
177 IN OUT LIST_ENTRY
*Entry
181 // ASSERT List not too long and Entry is not one of the nodes of List
183 ASSERT (!IsNodeInList (List
, Entry
));
185 Entry
->ForwardLink
= List
;
186 Entry
->BackLink
= List
->BackLink
;
187 Entry
->BackLink
->ForwardLink
= Entry
;
188 List
->BackLink
= Entry
;
193 Retrieves the first node of a doubly linked list.
195 Returns the first node of a doubly linked list. List must have been
196 initialized with InitializeListHead(). If List is empty, then NULL is
199 If List is NULL, then ASSERT().
200 If List was not initialized with InitializeListHead(), then ASSERT().
201 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
202 in List, including the List node, is greater than or equal to
203 PcdMaximumLinkedListLength, then ASSERT().
205 @param List A pointer to the head node of a doubly linked list.
207 @return The first node of a doubly linked list.
208 @retval NULL The list is empty.
214 IN CONST LIST_ENTRY
*List
218 // ASSERT List not too long
220 ASSERT (IsNodeInList (List
, List
));
222 return List
->ForwardLink
;
226 Retrieves the next node of a doubly linked list.
228 Returns the node of a doubly linked list that follows Node. List must have
229 been initialized with InitializeListHead(). If List is empty, then List is
232 If List is NULL, then ASSERT().
233 If Node is NULL, then ASSERT().
234 If List was not initialized with InitializeListHead(), then ASSERT().
235 If PcdMaximumLinkedListLenth is not zero, and List contains more than
236 PcdMaximumLinkedListLenth nodes, then ASSERT().
237 If Node is not a node in List, then ASSERT().
239 @param List A pointer to the head node of a doubly linked list.
240 @param Node A pointer to a node in the doubly linked list.
242 @return Pointer to the next node if one exists. Otherwise a null value which
243 is actually List is returned.
249 IN CONST LIST_ENTRY
*List
,
250 IN CONST LIST_ENTRY
*Node
254 // ASSERT List not too long and Node is one of the nodes of List
256 ASSERT (IsNodeInList (List
, Node
));
258 return Node
->ForwardLink
;
262 Checks to see if a doubly linked list is empty or not.
264 Checks to see if the doubly linked list is empty. If the linked list contains
265 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
267 If ListHead is NULL, then ASSERT().
268 If ListHead was not initialized with InitializeListHead(), then ASSERT().
269 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
270 in List, including the List node, is greater than or equal to
271 PcdMaximumLinkedListLength, then ASSERT().
273 @param List A pointer to the head node of a doubly linked list.
275 @retval TRUE The linked list is empty.
276 @retval FALSE The linked list is not empty.
282 IN CONST LIST_ENTRY
*List
286 // ASSERT List not too long
288 ASSERT (IsNodeInList (List
, List
));
290 return (BOOLEAN
)(List
->ForwardLink
== List
);
294 Determines if a node in a doubly linked list is null.
296 Returns FALSE if Node is one of the nodes in the doubly linked list specified
297 by List. Otherwise, TRUE is returned. List must have been initialized with
298 InitializeListHead().
300 If List is NULL, then ASSERT().
301 If Node is NULL, then ASSERT().
302 If List was not initialized with InitializeListHead(), then ASSERT().
303 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
304 in List, including the List node, is greater than or equal to
305 PcdMaximumLinkedListLength, then ASSERT().
306 If Node is not a node in List and Node is not equal to List, then ASSERT().
308 @param List A pointer to the head node of a doubly linked list.
309 @param Node A pointer to a node in the doubly linked list.
311 @retval TRUE Node is one of the nodes in the doubly linked list.
312 @retval FALSE Node is not one of the nodes in the doubly linked list.
318 IN CONST LIST_ENTRY
*List
,
319 IN CONST LIST_ENTRY
*Node
323 // ASSERT List not too long and Node is one of the nodes of List
325 ASSERT (IsNodeInList (List
, Node
));
327 return (BOOLEAN
)(Node
== List
);
331 Determines if a node the last node in a doubly linked list.
333 Returns TRUE if Node is the last node in the doubly linked list specified by
334 List. Otherwise, FALSE is returned. List must have been initialized with
335 InitializeListHead().
337 If List is NULL, then ASSERT().
338 If Node is NULL, then ASSERT().
339 If List was not initialized with InitializeListHead(), then ASSERT().
340 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
341 in List, including the List node, is greater than or equal to
342 PcdMaximumLinkedListLength, then ASSERT().
343 If Node is not a node in List, then ASSERT().
345 @param List A pointer to the head node of a doubly linked list.
346 @param Node A pointer to a node in the doubly linked list.
348 @retval TRUE Node is the last node in the linked list.
349 @retval FALSE Node is not the last node in the linked list.
355 IN CONST LIST_ENTRY
*List
,
356 IN CONST LIST_ENTRY
*Node
360 // ASSERT List not too long and Node is one of the nodes of List
362 ASSERT (IsNodeInList (List
, Node
));
364 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
368 Swaps the location of two nodes in a doubly linked list, and returns the
369 first node after the swap.
371 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
372 Otherwise, the location of the FirstEntry node is swapped with the location
373 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
374 same double linked list as FirstEntry and that double linked list must have
375 been initialized with InitializeListHead(). SecondEntry is returned after the
378 If FirstEntry is NULL, then ASSERT().
379 If SecondEntry is NULL, then ASSERT().
380 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
381 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
382 linked list containing the FirstEntry and SecondEntry nodes, including
383 the FirstEntry and SecondEntry nodes, is greater than or equal to
384 PcdMaximumLinkedListLength, then ASSERT().
386 @param FirstEntry A pointer to a node in a linked list.
387 @param SecondEntry A pointer to another node in the same linked list.
395 IN OUT LIST_ENTRY
*FirstEntry
,
396 IN OUT LIST_ENTRY
*SecondEntry
401 if (FirstEntry
== SecondEntry
) {
406 // ASSERT Entry1 and Entry2 are in the same linked list
408 ASSERT (IsNodeInList (FirstEntry
, SecondEntry
));
411 // Ptr is the node pointed to by FirstEntry->ForwardLink
413 Ptr
= RemoveEntryList (FirstEntry
);
416 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
417 // immediately in front of SecondEntry
419 if (Ptr
->BackLink
== SecondEntry
) {
420 return InsertTailList (SecondEntry
, FirstEntry
);
424 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
425 // then there are no further steps necessary
427 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
432 // Move SecondEntry to the front of Ptr
434 RemoveEntryList (SecondEntry
);
435 InsertTailList (Ptr
, SecondEntry
);
440 Removes a node from a doubly linked list, and returns the node that follows
443 Removes the node Entry from a doubly linked list. It is up to the caller of
444 this function to release the memory used by this node if that is required. On
445 exit, the node following Entry in the doubly linked list is returned. If
446 Entry is the only node in the linked list, then the head node of the linked
449 If Entry is NULL, then ASSERT().
450 If Entry is the head node of an empty list, then ASSERT().
451 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
452 linked list containing Entry, including the Entry node, is greater than
453 or equal to PcdMaximumLinkedListLength, then ASSERT().
455 @param Entry A pointer to a node in a linked list
463 IN CONST LIST_ENTRY
*Entry
466 ASSERT (!IsListEmpty (Entry
));
468 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
469 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
470 return Entry
->ForwardLink
;