1.Updated some functions header of BaseLib with new MWG spec
[mirror_edk2.git] / MdePkg / Library / BaseLib / LinkedList.c
1 /** @file
2 Linked List Library Functions.
3
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
9
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.
12
13 Module Name: LinkedList.c
14
15 **/
16
17 BOOLEAN
18 EFIAPI
19 IsNodeInList (
20 IN CONST LIST_ENTRY *List,
21 IN CONST LIST_ENTRY *Node
22 )
23 {
24 UINTN Count;
25 CONST LIST_ENTRY *Ptr;
26 BOOLEAN Found;
27
28 //
29 // Test the validity of List and Node
30 //
31 ASSERT (List != NULL);
32 ASSERT (List->ForwardLink != NULL);
33 ASSERT (List->BackLink != NULL);
34 ASSERT (Node != NULL);
35
36 Count = PcdGet32 (PcdMaximumLinkedListLength);
37 if (Count != 0) {
38 Count++;
39 }
40
41 Ptr = List;
42 do {
43 Ptr = Ptr->ForwardLink;
44 Count--;
45 } while ((Ptr != List) && (Ptr != Node) && (Count > 0));
46 Found = (BOOLEAN)(Ptr == Node);
47
48 if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
49 while ((Count > 0) && (Ptr != List)) {
50 Ptr = Ptr->ForwardLink;
51 Count--;
52 }
53 ASSERT (Count > 0);
54 }
55
56 return Found;
57 }
58
59 /**
60 Initializes the head node of a doubly linked list, and returns the pointer to
61 the head node of the doubly linked list.
62
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.
67
68 If ListHead is NULL, then ASSERT().
69
70 @param ListHead A pointer to the head node of a new doubly linked list.
71
72 @return ListHead
73
74 **/
75 LIST_ENTRY *
76 EFIAPI
77 InitializeListHead (
78 IN OUT LIST_ENTRY *List
79 )
80
81 {
82 ASSERT (List != NULL);
83
84 List->ForwardLink = List;
85 List->BackLink = List;
86 return List;
87 }
88
89 /**
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.
92
93 Adds the node Entry at the beginning of the doubly linked list denoted by
94 ListHead, and returns ListHead.
95
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().
102
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.
106
107 @return ListHead
108
109 **/
110 LIST_ENTRY *
111 EFIAPI
112 InsertHeadList (
113 IN OUT LIST_ENTRY *List,
114 IN OUT LIST_ENTRY *Entry
115 )
116 {
117 //
118 // ASSERT List not too long and Entry is not one of the nodes of List
119 //
120 ASSERT (!IsNodeInList (List, Entry));
121
122 Entry->ForwardLink = List->ForwardLink;
123 Entry->BackLink = List;
124 Entry->ForwardLink->BackLink = Entry;
125 List->ForwardLink = Entry;
126 return List;
127 }
128
129 /**
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.
132
133 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
134 and returns ListHead.
135
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().
142
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
145 doubly linked list.
146
147 @return ListHead
148
149 **/
150 LIST_ENTRY *
151 EFIAPI
152 InsertTailList (
153 IN OUT LIST_ENTRY *List,
154 IN OUT LIST_ENTRY *Entry
155 )
156 {
157 //
158 // ASSERT List not too long and Entry is not one of the nodes of List
159 //
160 ASSERT (!IsNodeInList (List, Entry));
161
162 Entry->ForwardLink = List;
163 Entry->BackLink = List->BackLink;
164 Entry->BackLink->ForwardLink = Entry;
165 List->BackLink = Entry;
166 return List;
167 }
168
169 /**
170 Retrieves the first node of a doubly linked list.
171
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
174 returned.
175
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().
181
182 @param List A pointer to the head node of a doubly linked list.
183
184 @return The first node of a doubly linked list.
185 @retval NULL The list is empty.
186
187 **/
188 LIST_ENTRY *
189 EFIAPI
190 GetFirstNode (
191 IN CONST LIST_ENTRY *List
192 )
193 {
194 //
195 // ASSERT List not too long
196 //
197 ASSERT (IsNodeInList (List, List));
198
199 return List->ForwardLink;
200 }
201
202 /**
203 Retrieves the next node of a doubly linked list.
204
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
207 returned.
208
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().
215
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.
218
219 @return Pointer to the next node if one exists. Otherwise a null value which
220 is actually List is returned.
221
222 **/
223 LIST_ENTRY *
224 EFIAPI
225 GetNextNode (
226 IN CONST LIST_ENTRY *List,
227 IN CONST LIST_ENTRY *Node
228 )
229 {
230 //
231 // ASSERT List not too long and Node is one of the nodes of List
232 //
233 ASSERT (IsNodeInList (List, Node));
234
235 return Node->ForwardLink;
236 }
237
238 /**
239 Checks to see if a doubly linked list is empty or not.
240
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.
243
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().
249
250 @param ListHead A pointer to the head node of a doubly linked list.
251
252 @retval TRUE The linked list is empty.
253 @retval FALSE The linked list is not empty.
254
255 **/
256 BOOLEAN
257 EFIAPI
258 IsListEmpty (
259 IN CONST LIST_ENTRY *List
260 )
261 {
262 //
263 // ASSERT List not too long
264 //
265 ASSERT (IsNodeInList (List, List));
266
267 return (BOOLEAN)(List->ForwardLink == List);
268 }
269
270 /**
271 Determines if a node in a doubly linked list is null.
272
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().
276
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().
284
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.
287
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.
290
291 **/
292 BOOLEAN
293 EFIAPI
294 IsNull (
295 IN CONST LIST_ENTRY *List,
296 IN CONST LIST_ENTRY *Node
297 )
298 {
299 //
300 // ASSERT List not too long and Node is one of the nodes of List
301 //
302 ASSERT (IsNodeInList (List, Node));
303
304 return (BOOLEAN)(Node == List);
305 }
306
307 /**
308 Determines if a node the last node in a doubly linked list.
309
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().
313
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().
321
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.
324
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.
327
328 **/
329 BOOLEAN
330 EFIAPI
331 IsNodeAtEnd (
332 IN CONST LIST_ENTRY *List,
333 IN CONST LIST_ENTRY *Node
334 )
335 {
336 //
337 // ASSERT List not too long and Node is one of the nodes of List
338 //
339 ASSERT (IsNodeInList (List, Node));
340
341 return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
342 }
343
344 /**
345 Swaps the location of two nodes in a doubly linked list, and returns the
346 first node after the swap.
347
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
353 nodes are swapped.
354
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().
362
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.
365
366 **/
367 LIST_ENTRY *
368 EFIAPI
369 SwapListEntries (
370 IN OUT LIST_ENTRY *FirstEntry,
371 IN OUT LIST_ENTRY *SecondEntry
372 )
373 {
374 LIST_ENTRY *Ptr;
375
376 if (FirstEntry == SecondEntry) {
377 return SecondEntry;
378 }
379
380 //
381 // ASSERT Entry1 and Entry2 are in the same linked list
382 //
383 ASSERT (IsNodeInList (FirstEntry, SecondEntry));
384
385 //
386 // Ptr is the node pointed to by FirstEntry->ForwardLink
387 //
388 Ptr = RemoveEntryList (FirstEntry);
389
390 //
391 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
392 // immediately in front of SecondEntry
393 //
394 if (Ptr->BackLink == SecondEntry) {
395 return InsertTailList (SecondEntry, FirstEntry);
396 }
397
398 //
399 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
400 // then there are no further steps necessary
401 //
402 if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
403 return Ptr;
404 }
405
406 //
407 // Move SecondEntry to the front of Ptr
408 //
409 RemoveEntryList (SecondEntry);
410 InsertTailList (Ptr, SecondEntry);
411 return SecondEntry;
412 }
413
414 /**
415 Removes a node from a doubly linked list, and returns the node that follows
416 the removed node.
417
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
422 list is returned.
423
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().
429
430 @param Entry A pointer to a node in a linked list
431
432 @return Entry
433
434 **/
435 LIST_ENTRY *
436 EFIAPI
437 RemoveEntryList (
438 IN CONST LIST_ENTRY *Entry
439 )
440 {
441 ASSERT (!IsListEmpty (Entry));
442
443 Entry->ForwardLink->BackLink = Entry->BackLink;
444 Entry->BackLink->ForwardLink = Entry->ForwardLink;
445 return Entry->ForwardLink;
446 }