VirtualBox

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

Last change on this file since 77807 was 76585, checked in by vboxsync, 6 years ago

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

© 2024 Oracle
Contact – Privacy/Do Not Sell My Info – Terms of Use