VirtualBox

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

Last change on this file since 103224 was 99739, checked in by vboxsync, 17 months ago

*: doxygen corrections (mostly about removing @returns from functions returning void).

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 19.8 KB
Line 
1/** @file
2 * IPRT - Generic Doubly Linked List.
3 */
4
5/*
6 * Copyright (C) 2010-2023 Oracle and/or its affiliates.
7 *
8 * This file is part of VirtualBox base platform packages, as
9 * available from https://www.virtualbox.org.
10 *
11 * This program is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU General Public License
13 * as published by the Free Software Foundation, in version 3 of the
14 * License.
15 *
16 * This program is distributed in the hope that it will be useful, but
17 * WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with this program; if not, see <https://www.gnu.org/licenses>.
23 *
24 * The contents of this file may alternatively be used under the terms
25 * of the Common Development and Distribution License Version 1.0
26 * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
27 * in the VirtualBox distribution, in which case the provisions of the
28 * CDDL are applicable instead of those of the GPL.
29 *
30 * You may elect to license modified versions of this file under the
31 * terms and conditions of either the GPL or the CDDL or both.
32 *
33 * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
34 */
35
36#ifndef IPRT_INCLUDED_list_h
37#define IPRT_INCLUDED_list_h
38#ifndef RT_WITHOUT_PRAGMA_ONCE
39# pragma once
40#endif
41
42#include <iprt/types.h>
43
44/** @defgroup grp_rt_list RTList - Generic Doubly Linked List
45 * @ingroup grp_rt
46 *
47 * The list implementation is circular without any type wise distintion between
48 * the list and its nodes. This can be confusing since the list head usually
49 * resides in a different structure than the nodes, so care must be taken when
50 * walking the list.
51 *
52 * @{
53 */
54
55RT_C_DECLS_BEGIN
56
57/**
58 * A list node of a doubly linked list.
59 */
60typedef struct RTLISTNODE
61{
62 /** Pointer to the next list node. */
63 struct RTLISTNODE *pNext;
64 /** Pointer to the previous list node. */
65 struct RTLISTNODE *pPrev;
66} RTLISTNODE;
67/** Pointer to a list node. */
68typedef RTLISTNODE *PRTLISTNODE;
69/** Pointer to a const list node. */
70typedef RTLISTNODE const *PCRTLISTNODE;
71/** Pointer to a list node pointer. */
72typedef PRTLISTNODE *PPRTLISTNODE;
73
74/** The anchor (head/tail) of a doubly linked list.
75 *
76 * @remarks Please use this instead of RTLISTNODE to indicate a list
77 * head/tail. It makes the code so much easier to read. Also,
78 * always mention the actual list node type(s) in the comment. */
79typedef RTLISTNODE RTLISTANCHOR;
80/** Pointer to a doubly linked list anchor. */
81typedef RTLISTANCHOR *PRTLISTANCHOR;
82/** Pointer to a const doubly linked list anchor. */
83typedef RTLISTANCHOR const *PCRTLISTANCHOR;
84
85/** Version of RTLISTNODE for holding a ring-3 only list in data which gets
86 * shared between multiple contexts. */
87#ifdef IN_RING3
88typedef RTLISTNODE RTLISTNODER3;
89#else
90typedef struct { RTR3PTR aOffLimits[2]; } RTLISTNODER3;
91#endif
92/** Version of RTLISTANCHOR for holding a ring-3 only list in data which gets
93 * shared between multiple contexts. */
94typedef RTLISTNODER3 RTLISTANCHORR3;
95
96/** Version of RTLISTNODE for holding a ring-0 only list in data which gets
97 * shared between multiple contexts. */
98#ifdef IN_RING0
99typedef RTLISTNODE RTLISTNODER0;
100#else
101typedef struct { RTR0PTR aOffLimits[2]; } RTLISTNODER0;
102#endif
103/** Version of RTLISTANCHOR for holding a ring-0 only list in data which gets
104 * shared between multiple contexts. */
105typedef RTLISTNODER0 RTLISTANCHORR0;
106
107
108/**
109 * Initialize a list.
110 *
111 * @param pList Pointer to an unitialised list.
112 */
113DECLINLINE(void) RTListInit(PRTLISTNODE pList)
114{
115 pList->pNext = pList;
116 pList->pPrev = pList;
117}
118
119/**
120 * Append a node to the end of the list.
121 *
122 * @param pList The list to append the node to.
123 * @param pNode The node to append.
124 */
125DECLINLINE(void) RTListAppend(PRTLISTNODE pList, PRTLISTNODE pNode)
126{
127 pList->pPrev->pNext = pNode;
128 pNode->pPrev = pList->pPrev;
129 pNode->pNext = pList;
130 pList->pPrev = pNode;
131}
132
133/**
134 * Add a node as the first element of the list.
135 *
136 * @param pList The list to prepend the node to.
137 * @param pNode The node to prepend.
138 */
139DECLINLINE(void) RTListPrepend(PRTLISTNODE pList, PRTLISTNODE pNode)
140{
141 pList->pNext->pPrev = pNode;
142 pNode->pNext = pList->pNext;
143 pNode->pPrev = pList;
144 pList->pNext = pNode;
145}
146
147/**
148 * Inserts a node after the specified one.
149 *
150 * @param pCurNode The current node.
151 * @param pNewNode The node to insert.
152 */
153DECLINLINE(void) RTListNodeInsertAfter(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
154{
155 RTListPrepend(pCurNode, pNewNode);
156}
157
158/**
159 * Inserts a node before the specified one.
160 *
161 * @param pCurNode The current node.
162 * @param pNewNode The node to insert.
163 */
164DECLINLINE(void) RTListNodeInsertBefore(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
165{
166 RTListAppend(pCurNode, pNewNode);
167}
168
169/**
170 * Remove a node from a list.
171 *
172 * @param pNode The node to remove.
173 */
174DECLINLINE(void) RTListNodeRemove(PRTLISTNODE pNode)
175{
176 PRTLISTNODE pPrev = pNode->pPrev;
177 PRTLISTNODE pNext = pNode->pNext;
178
179 pPrev->pNext = pNext;
180 pNext->pPrev = pPrev;
181
182 /* poison */
183 pNode->pNext = NULL;
184 pNode->pPrev = NULL;
185}
186
187
188/**
189 * Remove a node from a list, returns value.
190 *
191 * @returns pNode
192 * @param pNode The node to remove.
193 */
194DECLINLINE(PRTLISTNODE) RTListNodeRemoveRet(PRTLISTNODE pNode)
195{
196 PRTLISTNODE pPrev = pNode->pPrev;
197 PRTLISTNODE pNext = pNode->pNext;
198
199 pPrev->pNext = pNext;
200 pNext->pPrev = pPrev;
201
202 /* poison */
203 pNode->pNext = NULL;
204 pNode->pPrev = NULL;
205
206 return pNode;
207}
208
209/**
210 * Checks if a node is the last element in the list.
211 *
212 * @retval true if the node is the last element in the list.
213 * @retval false otherwise
214 *
215 * @param pList The list.
216 * @param pNode The node to check.
217 */
218#define RTListNodeIsLast(pList, pNode) ((pNode)->pNext == (pList))
219
220/**
221 * Checks if a node is the first element in the list.
222 *
223 * @retval true if the node is the first element in the list.
224 * @retval false otherwise.
225 *
226 * @param pList The list.
227 * @param pNode The node to check.
228 */
229#define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList))
230
231/**
232 * Checks if a type converted node is actually the dummy element (@a pList).
233 *
234 * @retval true if the node is the dummy element in the list.
235 * @retval false otherwise.
236 *
237 * @param pList The list.
238 * @param pNode The node structure to check. Typically
239 * something obtained from RTListNodeGetNext() or
240 * RTListNodeGetPrev(). This is NOT a PRTLISTNODE
241 * but something that contains a RTLISTNODE member!
242 * @param Type Structure the list node is a member of.
243 * @param Member The list node member.
244 */
245#define RTListNodeIsDummy(pList, pNode, Type, Member) \
246 ( (pNode) == RT_FROM_MEMBER((pList), Type, Member) )
247/** @copydoc RTListNodeIsDummy */
248#define RTListNodeIsDummyCpp(pList, pNode, Type, Member) \
249 ( (pNode) == RT_FROM_CPP_MEMBER((pList), Type, Member) )
250
251/**
252 * Checks if a list is empty.
253 *
254 * @retval true if the list is empty.
255 * @retval false otherwise.
256 *
257 * @param pList The list to check.
258 */
259#define RTListIsEmpty(pList) ((pList)->pPrev == (pList))
260
261/**
262 * Returns the next node in the list.
263 *
264 * @returns The next node.
265 *
266 * @param pCurNode The current node.
267 * @param Type Structure the list node is a member of.
268 * @param Member The list node member.
269 */
270#define RTListNodeGetNext(pCurNode, Type, Member) \
271 RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
272/** @copydoc RTListNodeGetNext */
273#define RTListNodeGetNextCpp(pCurNode, Type, Member) \
274 RT_FROM_CPP_MEMBER((pCurNode)->pNext, Type, Member)
275
276/**
277 * Returns the previous node in the list.
278 *
279 * @returns The previous node.
280 *
281 * @param pCurNode The current node.
282 * @param Type Structure the list node is a member of.
283 * @param Member The list node member.
284 */
285#define RTListNodeGetPrev(pCurNode, Type, Member) \
286 RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
287/** @copydoc RTListNodeGetPrev */
288#define RTListNodeGetPrevCpp(pCurNode, Type, Member) \
289 RT_FROM_CPP_MEMBER((pCurNode)->pPrev, Type, Member)
290
291/**
292 * Returns the first element in the list (checks for empty list).
293 *
294 * @returns Pointer to the first list element, or NULL if empty list.
295 *
296 * @param pList List to get the first element from.
297 * @param Type Structure the list node is a member of.
298 * @param Member The list node member.
299 */
300#define RTListGetFirst(pList, Type, Member) \
301 (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
302/** @copydoc RTListGetFirst */
303#define RTListGetFirstCpp(pList, Type, Member) \
304 (!RTListIsEmpty(pList) ? RTListNodeGetNextCpp(pList, Type, Member) : NULL)
305
306/**
307 * Returns the last element in the list (checks for empty list).
308 *
309 * @returns Pointer to the last list element, or NULL if empty list.
310 *
311 * @param pList List to get the last element from.
312 * @param Type Structure the list node is a member of.
313 * @param Member The list node member.
314 */
315#define RTListGetLast(pList, Type, Member) \
316 (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
317/** @copydoc RTListGetLast */
318#define RTListGetLastCpp(pList, Type, Member) \
319 (!RTListIsEmpty(pList) ? RTListNodeGetPrevCpp(pList, Type, Member) : NULL)
320
321/**
322 * Returns the next node in the list or NULL if the end has been reached.
323 *
324 * @returns The next node, or NULL if end of list.
325 *
326 * @param pList The list @a pCurNode is linked on.
327 * @param pCurNode The current node, of type @a Type.
328 * @param Type Structure the list node is a member of.
329 * @param Member The list node member.
330 */
331#define RTListGetNext(pList, pCurNode, Type, Member) \
332 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
333/** @copydoc RTListGetNext */
334#define RTListGetNextCpp(pList, pCurNode, Type, Member) \
335 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
336
337/**
338 * Returns the previous node in the list or NULL if the start has been reached.
339 *
340 * @returns The previous node, or NULL if end of list.
341 *
342 * @param pList The list @a pCurNode is linked on.
343 * @param pCurNode The current node, of type @a Type.
344 * @param Type Structure the list node is a member of.
345 * @param Member The list node member.
346 */
347#define RTListGetPrev(pList, pCurNode, Type, Member) \
348 ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
349/** @copydoc RTListGetPrev */
350#define RTListGetPrevCpp(pList, pCurNode, Type, Member) \
351 ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
352
353
354/**
355 * Removes and returns the first element in the list (checks for empty list).
356 *
357 * @returns Pointer to the first list element, or NULL if empty list.
358 *
359 * @param pList List to get the first element from.
360 * @param Type Structure the list node is a member of.
361 * @param Member The list node member.
362 */
363#define RTListRemoveFirst(pList, Type, Member) \
364 (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
365/** @copydoc RTListRemoveFirst */
366#define RTListRemoveFirstCpp(pList, Type, Member) \
367 (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
368
369/**
370 * Removes and returns the last element in the list (checks for empty list).
371 *
372 * @returns Pointer to the last list element, or NULL if empty list.
373 *
374 * @param pList List to get the last element from.
375 * @param Type Structure the list node is a member of.
376 * @param Member The list node member.
377 */
378#define RTListRemoveLast(pList, Type, Member) \
379 (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
380/** @copydoc RTListRemoveLast */
381#define RTListRemoveLastCpp(pList, Type, Member) \
382 (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
383
384/**
385 * Removes and returns the next node in the list or NULL if the end has been
386 * reached.
387 *
388 * @returns The next node, or NULL if end of list.
389 *
390 * @param pList The list @a pCurNode is linked on.
391 * @param pCurNode The current node, of type @a Type.
392 * @param Type Structure the list node is a member of.
393 * @param Member The list node member.
394 */
395#define RTListRemoveNext(pList, pCurNode, Type, Member) \
396 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
397/** @copydoc RTListRemoveNext */
398#define RTListRemoveNextCpp(pList, pCurNode, Type, Member) \
399 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
400
401/**
402 * Removes and returns the previous node in the list or NULL if the start has
403 * been reached.
404 *
405 * @returns The previous node, or NULL if end of list.
406 *
407 * @param pList The list @a pCurNode is linked on.
408 * @param pCurNode The current node, of type @a Type.
409 * @param Type Structure the list node is a member of.
410 * @param Member The list node member.
411 */
412#define RTListRemovePrev(pList, pCurNode, Type, Member) \
413 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
414/** @copydoc RTListRemovePrev */
415#define RTListRemovePrevCpp(pList, pCurNode, Type, Member) \
416 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
417
418
419/**
420 * Enumerate the list in head to tail order.
421 *
422 * @param pList List to enumerate.
423 * @param pIterator The iterator variable name.
424 * @param Type Structure the list node is a member of.
425 * @param Member The list node member name.
426 */
427#define RTListForEach(pList, pIterator, Type, Member) \
428 for (pIterator = RTListNodeGetNext(pList, Type, Member); \
429 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
430 pIterator = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
431/** @copydoc RTListForEach */
432#define RTListForEachCpp(pList, pIterator, Type, Member) \
433 for (pIterator = RTListNodeGetNextCpp(pList, Type, Member); \
434 !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
435 pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
436
437
438/**
439 * Enumerate the list in head to tail order, safe against removal of the
440 * current node.
441 *
442 * @param pList List to enumerate.
443 * @param pIterator The iterator variable name.
444 * @param pIterNext The name of the variable saving the pointer to
445 * the next element.
446 * @param Type Structure the list node is a member of.
447 * @param Member The list node member name.
448 */
449#define RTListForEachSafe(pList, pIterator, pIterNext, Type, Member) \
450 for (pIterator = RTListNodeGetNext(pList, Type, Member), \
451 pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member); \
452 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
453 pIterator = pIterNext, \
454 pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
455/** @copydoc RTListForEachSafe */
456#define RTListForEachSafeCpp(pList, pIterator, pIterNext, Type, Member) \
457 for (pIterator = RTListNodeGetNextCpp(pList, Type, Member), \
458 pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member); \
459 !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
460 pIterator = pIterNext, \
461 pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
462
463
464/**
465 * Enumerate the list in reverse order (tail to head).
466 *
467 * @param pList List to enumerate.
468 * @param pIterator The iterator variable name.
469 * @param Type Structure the list node is a member of.
470 * @param Member The list node member name.
471 */
472#define RTListForEachReverse(pList, pIterator, Type, Member) \
473 for (pIterator = RTListNodeGetPrev(pList, Type, Member); \
474 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
475 pIterator = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
476/** @copydoc RTListForEachReverse */
477#define RTListForEachReverseCpp(pList, pIterator, Type, Member) \
478 for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member); \
479 !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
480 pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
481
482
483/**
484 * Enumerate the list in reverse order (tail to head).
485 *
486 * @param pList List to enumerate.
487 * @param pIterator The iterator variable name.
488 * @param pIterPrev The name of the variable saving the pointer to
489 * the previous element.
490 * @param Type Structure the list node is a member of.
491 * @param Member The list node member name.
492 */
493#define RTListForEachReverseSafe(pList, pIterator, pIterPrev, Type, Member) \
494 for (pIterator = RTListNodeGetPrev(pList, Type, Member), \
495 pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member); \
496 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
497 pIterator = pIterPrev, \
498 pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
499/** @copydoc RTListForEachReverseSafe */
500#define RTListForEachReverseSafeCpp(pList, pIterator, pIterPrev, Type, Member) \
501 for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member), \
502 pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member); \
503 !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
504 pIterator = pIterPrev, \
505 pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
506
507
508/**
509 * Move the given list to a new list header.
510 *
511 * @param pListDst The new list.
512 * @param pListSrc The list to move.
513 */
514DECLINLINE(void) RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
515{
516 if (!RTListIsEmpty(pListSrc))
517 {
518 pListDst->pNext = pListSrc->pNext;
519 pListDst->pPrev = pListSrc->pPrev;
520
521 /* Adjust the first and last element links */
522 pListDst->pNext->pPrev = pListDst;
523 pListDst->pPrev->pNext = pListDst;
524
525 /* Finally remove the elements from the source list */
526 RTListInit(pListSrc);
527 }
528 else
529 RTListInit(pListDst);
530}
531
532/**
533 * List concatenation.
534 *
535 * @param pListDst The destination list.
536 * @param pListSrc The source list to concatenate.
537 */
538DECLINLINE(void) RTListConcatenate(PRTLISTANCHOR pListDst, PRTLISTANCHOR pListSrc)
539{
540 if (!RTListIsEmpty(pListSrc))
541 {
542 PRTLISTNODE pFirst = pListSrc->pNext;
543 PRTLISTNODE pLast = pListSrc->pPrev;
544
545 pListDst->pPrev->pNext = pFirst;
546 pFirst->pPrev = pListDst->pPrev;
547 pLast->pNext = pListDst;
548 pListDst->pPrev = pLast;
549
550 /* Finally remove the elements from the source list */
551 RTListInit(pListSrc);
552 }
553}
554
555RT_C_DECLS_END
556
557/** @} */
558
559#endif /* !IPRT_INCLUDED_list_h */
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