2 Linked List Library Functions.
4 Copyright (c) 2006 - 2008, 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.
15 #include "BaseLibInternals.h"
18 Worker function that locates the Node in the List
20 By searching the List, finds the location of the Node in List. At the same time,
21 verifies the validity of this list.
23 If List is NULL, then ASSERT().
24 If List->ForwardLink is NULL, then ASSERT().
25 If List->BackLink is NULL, then ASSERT().
26 If Node is NULL, then ASSERT();
27 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
28 of nodes in ListHead, including the ListHead node, is greater than or
29 equal to PcdMaximumLinkedListLength, then ASSERT().
31 @param List A pointer to a node in a linked list.
32 @param Node A pointer to one nod.
34 @retval TRUE Node is in List
35 @retval FALSE Node isn't in List, or List is invalid
41 IN CONST LIST_ENTRY
*List
,
42 IN CONST LIST_ENTRY
*Node
46 CONST LIST_ENTRY
*Ptr
;
50 // Test the validity of List and Node
52 ASSERT (List
!= NULL
);
53 ASSERT (List
->ForwardLink
!= NULL
);
54 ASSERT (List
->BackLink
!= NULL
);
55 ASSERT (Node
!= NULL
);
57 Count
= PcdGet32 (PcdMaximumLinkedListLength
);
61 Ptr
= Ptr
->ForwardLink
;
63 } while ((Ptr
!= List
) && (Ptr
!= Node
) && (Count
> 0));
64 Found
= (BOOLEAN
)(Ptr
== Node
);
66 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
67 while ((Count
> 0) && (Ptr
!= List
)) {
68 Ptr
= Ptr
->ForwardLink
;
78 Initializes the head node of a doubly linked list, and returns the pointer to
79 the head node of the doubly linked list.
81 Initializes the forward and backward links of a new linked list. After
82 initializing a linked list with this function, the other linked list
83 functions may be used to add and remove nodes from the linked list. It is up
84 to the caller of this function to allocate the memory for ListHead.
86 If ListHead is NULL, then ASSERT().
88 @param List A pointer to the head node of a new doubly linked list.
96 IN OUT LIST_ENTRY
*List
100 ASSERT (List
!= NULL
);
102 List
->ForwardLink
= List
;
103 List
->BackLink
= List
;
108 Adds a node to the beginning of a doubly linked list, and returns the pointer
109 to the head node of the doubly linked list.
111 Adds the node Entry at the beginning of the doubly linked list denoted by
112 ListHead, and returns ListHead.
114 If ListHead is NULL, then ASSERT().
115 If Entry is NULL, then ASSERT().
116 If ListHead was not initialized with InitializeListHead(), then ASSERT().
117 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
118 of nodes in ListHead, including the ListHead node, is greater than or
119 equal to PcdMaximumLinkedListLength, then ASSERT().
121 @param List A pointer to the head node of a doubly linked list.
122 @param Entry A pointer to a node that is to be inserted at the beginning
123 of a doubly linked list.
131 IN OUT LIST_ENTRY
*List
,
132 IN OUT LIST_ENTRY
*Entry
136 // ASSERT List not too long and Entry is not one of the nodes of List
138 ASSERT (!IsNodeInList (List
, Entry
));
140 Entry
->ForwardLink
= List
->ForwardLink
;
141 Entry
->BackLink
= List
;
142 Entry
->ForwardLink
->BackLink
= Entry
;
143 List
->ForwardLink
= Entry
;
148 Adds a node to the end of a doubly linked list, and returns the pointer to
149 the head node of the doubly linked list.
151 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
152 and returns ListHead.
154 If ListHead is NULL, then ASSERT().
155 If Entry is NULL, then ASSERT().
156 If ListHead was not initialized with InitializeListHead(), then ASSERT().
157 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
158 of nodes in ListHead, including the ListHead node, is greater than or
159 equal to PcdMaximumLinkedListLength, then ASSERT().
161 @param List A pointer to the head node of a doubly linked list.
162 @param Entry A pointer to a node that is to be added at the end of the
171 IN OUT LIST_ENTRY
*List
,
172 IN OUT LIST_ENTRY
*Entry
176 // ASSERT List not too long and Entry is not one of the nodes of List
178 ASSERT (!IsNodeInList (List
, Entry
));
180 Entry
->ForwardLink
= List
;
181 Entry
->BackLink
= List
->BackLink
;
182 Entry
->BackLink
->ForwardLink
= Entry
;
183 List
->BackLink
= Entry
;
188 Retrieves the first node of a doubly linked list.
190 Returns the first node of a doubly linked list. List must have been
191 initialized with InitializeListHead(). If List is empty, then NULL is
194 If List is NULL, then ASSERT().
195 If List was not initialized with InitializeListHead(), then ASSERT().
196 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
197 in List, including the List node, is greater than or equal to
198 PcdMaximumLinkedListLength, then ASSERT().
200 @param List A pointer to the head node of a doubly linked list.
202 @return The first node of a doubly linked list.
203 @retval NULL The list is empty.
209 IN CONST LIST_ENTRY
*List
213 // ASSERT List not too long
215 ASSERT (IsNodeInList (List
, List
));
217 return List
->ForwardLink
;
221 Retrieves the next node of a doubly linked list.
223 Returns the node of a doubly linked list that follows Node. List must have
224 been initialized with InitializeListHead(). If List is empty, then List is
227 If List is NULL, then ASSERT().
228 If Node is NULL, then ASSERT().
229 If List was not initialized with InitializeListHead(), then ASSERT().
230 If PcdMaximumLinkedListLenth is not zero, and List contains more than
231 PcdMaximumLinkedListLenth nodes, then ASSERT().
232 If Node is not a node in List, then ASSERT().
234 @param List A pointer to the head node of a doubly linked list.
235 @param Node A pointer to a node in the doubly linked list.
237 @return Pointer to the next node if one exists. Otherwise a null value which
238 is actually List is returned.
244 IN CONST LIST_ENTRY
*List
,
245 IN CONST LIST_ENTRY
*Node
249 // ASSERT List not too long and Node is one of the nodes of List
251 ASSERT (IsNodeInList (List
, Node
));
253 return Node
->ForwardLink
;
257 Checks to see if a doubly linked list is empty or not.
259 Checks to see if the doubly linked list is empty. If the linked list contains
260 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
262 If ListHead is NULL, then ASSERT().
263 If ListHead was not initialized with InitializeListHead(), then ASSERT().
264 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
265 in List, including the List node, is greater than or equal to
266 PcdMaximumLinkedListLength, then ASSERT().
268 @param List A pointer to the head node of a doubly linked list.
270 @retval TRUE The linked list is empty.
271 @retval FALSE The linked list is not empty.
277 IN CONST LIST_ENTRY
*List
281 // ASSERT List not too long
283 ASSERT (IsNodeInList (List
, List
));
285 return (BOOLEAN
)(List
->ForwardLink
== List
);
289 Determines if a node in a doubly linked list is the head node of a the same
290 doubly linked list. This function is typically used to terminate a loop that
291 traverses all the nodes in a doubly linked list starting with the head node.
293 Returns TRUE if Node is equal to List. Returns FALSE if Node is one of the
294 nodes in the doubly linked list specified by List. List must have been
295 initialized with InitializeListHead().
297 If List is NULL, then ASSERT().
298 If Node is NULL, then ASSERT().
299 If List was not initialized with InitializeListHead(), then ASSERT().
300 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
301 in List, including the List node, is greater than or equal to
302 PcdMaximumLinkedListLength, then ASSERT().
303 If Node is not a node in List and Node is not equal to List, then ASSERT().
305 @param List A pointer to the head node of a doubly linked list.
306 @param Node A pointer to a node in the doubly linked list.
308 @retval TRUE Node is one of the nodes in the doubly linked list.
309 @retval FALSE Node is not one of the nodes in the doubly linked list.
315 IN CONST LIST_ENTRY
*List
,
316 IN CONST LIST_ENTRY
*Node
320 // ASSERT List not too long and Node is one of the nodes of List
322 ASSERT (IsNodeInList (List
, Node
));
324 return (BOOLEAN
)(Node
== List
);
328 Determines if a node the last node in a doubly linked list.
330 Returns TRUE if Node is the last node in the doubly linked list specified by
331 List. Otherwise, FALSE is returned. List must have been initialized with
332 InitializeListHead().
334 If List is NULL, then ASSERT().
335 If Node is NULL, then ASSERT().
336 If List was not initialized with InitializeListHead(), then ASSERT().
337 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
338 in List, including the List node, is greater than or equal to
339 PcdMaximumLinkedListLength, then ASSERT().
340 If Node is not a node in List, then ASSERT().
342 @param List A pointer to the head node of a doubly linked list.
343 @param Node A pointer to a node in the doubly linked list.
345 @retval TRUE Node is the last node in the linked list.
346 @retval FALSE Node is not the last node in the linked list.
352 IN CONST LIST_ENTRY
*List
,
353 IN CONST LIST_ENTRY
*Node
357 // ASSERT List not too long and Node is one of the nodes of List
359 ASSERT (IsNodeInList (List
, Node
));
361 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
365 Swaps the location of two nodes in a doubly linked list, and returns the
366 first node after the swap.
368 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
369 Otherwise, the location of the FirstEntry node is swapped with the location
370 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
371 same double linked list as FirstEntry and that double linked list must have
372 been initialized with InitializeListHead(). SecondEntry is returned after the
375 If FirstEntry is NULL, then ASSERT().
376 If SecondEntry is NULL, then ASSERT().
377 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
378 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
379 linked list containing the FirstEntry and SecondEntry nodes, including
380 the FirstEntry and SecondEntry nodes, is greater than or equal to
381 PcdMaximumLinkedListLength, then ASSERT().
383 @param FirstEntry A pointer to a node in a linked list.
384 @param SecondEntry A pointer to another node in the same linked list.
386 @return SecondEntry after the nodes are swapped
392 IN OUT LIST_ENTRY
*FirstEntry
,
393 IN OUT LIST_ENTRY
*SecondEntry
398 if (FirstEntry
== SecondEntry
) {
403 // ASSERT Entry1 and Entry2 are in the same linked list
405 ASSERT (IsNodeInList (FirstEntry
, SecondEntry
));
408 // Ptr is the node pointed to by FirstEntry->ForwardLink
410 Ptr
= RemoveEntryList (FirstEntry
);
413 // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
414 // immediately in front of SecondEntry
416 if (Ptr
->BackLink
== SecondEntry
) {
417 return InsertTailList (SecondEntry
, FirstEntry
);
421 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
422 // then there are no further steps necessary
424 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
429 // Move SecondEntry to the front of Ptr
431 RemoveEntryList (SecondEntry
);
432 InsertTailList (Ptr
, SecondEntry
);
437 Removes a node from a doubly linked list, and returns the node that follows
440 Removes the node Entry from a doubly linked list. It is up to the caller of
441 this function to release the memory used by this node if that is required. On
442 exit, the node following Entry in the doubly linked list is returned. If
443 Entry is the only node in the linked list, then the head node of the linked
446 If Entry is NULL, then ASSERT().
447 If Entry is the head node of an empty list, then ASSERT().
448 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
449 linked list containing Entry, including the Entry node, is greater than
450 or equal to PcdMaximumLinkedListLength, then ASSERT().
452 @param Entry A pointer to a node in a linked list
454 @return The node following Entry in the doubly linked list.
455 If Entry is the only node in the linked list, then
456 the head node of the linked list is returned.
462 IN CONST LIST_ENTRY
*Entry
465 ASSERT (!IsListEmpty (Entry
));
467 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
468 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
469 return Entry
->ForwardLink
;