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
20 IN CONST LIST_ENTRY
*List
,
21 IN CONST LIST_ENTRY
*Node
25 CONST LIST_ENTRY
*Ptr
;
29 // Test the validity of List and Node
31 ASSERT (List
!= NULL
);
32 ASSERT (List
->ForwardLink
!= NULL
);
33 ASSERT (List
->BackLink
!= NULL
);
34 ASSERT (Node
!= NULL
);
36 Count
= PcdGet32 (PcdMaximumLinkedListLength
);
43 Ptr
= Ptr
->ForwardLink
;
45 } while ((Ptr
!= List
) && (Ptr
!= Node
) && (Count
> 0));
46 Found
= (BOOLEAN
)(Ptr
== Node
);
48 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
49 while ((Count
> 0) && (Ptr
!= List
)) {
50 Ptr
= Ptr
->ForwardLink
;
60 Initializes the head node of a doubly linked list, and returns the pointer to
61 the head node of the doubly linked list.
63 Initializes the forward and backward links of a new linked list. After
64 initializing a linked list with this function, the other linked list
65 functions may be used to add and remove nodes from the linked list. It is up
66 to the caller of this function to allocate the memory for ListHead.
68 If ListHead is NULL, then ASSERT().
70 @param ListHead A pointer to the head node of a new doubly linked list.
78 IN OUT LIST_ENTRY
*List
82 ASSERT (List
!= NULL
);
84 List
->ForwardLink
= List
;
85 List
->BackLink
= List
;
90 Adds a node to the beginning of a doubly linked list, and returns the pointer
91 to the head node of the doubly linked list.
93 Adds the node Entry at the beginning of the doubly linked list denoted by
94 ListHead, and returns ListHead.
96 If ListHead is NULL, then ASSERT().
97 If Entry is NULL, then ASSERT().
98 If ListHead was not initialized with InitializeListHead(), then ASSERT().
99 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
100 of nodes in ListHead, including the ListHead node, is greater than or
101 equal to PcdMaximumLinkedListLength, then ASSERT().
103 @param ListHead A pointer to the head node of a doubly linked list.
104 @param Entry A pointer to a node that is to be inserted at the beginning
105 of a doubly linked list.
113 IN OUT LIST_ENTRY
*List
,
114 IN OUT LIST_ENTRY
*Entry
118 // ASSERT List not too long and Entry is not one of the nodes of List
120 ASSERT (!IsNodeInList (List
, Entry
));
122 Entry
->ForwardLink
= List
->ForwardLink
;
123 Entry
->BackLink
= List
;
124 Entry
->ForwardLink
->BackLink
= Entry
;
125 List
->ForwardLink
= Entry
;
130 Adds a node to the end of a doubly linked list, and returns the pointer to
131 the head node of the doubly linked list.
133 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
134 and returns ListHead.
136 If ListHead is NULL, then ASSERT().
137 If Entry is NULL, then ASSERT().
138 If ListHead was not initialized with InitializeListHead(), then ASSERT().
139 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
140 of nodes in ListHead, including the ListHead node, is greater than or
141 equal to PcdMaximumLinkedListLength, then ASSERT().
143 @param ListHead A pointer to the head node of a doubly linked list.
144 @param Entry A pointer to a node that is to be added at the end of the
153 IN OUT LIST_ENTRY
*List
,
154 IN OUT LIST_ENTRY
*Entry
158 // ASSERT List not too long and Entry is not one of the nodes of List
160 ASSERT (!IsNodeInList (List
, Entry
));
162 Entry
->ForwardLink
= List
;
163 Entry
->BackLink
= List
->BackLink
;
164 Entry
->BackLink
->ForwardLink
= Entry
;
165 List
->BackLink
= Entry
;
170 Retrieves the first node of a doubly linked list.
172 Returns the first node of a doubly linked list. List must have been
173 initialized with InitializeListHead(). If List is empty, then NULL is
176 If List is NULL, then ASSERT().
177 If List was not initialized with InitializeListHead(), then ASSERT().
178 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
179 in List, including the List node, is greater than or equal to
180 PcdMaximumLinkedListLength, then ASSERT().
182 @param List A pointer to the head node of a doubly linked list.
184 @return The first node of a doubly linked list.
185 @retval NULL The list is empty.
191 IN CONST LIST_ENTRY
*List
195 // ASSERT List not too long
197 ASSERT (IsNodeInList (List
, List
));
199 return List
->ForwardLink
;
203 Retrieves the next node of a doubly linked list.
205 Returns the node of a doubly linked list that follows Node. List must have
206 been initialized with InitializeListHead(). If List is empty, then List is
209 If List is NULL, then ASSERT().
210 If Node is NULL, then ASSERT().
211 If List was not initialized with InitializeListHead(), then ASSERT().
212 If PcdMaximumLinkedListLenth is not zero, and List contains more than
213 PcdMaximumLinkedListLenth nodes, then ASSERT().
214 If Node is not a node in List, then ASSERT().
216 @param List A pointer to the head node of a doubly linked list.
217 @param Node A pointer to a node in the doubly linked list.
219 @return Pointer to the next node if one exists. Otherwise a null value which
220 is actually List is returned.
226 IN CONST LIST_ENTRY
*List
,
227 IN CONST LIST_ENTRY
*Node
231 // ASSERT List not too long and Node is one of the nodes of List
233 ASSERT (IsNodeInList (List
, Node
));
235 return Node
->ForwardLink
;
239 Checks to see if a doubly linked list is empty or not.
241 Checks to see if the doubly linked list is empty. If the linked list contains
242 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
244 If ListHead is NULL, then ASSERT().
245 If ListHead was not initialized with InitializeListHead(), then ASSERT().
246 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
247 in List, including the List node, is greater than or equal to
248 PcdMaximumLinkedListLength, then ASSERT().
250 @param ListHead A pointer to the head node of a doubly linked list.
252 @retval TRUE The linked list is empty.
253 @retval FALSE The linked list is not empty.
259 IN CONST LIST_ENTRY
*List
263 // ASSERT List not too long
265 ASSERT (IsNodeInList (List
, List
));
267 return (BOOLEAN
)(List
->ForwardLink
== List
);
271 Determines if a node in a doubly linked list is null.
273 Returns FALSE if Node is one of the nodes in the doubly linked list specified
274 by List. Otherwise, TRUE is returned. List must have been initialized with
275 InitializeListHead().
277 If List is NULL, then ASSERT().
278 If Node is NULL, then ASSERT().
279 If List was not initialized with InitializeListHead(), then ASSERT().
280 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
281 in List, including the List node, is greater than or equal to
282 PcdMaximumLinkedListLength, then ASSERT().
283 If Node is not a node in List and Node is not equal to List, then ASSERT().
285 @param List A pointer to the head node of a doubly linked list.
286 @param Node A pointer to a node in the doubly linked list.
288 @retval TRUE Node is one of the nodes in the doubly linked list.
289 @retval FALSE Node is not one of the nodes in the doubly linked list.
295 IN CONST LIST_ENTRY
*List
,
296 IN CONST LIST_ENTRY
*Node
300 // ASSERT List not too long and Node is one of the nodes of List
302 ASSERT (IsNodeInList (List
, Node
));
304 return (BOOLEAN
)(Node
== List
);
308 Determines if a node the last node in a doubly linked list.
310 Returns TRUE if Node is the last node in the doubly linked list specified by
311 List. Otherwise, FALSE is returned. List must have been initialized with
312 InitializeListHead().
314 If List is NULL, then ASSERT().
315 If Node is NULL, then ASSERT().
316 If List was not initialized with InitializeListHead(), then ASSERT().
317 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
318 in List, including the List node, is greater than or equal to
319 PcdMaximumLinkedListLength, then ASSERT().
320 If Node is not a node in List, then ASSERT().
322 @param List A pointer to the head node of a doubly linked list.
323 @param Node A pointer to a node in the doubly linked list.
325 @retval TRUE Node is the last node in the linked list.
326 @retval FALSE Node is not the last node in the linked list.
332 IN CONST LIST_ENTRY
*List
,
333 IN CONST LIST_ENTRY
*Node
337 // ASSERT List not too long and Node is one of the nodes of List
339 ASSERT (IsNodeInList (List
, Node
));
341 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
345 Swaps the location of two nodes in a doubly linked list, and returns the
346 first node after the swap.
348 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
349 Otherwise, the location of the FirstEntry node is swapped with the location
350 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
351 same double linked list as FirstEntry and that double linked list must have
352 been initialized with InitializeListHead(). SecondEntry is returned after the
355 If FirstEntry is NULL, then ASSERT().
356 If SecondEntry is NULL, then ASSERT().
357 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
358 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
359 linked list containing the FirstEntry and SecondEntry nodes, including
360 the FirstEntry and SecondEntry nodes, is greater than or equal to
361 PcdMaximumLinkedListLength, then ASSERT().
363 @param FirstEntry A pointer to a node in a linked list.
364 @param SecondEntry A pointer to another node in the same linked list.
370 IN OUT LIST_ENTRY
*FirstEntry
,
371 IN OUT LIST_ENTRY
*SecondEntry
376 if (FirstEntry
== SecondEntry
) {
381 // ASSERT Entry1 and Entry2 are in the same linked list
383 ASSERT (IsNodeInList (FirstEntry
, SecondEntry
));
386 // Ptr is the node pointed to by FirstEntry->ForwardLink
388 Ptr
= RemoveEntryList (FirstEntry
);
391 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
392 // immediately in front of SecondEntry
394 if (Ptr
->BackLink
== SecondEntry
) {
395 return InsertTailList (SecondEntry
, FirstEntry
);
399 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
400 // then there are no further steps necessary
402 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
407 // Move SecondEntry to the front of Ptr
409 RemoveEntryList (SecondEntry
);
410 InsertTailList (Ptr
, SecondEntry
);
415 Removes a node from a doubly linked list, and returns the node that follows
418 Removes the node Entry from a doubly linked list. It is up to the caller of
419 this function to release the memory used by this node if that is required. On
420 exit, the node following Entry in the doubly linked list is returned. If
421 Entry is the only node in the linked list, then the head node of the linked
424 If Entry is NULL, then ASSERT().
425 If Entry is the head node of an empty list, then ASSERT().
426 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
427 linked list containing Entry, including the Entry node, is greater than
428 or equal to PcdMaximumLinkedListLength, then ASSERT().
430 @param Entry A pointer to a node in a linked list
438 IN CONST LIST_ENTRY
*Entry
441 ASSERT (!IsListEmpty (Entry
));
443 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
444 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
445 return Entry
->ForwardLink
;