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 // Include common header file for this module.
20 #include "CommonHeader.h"
22 #include "BaseLibInternals.h"
25 Worker function that locates the Node in the List
27 By searching the List, finds the location of the Node in List. At the same time,
28 verifies the validity of this list.
30 If List is NULL, then ASSERT().
31 If List->ForwardLink is NULL, then ASSERT().
32 If List->backLink is NULL, then ASSERT().
33 If Node is NULL, then ASSERT();
34 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
35 of nodes in ListHead, including the ListHead node, is greater than or
36 equal to PcdMaximumLinkedListLength, then ASSERT().
38 @param List A pointer to a node in a linked list.
39 @param Node A pointer to one nod.
41 @retval TRUE Node is in List
42 @retval FALSE Node isn't in List, or List is invalid
47 IN CONST LIST_ENTRY
*List
,
48 IN CONST LIST_ENTRY
*Node
52 CONST LIST_ENTRY
*Ptr
;
56 // Test the validity of List and Node
58 ASSERT (List
!= NULL
);
59 ASSERT (List
->ForwardLink
!= NULL
);
60 ASSERT (List
->BackLink
!= NULL
);
61 ASSERT (Node
!= NULL
);
63 Count
= PcdGet32 (PcdMaximumLinkedListLength
);
67 Ptr
= Ptr
->ForwardLink
;
69 } while ((Ptr
!= List
) && (Ptr
!= Node
) && (Count
> 0));
70 Found
= (BOOLEAN
)(Ptr
== Node
);
72 if (PcdGet32 (PcdMaximumLinkedListLength
) > 0) {
73 while ((Count
> 0) && (Ptr
!= List
)) {
74 Ptr
= Ptr
->ForwardLink
;
84 Initializes the head node of a doubly linked list, and returns the pointer to
85 the head node of the doubly linked list.
87 Initializes the forward and backward links of a new linked list. After
88 initializing a linked list with this function, the other linked list
89 functions may be used to add and remove nodes from the linked list. It is up
90 to the caller of this function to allocate the memory for ListHead.
92 If ListHead is NULL, then ASSERT().
94 @param ListHead A pointer to the head node of a new doubly linked list.
102 IN OUT LIST_ENTRY
*List
106 ASSERT (List
!= NULL
);
108 List
->ForwardLink
= List
;
109 List
->BackLink
= List
;
114 Adds a node to the beginning of a doubly linked list, and returns the pointer
115 to the head node of the doubly linked list.
117 Adds the node Entry at the beginning of the doubly linked list denoted by
118 ListHead, and returns ListHead.
120 If ListHead is NULL, then ASSERT().
121 If Entry is NULL, then ASSERT().
122 If ListHead was not initialized with InitializeListHead(), then ASSERT().
123 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
124 of nodes in ListHead, including the ListHead node, is greater than or
125 equal to PcdMaximumLinkedListLength, then ASSERT().
127 @param ListHead A pointer to the head node of a doubly linked list.
128 @param Entry A pointer to a node that is to be inserted at the beginning
129 of a doubly linked list.
137 IN OUT LIST_ENTRY
*List
,
138 IN OUT LIST_ENTRY
*Entry
142 // ASSERT List not too long and Entry is not one of the nodes of List
144 ASSERT (!IsNodeInList (List
, Entry
));
146 Entry
->ForwardLink
= List
->ForwardLink
;
147 Entry
->BackLink
= List
;
148 Entry
->ForwardLink
->BackLink
= Entry
;
149 List
->ForwardLink
= Entry
;
154 Adds a node to the end of a doubly linked list, and returns the pointer to
155 the head node of the doubly linked list.
157 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
158 and returns ListHead.
160 If ListHead is NULL, then ASSERT().
161 If Entry is NULL, then ASSERT().
162 If ListHead was not initialized with InitializeListHead(), then ASSERT().
163 If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number
164 of nodes in ListHead, including the ListHead node, is greater than or
165 equal to PcdMaximumLinkedListLength, then ASSERT().
167 @param ListHead A pointer to the head node of a doubly linked list.
168 @param Entry A pointer to a node that is to be added at the end of the
177 IN OUT LIST_ENTRY
*List
,
178 IN OUT LIST_ENTRY
*Entry
182 // ASSERT List not too long and Entry is not one of the nodes of List
184 ASSERT (!IsNodeInList (List
, Entry
));
186 Entry
->ForwardLink
= List
;
187 Entry
->BackLink
= List
->BackLink
;
188 Entry
->BackLink
->ForwardLink
= Entry
;
189 List
->BackLink
= Entry
;
194 Retrieves the first node of a doubly linked list.
196 Returns the first node of a doubly linked list. List must have been
197 initialized with InitializeListHead(). If List is empty, then NULL is
200 If List is NULL, then ASSERT().
201 If List was not initialized with InitializeListHead(), then ASSERT().
202 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
203 in List, including the List node, is greater than or equal to
204 PcdMaximumLinkedListLength, then ASSERT().
206 @param List A pointer to the head node of a doubly linked list.
208 @return The first node of a doubly linked list.
209 @retval NULL The list is empty.
215 IN CONST LIST_ENTRY
*List
219 // ASSERT List not too long
221 ASSERT (IsNodeInList (List
, List
));
223 return List
->ForwardLink
;
227 Retrieves the next node of a doubly linked list.
229 Returns the node of a doubly linked list that follows Node. List must have
230 been initialized with InitializeListHead(). If List is empty, then List is
233 If List is NULL, then ASSERT().
234 If Node is NULL, then ASSERT().
235 If List was not initialized with InitializeListHead(), then ASSERT().
236 If PcdMaximumLinkedListLenth is not zero, and List contains more than
237 PcdMaximumLinkedListLenth nodes, then ASSERT().
238 If Node is not a node in List, then ASSERT().
240 @param List A pointer to the head node of a doubly linked list.
241 @param Node A pointer to a node in the doubly linked list.
243 @return Pointer to the next node if one exists. Otherwise a null value which
244 is actually List is returned.
250 IN CONST LIST_ENTRY
*List
,
251 IN CONST LIST_ENTRY
*Node
255 // ASSERT List not too long and Node is one of the nodes of List
257 ASSERT (IsNodeInList (List
, Node
));
259 return Node
->ForwardLink
;
263 Checks to see if a doubly linked list is empty or not.
265 Checks to see if the doubly linked list is empty. If the linked list contains
266 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
268 If ListHead is NULL, then ASSERT().
269 If ListHead was not initialized with InitializeListHead(), then ASSERT().
270 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
271 in List, including the List node, is greater than or equal to
272 PcdMaximumLinkedListLength, then ASSERT().
274 @param ListHead A pointer to the head node of a doubly linked list.
276 @retval TRUE The linked list is empty.
277 @retval FALSE The linked list is not empty.
283 IN CONST LIST_ENTRY
*List
287 // ASSERT List not too long
289 ASSERT (IsNodeInList (List
, List
));
291 return (BOOLEAN
)(List
->ForwardLink
== List
);
295 Determines if a node in a doubly linked list is null.
297 Returns FALSE if Node is one of the nodes in the doubly linked list specified
298 by List. Otherwise, TRUE is returned. List must have been initialized with
299 InitializeListHead().
301 If List is NULL, then ASSERT().
302 If Node is NULL, then ASSERT().
303 If List was not initialized with InitializeListHead(), then ASSERT().
304 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
305 in List, including the List node, is greater than or equal to
306 PcdMaximumLinkedListLength, then ASSERT().
307 If Node is not a node in List and Node is not equal to List, then ASSERT().
309 @param List A pointer to the head node of a doubly linked list.
310 @param Node A pointer to a node in the doubly linked list.
312 @retval TRUE Node is one of the nodes in the doubly linked list.
313 @retval FALSE Node is not one of the nodes in the doubly linked list.
319 IN CONST LIST_ENTRY
*List
,
320 IN CONST LIST_ENTRY
*Node
324 // ASSERT List not too long and Node is one of the nodes of List
326 ASSERT (IsNodeInList (List
, Node
));
328 return (BOOLEAN
)(Node
== List
);
332 Determines if a node the last node in a doubly linked list.
334 Returns TRUE if Node is the last node in the doubly linked list specified by
335 List. Otherwise, FALSE is returned. List must have been initialized with
336 InitializeListHead().
338 If List is NULL, then ASSERT().
339 If Node is NULL, then ASSERT().
340 If List was not initialized with InitializeListHead(), then ASSERT().
341 If PcdMaximumLinkedListLenth is not zero, and the number of nodes
342 in List, including the List node, is greater than or equal to
343 PcdMaximumLinkedListLength, then ASSERT().
344 If Node is not a node in List, then ASSERT().
346 @param List A pointer to the head node of a doubly linked list.
347 @param Node A pointer to a node in the doubly linked list.
349 @retval TRUE Node is the last node in the linked list.
350 @retval FALSE Node is not the last node in the linked list.
356 IN CONST LIST_ENTRY
*List
,
357 IN CONST LIST_ENTRY
*Node
361 // ASSERT List not too long and Node is one of the nodes of List
363 ASSERT (IsNodeInList (List
, Node
));
365 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
369 Swaps the location of two nodes in a doubly linked list, and returns the
370 first node after the swap.
372 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
373 Otherwise, the location of the FirstEntry node is swapped with the location
374 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
375 same double linked list as FirstEntry and that double linked list must have
376 been initialized with InitializeListHead(). SecondEntry is returned after the
379 If FirstEntry is NULL, then ASSERT().
380 If SecondEntry is NULL, then ASSERT().
381 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
382 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
383 linked list containing the FirstEntry and SecondEntry nodes, including
384 the FirstEntry and SecondEntry nodes, is greater than or equal to
385 PcdMaximumLinkedListLength, then ASSERT().
387 @param FirstEntry A pointer to a node in a linked list.
388 @param SecondEntry A pointer to another node in the same linked list.
394 IN OUT LIST_ENTRY
*FirstEntry
,
395 IN OUT LIST_ENTRY
*SecondEntry
400 if (FirstEntry
== SecondEntry
) {
405 // ASSERT Entry1 and Entry2 are in the same linked list
407 ASSERT (IsNodeInList (FirstEntry
, SecondEntry
));
410 // Ptr is the node pointed to by FirstEntry->ForwardLink
412 Ptr
= RemoveEntryList (FirstEntry
);
415 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
416 // immediately in front of SecondEntry
418 if (Ptr
->BackLink
== SecondEntry
) {
419 return InsertTailList (SecondEntry
, FirstEntry
);
423 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
424 // then there are no further steps necessary
426 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
431 // Move SecondEntry to the front of Ptr
433 RemoveEntryList (SecondEntry
);
434 InsertTailList (Ptr
, SecondEntry
);
439 Removes a node from a doubly linked list, and returns the node that follows
442 Removes the node Entry from a doubly linked list. It is up to the caller of
443 this function to release the memory used by this node if that is required. On
444 exit, the node following Entry in the doubly linked list is returned. If
445 Entry is the only node in the linked list, then the head node of the linked
448 If Entry is NULL, then ASSERT().
449 If Entry is the head node of an empty list, then ASSERT().
450 If PcdMaximumLinkedListLength is not zero, and the number of nodes in the
451 linked list containing Entry, including the Entry node, is greater than
452 or equal to PcdMaximumLinkedListLength, then ASSERT().
454 @param Entry A pointer to a node in a linked list
462 IN CONST LIST_ENTRY
*Entry
465 ASSERT (!IsListEmpty (Entry
));
467 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
468 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
469 return Entry
->ForwardLink
;