VirtualBox

source: vbox/trunk/include/iprt/list.h@ 68920

Last change on this file since 68920 was 62473, checked in by vboxsync, 8 years ago

(C) 2016

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 19.0 KB
Line 
1/** @file
2 * IPRT - Generic Doubly Linked List.
3 */
4
5/*
6 * Copyright (C) 2010-2016 Oracle Corporation
7 *
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.
15 *
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.
21 *
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.
24 */
25
26#ifndef ___iprt_list_h
27#define ___iprt_list_h
28
29#include <iprt/types.h>
30
31/** @defgroup grp_rt_list RTList - Generic Doubly Linked List
32 * @ingroup grp_rt
33 *
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
37 * walking the list.
38 *
39 * @{
40 */
41
42RT_C_DECLS_BEGIN
43
44/**
45 * A list node of a doubly linked list.
46 */
47typedef struct RTLISTNODE
48{
49 /** Pointer to the next list node. */
50 struct RTLISTNODE *pNext;
51 /** Pointer to the previous list node. */
52 struct RTLISTNODE *pPrev;
53} RTLISTNODE;
54/** Pointer to a list node. */
55typedef RTLISTNODE *PRTLISTNODE;
56/** Pointer to a const list node. */
57typedef RTLISTNODE const *PCRTLISTNODE;
58/** Pointer to a list node pointer. */
59typedef PRTLISTNODE *PPRTLISTNODE;
60
61/** The anchor (head/tail) of a doubly linked list.
62 *
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. */
66typedef RTLISTNODE RTLISTANCHOR;
67/** Pointer to a doubly linked list anchor. */
68typedef RTLISTANCHOR *PRTLISTANCHOR;
69/** Pointer to a const doubly linked list anchor. */
70typedef RTLISTANCHOR const *PCRTLISTANCHOR;
71
72/** Version of RTLISTNODE for holding a ring-3 only list in data which gets
73 * shared between multiple contexts */
74#if defined(IN_RING3)
75typedef RTLISTNODE RTLISTNODER3;
76#else
77typedef struct { RTR3PTR aOffLimits[2]; } RTLISTNODER3;
78#endif
79/** Version of RTLISTANCHOR for holding a ring-3 only list in data which gets
80 * shared between multiple contexts */
81typedef RTLISTNODER3 RTLISTANCHORR3;
82
83
84/**
85 * Initialize a list.
86 *
87 * @param pList Pointer to an unitialised list.
88 */
89DECLINLINE(void) RTListInit(PRTLISTNODE pList)
90{
91 pList->pNext = pList;
92 pList->pPrev = pList;
93}
94
95/**
96 * Append a node to the end of the list.
97 *
98 * @param pList The list to append the node to.
99 * @param pNode The node to append.
100 */
101DECLINLINE(void) RTListAppend(PRTLISTNODE pList, PRTLISTNODE pNode)
102{
103 pList->pPrev->pNext = pNode;
104 pNode->pPrev = pList->pPrev;
105 pNode->pNext = pList;
106 pList->pPrev = pNode;
107}
108
109/**
110 * Add a node as the first element of the list.
111 *
112 * @param pList The list to prepend the node to.
113 * @param pNode The node to prepend.
114 */
115DECLINLINE(void) RTListPrepend(PRTLISTNODE pList, PRTLISTNODE pNode)
116{
117 pList->pNext->pPrev = pNode;
118 pNode->pNext = pList->pNext;
119 pNode->pPrev = pList;
120 pList->pNext = pNode;
121}
122
123/**
124 * Inserts a node after the specified one.
125 *
126 * @param pCurNode The current node.
127 * @param pNewNode The node to insert.
128 */
129DECLINLINE(void) RTListNodeInsertAfter(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
130{
131 RTListPrepend(pCurNode, pNewNode);
132}
133
134/**
135 * Inserts a node before the specified one.
136 *
137 * @param pCurNode The current node.
138 * @param pNewNode The node to insert.
139 */
140DECLINLINE(void) RTListNodeInsertBefore(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
141{
142 RTListAppend(pCurNode, pNewNode);
143}
144
145/**
146 * Remove a node from a list.
147 *
148 * @param pNode The node to remove.
149 */
150DECLINLINE(void) RTListNodeRemove(PRTLISTNODE pNode)
151{
152 PRTLISTNODE pPrev = pNode->pPrev;
153 PRTLISTNODE pNext = pNode->pNext;
154
155 pPrev->pNext = pNext;
156 pNext->pPrev = pPrev;
157
158 /* poison */
159 pNode->pNext = NULL;
160 pNode->pPrev = NULL;
161}
162
163
164/**
165 * Remove a node from a list, returns value.
166 *
167 * @returns pNode
168 * @param pNode The node to remove.
169 */
170DECLINLINE(PRTLISTNODE) RTListNodeRemoveRet(PRTLISTNODE pNode)
171{
172 PRTLISTNODE pPrev = pNode->pPrev;
173 PRTLISTNODE pNext = pNode->pNext;
174
175 pPrev->pNext = pNext;
176 pNext->pPrev = pPrev;
177
178 /* poison */
179 pNode->pNext = NULL;
180 pNode->pPrev = NULL;
181
182 return pNode;
183}
184
185/**
186 * Checks if a node is the last element in the list.
187 *
188 * @retval true if the node is the last element in the list.
189 * @retval false otherwise
190 *
191 * @param pList The list.
192 * @param pNode The node to check.
193 */
194#define RTListNodeIsLast(pList, pNode) ((pNode)->pNext == (pList))
195
196/**
197 * Checks if a node is the first element in the list.
198 *
199 * @retval true if the node is the first element in the list.
200 * @retval false otherwise.
201 *
202 * @param pList The list.
203 * @param pNode The node to check.
204 */
205#define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList))
206
207/**
208 * Checks if a type converted node is actually the dummy element (@a pList).
209 *
210 * @retval true if the node is the dummy element in the list.
211 * @retval false otherwise.
212 *
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.
220 */
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) )
226
227/**
228 * Checks if a list is empty.
229 *
230 * @retval true if the list is empty.
231 * @retval false otherwise.
232 *
233 * @param pList The list to check.
234 */
235#define RTListIsEmpty(pList) ((pList)->pPrev == (pList))
236
237/**
238 * Returns the next node in the list.
239 *
240 * @returns The next node.
241 *
242 * @param pCurNode The current node.
243 * @param Type Structure the list node is a member of.
244 * @param Member The list node member.
245 */
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)
251
252/**
253 * Returns the previous node in the list.
254 *
255 * @returns The previous node.
256 *
257 * @param pCurNode The current node.
258 * @param Type Structure the list node is a member of.
259 * @param Member The list node member.
260 */
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)
266
267/**
268 * Returns the first element in the list (checks for empty list).
269 *
270 * @returns Pointer to the first list element, or NULL if empty list.
271 *
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.
275 */
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)
281
282/**
283 * Returns the last element in the list (checks for empty list).
284 *
285 * @returns Pointer to the last list element, or NULL if empty list.
286 *
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.
290 */
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)
296
297/**
298 * Returns the next node in the list or NULL if the end has been reached.
299 *
300 * @returns The next node, or NULL if end of list.
301 *
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.
306 */
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 )
312
313/**
314 * Returns the previous node in the list or NULL if the start has been reached.
315 *
316 * @returns The previous node, or NULL if end of list.
317 *
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.
322 */
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 )
328
329
330/**
331 * Removes and returns the first element in the list (checks for empty list).
332 *
333 * @returns Pointer to the first list element, or NULL if empty list.
334 *
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.
338 */
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)
344
345/**
346 * Removes and returns the last element in the list (checks for empty list).
347 *
348 * @returns Pointer to the last list element, or NULL if empty list.
349 *
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.
353 */
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)
359
360/**
361 * Removes and returns the next node in the list or NULL if the end has been
362 * reached.
363 *
364 * @returns The next node, or NULL if end of list.
365 *
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.
370 */
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 )
376
377/**
378 * Removes and returns the previous node in the list or NULL if the start has
379 * been reached.
380 *
381 * @returns The previous node, or NULL if end of list.
382 *
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.
387 */
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 )
393
394
395/**
396 * Enumerate the list in head to tail order.
397 *
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.
402 */
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) )
412
413
414/**
415 * Enumerate the list in head to tail order, safe against removal of the
416 * current node.
417 *
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
421 * the next element.
422 * @param Type Structure the list node is a member of.
423 * @param Member The list node member name.
424 */
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) )
438
439
440/**
441 * Enumerate the list in reverse order (tail to head).
442 *
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.
447 */
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) )
457
458
459/**
460 * Enumerate the list in reverse order (tail to head).
461 *
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.
468 */
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) )
482
483
484/**
485 * Move the given list to a new list header.
486 *
487 * @param pListDst The new list.
488 * @param pListSrc The list to move.
489 */
490DECLINLINE(void) RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
491{
492 if (!RTListIsEmpty(pListSrc))
493 {
494 pListDst->pNext = pListSrc->pNext;
495 pListDst->pPrev = pListSrc->pPrev;
496
497 /* Adjust the first and last element links */
498 pListDst->pNext->pPrev = pListDst;
499 pListDst->pPrev->pNext = pListDst;
500
501 /* Finally remove the elements from the source list */
502 RTListInit(pListSrc);
503 }
504}
505
506/**
507 * List concatenation.
508 *
509 * @returns nothing.
510 * @param pListDst The destination list.
511 * @param pListSrc The source list to concatenate.
512 */
513DECLINLINE(void) RTListConcatenate(PRTLISTANCHOR pListDst, PRTLISTANCHOR pListSrc)
514{
515 if (!RTListIsEmpty(pListSrc))
516 {
517 PRTLISTNODE pFirst = pListSrc->pNext;
518 PRTLISTNODE pLast = pListSrc->pPrev;
519
520 pListDst->pPrev->pNext = pFirst;
521 pFirst->pPrev = pListDst->pPrev;
522 pLast->pNext = pListDst;
523 pListDst->pPrev = pLast;
524
525 /* Finally remove the elements from the source list */
526 RTListInit(pListSrc);
527 }
528}
529
530RT_C_DECLS_END
531
532/** @} */
533
534#endif
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette