VirtualBox

source: vbox/trunk/include/iprt/list-off32.h

Last change on this file was 99739, checked in by vboxsync, 12 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.3 KB
Line 
1/** @file
2 * IPRT - Generic Doubly Linked List, using 32-bit offset instead of pointers.
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_off32_h
37#define IPRT_INCLUDED_list_off32_h
38#ifndef RT_WITHOUT_PRAGMA_ONCE
39# pragma once
40#endif
41
42#include <iprt/types.h>
43
44/** @defgroup grp_rt_list_off32 RTListOff32 - Generic Doubly Linked List based on 32-bit offset.
45 * @ingroup grp_rt
46 *
47 * This is the same as @ref grp_rt_list , except that instead of pointers we use
48 * 32-bit offsets. The list implementation is circular, with a dummy node as
49 * anchor. Be careful with the dummy node when walking the list.
50 *
51 * @{
52 */
53
54RT_C_DECLS_BEGIN
55
56/**
57 * A list node of a doubly linked list.
58 */
59typedef struct RTLISTOFF32NODE
60{
61 /** Offset to the next list node, relative to this structure. */
62 int32_t offNext;
63 /** Offset to the previous list node, relative to this structure. */
64 int32_t offPrev;
65} RTLISTOFF32NODE;
66/** Pointer to a list node. */
67typedef RTLISTOFF32NODE *PRTLISTOFF32NODE;
68/** Pointer to a const list node. */
69typedef RTLISTOFF32NODE const *PCRTLISTOFF32NODE;
70/** Pointer to a list node pointer. */
71typedef PRTLISTOFF32NODE *PPRTLISTOFF32NODE;
72
73/** The anchor (head/tail) of a doubly linked list.
74 *
75 * @remarks Please always use this instead of RTLISTOFF32NODE to indicate a list
76 * head/tail. It makes the code so much easier to read. Also,
77 * always mention the actual list node type(s) in the comment.
78 * @remarks Must be allocated in a similar manner as the nodes, so as to
79 * keep it within a 32-bit distance from them.
80 */
81typedef RTLISTOFF32NODE RTLISTOFF32ANCHOR;
82/** Pointer to a doubly linked list anchor. */
83typedef RTLISTOFF32ANCHOR *PRTLISTOFF32ANCHOR;
84/** Pointer to a const doubly linked list anchor. */
85typedef RTLISTOFF32ANCHOR const *PCRTLISTOFF32ANCHOR;
86
87
88/**
89 * Initialize a list.
90 *
91 * @param pList Pointer to an unitialised list.
92 */
93DECLINLINE(void) RTListOff32Init(PRTLISTOFF32NODE pList)
94{
95 pList->offNext = 0;
96 pList->offPrev = 0;
97}
98
99/**
100 * Internal macro for converting an offset to a pointer.
101 * @returns PRTLISTOFF32NODE
102 * @param a_pNode The node the offset is relative to.
103 * @param a_off The offset.
104 */
105#define RTLISTOFF32_TO_PTR(a_pNode, a_off) ((PRTLISTOFF32NODE)((intptr_t)(a_pNode) + (a_off)))
106
107/**
108 * Internal macro for getting the pointer to the next node.
109 * @returns PRTLISTOFF32NODE
110 * @param a_pNode The node the offset is relative to.
111 */
112#define RTLISTOFF32_NEXT_PTR(a_pNode) RTLISTOFF32_TO_PTR(a_pNode, (a_pNode)->offNext)
113
114/**
115 * Internal macro for getting the pointer to the previous node.
116 * @returns PRTLISTOFF32NODE
117 * @param a_pNode The node the offset is relative to.
118 */
119#define RTLISTOFF32_PREV_PTR(a_pNode) RTLISTOFF32_TO_PTR(a_pNode, (a_pNode)->offPrev)
120
121/**
122 * Internal macro for converting an a pointer to an offset.
123 * @returns offset
124 * @param a_pNode The node the offset is relative to.
125 * @param a_pOtherNode The pointer to convert.
126 */
127#define RTLISTOFF32_TO_OFF(a_pNode, a_pOtherNode) ((int32_t)((intptr_t)(a_pOtherNode) - (intptr_t)(a_pNode)))
128
129/**
130 * Internal macro for getting the pointer to the next node.
131 * @returns PRTLISTOFF32NODE
132 * @param a_pNode The node which offNext member should be set.
133 * @param a_pNewNext Pointer to the new next node.
134 */
135#define RTLISTOFF32_SET_NEXT_PTR(a_pNode, a_pNewNext) \
136 do { (a_pNode)->offNext = RTLISTOFF32_TO_OFF(a_pNode, a_pNewNext); } while (0)
137
138/**
139 * Internal macro for getting the pointer to the previous node.
140 * @returns PRTLISTOFF32NODE
141 * @param a_pNode The node which offPrev member should be set.
142 * @param a_pNewPrev Pointer to the new previous node.
143 */
144#define RTLISTOFF32_SET_PREV_PTR(a_pNode, a_pNewPrev) \
145 do { (a_pNode)->offPrev = RTLISTOFF32_TO_OFF(a_pNode, a_pNewPrev); } while (0)
146
147
148
149/**
150 * Append a node to the end of the list.
151 *
152 * @param pList The list to append the node to.
153 * @param pNode The node to append.
154 */
155DECLINLINE(void) RTListOff32Append(PRTLISTOFF32NODE pList, PRTLISTOFF32NODE pNode)
156{
157 PRTLISTOFF32NODE pLast = RTLISTOFF32_PREV_PTR(pList);
158 RTLISTOFF32_SET_NEXT_PTR(pLast, pNode);
159 RTLISTOFF32_SET_PREV_PTR(pNode, pLast);
160 RTLISTOFF32_SET_NEXT_PTR(pNode, pList);
161 RTLISTOFF32_SET_PREV_PTR(pList, pNode);
162}
163
164/**
165 * Add a node as the first element of the list.
166 *
167 * @param pList The list to prepend the node to.
168 * @param pNode The node to prepend.
169 */
170DECLINLINE(void) RTListOff32Prepend(PRTLISTOFF32NODE pList, PRTLISTOFF32NODE pNode)
171{
172 PRTLISTOFF32NODE pFirst = RTLISTOFF32_NEXT_PTR(pList);
173 RTLISTOFF32_SET_PREV_PTR(pFirst, pNode);
174 RTLISTOFF32_SET_NEXT_PTR(pNode, pFirst);
175 RTLISTOFF32_SET_PREV_PTR(pNode, pList);
176 RTLISTOFF32_SET_NEXT_PTR(pList, pNode);
177}
178
179/**
180 * Inserts a node after the specified one.
181 *
182 * @param pCurNode The current node.
183 * @param pNewNode The node to insert.
184 */
185DECLINLINE(void) RTListOff32NodeInsertAfter(PRTLISTOFF32NODE pCurNode, PRTLISTOFF32NODE pNewNode)
186{
187 RTListOff32Prepend(pCurNode, pNewNode);
188}
189
190/**
191 * Inserts a node before the specified one.
192 *
193 * @param pCurNode The current node.
194 * @param pNewNode The node to insert.
195 */
196DECLINLINE(void) RTListOff32NodeInsertBefore(PRTLISTOFF32NODE pCurNode, PRTLISTOFF32NODE pNewNode)
197{
198 RTListOff32Append(pCurNode, pNewNode);
199}
200
201/**
202 * Remove a node from a list.
203 *
204 * @param pNode The node to remove.
205 */
206DECLINLINE(void) RTListOff32NodeRemove(PRTLISTOFF32NODE pNode)
207{
208 PRTLISTOFF32NODE pPrev = RTLISTOFF32_PREV_PTR(pNode);
209 PRTLISTOFF32NODE pNext = RTLISTOFF32_NEXT_PTR(pNode);
210
211 RTLISTOFF32_SET_NEXT_PTR(pPrev, pNext);
212 RTLISTOFF32_SET_PREV_PTR(pNext, pPrev);
213
214 /* poison */
215 pNode->offNext = INT32_MAX / 2;
216 pNode->offPrev = INT32_MAX / 2;
217}
218
219/**
220 * Checks if a node is the last element in the list.
221 *
222 * @retval true if the node is the last element in the list.
223 * @retval false otherwise
224 *
225 * @param pList The list.
226 * @param pNode The node to check.
227 */
228#define RTListOff32NodeIsLast(pList, pNode) (RTLISTOFF32_NEXT_PTR(pNode) == (pList))
229
230/**
231 * Checks if a node is the first element in the list.
232 *
233 * @retval true if the node is the first element in the list.
234 * @retval false otherwise.
235 *
236 * @param pList The list.
237 * @param pNode The node to check.
238 */
239#define RTListOff32NodeIsFirst(pList, pNode) (RTLISTOFF32_PREV_PTR(pNode) == (pList))
240
241/**
242 * Checks if a type converted node is actually the dummy element (@a pList).
243 *
244 * @retval true if the node is the dummy element in the list.
245 * @retval false otherwise.
246 *
247 * @param pList The list.
248 * @param pNode The node structure to check. Typically
249 * something obtained from RTListOff32NodeGetNext()
250 * or RTListOff32NodeGetPrev(). This is NOT a
251 * PRTLISTOFF32NODE but something that contains a
252 * RTLISTOFF32NODE member!
253 * @param Type Structure the list node is a member of.
254 * @param Member The list node member.
255 */
256#define RTListOff32NodeIsDummy(pList, pNode, Type, Member) \
257 ( (pNode) == RT_FROM_MEMBER((pList), Type, Member) )
258/** @copydoc RTListOff32NodeIsDummy */
259#define RTListOff32NodeIsDummyCpp(pList, pNode, Type, Member) \
260 ( (pNode) == RT_FROM_CPP_MEMBER((pList), Type, Member) )
261
262/**
263 * Checks if a list is empty.
264 *
265 * @retval true if the list is empty.
266 * @retval false otherwise.
267 *
268 * @param pList The list to check.
269 */
270#define RTListOff32IsEmpty(pList) ((pList)->offNext == 0)
271
272/**
273 * Returns the next node in the list.
274 *
275 * @returns The next node.
276 *
277 * @param pCurNode The current node.
278 * @param Type Structure the list node is a member of.
279 * @param Member The list node member.
280 */
281#define RTListOff32NodeGetNext(pCurNode, Type, Member) \
282 RT_FROM_MEMBER(RTLISTOFF32_NEXT_PTR(pCurNode), Type, Member)
283/** @copydoc RTListOff32NodeGetNext */
284#define RTListOff32NodeGetNextCpp(pCurNode, Type, Member) \
285 RT_FROM_CPP_MEMBER(RTLISTOFF32_NEXT_PTR(pCurNode), Type, Member)
286
287/**
288 * Returns the previous node in the list.
289 *
290 * @returns The previous node.
291 *
292 * @param pCurNode The current node.
293 * @param Type Structure the list node is a member of.
294 * @param Member The list node member.
295 */
296#define RTListOff32NodeGetPrev(pCurNode, Type, Member) \
297 RT_FROM_MEMBER(RTLISTOFF32_PREV_PTR(pCurNode), Type, Member)
298/** @copydoc RTListOff32NodeGetPrev */
299#define RTListOff32NodeGetPrevCpp(pCurNode, Type, Member) \
300 RT_FROM_CPP_MEMBER(RTLISTOFF32_PREV_PTR(pCurNode), Type, Member)
301
302/**
303 * Returns the first element in the list (checks for empty list).
304 *
305 * @retval Pointer to the first list element.
306 * @retval NULL if the list is empty.
307 *
308 * @param pList List to get the first element from.
309 * @param Type Structure the list node is a member of.
310 * @param Member The list node member.
311 */
312#define RTListOff32GetFirst(pList, Type, Member) \
313 ((pList)->offNext != 0 ? RTListOff32NodeGetNext(pList, Type, Member) : NULL)
314/** @copydoc RTListOff32GetFirst */
315#define RTListOff32GetFirstCpp(pList, Type, Member) \
316 ((pList)->offNext != 0 ? RTListOff32NodeGetNextCpp(pList, Type, Member) : NULL)
317
318/**
319 * Returns the last element in the list (checks for empty list).
320 *
321 * @retval Pointer to the last list element.
322 * @retval NULL if the list is empty.
323 *
324 * @param pList List to get the last element from.
325 * @param Type Structure the list node is a member of.
326 * @param Member The list node member.
327 */
328#define RTListOff32GetLast(pList, Type, Member) \
329 ((pList)->offPrev != 0 ? RTListOff32NodeGetPrev(pList, Type, Member) : NULL)
330/** @copydoc RTListOff32GetLast */
331#define RTListOff32GetLastCpp(pList, Type, Member) \
332 ((pList)->offPrev != 0 ? RTListOff32NodeGetPrevCpp(pList, Type, Member) : NULL)
333
334/**
335 * Returns the next node in the list or NULL if the end has been reached.
336 *
337 * @returns The next node or NULL.
338 *
339 * @param pList The list @a pCurNode is linked on.
340 * @param pCurNode The current node, of type @a Type.
341 * @param Type Structure the list node is a member of.
342 * @param Member The list node member.
343 */
344#define RTListOff32GetNext(pList, pCurNode, Type, Member) \
345 ( RTLISTOFF32_NEXT_PTR(&(pCurNode)->Member) != (pList) \
346 ? RT_FROM_MEMBER(RTLISTOFF32_NEXT_PTR(&(pCurNode)->Member), Type, Member) : NULL )
347/** @copydoc RTListOff32GetNext */
348#define RTListOff32GetNextCpp(pList, pCurNode, Type, Member) \
349 ( RTLISTOFF32_NEXT_PTR(&(pCurNode)->Member) != (pList) \
350 ? RT_FROM_CPP_MEMBER(RTLISTOFF32_NEXT_PTR(&(pCurNode)->Member), Type, Member) : NULL )
351
352/**
353 * Returns the previous node in the list or NULL if the start has been reached.
354 *
355 * @returns The previous node or NULL.
356 *
357 * @param pList The list @a pCurNode is linked on.
358 * @param pCurNode The current node, of type @a Type.
359 * @param Type Structure the list node is a member of.
360 * @param Member The list node member.
361 */
362#define RTListOff32GetPrev(pList, pCurNode, Type, Member) \
363 ( RTLISTOFF32_PREV_PTR(&(pCurNode)->Member) != (pList) \
364 ? RT_FROM_MEMBER(RTLISTOFF32_PREV_PTR(&(pCurNode)->Member), Type, Member) : NULL )
365/** @copydoc RTListOff32GetPrev */
366#define RTListOff32GetPrevCpp(pList, pCurNode, Type, Member) \
367 ( RTLISTOFF32_PREV_PTR(&(pCurNode)->Member) != (pList) \
368 ? RT_FROM_CPP_MEMBER(RTLISTOFF32_PREV_PTR(&(pCurNode)->Member), Type, Member) : NULL )
369
370/**
371 * Enumerate the list in head to tail order.
372 *
373 * @param pList List to enumerate.
374 * @param pIterator The iterator variable name.
375 * @param Type Structure the list node is a member of.
376 * @param Member The list node member name.
377 */
378#define RTListOff32ForEach(pList, pIterator, Type, Member) \
379 for (pIterator = RTListOff32NodeGetNext(pList, Type, Member); \
380 !RTListOff32NodeIsDummy(pList, pIterator, Type, Member); \
381 pIterator = RT_FROM_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member) )
382/** @copydoc RTListOff32ForEach */
383#define RTListOff32ForEachCpp(pList, pIterator, Type, Member) \
384 for (pIterator = RTListOff32NodeGetNextCpp(pList, Type, Member); \
385 !RTListOff32NodeIsDummyCpp(pList, pIterator, Type, Member); \
386 pIterator = RT_FROM_CPP_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member) )
387
388
389/**
390 * Enumerate the list in head to tail order, safe against removal of the
391 * current node.
392 *
393 * @param pList List to enumerate.
394 * @param pIterator The iterator variable name.
395 * @param pIterNext The name of the variable saving the pointer to
396 * the next element.
397 * @param Type Structure the list node is a member of.
398 * @param Member The list node member name.
399 */
400#define RTListOff32ForEachSafe(pList, pIterator, pIterNext, Type, Member) \
401 for (pIterator = RTListOff32NodeGetNext(pList, Type, Member), \
402 pIterNext = RT_FROM_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member); \
403 !RTListOff32NodeIsDummy(pList, pIterator, Type, Member); \
404 pIterator = pIterNext, \
405 pIterNext = RT_FROM_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member) )
406/** @copydoc RTListOff32ForEachSafe */
407#define RTListOff32ForEachSafeCpp(pList, pIterator, pIterNext, Type, Member) \
408 for (pIterator = RTListOff32NodeGetNextCpp(pList, Type, Member), \
409 pIterNext = RT_FROM_CPP_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member); \
410 !RTListOff32NodeIsDummyCpp(pList, pIterator, Type, Member); \
411 pIterator = pIterNext, \
412 pIterNext = RT_FROM_CPP_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member) )
413
414
415/**
416 * Enumerate the list in reverse order (tail to head).
417 *
418 * @param pList List to enumerate.
419 * @param pIterator The iterator variable name.
420 * @param Type Structure the list node is a member of.
421 * @param Member The list node member name.
422 */
423#define RTListOff32ForEachReverse(pList, pIterator, Type, Member) \
424 for (pIterator = RTListOff32NodeGetPrev(pList, Type, Member); \
425 !RTListOff32NodeIsDummy(pList, pIterator, Type, Member); \
426 pIterator = RT_FROM_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member) )
427/** @copydoc RTListOff32ForEachReverse */
428#define RTListOff32ForEachReverseCpp(pList, pIterator, Type, Member) \
429 for (pIterator = RTListOff32NodeGetPrevCpp(pList, Type, Member); \
430 !RTListOff32NodeIsDummyCpp(pList, pIterator, Type, Member); \
431 pIterator = RT_FROM_CPP_MEMBER(RTLISTOFF32_PREV_PTR(&(pIterator)->Member), Type, Member) )
432
433
434/**
435 * Enumerate the list in reverse order (tail to head).
436 *
437 * @param pList List to enumerate.
438 * @param pIterator The iterator variable name.
439 * @param pIterPrev The name of the variable saving the pointer to
440 * the previous element.
441 * @param Type Structure the list node is a member of.
442 * @param Member The list node member name.
443 */
444#define RTListOff32ForEachReverseSafe(pList, pIterator, pIterPrev, Type, Member) \
445 for (pIterator = RTListOff32NodeGetPrev(pList, Type, Member), \
446 pIterPrev = RT_FROM_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member); \
447 !RTListOff32NodeIsDummy(pList, pIterator, Type, Member); \
448 pIterator = pIterPrev, \
449 pIterPrev = RT_FROM_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member) )
450/** @copydoc RTListOff32ForEachReverseSafe */
451#define RTListOff32ForEachReverseSafeCpp(pList, pIterator, pIterPrev, Type, Member) \
452 for (pIterator = RTListOff32NodeGetPrevCpp(pList, Type, Member), \
453 pIterPrev = RT_FROM_CPP_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member); \
454 !RTListOff32NodeIsDummyCpp(pList, pIterator, Type, Member); \
455 pIterator = pIterPrev, \
456 pIterPrev = RT_FROM_CPP_MEMBER(RTLISTOFF32_NEXT_PTR(&(pIterator)->Member), Type, Member) )
457
458
459/**
460 * Move the given list to a new list header.
461 *
462 * @param pListDst The new list.
463 * @param pListSrc The list to move.
464 */
465DECLINLINE(void) RTListOff32Move(PRTLISTOFF32NODE pListDst, PRTLISTOFF32NODE pListSrc)
466{
467 if (!RTListOff32IsEmpty(pListSrc))
468 {
469 PRTLISTOFF32NODE pFirst = RTLISTOFF32_NEXT_PTR(pListSrc);
470 PRTLISTOFF32NODE pLast = RTLISTOFF32_PREV_PTR(pListSrc);
471
472 RTLISTOFF32_SET_NEXT_PTR(pListDst, pFirst);
473 RTLISTOFF32_SET_PREV_PTR(pListDst, pLast);
474
475 /* Adjust the first and last element links */
476 RTLISTOFF32_SET_NEXT_PTR(pLast, pListDst);
477 RTLISTOFF32_SET_PREV_PTR(pFirst, pListDst);
478
479 /* Finally remove the elements from the source list */
480 RTListOff32Init(pListSrc);
481 }
482}
483
484/**
485 * List concatenation.
486 *
487 * @param pListDst The destination list.
488 * @param pListSrc The source list to concatenate.
489 */
490DECLINLINE(void) RTListOff32Concatenate(PRTLISTOFF32ANCHOR pListDst, PRTLISTOFF32ANCHOR pListSrc)
491{
492 if (!RTListOff32IsEmpty(pListSrc))
493 {
494 PRTLISTOFF32NODE pFirstSrc = RTLISTOFF32_NEXT_PTR(pListSrc);
495 PRTLISTOFF32NODE pLastSrc = RTLISTOFF32_PREV_PTR(pListSrc);
496 PRTLISTOFF32NODE pLastDst = RTLISTOFF32_PREV_PTR(pListDst);
497
498 RTLISTOFF32_SET_NEXT_PTR(pLastDst, pFirstSrc);
499 RTLISTOFF32_SET_PREV_PTR(pFirstSrc, pLastDst);
500
501 RTLISTOFF32_SET_NEXT_PTR(pLastSrc, pListDst);
502 RTLISTOFF32_SET_PREV_PTR(pListDst, pLastSrc);
503
504 /* Finally remove the elements from the source list */
505 RTListOff32Init(pListSrc);
506 }
507}
508
509/** @} */
510RT_C_DECLS_END
511
512#endif /* !IPRT_INCLUDED_list_off32_h */
513
Note: See TracBrowser for help on using the repository browser.

© 2023 Oracle
Contact – Privacy policy – Terms of Use