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
= FixedPcdGet32 (PcdMaximumLinkedListLength
);
43 Ptr
= Ptr
->ForwardLink
;
45 } while ((Ptr
!= List
) && (Ptr
!= Node
) && (Count
> 0));
46 Found
= (BOOLEAN
)(Ptr
== Node
);
48 if (FixedPcdGet32 (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 ListHead contains more than
100 PcdMaximumLinkedListLenth nodes, then ASSERT().
102 @param ListHead A pointer to the head node of a doubly linked list.
103 @param Entry A pointer to a node that is to be inserted at the beginning
104 of a doubly linked list.
112 IN OUT LIST_ENTRY
*List
,
113 IN OUT LIST_ENTRY
*Entry
117 // ASSERT List not too long and Entry is not one of the nodes of List
119 ASSERT (!IsNodeInList (List
, Entry
));
121 Entry
->ForwardLink
= List
->ForwardLink
;
122 Entry
->BackLink
= List
;
123 Entry
->ForwardLink
->BackLink
= Entry
;
124 List
->ForwardLink
= Entry
;
129 Adds a node to the end of a doubly linked list, and returns the pointer to
130 the head node of the doubly linked list.
132 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
133 and returns ListHead.
135 If ListHead is NULL, then ASSERT().
136 If Entry is NULL, then ASSERT().
137 If ListHead was not initialized with InitializeListHead(), then ASSERT().
138 If PcdMaximumLinkedListLenth is not zero, and ListHead contains more than
139 PcdMaximumLinkedListLenth nodes, then ASSERT().
141 @param ListHead A pointer to the head node of a doubly linked list.
142 @param Entry A pointer to a node that is to be added at the end of the
151 IN OUT LIST_ENTRY
*List
,
152 IN OUT LIST_ENTRY
*Entry
156 // ASSERT List not too long and Entry is not one of the nodes of List
158 ASSERT (!IsNodeInList (List
, Entry
));
160 Entry
->ForwardLink
= List
;
161 Entry
->BackLink
= List
->BackLink
;
162 Entry
->BackLink
->ForwardLink
= Entry
;
163 List
->BackLink
= Entry
;
168 Retrieves the first node of a doubly linked list.
170 Returns the first node of a doubly linked list. List must have been
171 initialized with InitializeListHead(). If List is empty, then NULL is
174 If List is NULL, then ASSERT().
175 If List was not initialized with InitializeListHead(), then ASSERT().
176 If PcdMaximumLinkedListLenth is not zero, and List contains more than
177 PcdMaximumLinkedListLenth nodes, then ASSERT().
179 @param List A pointer to the head node of a doubly linked list.
181 @return The first node of a doubly linked list.
182 @retval NULL The list is empty.
188 IN CONST LIST_ENTRY
*List
192 // ASSERT List not too long
194 ASSERT (IsNodeInList (List
, List
));
196 return List
->ForwardLink
;
200 Retrieves the next node of a doubly linked list.
202 Returns the node of a doubly linked list that follows Node. List must have
203 been initialized with InitializeListHead(). If List is empty, then List is
206 If List is NULL, then ASSERT().
207 If Node is NULL, then ASSERT().
208 If List was not initialized with InitializeListHead(), then ASSERT().
209 If PcdMaximumLinkedListLenth is not zero, and List contains more than
210 PcdMaximumLinkedListLenth nodes, then ASSERT().
211 If Node is not a node in List, then ASSERT().
213 @param List A pointer to the head node of a doubly linked list.
214 @param Node A pointer to a node in the doubly linked list.
216 @return Pointer to the next node if one exists. Otherwise a null value which
217 is actually List is returned.
223 IN CONST LIST_ENTRY
*List
,
224 IN CONST LIST_ENTRY
*Node
228 // ASSERT List not too long and Node is one of the nodes of List
230 ASSERT (IsNodeInList (List
, Node
));
232 return Node
->ForwardLink
;
236 Checks to see if a doubly linked list is empty or not.
238 Checks to see if the doubly linked list is empty. If the linked list contains
239 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
241 If ListHead is NULL, then ASSERT().
242 If ListHead was not initialized with InitializeListHead(), then ASSERT().
243 If PcdMaximumLinkedListLenth is not zero, and List contains more than
244 PcdMaximumLinkedListLenth nodes, then ASSERT().
246 @param ListHead A pointer to the head node of a doubly linked list.
248 @retval TRUE The linked list is empty.
249 @retval FALSE The linked list is not empty.
255 IN CONST LIST_ENTRY
*List
259 // ASSERT List not too long
261 ASSERT (IsNodeInList (List
, List
));
263 return (BOOLEAN
)(List
->ForwardLink
== List
);
267 Determines if a node in a doubly linked list is null.
269 Returns FALSE if Node is one of the nodes in the doubly linked list specified
270 by List. Otherwise, TRUE is returned. List must have been initialized with
271 InitializeListHead().
273 If List is NULL, then ASSERT().
274 If Node is NULL, then ASSERT().
275 If List was not initialized with InitializeListHead(), then ASSERT().
276 If PcdMaximumLinkedListLenth is not zero, and List contains more than
277 PcdMaximumLinkedListLenth nodes, then ASSERT().
278 If Node is not a node in List and Node is not equal to List, then ASSERT().
280 @param List A pointer to the head node of a doubly linked list.
281 @param Node A pointer to a node in the doubly linked list.
283 @retval TRUE Node is one of the nodes in the doubly linked list.
284 @retval FALSE Node is not one of the nodes in the doubly linked list.
290 IN CONST LIST_ENTRY
*List
,
291 IN CONST LIST_ENTRY
*Node
295 // ASSERT List not too long and Node is one of the nodes of List
297 ASSERT (IsNodeInList (List
, Node
));
299 return (BOOLEAN
)(Node
== List
);
303 Determines if a node the last node in a doubly linked list.
305 Returns TRUE if Node is the last node in the doubly linked list specified by
306 List. Otherwise, FALSE is returned. List must have been initialized with
307 InitializeListHead().
309 If List is NULL, then ASSERT().
310 If Node is NULL, then ASSERT().
311 If List was not initialized with InitializeListHead(), then ASSERT().
312 If PcdMaximumLinkedListLenth is not zero, and List contains more than
313 PcdMaximumLinkedListLenth nodes, then ASSERT().
314 If Node is not a node in List, then ASSERT().
316 @param List A pointer to the head node of a doubly linked list.
317 @param Node A pointer to a node in the doubly linked list.
319 @retval TRUE Node is the last node in the linked list.
320 @retval FALSE Node is not the last node in the linked list.
326 IN CONST LIST_ENTRY
*List
,
327 IN CONST LIST_ENTRY
*Node
331 // ASSERT List not too long and Node is one of the nodes of List
333 ASSERT (IsNodeInList (List
, Node
));
335 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
339 Swaps the location of two nodes in a doubly linked list, and returns the
340 first node after the swap.
342 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
343 Otherwise, the location of the FirstEntry node is swapped with the location
344 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
345 same double linked list as FirstEntry and that double linked list must have
346 been initialized with InitializeListHead(). SecondEntry is returned after the
349 If FirstEntry is NULL, then ASSERT().
350 If SecondEntry is NULL, then ASSERT().
351 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
352 If PcdMaximumLinkedListLenth is not zero, and the linked list containing
353 FirstEntry and SecondEntry contains more than PcdMaximumLinkedListLenth
354 nodes, then ASSERT().
356 @param FirstEntry A pointer to a node in a linked list.
357 @param SecondEntry A pointer to another node in the same linked list.
363 IN OUT LIST_ENTRY
*FirstEntry
,
364 IN OUT LIST_ENTRY
*SecondEntry
369 if (FirstEntry
== SecondEntry
) {
374 // ASSERT Entry1 and Entry2 are in the same linked list
376 ASSERT (IsNodeInList (FirstEntry
, SecondEntry
));
379 // Ptr is the node pointed to by FirstEntry->ForwardLink
381 Ptr
= RemoveEntryList (FirstEntry
);
384 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
385 // immediately in front of SecondEntry
387 if (Ptr
->BackLink
== SecondEntry
) {
388 return InsertTailList (SecondEntry
, FirstEntry
);
392 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
393 // then there are no further steps necessary
395 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
400 // Move SecondEntry to the front of Ptr
402 RemoveEntryList (SecondEntry
);
403 InsertTailList (Ptr
, SecondEntry
);
408 Removes a node from a doubly linked list, and returns the node that follows
411 Removes the node Entry from a doubly linked list. It is up to the caller of
412 this function to release the memory used by this node if that is required. On
413 exit, the node following Entry in the doubly linked list is returned. If
414 Entry is the only node in the linked list, then the head node of the linked
417 If Entry is NULL, then ASSERT().
418 If Entry is the head node of an empty list, then ASSERT().
419 If PcdMaximumLinkedListLenth is not zero, and the linked list containing
420 Entry contains more than PcdMaximumLinkedListLenth nodes, then ASSERT().
422 @param Entry A pointer to a node in a linked list
430 IN CONST LIST_ENTRY
*Entry
433 ASSERT (!IsListEmpty (Entry
));
435 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
436 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
437 return Entry
->ForwardLink
;