list-off32.h@ 78394

Last change on this file since 78394 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
44	RT_C_DECLS_BEGIN
45
46	/**
47	* A list node of a doubly linked list.
48	*/
49	typedef 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. */
57	typedef RTLISTOFF32NODE *PRTLISTOFF32NODE;
58	/** Pointer to a const list node. */
59	typedef RTLISTOFF32NODE const *PCRTLISTOFF32NODE;
60	/** Pointer to a list node pointer. */
61	typedef 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	*/
71	typedef RTLISTOFF32NODE RTLISTOFF32ANCHOR;
72	/** Pointer to a doubly linked list anchor. */
73	typedef RTLISTOFF32ANCHOR *PRTLISTOFF32ANCHOR;
74	/** Pointer to a const doubly linked list anchor. */
75	typedef RTLISTOFF32ANCHOR const *PCRTLISTOFF32ANCHOR;
76
77
78	/**
79	* Initialize a list.
80	*
81	* @param pList Pointer to an unitialised list.
82	*/
83	DECLINLINE(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	*/
145	DECLINLINE(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	*/
160	DECLINLINE(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	*/
175	DECLINLINE(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	*/
186	DECLINLINE(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	*/
196	DECLINLINE(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	*/
455	DECLINLINE(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	*/
481	DECLINLINE(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
500	RT_C_DECLS_END
501
502	/** @} */
503
504	#endif /* !IPRT_INCLUDED_list_off32_h */
505

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

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

Download in other formats: