list-off32.h@ 56118

Last change on this file since 56118 was 55487, checked in by vboxsync, 10 years ago
iprt: Cloned iprt/list.h and morphed it into a 32-bit offset based affair suitable for cross context lists.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 18.9 KB

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

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

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

Download in other formats: