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
40 InternalBaseLibIsNodeInList (
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 ListHead A pointer to the head node of a new doubly linked list.
96 IN OUT LIST_ENTRY
*ListHead
100 ASSERT (ListHead
!= NULL
);
102 ListHead
->ForwardLink
= ListHead
;
103 ListHead
->BackLink
= ListHead
;
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 INTIALIZE_LIST_HEAD_VARIABLE() or
117 InitializeListHead(), then ASSERT().
118 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
119 of nodes in ListHead, including the ListHead node, is greater than or
120 equal to PcdMaximumLinkedListLength, then ASSERT().
122 @param ListHead A pointer to the head node of a doubly linked list.
123 @param Entry A pointer to a node that is to be inserted at the beginning
124 of a doubly linked list.
132 IN OUT LIST_ENTRY
*ListHead
,
133 IN OUT LIST_ENTRY
*Entry
137 // ASSERT List not too long and Entry is not one of the nodes of List
139 ASSERT (!InternalBaseLibIsNodeInList (ListHead
, Entry
));
141 Entry
->ForwardLink
= ListHead
->ForwardLink
;
142 Entry
->BackLink
= ListHead
;
143 Entry
->ForwardLink
->BackLink
= Entry
;
144 ListHead
->ForwardLink
= Entry
;
149 Adds a node to the end of a doubly linked list, and returns the pointer to
150 the head node of the doubly linked list.
152 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
153 and returns ListHead.
155 If ListHead is NULL, then ASSERT().
156 If Entry is NULL, then ASSERT().
157 If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
158 InitializeListHead(), then ASSERT().
159 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
160 of nodes in ListHead, including the ListHead node, is greater than or
161 equal to PcdMaximumLinkedListLength, then ASSERT().
163 @param ListHead A pointer to the head node of a doubly linked list.
164 @param Entry A pointer to a node that is to be added at the end of the
173 IN OUT LIST_ENTRY
*ListHead
,
174 IN OUT LIST_ENTRY
*Entry
178 // ASSERT List not too long and Entry is not one of the nodes of List
180 ASSERT (!InternalBaseLibIsNodeInList (ListHead
, Entry
));
182 Entry
->ForwardLink
= ListHead
;
183 Entry
->BackLink
= ListHead
->BackLink
;
184 Entry
->BackLink
->ForwardLink
= Entry
;
185 ListHead
->BackLink
= Entry
;
190 Retrieves the first node of a doubly linked list.
192 Returns the first node of a doubly linked list. List must have been
193 initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
194 If List is empty, then List is returned.
196 If List is NULL, then ASSERT().
197 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
198 InitializeListHead(), then ASSERT().
199 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
200 in List, including the List node, is greater than or equal to
201 PcdMaximumLinkedListLength, then ASSERT().
203 @param List A pointer to the head node of a doubly linked list.
205 @return The first node of a doubly linked list.
206 @retval NULL The list is empty.
212 IN CONST LIST_ENTRY
*List
216 // ASSERT List not too long
218 ASSERT (InternalBaseLibIsNodeInList (List
, List
));
220 return List
->ForwardLink
;
224 Retrieves the next node of a doubly linked list.
226 Returns the node of a doubly linked list that follows Node.
227 List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()
228 or InitializeListHead(). If List is empty, then List is returned.
230 If List is NULL, then ASSERT().
231 If Node is NULL, then ASSERT().
232 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
233 InitializeListHead(), then ASSERT().
234 If PcdMaximumLinkedListLenth is not zero, and List contains more than
235 PcdMaximumLinkedListLenth nodes, then ASSERT().
236 If Node is not a node in List, then ASSERT().
238 @param List A pointer to the head node of a doubly linked list.
239 @param Node A pointer to a node in the doubly linked list.
241 @return Pointer to the next node if one exists. Otherwise a null value which
242 is actually List is returned.
248 IN CONST LIST_ENTRY
*List
,
249 IN CONST LIST_ENTRY
*Node
253 // ASSERT List not too long and Node is one of the nodes of List
255 ASSERT (InternalBaseLibIsNodeInList (List
, Node
));
257 return Node
->ForwardLink
;
261 Checks to see if a doubly linked list is empty or not.
263 Checks to see if the doubly linked list is empty. If the linked list contains
264 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
266 If ListHead is NULL, then ASSERT().
267 If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
268 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 ListHead 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
*ListHead
286 // ASSERT List not too long
288 ASSERT (InternalBaseLibIsNodeInList (ListHead
, ListHead
));
290 return (BOOLEAN
)(ListHead
->ForwardLink
== ListHead
);
294 Determines if a node in a doubly linked list is the head node of a the same
295 doubly linked list. This function is typically used to terminate a loop that
296 traverses all the nodes in a doubly linked list starting with the head node.
298 Returns TRUE if Node is equal to List. Returns FALSE if Node is one of the
299 nodes in the doubly linked list specified by List. List must have been
300 initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
302 If List is NULL, then ASSERT().
303 If Node is NULL, then ASSERT().
304 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(),
306 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
307 in List, including the List node, is greater than or equal to
308 PcdMaximumLinkedListLength, then ASSERT().
309 If Node is not a node in List and Node is not equal to List, then ASSERT().
311 @param List A pointer to the head node of a doubly linked list.
312 @param Node A pointer to a node in the doubly linked list.
314 @retval TRUE Node is one of the nodes in the doubly linked list.
315 @retval FALSE Node is not one of the nodes in the doubly linked list.
321 IN CONST LIST_ENTRY
*List
,
322 IN CONST LIST_ENTRY
*Node
326 // ASSERT List not too long and Node is one of the nodes of List
328 ASSERT (InternalBaseLibIsNodeInList (List
, Node
));
330 return (BOOLEAN
)(Node
== List
);
334 Determines if a node the last node in a doubly linked list.
336 Returns TRUE if Node is the last node in the doubly linked list specified by
337 List. Otherwise, FALSE is returned. List must have been initialized with
338 INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
340 If List is NULL, then ASSERT().
341 If Node is NULL, then ASSERT().
342 If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or
343 InitializeListHead(), then ASSERT().
344 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
345 in List, including the List node, is greater than or equal to
346 PcdMaximumLinkedListLength, then ASSERT().
347 If Node is not a node in List, then ASSERT().
349 @param List A pointer to the head node of a doubly linked list.
350 @param Node A pointer to a node in the doubly linked list.
352 @retval TRUE Node is the last node in the linked list.
353 @retval FALSE Node is not the last node in the linked list.
359 IN CONST LIST_ENTRY
*List
,
360 IN CONST LIST_ENTRY
*Node
364 // ASSERT List not too long and Node is one of the nodes of List
366 ASSERT (InternalBaseLibIsNodeInList (List
, Node
));
368 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
372 Swaps the location of two nodes in a doubly linked list, and returns the
373 first node after the swap.
375 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
376 Otherwise, the location of the FirstEntry node is swapped with the location
377 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
378 same double linked list as FirstEntry and that double linked list must have
379 been initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().
380 SecondEntry is returned after the nodes are swapped.
382 If FirstEntry is NULL, then ASSERT().
383 If SecondEntry is NULL, then ASSERT().
384 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
385 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
386 linked list containing the FirstEntry and SecondEntry nodes, including
387 the FirstEntry and SecondEntry nodes, is greater than or equal to
388 PcdMaximumLinkedListLength, then ASSERT().
390 @param FirstEntry A pointer to a node in a linked list.
391 @param SecondEntry A pointer to another node in the same linked list.
399 IN OUT LIST_ENTRY
*FirstEntry
,
400 IN OUT LIST_ENTRY
*SecondEntry
405 if (FirstEntry
== SecondEntry
) {
410 // ASSERT Entry1 and Entry2 are in the same linked list
412 ASSERT (InternalBaseLibIsNodeInList (FirstEntry
, SecondEntry
));
415 // Ptr is the node pointed to by FirstEntry->ForwardLink
417 Ptr
= RemoveEntryList (FirstEntry
);
420 // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed
421 // immediately in front of SecondEntry
423 if (Ptr
->BackLink
== SecondEntry
) {
424 return InsertTailList (SecondEntry
, FirstEntry
);
428 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
429 // then there are no further steps necessary
431 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
436 // Move SecondEntry to the front of Ptr
438 RemoveEntryList (SecondEntry
);
439 InsertTailList (Ptr
, SecondEntry
);
444 Removes a node from a doubly linked list, and returns the node that follows
447 Removes the node Entry from a doubly linked list. It is up to the caller of
448 this function to release the memory used by this node if that is required. On
449 exit, the node following Entry in the doubly linked list is returned. If
450 Entry is the only node in the linked list, then the head node of the linked
453 If Entry is NULL, then ASSERT().
454 If Entry is the head node of an empty list, then ASSERT().
455 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
456 linked list containing Entry, including the Entry node, is greater than
457 or equal to PcdMaximumLinkedListLength, then ASSERT().
459 @param Entry A pointer to a node in a linked list.
467 IN CONST LIST_ENTRY
*Entry
470 ASSERT (!IsListEmpty (Entry
));
472 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
473 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
474 return Entry
->ForwardLink
;