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.
13 Module Name: LinkedList.c
17 #include "BaseLibInternals.h"
20 Worker function that locates the Node in the List
22 By searching the List, finds the location of the Node in List. At the same time,
23 verifies the validity of this list.
25 If List is NULL, then ASSERT().
26 If List->ForwardLink is NULL, then ASSERT().
27 If List->backLink is NULL, then ASSERT().
28 If Node is NULL, then ASSERT();
29 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
30 of nodes in ListHead, including the ListHead node, is greater than or
31 equal to PcdMaximumLinkedListLength, then ASSERT().
33 @param List A pointer to a node in a linked list.
34 @param Node A pointer to one nod.
36 @retval TRUE Node is in List
37 @retval FALSE Node isn't in List, or List is invalid
42 IN CONST LIST_ENTRY
*List
,
43 IN CONST LIST_ENTRY
*Node
47 CONST LIST_ENTRY
*Ptr
;
51 // Test the validity of List and Node
53 ASSERT (List
!= NULL
);
54 ASSERT (List
->ForwardLink
!= NULL
);
55 ASSERT (List
->BackLink
!= NULL
);
56 ASSERT (Node
!= NULL
);
58 Count
= PcdGet32 (PcdMaximumLinkedListLength
);
62 Ptr
= Ptr
->ForwardLink
;
64 } while ((Ptr
!= List
) && (Ptr
!= Node
) && (Count
> 0));
65 Found
= (BOOLEAN
)(Ptr
== Node
);
67 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
68 while ((Count
> 0) && (Ptr
!= List
)) {
69 Ptr
= Ptr
->ForwardLink
;
79 Initializes the head node of a doubly linked list, and returns the pointer to
80 the head node of the doubly linked list.
82 Initializes the forward and backward links of a new linked list. After
83 initializing a linked list with this function, the other linked list
84 functions may be used to add and remove nodes from the linked list. It is up
85 to the caller of this function to allocate the memory for ListHead.
87 If ListHead is NULL, then ASSERT().
89 @param ListHead A pointer to the head node of a new doubly linked list.
97 IN OUT LIST_ENTRY
*List
101 ASSERT (List
!= NULL
);
103 List
->ForwardLink
= List
;
104 List
->BackLink
= List
;
109 Adds a node to the beginning of a doubly linked list, and returns the pointer
110 to the head node of the doubly linked list.
112 Adds the node Entry at the beginning of the doubly linked list denoted by
113 ListHead, and returns ListHead.
115 If ListHead is NULL, then ASSERT().
116 If Entry is NULL, then ASSERT().
117 If ListHead was not initialized with 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
*List
,
133 IN OUT LIST_ENTRY
*Entry
137 // ASSERT List not too long and Entry is not one of the nodes of List
139 ASSERT (!IsNodeInList (List
, Entry
));
141 Entry
->ForwardLink
= List
->ForwardLink
;
142 Entry
->BackLink
= List
;
143 Entry
->ForwardLink
->BackLink
= Entry
;
144 List
->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 InitializeListHead(), then ASSERT().
158 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
159 of nodes in ListHead, including the ListHead node, is greater than or
160 equal to PcdMaximumLinkedListLength, then ASSERT().
162 @param ListHead A pointer to the head node of a doubly linked list.
163 @param Entry A pointer to a node that is to be added at the end of the
172 IN OUT LIST_ENTRY
*List
,
173 IN OUT LIST_ENTRY
*Entry
177 // ASSERT List not too long and Entry is not one of the nodes of List
179 ASSERT (!IsNodeInList (List
, Entry
));
181 Entry
->ForwardLink
= List
;
182 Entry
->BackLink
= List
->BackLink
;
183 Entry
->BackLink
->ForwardLink
= Entry
;
184 List
->BackLink
= Entry
;
189 Retrieves the first node of a doubly linked list.
191 Returns the first node of a doubly linked list. List must have been
192 initialized with InitializeListHead(). If List is empty, then NULL is
195 If List is NULL, then ASSERT().
196 If List was not initialized with InitializeListHead(), then ASSERT().
197 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
198 in List, including the List node, is greater than or equal to
199 PcdMaximumLinkedListLength, then ASSERT().
201 @param List A pointer to the head node of a doubly linked list.
203 @return The first node of a doubly linked list.
204 @retval NULL The list is empty.
210 IN CONST LIST_ENTRY
*List
214 // ASSERT List not too long
216 ASSERT (IsNodeInList (List
, List
));
218 return List
->ForwardLink
;
222 Retrieves the next node of a doubly linked list.
224 Returns the node of a doubly linked list that follows Node. List must have
225 been initialized with InitializeListHead(). If List is empty, then List is
228 If List is NULL, then ASSERT().
229 If Node is NULL, then ASSERT().
230 If List was not initialized with InitializeListHead(), then ASSERT().
231 If PcdMaximumLinkedListLenth is not zero, and List contains more than
232 PcdMaximumLinkedListLenth nodes, then ASSERT().
233 If Node is not a node in List, then ASSERT().
235 @param List A pointer to the head node of a doubly linked list.
236 @param Node A pointer to a node in the doubly linked list.
238 @return Pointer to the next node if one exists. Otherwise a null value which
239 is actually List is returned.
245 IN CONST LIST_ENTRY
*List
,
246 IN CONST LIST_ENTRY
*Node
250 // ASSERT List not too long and Node is one of the nodes of List
252 ASSERT (IsNodeInList (List
, Node
));
254 return Node
->ForwardLink
;
258 Checks to see if a doubly linked list is empty or not.
260 Checks to see if the doubly linked list is empty. If the linked list contains
261 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
263 If ListHead is NULL, then ASSERT().
264 If ListHead was not initialized with InitializeListHead(), then ASSERT().
265 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
266 in List, including the List node, is greater than or equal to
267 PcdMaximumLinkedListLength, then ASSERT().
269 @param ListHead A pointer to the head node of a doubly linked list.
271 @retval TRUE The linked list is empty.
272 @retval FALSE The linked list is not empty.
278 IN CONST LIST_ENTRY
*List
282 // ASSERT List not too long
284 ASSERT (IsNodeInList (List
, List
));
286 return (BOOLEAN
)(List
->ForwardLink
== List
);
290 Determines if a node in a doubly linked list is null.
292 Returns FALSE if Node is one of the nodes in the doubly linked list specified
293 by List. Otherwise, TRUE is returned. List must have been initialized with
294 InitializeListHead().
296 If List is NULL, then ASSERT().
297 If Node is NULL, then ASSERT().
298 If List was not initialized with InitializeListHead(), then ASSERT().
299 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
300 in List, including the List node, is greater than or equal to
301 PcdMaximumLinkedListLength, then ASSERT().
302 If Node is not a node in List and Node is not equal to List, then ASSERT().
304 @param List A pointer to the head node of a doubly linked list.
305 @param Node A pointer to a node in the doubly linked list.
307 @retval TRUE Node is one of the nodes in the doubly linked list.
308 @retval FALSE Node is not one of the nodes in the doubly linked list.
314 IN CONST LIST_ENTRY
*List
,
315 IN CONST LIST_ENTRY
*Node
319 // ASSERT List not too long and Node is one of the nodes of List
321 ASSERT (IsNodeInList (List
, Node
));
323 return (BOOLEAN
)(Node
== List
);
327 Determines if a node the last node in a doubly linked list.
329 Returns TRUE if Node is the last node in the doubly linked list specified by
330 List. Otherwise, FALSE is returned. List must have been initialized with
331 InitializeListHead().
333 If List is NULL, then ASSERT().
334 If Node is NULL, then ASSERT().
335 If List was not initialized with InitializeListHead(), then ASSERT().
336 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
337 in List, including the List node, is greater than or equal to
338 PcdMaximumLinkedListLength, then ASSERT().
339 If Node is not a node in List, then ASSERT().
341 @param List A pointer to the head node of a doubly linked list.
342 @param Node A pointer to a node in the doubly linked list.
344 @retval TRUE Node is the last node in the linked list.
345 @retval FALSE Node is not the last node in the linked list.
351 IN CONST LIST_ENTRY
*List
,
352 IN CONST LIST_ENTRY
*Node
356 // ASSERT List not too long and Node is one of the nodes of List
358 ASSERT (IsNodeInList (List
, Node
));
360 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
364 Swaps the location of two nodes in a doubly linked list, and returns the
365 first node after the swap.
367 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
368 Otherwise, the location of the FirstEntry node is swapped with the location
369 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
370 same double linked list as FirstEntry and that double linked list must have
371 been initialized with InitializeListHead(). SecondEntry is returned after the
374 If FirstEntry is NULL, then ASSERT().
375 If SecondEntry is NULL, then ASSERT().
376 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
377 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
378 linked list containing the FirstEntry and SecondEntry nodes, including
379 the FirstEntry and SecondEntry nodes, is greater than or equal to
380 PcdMaximumLinkedListLength, then ASSERT().
382 @param FirstEntry A pointer to a node in a linked list.
383 @param SecondEntry A pointer to another node in the same linked list.
389 IN OUT LIST_ENTRY
*FirstEntry
,
390 IN OUT LIST_ENTRY
*SecondEntry
395 if (FirstEntry
== SecondEntry
) {
400 // ASSERT Entry1 and Entry2 are in the same linked list
402 ASSERT (IsNodeInList (FirstEntry
, SecondEntry
));
405 // Ptr is the node pointed to by FirstEntry->ForwardLink
407 Ptr
= RemoveEntryList (FirstEntry
);
410 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
411 // immediately in front of SecondEntry
413 if (Ptr
->BackLink
== SecondEntry
) {
414 return InsertTailList (SecondEntry
, FirstEntry
);
418 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
419 // then there are no further steps necessary
421 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
426 // Move SecondEntry to the front of Ptr
428 RemoveEntryList (SecondEntry
);
429 InsertTailList (Ptr
, SecondEntry
);
434 Removes a node from a doubly linked list, and returns the node that follows
437 Removes the node Entry from a doubly linked list. It is up to the caller of
438 this function to release the memory used by this node if that is required. On
439 exit, the node following Entry in the doubly linked list is returned. If
440 Entry is the only node in the linked list, then the head node of the linked
443 If Entry is NULL, then ASSERT().
444 If Entry is the head node of an empty list, then ASSERT().
445 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
446 linked list containing Entry, including the Entry node, is greater than
447 or equal to PcdMaximumLinkedListLength, then ASSERT().
449 @param Entry A pointer to a node in a linked list
457 IN CONST LIST_ENTRY
*Entry
460 ASSERT (!IsListEmpty (Entry
));
462 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
463 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
464 return Entry
->ForwardLink
;