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
);
39 Ptr
= Ptr
->ForwardLink
;
41 } while ((Ptr
!= List
) && (Ptr
!= Node
) && (Count
> 0));
42 Found
= (BOOLEAN
)(Ptr
== Node
);
44 if (FixedPcdGet32 (PcdMaximumLinkedListLength
) > 0) {
45 while ((Count
> 0) && (Ptr
!= List
)) {
46 Ptr
= Ptr
->ForwardLink
;
55 Initializes the head node of a doubly linked list, and returns the pointer to
56 the head node of the doubly linked list.
58 Initializes the forward and backward links of a new linked list. After
59 initializing a linked list with this function, the other linked list
60 functions may be used to add and remove nodes from the linked list. It is up
61 to the caller of this function to allocate the memory for ListHead.
63 If ListHead is NULL, then ASSERT().
65 @param ListHead A pointer to the head node of a new doubly linked list.
73 IN OUT LIST_ENTRY
*List
77 ASSERT (List
!= NULL
);
79 List
->ForwardLink
= List
;
80 List
->BackLink
= List
;
85 Adds a node to the beginning of a doubly linked list, and returns the pointer
86 to the head node of the doubly linked list.
88 Adds the node Entry at the beginning of the doubly linked list denoted by
89 ListHead, and returns ListHead.
91 If ListHead is NULL, then ASSERT().
92 If Entry is NULL, then ASSERT().
93 If ListHead was not initialized with InitializeListHead(), then ASSERT().
94 If PcdMaximumLinkedListLenth is not zero, and ListHead contains more than
95 PcdMaximumLinkedListLenth nodes, then ASSERT().
97 @param ListHead A pointer to the head node of a doubly linked list.
98 @param Entry A pointer to a node that is to be inserted at the beginning
99 of a doubly linked list.
107 IN OUT LIST_ENTRY
*List
,
108 IN OUT LIST_ENTRY
*Entry
112 // ASSERT List not too long and Entry is not one of the nodes of List
114 ASSERT (!IsNodeInList (List
, Entry
));
116 Entry
->ForwardLink
= List
->ForwardLink
;
117 Entry
->BackLink
= List
;
118 Entry
->ForwardLink
->BackLink
= Entry
;
119 List
->ForwardLink
= Entry
;
124 Adds a node to the end of a doubly linked list, and returns the pointer to
125 the head node of the doubly linked list.
127 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
128 and returns ListHead.
130 If ListHead is NULL, then ASSERT().
131 If Entry is NULL, then ASSERT().
132 If ListHead was not initialized with InitializeListHead(), then ASSERT().
133 If PcdMaximumLinkedListLenth is not zero, and ListHead contains more than
134 PcdMaximumLinkedListLenth nodes, then ASSERT().
136 @param ListHead A pointer to the head node of a doubly linked list.
137 @param Entry A pointer to a node that is to be added at the end of the
146 IN OUT LIST_ENTRY
*List
,
147 IN OUT LIST_ENTRY
*Entry
151 // ASSERT List not too long and Entry is not one of the nodes of List
153 ASSERT (!IsNodeInList (List
, Entry
));
155 Entry
->ForwardLink
= List
;
156 Entry
->BackLink
= List
->BackLink
;
157 Entry
->BackLink
->ForwardLink
= Entry
;
158 List
->BackLink
= Entry
;
163 Retrieves the first node of a doubly linked list.
165 Returns the first node of a doubly linked list. List must have been
166 initialized with InitializeListHead(). If List is empty, then NULL is
169 If List is NULL, then ASSERT().
170 If List was not initialized with InitializeListHead(), then ASSERT().
171 If PcdMaximumLinkedListLenth is not zero, and List contains more than
172 PcdMaximumLinkedListLenth nodes, then ASSERT().
174 @param List A pointer to the head node of a doubly linked list.
176 @return The first node of a doubly linked list.
177 @retval NULL The list is empty.
183 IN CONST LIST_ENTRY
*List
187 // ASSERT List not too long
189 ASSERT (IsNodeInList (List
, List
));
191 return List
->ForwardLink
;
195 Retrieves the next node of a doubly linked list.
197 Returns the node of a doubly linked list that follows Node. List must have
198 been initialized with InitializeListHead(). If List is empty, then List is
201 If List is NULL, then ASSERT().
202 If Node is NULL, then ASSERT().
203 If List was not initialized with InitializeListHead(), then ASSERT().
204 If PcdMaximumLinkedListLenth is not zero, and List contains more than
205 PcdMaximumLinkedListLenth nodes, then ASSERT().
206 If Node is not a node in List, then ASSERT().
208 @param List A pointer to the head node of a doubly linked list.
209 @param Node A pointer to a node in the doubly linked list.
211 @return Pointer to the next node if one exists. Otherwise a null value which
212 is actually List is returned.
218 IN CONST LIST_ENTRY
*List
,
219 IN CONST LIST_ENTRY
*Node
223 // ASSERT List not too long and Node is one of the nodes of List
225 ASSERT (IsNodeInList (List
, Node
));
227 return Node
->ForwardLink
;
231 Checks to see if a doubly linked list is empty or not.
233 Checks to see if the doubly linked list is empty. If the linked list contains
234 zero nodes, this function returns TRUE. Otherwise, it returns FALSE.
236 If ListHead is NULL, then ASSERT().
237 If ListHead was not initialized with InitializeListHead(), then ASSERT().
238 If PcdMaximumLinkedListLenth is not zero, and List contains more than
239 PcdMaximumLinkedListLenth nodes, then ASSERT().
241 @param ListHead A pointer to the head node of a doubly linked list.
243 @retval TRUE The linked list is empty.
244 @retval FALSE The linked list is not empty.
250 IN CONST LIST_ENTRY
*List
254 // ASSERT List not too long
256 ASSERT (IsNodeInList (List
, List
));
258 return (BOOLEAN
)(List
->ForwardLink
== List
);
262 Determines if a node in a doubly linked list is null.
264 Returns FALSE if Node is one of the nodes in the doubly linked list specified
265 by List. Otherwise, TRUE is returned. List must have been initialized with
266 InitializeListHead().
268 If List is NULL, then ASSERT().
269 If Node is NULL, then ASSERT().
270 If List was not initialized with InitializeListHead(), then ASSERT().
271 If PcdMaximumLinkedListLenth is not zero, and List contains more than
272 PcdMaximumLinkedListLenth nodes, then ASSERT().
273 If Node is not a node in List and Node is not equal to List, then ASSERT().
275 @param List A pointer to the head node of a doubly linked list.
276 @param Node A pointer to a node in the doubly linked list.
278 @retval TRUE Node is one of the nodes in the doubly linked list.
279 @retval FALSE Node is not one of the nodes in the doubly linked list.
285 IN CONST LIST_ENTRY
*List
,
286 IN CONST LIST_ENTRY
*Node
290 // ASSERT List not too long and Node is one of the nodes of List
292 ASSERT (IsNodeInList (List
, Node
));
294 return (BOOLEAN
)(Node
== List
);
298 Determines if a node the last node in a doubly linked list.
300 Returns TRUE if Node is the last node in the doubly linked list specified by
301 List. Otherwise, FALSE is returned. List must have been initialized with
302 InitializeListHead().
304 If List is NULL, then ASSERT().
305 If Node is NULL, then ASSERT().
306 If List was not initialized with InitializeListHead(), then ASSERT().
307 If PcdMaximumLinkedListLenth is not zero, and List contains more than
308 PcdMaximumLinkedListLenth nodes, then ASSERT().
309 If Node is not a node in List, then ASSERT().
311 @param List A pointer to the head node of a doubly linked list.
312 @param Node A pointer to a node in the doubly linked list.
314 @retval TRUE Node is the last node in the linked list.
315 @retval FALSE Node is not the last node in the linked list.
321 IN CONST LIST_ENTRY
*List
,
322 IN CONST LIST_ENTRY
*Node
326 // ASSERT List not too long and Node is one of the nodes of List
328 ASSERT (IsNodeInList (List
, Node
));
330 return (BOOLEAN
)(!IsNull (List
, Node
) && List
->BackLink
== Node
);
334 Swaps the location of two nodes in a doubly linked list, and returns the
335 first node after the swap.
337 If FirstEntry is identical to SecondEntry, then SecondEntry is returned.
338 Otherwise, the location of the FirstEntry node is swapped with the location
339 of the SecondEntry node in a doubly linked list. SecondEntry must be in the
340 same double linked list as FirstEntry and that double linked list must have
341 been initialized with InitializeListHead(). SecondEntry is returned after the
344 If FirstEntry is NULL, then ASSERT().
345 If SecondEntry is NULL, then ASSERT().
346 If SecondEntry and FirstEntry are not in the same linked list, then ASSERT().
347 If PcdMaximumLinkedListLenth is not zero, and the linked list containing
348 FirstEntry and SecondEntry contains more than PcdMaximumLinkedListLenth
349 nodes, then ASSERT().
351 @param FirstEntry A pointer to a node in a linked list.
352 @param SecondEntry A pointer to another node in the same linked list.
358 IN OUT LIST_ENTRY
*FirstEntry
,
359 IN OUT LIST_ENTRY
*SecondEntry
364 if (FirstEntry
== SecondEntry
) {
369 // ASSERT Entry1 and Entry2 are in the same linked list
371 ASSERT (IsNodeInList (FirstEntry
, SecondEntry
));
374 // Ptr is the node pointed to by FirstEntry->ForwardLink
376 Ptr
= RemoveEntryList (FirstEntry
);
379 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
380 // immediately in front of SecondEntry
382 if (Ptr
->BackLink
== SecondEntry
) {
383 return InsertTailList (SecondEntry
, FirstEntry
);
387 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
388 // then there are no further steps necessary
390 if (Ptr
== InsertHeadList (SecondEntry
, FirstEntry
)) {
395 // Move SecondEntry to the front of Ptr
397 RemoveEntryList (SecondEntry
);
398 InsertTailList (Ptr
, SecondEntry
);
403 Removes a node from a doubly linked list, and returns the node that follows
406 Removes the node Entry from a doubly linked list. It is up to the caller of
407 this function to release the memory used by this node if that is required. On
408 exit, the node following Entry in the doubly linked list is returned. If
409 Entry is the only node in the linked list, then the head node of the linked
412 If Entry is NULL, then ASSERT().
413 If Entry is the head node of an empty list, then ASSERT().
414 If PcdMaximumLinkedListLenth is not zero, and the linked list containing
415 Entry contains more than PcdMaximumLinkedListLenth nodes, then ASSERT().
417 @param Entry A pointer to a node in a linked list
425 IN CONST LIST_ENTRY
*Entry
428 ASSERT (!IsListEmpty (Entry
));
430 Entry
->ForwardLink
->BackLink
= Entry
->BackLink
;
431 Entry
->BackLink
->ForwardLink
= Entry
->ForwardLink
;
432 return Entry
->ForwardLink
;