list-off32.h

Last change on this file was 106061, checked in by vboxsync, 2 months ago
Copyright year updates by scm.
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-2024 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
54	RT_C_DECLS_BEGIN
55
56	/**
57	* A list node of a doubly linked list.
58	*/
59	typedef 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. */
67	typedef RTLISTOFF32NODE *PRTLISTOFF32NODE;
68	/** Pointer to a const list node. */
69	typedef RTLISTOFF32NODE const *PCRTLISTOFF32NODE;
70	/** Pointer to a list node pointer. */
71	typedef 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	*/
81	typedef RTLISTOFF32NODE RTLISTOFF32ANCHOR;
82	/** Pointer to a doubly linked list anchor. */
83	typedef RTLISTOFF32ANCHOR *PRTLISTOFF32ANCHOR;
84	/** Pointer to a const doubly linked list anchor. */
85	typedef RTLISTOFF32ANCHOR const *PCRTLISTOFF32ANCHOR;
86
87
88	/**
89	* Initialize a list.
90	*
91	* @param pList Pointer to an unitialised list.
92	*/
93	DECLINLINE(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	*/
155	DECLINLINE(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	*/
170	DECLINLINE(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	*/
185	DECLINLINE(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	*/
196	DECLINLINE(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	*/
206	DECLINLINE(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	*/
465	DECLINLINE(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	*/
490	DECLINLINE(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	/** @} */
510	RT_C_DECLS_END
511
512	#endif /* !IPRT_INCLUDED_list_off32_h */
513

Note: See TracBrowser for help on using the repository browser.

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

Download in other formats: