9ad1b0875b0ecc3d1280a610e98144235c9449e4
[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 = FixedPcdGet32 (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 (FixedPcdGet32 (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 ListHead contains more than
100 PcdMaximumLinkedListLenth nodes, then ASSERT().
101
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.
105
106 @return ListHead
107
108 **/
109 LIST_ENTRY *
110 EFIAPI
111 InsertHeadList (
112 IN OUT LIST_ENTRY *List,
113 IN OUT LIST_ENTRY *Entry
114 )
115 {
116 //
117 // ASSERT List not too long and Entry is not one of the nodes of List
118 //
119 ASSERT (!IsNodeInList (List, Entry));
120
121 Entry->ForwardLink = List->ForwardLink;
122 Entry->BackLink = List;
123 Entry->ForwardLink->BackLink = Entry;
124 List->ForwardLink = Entry;
125 return List;
126 }
127
128 /**
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.
131
132 Adds the node Entry to the end of the doubly linked list denoted by ListHead,
133 and returns ListHead.
134
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().
140
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
143 doubly linked list.
144
145 @return ListHead
146
147 **/
148 LIST_ENTRY *
149 EFIAPI
150 InsertTailList (
151 IN OUT LIST_ENTRY *List,
152 IN OUT LIST_ENTRY *Entry
153 )
154 {
155 //
156 // ASSERT List not too long and Entry is not one of the nodes of List
157 //
158 ASSERT (!IsNodeInList (List, Entry));
159
160 Entry->ForwardLink = List;
161 Entry->BackLink = List->BackLink;
162 Entry->BackLink->ForwardLink = Entry;
163 List->BackLink = Entry;
164 return List;
165 }
166
167 /**
168 Retrieves the first node of a doubly linked list.
169
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
172 returned.
173
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().
178
179 @param List A pointer to the head node of a doubly linked list.
180
181 @return The first node of a doubly linked list.
182 @retval NULL The list is empty.
183
184 **/
185 LIST_ENTRY *
186 EFIAPI
187 GetFirstNode (
188 IN CONST LIST_ENTRY *List
189 )
190 {
191 //
192 // ASSERT List not too long
193 //
194 ASSERT (IsNodeInList (List, List));
195
196 return List->ForwardLink;
197 }
198
199 /**
200 Retrieves the next node of a doubly linked list.
201
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
204 returned.
205
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().
212
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.
215
216 @return Pointer to the next node if one exists. Otherwise a null value which
217 is actually List is returned.
218
219 **/
220 LIST_ENTRY *
221 EFIAPI
222 GetNextNode (
223 IN CONST LIST_ENTRY *List,
224 IN CONST LIST_ENTRY *Node
225 )
226 {
227 //
228 // ASSERT List not too long and Node is one of the nodes of List
229 //
230 ASSERT (IsNodeInList (List, Node));
231
232 return Node->ForwardLink;
233 }
234
235 /**
236 Checks to see if a doubly linked list is empty or not.
237
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.
240
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().
245
246 @param ListHead A pointer to the head node of a doubly linked list.
247
248 @retval TRUE The linked list is empty.
249 @retval FALSE The linked list is not empty.
250
251 **/
252 BOOLEAN
253 EFIAPI
254 IsListEmpty (
255 IN CONST LIST_ENTRY *List
256 )
257 {
258 //
259 // ASSERT List not too long
260 //
261 ASSERT (IsNodeInList (List, List));
262
263 return (BOOLEAN)(List->ForwardLink == List);
264 }
265
266 /**
267 Determines if a node in a doubly linked list is null.
268
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().
272
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().
279
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.
282
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.
285
286 **/
287 BOOLEAN
288 EFIAPI
289 IsNull (
290 IN CONST LIST_ENTRY *List,
291 IN CONST LIST_ENTRY *Node
292 )
293 {
294 //
295 // ASSERT List not too long and Node is one of the nodes of List
296 //
297 ASSERT (IsNodeInList (List, Node));
298
299 return (BOOLEAN)(Node == List);
300 }
301
302 /**
303 Determines if a node the last node in a doubly linked list.
304
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().
308
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().
315
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.
318
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.
321
322 **/
323 BOOLEAN
324 EFIAPI
325 IsNodeAtEnd (
326 IN CONST LIST_ENTRY *List,
327 IN CONST LIST_ENTRY *Node
328 )
329 {
330 //
331 // ASSERT List not too long and Node is one of the nodes of List
332 //
333 ASSERT (IsNodeInList (List, Node));
334
335 return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
336 }
337
338 /**
339 Swaps the location of two nodes in a doubly linked list, and returns the
340 first node after the swap.
341
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
347 nodes are swapped.
348
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().
355
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.
358
359 **/
360 LIST_ENTRY *
361 EFIAPI
362 SwapListEntries (
363 IN OUT LIST_ENTRY *FirstEntry,
364 IN OUT LIST_ENTRY *SecondEntry
365 )
366 {
367 LIST_ENTRY *Ptr;
368
369 if (FirstEntry == SecondEntry) {
370 return SecondEntry;
371 }
372
373 //
374 // ASSERT Entry1 and Entry2 are in the same linked list
375 //
376 ASSERT (IsNodeInList (FirstEntry, SecondEntry));
377
378 //
379 // Ptr is the node pointed to by FirstEntry->ForwardLink
380 //
381 Ptr = RemoveEntryList (FirstEntry);
382
383 //
384 // If FirstEntry immediately follows SecondEntry, FirstEntry willl be placed
385 // immediately in front of SecondEntry
386 //
387 if (Ptr->BackLink == SecondEntry) {
388 return InsertTailList (SecondEntry, FirstEntry);
389 }
390
391 //
392 // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,
393 // then there are no further steps necessary
394 //
395 if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {
396 return Ptr;
397 }
398
399 //
400 // Move SecondEntry to the front of Ptr
401 //
402 RemoveEntryList (SecondEntry);
403 InsertTailList (Ptr, SecondEntry);
404 return SecondEntry;
405 }
406
407 /**
408 Removes a node from a doubly linked list, and returns the node that follows
409 the removed node.
410
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
415 list is returned.
416
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().
421
422 @param Entry A pointer to a node in a linked list
423
424 @return Entry
425
426 **/
427 LIST_ENTRY *
428 EFIAPI
429 RemoveEntryList (
430 IN CONST LIST_ENTRY *Entry
431 )
432 {
433 ASSERT (!IsListEmpty (Entry));
434
435 Entry->ForwardLink->BackLink = Entry->BackLink;
436 Entry->BackLink->ForwardLink = Entry->ForwardLink;
437 return Entry->ForwardLink;
438 }