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
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 IN CONST LIST_ENTRY
*List
,
41 IN CONST LIST_ENTRY
*Node
45 CONST LIST_ENTRY
*Ptr
;
49 // Test the validity of List and Node
51 ASSERT (List
!= NULL
);
52 ASSERT (List
->ForwardLink
!= NULL
);
53 ASSERT (List
->BackLink
!= NULL
);
54 ASSERT (Node
!= NULL
);
56 Count
= PcdGet32 (PcdMaximumLinkedListLength
);
60 Ptr
= Ptr
->ForwardLink
;
62 } while ((Ptr
!= List
) && (Ptr
!= Node
) && (Count
> 0));
63 Found
= (BOOLEAN
)(Ptr
== Node
);
65 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
66 while ((Count
> 0) && (Ptr
!= List
)) {
67 Ptr
= Ptr
->ForwardLink
;
77 Initializes the head node of a doubly linked list, and returns the pointer to
78 the head node of the doubly linked list.
80 Initializes the forward and backward links of a new linked list. After
81 initializing a linked list with this function, the other linked list
82 functions may be used to add and remove nodes from the linked list. It is up
83 to the caller of this function to allocate the memory for ListHead.
85 If ListHead is NULL, then ASSERT().
87 @param ListHead A pointer to the head node of a new doubly linked list.
95 IN OUT LIST_ENTRY
*List
99 ASSERT (List
!= NULL
);
101 List
->ForwardLink
= List
;
102 List
->BackLink
= List
;
107 Adds a node to the beginning of a doubly linked list, and returns the pointer
108 to the head node of the doubly linked list.
110 Adds the node Entry at the beginning of the doubly linked list denoted by
111 ListHead, and returns ListHead.
113 If ListHead is NULL, then ASSERT().
114 If Entry is NULL, then ASSERT().
115 If ListHead was not initialized with InitializeListHead(), then ASSERT().
116 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
117 of nodes in ListHead, including the ListHead node, is greater than or
118 equal to PcdMaximumLinkedListLength, then ASSERT().
120 @param ListHead A pointer to the head node of a doubly linked list.
121 @param Entry A pointer to a node that is to be inserted at the beginning
122 of a doubly linked list.
130 IN OUT LIST_ENTRY
*List
,
131 IN OUT LIST_ENTRY
*Entry
135 // ASSERT List not too long and Entry is not one of the nodes of List
137 ASSERT (!IsNodeInList (List
, Entry
));
139 Entry
->ForwardLink
= List
->ForwardLink
;
140 Entry
->BackLink
= List
;
141 Entry
->ForwardLink
->BackLink
= Entry
;
142 List
->ForwardLink
= Entry
;
147 Adds a node to the end of a doubly linked list, and returns the pointer to
148 the head node of the doubly linked list.
150 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
151 and returns ListHead.
153 If ListHead is NULL, then ASSERT().
154 If Entry is NULL, then ASSERT().
155 If ListHead was not initialized with InitializeListHead(), then ASSERT().
156 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
157 of nodes in ListHead, including the ListHead node, is greater than or
158 equal to PcdMaximumLinkedListLength, then ASSERT().
160 @param ListHead A pointer to the head node of a doubly linked list.
161 @param Entry A pointer to a node that is to be added at the end of the
170 IN OUT LIST_ENTRY
*List
,
171 IN OUT LIST_ENTRY
*Entry
175 // ASSERT List not too long and Entry is not one of the nodes of List
177 ASSERT (!IsNodeInList (List
, Entry
));
179 Entry
->ForwardLink
= List
;
180 Entry
->BackLink
= List
->BackLink
;
181 Entry
->BackLink
->ForwardLink
= Entry
;
182 List
->BackLink
= Entry
;
187 Retrieves the first node of a doubly linked list.
189 Returns the first node of a doubly linked list. List must have been
190 initialized with InitializeListHead(). If List is empty, then NULL is
193 If List is NULL, then ASSERT().
194 If List was not initialized with InitializeListHead(), then ASSERT().
195 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
196 in List, including the List node, is greater than or equal to
197 PcdMaximumLinkedListLength, then ASSERT().
199 @param List A pointer to the head node of a doubly linked list.
201 @return The first node of a doubly linked list.
202 @retval NULL The list is empty.
208 IN CONST LIST_ENTRY
*List
212 // ASSERT List not too long
214 ASSERT (IsNodeInList (List
, List
));
216 return List
->ForwardLink
;
220 Retrieves the next node of a doubly linked list.
222 Returns the node of a doubly linked list that follows Node. List must have
223 been initialized with InitializeListHead(). If List is empty, then List is
226 If List is NULL, then ASSERT().
227 If Node is NULL, then ASSERT().
228 If List was not initialized with InitializeListHead(), then ASSERT().
229 If PcdMaximumLinkedListLenth is not zero, and List contains more than
230 PcdMaximumLinkedListLenth nodes, then ASSERT().
231 If Node is not a node in List, then ASSERT().
233 @param List A pointer to the head node of a doubly linked list.
234 @param Node A pointer to a node in the doubly linked list.
236 @return Pointer to the next node if one exists. Otherwise a null value which
237 is actually List is returned.
243 IN CONST LIST_ENTRY
*List
,
244 IN CONST LIST_ENTRY
*Node
248 // ASSERT List not too long and Node is one of the nodes of List
250 ASSERT (IsNodeInList (List
, Node
));
252 return Node
->ForwardLink
;
256 Checks to see if a doubly linked list is empty or not.
258 Checks to see if the doubly linked list is empty. If the linked list contains
259 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
261 If ListHead is NULL, then ASSERT().
262 If ListHead was not initialized with InitializeListHead(), then ASSERT().
263 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
264 in List, including the List node, is greater than or equal to
265 PcdMaximumLinkedListLength, then ASSERT().
267 @param ListHead A pointer to the head node of a doubly linked list.
269 @retval TRUE The linked list is empty.
270 @retval FALSE The linked list is not empty.
276 IN CONST LIST_ENTRY
*List
280 // ASSERT List not too long
282 ASSERT (IsNodeInList (List
, List
));
284 return (BOOLEAN
)(List
->ForwardLink
== List
);
288 Determines if a node in a doubly linked list is null.
290 Returns FALSE if Node is one of the nodes in the doubly linked list specified
291 by List. Otherwise, TRUE is returned. List must have been initialized with
292 InitializeListHead().
294 If List is NULL, then ASSERT().
295 If Node is NULL, then ASSERT().
296 If List was not initialized with InitializeListHead(), then ASSERT().
297 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
298 in List, including the List node, is greater than or equal to
299 PcdMaximumLinkedListLength, then ASSERT().
300 If Node is not a node in List and Node is not equal to List, then ASSERT().
302 @param List A pointer to the head node of a doubly linked list.
303 @param Node A pointer to a node in the doubly linked list.
305 @retval TRUE Node is one of the nodes in the doubly linked list.
306 @retval FALSE Node is not one of the nodes in the doubly linked list.
312 IN CONST LIST_ENTRY
*List
,
313 IN CONST LIST_ENTRY
*Node
317 // ASSERT List not too long and Node is one of the nodes of List
319 ASSERT (IsNodeInList (List
, Node
));
321 return (BOOLEAN
)(Node
== List
);
325 Determines if a node the last node in a doubly linked list.
327 Returns TRUE if Node is the last node in the doubly linked list specified by
328 List. Otherwise, FALSE is returned. List must have been initialized with
329 InitializeListHead().
331 If List is NULL, then ASSERT().
332 If Node is NULL, then ASSERT().
333 If List was not initialized with InitializeListHead(), then ASSERT().
334 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
335 in List, including the List node, is greater than or equal to
336 PcdMaximumLinkedListLength, then ASSERT().
337 If Node is not a node in List, then ASSERT().
339 @param List A pointer to the head node of a doubly linked list.
340 @param Node A pointer to a node in the doubly linked list.
342 @retval TRUE Node is the last node in the linked list.
343 @retval FALSE Node is not the last node in the linked list.
349 IN CONST LIST_ENTRY
*List
,
350 IN CONST LIST_ENTRY
*Node
354 // ASSERT List not too long and Node is one of the nodes of List
356 ASSERT (IsNodeInList (List
, Node
));
358 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
362 Swaps the location of two nodes in a doubly linked list, and returns the
363 first node after the swap.
365 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
366 Otherwise, the location of the FirstEntry node is swapped with the location
367 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
368 same double linked list as FirstEntry and that double linked list must have
369 been initialized with InitializeListHead(). SecondEntry is returned after the
372 If FirstEntry is NULL, then ASSERT().
373 If SecondEntry is NULL, then ASSERT().
374 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
375 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
376 linked list containing the FirstEntry and SecondEntry nodes, including
377 the FirstEntry and SecondEntry nodes, is greater than or equal to
378 PcdMaximumLinkedListLength, then ASSERT().
380 @param FirstEntry A pointer to a node in a linked list.
381 @param SecondEntry A pointer to another node in the same linked list.
387 IN OUT LIST_ENTRY
*FirstEntry
,
388 IN OUT LIST_ENTRY
*SecondEntry
393 if (FirstEntry
== SecondEntry
) {
398 // ASSERT Entry1 and Entry2 are in the same linked list
400 ASSERT (IsNodeInList (FirstEntry
, SecondEntry
));
403 // Ptr is the node pointed to by FirstEntry->ForwardLink
405 Ptr
= RemoveEntryList (FirstEntry
);
408 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
409 // immediately in front of SecondEntry
411 if (Ptr
->BackLink
== SecondEntry
) {
412 return InsertTailList (SecondEntry
, FirstEntry
);
416 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
417 // then there are no further steps necessary
419 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
424 // Move SecondEntry to the front of Ptr
426 RemoveEntryList (SecondEntry
);
427 InsertTailList (Ptr
, SecondEntry
);
432 Removes a node from a doubly linked list, and returns the node that follows
435 Removes the node Entry from a doubly linked list. It is up to the caller of
436 this function to release the memory used by this node if that is required. On
437 exit, the node following Entry in the doubly linked list is returned. If
438 Entry is the only node in the linked list, then the head node of the linked
441 If Entry is NULL, then ASSERT().
442 If Entry is the head node of an empty list, then ASSERT().
443 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
444 linked list containing Entry, including the Entry node, is greater than
445 or equal to PcdMaximumLinkedListLength, then ASSERT().
447 @param Entry A pointer to a node in a linked list
455 IN CONST LIST_ENTRY
*Entry
458 ASSERT (!IsListEmpty (Entry
));
460 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
461 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
462 return Entry
->ForwardLink
;