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
45 IN CONST LIST_ENTRY
*List
,
46 IN CONST LIST_ENTRY
*Node
50 CONST LIST_ENTRY
*Ptr
;
54 // Test the validity of List and Node
56 ASSERT (List
!= NULL
);
57 ASSERT (List
->ForwardLink
!= NULL
);
58 ASSERT (List
->BackLink
!= NULL
);
59 ASSERT (Node
!= NULL
);
61 Count
= PcdGet32 (PcdMaximumLinkedListLength
);
65 Ptr
= Ptr
->ForwardLink
;
67 } while ((Ptr
!= List
) && (Ptr
!= Node
) && (Count
> 0));
68 Found
= (BOOLEAN
)(Ptr
== Node
);
70 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
71 while ((Count
> 0) && (Ptr
!= List
)) {
72 Ptr
= Ptr
->ForwardLink
;
82 Initializes the head node of a doubly linked list, and returns the pointer to
83 the head node of the doubly linked list.
85 Initializes the forward and backward links of a new linked list. After
86 initializing a linked list with this function, the other linked list
87 functions may be used to add and remove nodes from the linked list. It is up
88 to the caller of this function to allocate the memory for ListHead.
90 If ListHead is NULL, then ASSERT().
92 @param ListHead A pointer to the head node of a new doubly linked list.
100 IN OUT LIST_ENTRY
*List
104 ASSERT (List
!= NULL
);
106 List
->ForwardLink
= List
;
107 List
->BackLink
= List
;
112 Adds a node to the beginning of a doubly linked list, and returns the pointer
113 to the head node of the doubly linked list.
115 Adds the node Entry at the beginning of the doubly linked list denoted by
116 ListHead, and returns ListHead.
118 If ListHead is NULL, then ASSERT().
119 If Entry is NULL, then ASSERT().
120 If ListHead was not initialized with InitializeListHead(), then ASSERT().
121 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
122 of nodes in ListHead, including the ListHead node, is greater than or
123 equal to PcdMaximumLinkedListLength, then ASSERT().
125 @param ListHead A pointer to the head node of a doubly linked list.
126 @param Entry A pointer to a node that is to be inserted at the beginning
127 of a doubly linked list.
135 IN OUT LIST_ENTRY
*List
,
136 IN OUT LIST_ENTRY
*Entry
140 // ASSERT List not too long and Entry is not one of the nodes of List
142 ASSERT (!IsNodeInList (List
, Entry
));
144 Entry
->ForwardLink
= List
->ForwardLink
;
145 Entry
->BackLink
= List
;
146 Entry
->ForwardLink
->BackLink
= Entry
;
147 List
->ForwardLink
= Entry
;
152 Adds a node to the end of a doubly linked list, and returns the pointer to
153 the head node of the doubly linked list.
155 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
156 and returns ListHead.
158 If ListHead is NULL, then ASSERT().
159 If Entry is NULL, then ASSERT().
160 If ListHead was not initialized with InitializeListHead(), then ASSERT().
161 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
162 of nodes in ListHead, including the ListHead node, is greater than or
163 equal to PcdMaximumLinkedListLength, then ASSERT().
165 @param ListHead A pointer to the head node of a doubly linked list.
166 @param Entry A pointer to a node that is to be added at the end of the
175 IN OUT LIST_ENTRY
*List
,
176 IN OUT LIST_ENTRY
*Entry
180 // ASSERT List not too long and Entry is not one of the nodes of List
182 ASSERT (!IsNodeInList (List
, Entry
));
184 Entry
->ForwardLink
= List
;
185 Entry
->BackLink
= List
->BackLink
;
186 Entry
->BackLink
->ForwardLink
= Entry
;
187 List
->BackLink
= Entry
;
192 Retrieves the first node of a doubly linked list.
194 Returns the first node of a doubly linked list. List must have been
195 initialized with InitializeListHead(). If List is empty, then NULL is
198 If List is NULL, then ASSERT().
199 If List was not initialized with InitializeListHead(), then ASSERT().
200 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
201 in List, including the List node, is greater than or equal to
202 PcdMaximumLinkedListLength, then ASSERT().
204 @param List A pointer to the head node of a doubly linked list.
206 @return The first node of a doubly linked list.
207 @retval NULL The list is empty.
213 IN CONST LIST_ENTRY
*List
217 // ASSERT List not too long
219 ASSERT (IsNodeInList (List
, List
));
221 return List
->ForwardLink
;
225 Retrieves the next node of a doubly linked list.
227 Returns the node of a doubly linked list that follows Node. List must have
228 been initialized with InitializeListHead(). If List is empty, then List is
231 If List is NULL, then ASSERT().
232 If Node is NULL, then ASSERT().
233 If List was not initialized with 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 (IsNodeInList (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 InitializeListHead(), then ASSERT().
268 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
269 in List, including the List node, is greater than or equal to
270 PcdMaximumLinkedListLength, then ASSERT().
272 @param ListHead A pointer to the head node of a doubly linked list.
274 @retval TRUE The linked list is empty.
275 @retval FALSE The linked list is not empty.
281 IN CONST LIST_ENTRY
*List
285 // ASSERT List not too long
287 ASSERT (IsNodeInList (List
, List
));
289 return (BOOLEAN
)(List
->ForwardLink
== List
);
293 Determines if a node in a doubly linked list is null.
295 Returns FALSE if Node is one of the nodes in the doubly linked list specified
296 by List. Otherwise, TRUE is returned. List must have been initialized with
297 InitializeListHead().
299 If List is NULL, then ASSERT().
300 If Node is NULL, then ASSERT().
301 If List was not initialized with InitializeListHead(), then ASSERT().
302 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
303 in List, including the List node, is greater than or equal to
304 PcdMaximumLinkedListLength, then ASSERT().
305 If Node is not a node in List and Node is not equal to List, then ASSERT().
307 @param List A pointer to the head node of a doubly linked list.
308 @param Node A pointer to a node in the doubly linked list.
310 @retval TRUE Node is one of the nodes in the doubly linked list.
311 @retval FALSE Node is not one of the nodes in the doubly linked list.
317 IN CONST LIST_ENTRY
*List
,
318 IN CONST LIST_ENTRY
*Node
322 // ASSERT List not too long and Node is one of the nodes of List
324 ASSERT (IsNodeInList (List
, Node
));
326 return (BOOLEAN
)(Node
== List
);
330 Determines if a node the last node in a doubly linked list.
332 Returns TRUE if Node is the last node in the doubly linked list specified by
333 List. Otherwise, FALSE is returned. List must have been initialized with
334 InitializeListHead().
336 If List is NULL, then ASSERT().
337 If Node is NULL, then ASSERT().
338 If List was not initialized with InitializeListHead(), then ASSERT().
339 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
340 in List, including the List node, is greater than or equal to
341 PcdMaximumLinkedListLength, then ASSERT().
342 If Node is not a node in List, then ASSERT().
344 @param List A pointer to the head node of a doubly linked list.
345 @param Node A pointer to a node in the doubly linked list.
347 @retval TRUE Node is the last node in the linked list.
348 @retval FALSE Node is not the last node in the linked list.
354 IN CONST LIST_ENTRY
*List
,
355 IN CONST LIST_ENTRY
*Node
359 // ASSERT List not too long and Node is one of the nodes of List
361 ASSERT (IsNodeInList (List
, Node
));
363 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
367 Swaps the location of two nodes in a doubly linked list, and returns the
368 first node after the swap.
370 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
371 Otherwise, the location of the FirstEntry node is swapped with the location
372 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
373 same double linked list as FirstEntry and that double linked list must have
374 been initialized with InitializeListHead(). SecondEntry is returned after the
377 If FirstEntry is NULL, then ASSERT().
378 If SecondEntry is NULL, then ASSERT().
379 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
380 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
381 linked list containing the FirstEntry and SecondEntry nodes, including
382 the FirstEntry and SecondEntry nodes, is greater than or equal to
383 PcdMaximumLinkedListLength, then ASSERT().
385 @param FirstEntry A pointer to a node in a linked list.
386 @param SecondEntry A pointer to another node in the same linked list.
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 willl 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
460 IN CONST LIST_ENTRY
*Entry
463 ASSERT (!IsListEmpty (Entry
));
465 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
466 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
467 return Entry
->ForwardLink
;