2 * IPRT - Generic Doubly Linked List.
6 * Copyright (C) 2010-2016 Oracle Corporation
8 * This file is part of VirtualBox Open Source Edition (OSE), as
9 * available from http://www.virtualbox.org. This file is free software;
10 * you can redistribute it and/or modify it under the terms of the GNU
11 * General Public License (GPL) as published by the Free Software
12 * Foundation, in version 2 as it comes in the "COPYING" file of the
13 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
14 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16 * The contents of this file may alternatively be used under the terms
17 * of the Common Development and Distribution License Version 1.0
18 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
19 * VirtualBox OSE distribution, in which case the provisions of the
20 * CDDL are applicable instead of those of the GPL.
22 * You may elect to license modified versions of this file under the
23 * terms and conditions of either the GPL or the CDDL or both.
26 #ifndef ___iprt_list_h
27 #define ___iprt_list_h
29 #include <iprt/types.h>
31 /** @defgroup grp_rt_list RTList - Generic Doubly Linked List
34 * The list implementation is circular without any type wise distintion between
35 * the list and its nodes. This can be confusing since the list head usually
36 * resides in a different structure than the nodes, so care must be taken when
45 * A list node of a doubly linked list.
47 typedef struct RTLISTNODE
49 /** Pointer to the next list node. */
50 struct RTLISTNODE
*pNext
;
51 /** Pointer to the previous list node. */
52 struct RTLISTNODE
*pPrev
;
54 /** Pointer to a list node. */
55 typedef RTLISTNODE
*PRTLISTNODE
;
56 /** Pointer to a const list node. */
57 typedef RTLISTNODE
const *PCRTLISTNODE
;
58 /** Pointer to a list node pointer. */
59 typedef PRTLISTNODE
*PPRTLISTNODE
;
61 /** The anchor (head/tail) of a doubly linked list.
63 * @remarks Please use this instead of RTLISTNODE to indicate a list
64 * head/tail. It makes the code so much easier to read. Also,
65 * always mention the actual list node type(s) in the comment. */
66 typedef RTLISTNODE RTLISTANCHOR
;
67 /** Pointer to a doubly linked list anchor. */
68 typedef RTLISTANCHOR
*PRTLISTANCHOR
;
69 /** Pointer to a const doubly linked list anchor. */
70 typedef RTLISTANCHOR
const *PCRTLISTANCHOR
;
72 /** Version of RTLISTNODE for holding a ring-3 only list in data which gets
73 * shared between multiple contexts */
75 typedef RTLISTNODE RTLISTNODER3
;
77 typedef struct { RTR3PTR aOffLimits
[2]; } RTLISTNODER3
;
79 /** Version of RTLISTANCHOR for holding a ring-3 only list in data which gets
80 * shared between multiple contexts */
81 typedef RTLISTNODER3 RTLISTANCHORR3
;
87 * @param pList Pointer to an unitialised list.
89 DECLINLINE(void) RTListInit(PRTLISTNODE pList
)
96 * Append a node to the end of the list.
98 * @param pList The list to append the node to.
99 * @param pNode The node to append.
101 DECLINLINE(void) RTListAppend(PRTLISTNODE pList
, PRTLISTNODE pNode
)
103 pList
->pPrev
->pNext
= pNode
;
104 pNode
->pPrev
= pList
->pPrev
;
105 pNode
->pNext
= pList
;
106 pList
->pPrev
= pNode
;
110 * Add a node as the first element of the list.
112 * @param pList The list to prepend the node to.
113 * @param pNode The node to prepend.
115 DECLINLINE(void) RTListPrepend(PRTLISTNODE pList
, PRTLISTNODE pNode
)
117 pList
->pNext
->pPrev
= pNode
;
118 pNode
->pNext
= pList
->pNext
;
119 pNode
->pPrev
= pList
;
120 pList
->pNext
= pNode
;
124 * Inserts a node after the specified one.
126 * @param pCurNode The current node.
127 * @param pNewNode The node to insert.
129 DECLINLINE(void) RTListNodeInsertAfter(PRTLISTNODE pCurNode
, PRTLISTNODE pNewNode
)
131 RTListPrepend(pCurNode
, pNewNode
);
135 * Inserts a node before the specified one.
137 * @param pCurNode The current node.
138 * @param pNewNode The node to insert.
140 DECLINLINE(void) RTListNodeInsertBefore(PRTLISTNODE pCurNode
, PRTLISTNODE pNewNode
)
142 RTListAppend(pCurNode
, pNewNode
);
146 * Remove a node from a list.
148 * @param pNode The node to remove.
150 DECLINLINE(void) RTListNodeRemove(PRTLISTNODE pNode
)
152 PRTLISTNODE pPrev
= pNode
->pPrev
;
153 PRTLISTNODE pNext
= pNode
->pNext
;
155 pPrev
->pNext
= pNext
;
156 pNext
->pPrev
= pPrev
;
165 * Remove a node from a list, returns value.
168 * @param pNode The node to remove.
170 DECLINLINE(PRTLISTNODE
) RTListNodeRemoveRet(PRTLISTNODE pNode
)
172 PRTLISTNODE pPrev
= pNode
->pPrev
;
173 PRTLISTNODE pNext
= pNode
->pNext
;
175 pPrev
->pNext
= pNext
;
176 pNext
->pPrev
= pPrev
;
186 * Checks if a node is the last element in the list.
188 * @retval true if the node is the last element in the list.
189 * @retval false otherwise
191 * @param pList The list.
192 * @param pNode The node to check.
194 #define RTListNodeIsLast(pList, pNode) ((pNode)->pNext == (pList))
197 * Checks if a node is the first element in the list.
199 * @retval true if the node is the first element in the list.
200 * @retval false otherwise.
202 * @param pList The list.
203 * @param pNode The node to check.
205 #define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList))
208 * Checks if a type converted node is actually the dummy element (@a pList).
210 * @retval true if the node is the dummy element in the list.
211 * @retval false otherwise.
213 * @param pList The list.
214 * @param pNode The node structure to check. Typically
215 * something obtained from RTListNodeGetNext() or
216 * RTListNodeGetPrev(). This is NOT a PRTLISTNODE
217 * but something that contains a RTLISTNODE member!
218 * @param Type Structure the list node is a member of.
219 * @param Member The list node member.
221 #define RTListNodeIsDummy(pList, pNode, Type, Member) \
222 ( (pNode) == RT_FROM_MEMBER((pList), Type, Member) )
223 /** @copydoc RTListNodeIsDummy */
224 #define RTListNodeIsDummyCpp(pList, pNode, Type, Member) \
225 ( (pNode) == RT_FROM_CPP_MEMBER((pList), Type, Member) )
228 * Checks if a list is empty.
230 * @retval true if the list is empty.
231 * @retval false otherwise.
233 * @param pList The list to check.
235 #define RTListIsEmpty(pList) ((pList)->pPrev == (pList))
238 * Returns the next node in the list.
240 * @returns The next node.
242 * @param pCurNode The current node.
243 * @param Type Structure the list node is a member of.
244 * @param Member The list node member.
246 #define RTListNodeGetNext(pCurNode, Type, Member) \
247 RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
248 /** @copydoc RTListNodeGetNext */
249 #define RTListNodeGetNextCpp(pCurNode, Type, Member) \
250 RT_FROM_CPP_MEMBER((pCurNode)->pNext, Type, Member)
253 * Returns the previous node in the list.
255 * @returns The previous node.
257 * @param pCurNode The current node.
258 * @param Type Structure the list node is a member of.
259 * @param Member The list node member.
261 #define RTListNodeGetPrev(pCurNode, Type, Member) \
262 RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
263 /** @copydoc RTListNodeGetPrev */
264 #define RTListNodeGetPrevCpp(pCurNode, Type, Member) \
265 RT_FROM_CPP_MEMBER((pCurNode)->pPrev, Type, Member)
268 * Returns the first element in the list (checks for empty list).
270 * @returns Pointer to the first list element, or NULL if empty list.
272 * @param pList List to get the first element from.
273 * @param Type Structure the list node is a member of.
274 * @param Member The list node member.
276 #define RTListGetFirst(pList, Type, Member) \
277 (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
278 /** @copydoc RTListGetFirst */
279 #define RTListGetFirstCpp(pList, Type, Member) \
280 (!RTListIsEmpty(pList) ? RTListNodeGetNextCpp(pList, Type, Member) : NULL)
283 * Returns the last element in the list (checks for empty list).
285 * @returns Pointer to the last list element, or NULL if empty list.
287 * @param pList List to get the last element from.
288 * @param Type Structure the list node is a member of.
289 * @param Member The list node member.
291 #define RTListGetLast(pList, Type, Member) \
292 (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
293 /** @copydoc RTListGetLast */
294 #define RTListGetLastCpp(pList, Type, Member) \
295 (!RTListIsEmpty(pList) ? RTListNodeGetPrevCpp(pList, Type, Member) : NULL)
298 * Returns the next node in the list or NULL if the end has been reached.
300 * @returns The next node, or NULL if end of list.
302 * @param pList The list @a pCurNode is linked on.
303 * @param pCurNode The current node, of type @a Type.
304 * @param Type Structure the list node is a member of.
305 * @param Member The list node member.
307 #define RTListGetNext(pList, pCurNode, Type, Member) \
308 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
309 /** @copydoc RTListGetNext */
310 #define RTListGetNextCpp(pList, pCurNode, Type, Member) \
311 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
314 * Returns the previous node in the list or NULL if the start has been reached.
316 * @returns The previous node, or NULL if end of list.
318 * @param pList The list @a pCurNode is linked on.
319 * @param pCurNode The current node, of type @a Type.
320 * @param Type Structure the list node is a member of.
321 * @param Member The list node member.
323 #define RTListGetPrev(pList, pCurNode, Type, Member) \
324 ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
325 /** @copydoc RTListGetPrev */
326 #define RTListGetPrevCpp(pList, pCurNode, Type, Member) \
327 ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
331 * Removes and returns the first element in the list (checks for empty list).
333 * @returns Pointer to the first list element, or NULL if empty list.
335 * @param pList List to get the first element from.
336 * @param Type Structure the list node is a member of.
337 * @param Member The list node member.
339 #define RTListRemoveFirst(pList, Type, Member) \
340 (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
341 /** @copydoc RTListRemoveFirst */
342 #define RTListRemoveFirstCpp(pList, Type, Member) \
343 (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
346 * Removes and returns the last element in the list (checks for empty list).
348 * @returns Pointer to the last list element, or NULL if empty list.
350 * @param pList List to get the last element from.
351 * @param Type Structure the list node is a member of.
352 * @param Member The list node member.
354 #define RTListRemoveLast(pList, Type, Member) \
355 (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
356 /** @copydoc RTListRemoveLast */
357 #define RTListRemoveLastCpp(pList, Type, Member) \
358 (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
361 * Removes and returns the next node in the list or NULL if the end has been
364 * @returns The next node, or NULL if end of list.
366 * @param pList The list @a pCurNode is linked on.
367 * @param pCurNode The current node, of type @a Type.
368 * @param Type Structure the list node is a member of.
369 * @param Member The list node member.
371 #define RTListRemoveNext(pList, pCurNode, Type, Member) \
372 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
373 /** @copydoc RTListRemoveNext */
374 #define RTListRemoveNextCpp(pList, pCurNode, Type, Member) \
375 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
378 * Removes and returns the previous node in the list or NULL if the start has
381 * @returns The previous node, or NULL if end of list.
383 * @param pList The list @a pCurNode is linked on.
384 * @param pCurNode The current node, of type @a Type.
385 * @param Type Structure the list node is a member of.
386 * @param Member The list node member.
388 #define RTListRemovePrev(pList, pCurNode, Type, Member) \
389 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
390 /** @copydoc RTListRemovePrev */
391 #define RTListRemovePrevCpp(pList, pCurNode, Type, Member) \
392 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
396 * Enumerate the list in head to tail order.
398 * @param pList List to enumerate.
399 * @param pIterator The iterator variable name.
400 * @param Type Structure the list node is a member of.
401 * @param Member The list node member name.
403 #define RTListForEach(pList, pIterator, Type, Member) \
404 for (pIterator = RTListNodeGetNext(pList, Type, Member); \
405 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
406 pIterator = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
407 /** @copydoc RTListForEach */
408 #define RTListForEachCpp(pList, pIterator, Type, Member) \
409 for (pIterator = RTListNodeGetNextCpp(pList, Type, Member); \
410 !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
411 pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
415 * Enumerate the list in head to tail order, safe against removal of the
418 * @param pList List to enumerate.
419 * @param pIterator The iterator variable name.
420 * @param pIterNext The name of the variable saving the pointer to
422 * @param Type Structure the list node is a member of.
423 * @param Member The list node member name.
425 #define RTListForEachSafe(pList, pIterator, pIterNext, Type, Member) \
426 for (pIterator = RTListNodeGetNext(pList, Type, Member), \
427 pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member); \
428 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
429 pIterator = pIterNext, \
430 pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
431 /** @copydoc RTListForEachSafe */
432 #define RTListForEachSafeCpp(pList, pIterator, pIterNext, Type, Member) \
433 for (pIterator = RTListNodeGetNextCpp(pList, Type, Member), \
434 pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member); \
435 !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
436 pIterator = pIterNext, \
437 pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
441 * Enumerate the list in reverse order (tail to head).
443 * @param pList List to enumerate.
444 * @param pIterator The iterator variable name.
445 * @param Type Structure the list node is a member of.
446 * @param Member The list node member name.
448 #define RTListForEachReverse(pList, pIterator, Type, Member) \
449 for (pIterator = RTListNodeGetPrev(pList, Type, Member); \
450 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
451 pIterator = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
452 /** @copydoc RTListForEachReverse */
453 #define RTListForEachReverseCpp(pList, pIterator, Type, Member) \
454 for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member); \
455 !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
456 pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
460 * Enumerate the list in reverse order (tail to head).
462 * @param pList List to enumerate.
463 * @param pIterator The iterator variable name.
464 * @param pIterPrev The name of the variable saving the pointer to
465 * the previous element.
466 * @param Type Structure the list node is a member of.
467 * @param Member The list node member name.
469 #define RTListForEachReverseSafe(pList, pIterator, pIterPrev, Type, Member) \
470 for (pIterator = RTListNodeGetPrev(pList, Type, Member), \
471 pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member); \
472 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
473 pIterator = pIterPrev, \
474 pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
475 /** @copydoc RTListForEachReverseSafe */
476 #define RTListForEachReverseSafeCpp(pList, pIterator, pIterPrev, Type, Member) \
477 for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member), \
478 pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member); \
479 !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
480 pIterator = pIterPrev, \
481 pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
485 * Move the given list to a new list header.
487 * @param pListDst The new list.
488 * @param pListSrc The list to move.
490 DECLINLINE(void) RTListMove(PRTLISTNODE pListDst
, PRTLISTNODE pListSrc
)
492 if (!RTListIsEmpty(pListSrc
))
494 pListDst
->pNext
= pListSrc
->pNext
;
495 pListDst
->pPrev
= pListSrc
->pPrev
;
497 /* Adjust the first and last element links */
498 pListDst
->pNext
->pPrev
= pListDst
;
499 pListDst
->pPrev
->pNext
= pListDst
;
501 /* Finally remove the elements from the source list */
502 RTListInit(pListSrc
);
507 * List concatenation.
510 * @param pListDst The destination list.
511 * @param pListSrc The source list to concatenate.
513 DECLINLINE(void) RTListConcatenate(PRTLISTANCHOR pListDst
, PRTLISTANCHOR pListSrc
)
515 if (!RTListIsEmpty(pListSrc
))
517 PRTLISTNODE pFirst
= pListSrc
->pNext
;
518 PRTLISTNODE pLast
= pListSrc
->pPrev
;
520 pListDst
->pPrev
->pNext
= pFirst
;
521 pFirst
->pPrev
= pListDst
->pPrev
;
522 pLast
->pNext
= pListDst
;
523 pListDst
->pPrev
= pLast
;
525 /* Finally remove the elements from the source list */
526 RTListInit(pListSrc
);