list.h@ 90062

Last change on this file since 90062 was 82968, checked in by vboxsync, 5 years 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.5 KB

Line
1	/** @file
2	* IPRT - Generic Doubly Linked List.
3	*/
4
5	/*
6	* Copyright (C) 2010-2020 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_h
27	#define IPRT_INCLUDED_list_h
28	#ifndef RT_WITHOUT_PRAGMA_ONCE
29	# pragma once
30	#endif
31
32	#include <iprt/types.h>
33
34	/** @defgroup grp_rt_list RTList - Generic Doubly Linked List
35	* @ingroup grp_rt
36	*
37	* The list implementation is circular without any type wise distintion between
38	* the list and its nodes. This can be confusing since the list head usually
39	* resides in a different structure than the nodes, so care must be taken when
40	* walking the list.
41	*
42	* @{
43	*/
44
45	RT_C_DECLS_BEGIN
46
47	/**
48	* A list node of a doubly linked list.
49	*/
50	typedef struct RTLISTNODE
51	{
52	/** Pointer to the next list node. */
53	struct RTLISTNODE *pNext;
54	/** Pointer to the previous list node. */
55	struct RTLISTNODE *pPrev;
56	} RTLISTNODE;
57	/** Pointer to a list node. */
58	typedef RTLISTNODE *PRTLISTNODE;
59	/** Pointer to a const list node. */
60	typedef RTLISTNODE const *PCRTLISTNODE;
61	/** Pointer to a list node pointer. */
62	typedef PRTLISTNODE *PPRTLISTNODE;
63
64	/** The anchor (head/tail) of a doubly linked list.
65	*
66	* @remarks Please use this instead of RTLISTNODE to indicate a list
67	* head/tail. It makes the code so much easier to read. Also,
68	* always mention the actual list node type(s) in the comment. */
69	typedef RTLISTNODE RTLISTANCHOR;
70	/** Pointer to a doubly linked list anchor. */
71	typedef RTLISTANCHOR *PRTLISTANCHOR;
72	/** Pointer to a const doubly linked list anchor. */
73	typedef RTLISTANCHOR const *PCRTLISTANCHOR;
74
75	/** Version of RTLISTNODE for holding a ring-3 only list in data which gets
76	* shared between multiple contexts. */
77	#ifdef IN_RING3
78	typedef RTLISTNODE RTLISTNODER3;
79	#else
80	typedef struct { RTR3PTR aOffLimits[2]; } RTLISTNODER3;
81	#endif
82	/** Version of RTLISTANCHOR for holding a ring-3 only list in data which gets
83	* shared between multiple contexts. */
84	typedef RTLISTNODER3 RTLISTANCHORR3;
85
86	/** Version of RTLISTNODE for holding a ring-0 only list in data which gets
87	* shared between multiple contexts. */
88	#ifdef IN_RING0
89	typedef RTLISTNODE RTLISTNODER0;
90	#else
91	typedef struct { RTR0PTR aOffLimits[2]; } RTLISTNODER0;
92	#endif
93	/** Version of RTLISTANCHOR for holding a ring-0 only list in data which gets
94	* shared between multiple contexts. */
95	typedef RTLISTNODER0 RTLISTANCHORR0;
96
97
98	/**
99	* Initialize a list.
100	*
101	* @param pList Pointer to an unitialised list.
102	*/
103	DECLINLINE(void) RTListInit(PRTLISTNODE pList)
104	{
105	pList->pNext = pList;
106	pList->pPrev = pList;
107	}
108
109	/**
110	* Append a node to the end of the list.
111	*
112	* @param pList The list to append the node to.
113	* @param pNode The node to append.
114	*/
115	DECLINLINE(void) RTListAppend(PRTLISTNODE pList, PRTLISTNODE pNode)
116	{
117	pList->pPrev->pNext = pNode;
118	pNode->pPrev = pList->pPrev;
119	pNode->pNext = pList;
120	pList->pPrev = pNode;
121	}
122
123	/**
124	* Add a node as the first element of the list.
125	*
126	* @param pList The list to prepend the node to.
127	* @param pNode The node to prepend.
128	*/
129	DECLINLINE(void) RTListPrepend(PRTLISTNODE pList, PRTLISTNODE pNode)
130	{
131	pList->pNext->pPrev = pNode;
132	pNode->pNext = pList->pNext;
133	pNode->pPrev = pList;
134	pList->pNext = pNode;
135	}
136
137	/**
138	* Inserts a node after the specified one.
139	*
140	* @param pCurNode The current node.
141	* @param pNewNode The node to insert.
142	*/
143	DECLINLINE(void) RTListNodeInsertAfter(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
144	{
145	RTListPrepend(pCurNode, pNewNode);
146	}
147
148	/**
149	* Inserts a node before the specified one.
150	*
151	* @param pCurNode The current node.
152	* @param pNewNode The node to insert.
153	*/
154	DECLINLINE(void) RTListNodeInsertBefore(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
155	{
156	RTListAppend(pCurNode, pNewNode);
157	}
158
159	/**
160	* Remove a node from a list.
161	*
162	* @param pNode The node to remove.
163	*/
164	DECLINLINE(void) RTListNodeRemove(PRTLISTNODE pNode)
165	{
166	PRTLISTNODE pPrev = pNode->pPrev;
167	PRTLISTNODE pNext = pNode->pNext;
168
169	pPrev->pNext = pNext;
170	pNext->pPrev = pPrev;
171
172	/* poison */
173	pNode->pNext = NULL;
174	pNode->pPrev = NULL;
175	}
176
177
178	/**
179	* Remove a node from a list, returns value.
180	*
181	* @returns pNode
182	* @param pNode The node to remove.
183	*/
184	DECLINLINE(PRTLISTNODE) RTListNodeRemoveRet(PRTLISTNODE pNode)
185	{
186	PRTLISTNODE pPrev = pNode->pPrev;
187	PRTLISTNODE pNext = pNode->pNext;
188
189	pPrev->pNext = pNext;
190	pNext->pPrev = pPrev;
191
192	/* poison */
193	pNode->pNext = NULL;
194	pNode->pPrev = NULL;
195
196	return pNode;
197	}
198
199	/**
200	* Checks if a node is the last element in the list.
201	*
202	* @retval true if the node is the last element in the list.
203	* @retval false otherwise
204	*
205	* @param pList The list.
206	* @param pNode The node to check.
207	*/
208	#define RTListNodeIsLast(pList, pNode) ((pNode)->pNext == (pList))
209
210	/**
211	* Checks if a node is the first element in the list.
212	*
213	* @retval true if the node is the first element in the list.
214	* @retval false otherwise.
215	*
216	* @param pList The list.
217	* @param pNode The node to check.
218	*/
219	#define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList))
220
221	/**
222	* Checks if a type converted node is actually the dummy element (@a pList).
223	*
224	* @retval true if the node is the dummy element in the list.
225	* @retval false otherwise.
226	*
227	* @param pList The list.
228	* @param pNode The node structure to check. Typically
229	* something obtained from RTListNodeGetNext() or
230	* RTListNodeGetPrev(). This is NOT a PRTLISTNODE
231	* but something that contains a RTLISTNODE member!
232	* @param Type Structure the list node is a member of.
233	* @param Member The list node member.
234	*/
235	#define RTListNodeIsDummy(pList, pNode, Type, Member) \
236	( (pNode) == RT_FROM_MEMBER((pList), Type, Member) )
237	/** @copydoc RTListNodeIsDummy */
238	#define RTListNodeIsDummyCpp(pList, pNode, Type, Member) \
239	( (pNode) == RT_FROM_CPP_MEMBER((pList), Type, Member) )
240
241	/**
242	* Checks if a list is empty.
243	*
244	* @retval true if the list is empty.
245	* @retval false otherwise.
246	*
247	* @param pList The list to check.
248	*/
249	#define RTListIsEmpty(pList) ((pList)->pPrev == (pList))
250
251	/**
252	* Returns the next node in the list.
253	*
254	* @returns The next node.
255	*
256	* @param pCurNode The current node.
257	* @param Type Structure the list node is a member of.
258	* @param Member The list node member.
259	*/
260	#define RTListNodeGetNext(pCurNode, Type, Member) \
261	RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
262	/** @copydoc RTListNodeGetNext */
263	#define RTListNodeGetNextCpp(pCurNode, Type, Member) \
264	RT_FROM_CPP_MEMBER((pCurNode)->pNext, Type, Member)
265
266	/**
267	* Returns the previous node in the list.
268	*
269	* @returns The previous node.
270	*
271	* @param pCurNode The current node.
272	* @param Type Structure the list node is a member of.
273	* @param Member The list node member.
274	*/
275	#define RTListNodeGetPrev(pCurNode, Type, Member) \
276	RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
277	/** @copydoc RTListNodeGetPrev */
278	#define RTListNodeGetPrevCpp(pCurNode, Type, Member) \
279	RT_FROM_CPP_MEMBER((pCurNode)->pPrev, Type, Member)
280
281	/**
282	* Returns the first element in the list (checks for empty list).
283	*
284	* @returns Pointer to the first list element, or NULL if empty list.
285	*
286	* @param pList List to get the first element from.
287	* @param Type Structure the list node is a member of.
288	* @param Member The list node member.
289	*/
290	#define RTListGetFirst(pList, Type, Member) \
291	(!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
292	/** @copydoc RTListGetFirst */
293	#define RTListGetFirstCpp(pList, Type, Member) \
294	(!RTListIsEmpty(pList) ? RTListNodeGetNextCpp(pList, Type, Member) : NULL)
295
296	/**
297	* Returns the last element in the list (checks for empty list).
298	*
299	* @returns Pointer to the last list element, or NULL if empty list.
300	*
301	* @param pList List to get the last element from.
302	* @param Type Structure the list node is a member of.
303	* @param Member The list node member.
304	*/
305	#define RTListGetLast(pList, Type, Member) \
306	(!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
307	/** @copydoc RTListGetLast */
308	#define RTListGetLastCpp(pList, Type, Member) \
309	(!RTListIsEmpty(pList) ? RTListNodeGetPrevCpp(pList, Type, Member) : NULL)
310
311	/**
312	* Returns the next node in the list or NULL if the end has been reached.
313	*
314	* @returns The next node, or NULL if end of list.
315	*
316	* @param pList The list @a pCurNode is linked on.
317	* @param pCurNode The current node, of type @a Type.
318	* @param Type Structure the list node is a member of.
319	* @param Member The list node member.
320	*/
321	#define RTListGetNext(pList, pCurNode, Type, Member) \
322	( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
323	/** @copydoc RTListGetNext */
324	#define RTListGetNextCpp(pList, pCurNode, Type, Member) \
325	( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
326
327	/**
328	* Returns the previous node in the list or NULL if the start has been reached.
329	*
330	* @returns The previous node, or NULL if end of list.
331	*
332	* @param pList The list @a pCurNode is linked on.
333	* @param pCurNode The current node, of type @a Type.
334	* @param Type Structure the list node is a member of.
335	* @param Member The list node member.
336	*/
337	#define RTListGetPrev(pList, pCurNode, Type, Member) \
338	( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
339	/** @copydoc RTListGetPrev */
340	#define RTListGetPrevCpp(pList, pCurNode, Type, Member) \
341	( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
342
343
344	/**
345	* Removes and returns the first element in the list (checks for empty list).
346	*
347	* @returns Pointer to the first list element, or NULL if empty list.
348	*
349	* @param pList List to get the first element from.
350	* @param Type Structure the list node is a member of.
351	* @param Member The list node member.
352	*/
353	#define RTListRemoveFirst(pList, Type, Member) \
354	(!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
355	/** @copydoc RTListRemoveFirst */
356	#define RTListRemoveFirstCpp(pList, Type, Member) \
357	(!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
358
359	/**
360	* Removes and returns the last element in the list (checks for empty list).
361	*
362	* @returns Pointer to the last list element, or NULL if empty list.
363	*
364	* @param pList List to get the last element from.
365	* @param Type Structure the list node is a member of.
366	* @param Member The list node member.
367	*/
368	#define RTListRemoveLast(pList, Type, Member) \
369	(!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
370	/** @copydoc RTListRemoveLast */
371	#define RTListRemoveLastCpp(pList, Type, Member) \
372	(!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
373
374	/**
375	* Removes and returns the next node in the list or NULL if the end has been
376	* reached.
377	*
378	* @returns The next node, or NULL if end of list.
379	*
380	* @param pList The list @a pCurNode is linked on.
381	* @param pCurNode The current node, of type @a Type.
382	* @param Type Structure the list node is a member of.
383	* @param Member The list node member.
384	*/
385	#define RTListRemoveNext(pList, pCurNode, Type, Member) \
386	( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
387	/** @copydoc RTListRemoveNext */
388	#define RTListRemoveNextCpp(pList, pCurNode, Type, Member) \
389	( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
390
391	/**
392	* Removes and returns the previous node in the list or NULL if the start has
393	* been reached.
394	*
395	* @returns The previous node, or NULL if end of list.
396	*
397	* @param pList The list @a pCurNode is linked on.
398	* @param pCurNode The current node, of type @a Type.
399	* @param Type Structure the list node is a member of.
400	* @param Member The list node member.
401	*/
402	#define RTListRemovePrev(pList, pCurNode, Type, Member) \
403	( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
404	/** @copydoc RTListRemovePrev */
405	#define RTListRemovePrevCpp(pList, pCurNode, Type, Member) \
406	( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
407
408
409	/**
410	* Enumerate the list in head to tail order.
411	*
412	* @param pList List to enumerate.
413	* @param pIterator The iterator variable name.
414	* @param Type Structure the list node is a member of.
415	* @param Member The list node member name.
416	*/
417	#define RTListForEach(pList, pIterator, Type, Member) \
418	for (pIterator = RTListNodeGetNext(pList, Type, Member); \
419	!RTListNodeIsDummy(pList, pIterator, Type, Member); \
420	pIterator = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
421	/** @copydoc RTListForEach */
422	#define RTListForEachCpp(pList, pIterator, Type, Member) \
423	for (pIterator = RTListNodeGetNextCpp(pList, Type, Member); \
424	!RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
425	pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
426
427
428	/**
429	* Enumerate the list in head to tail order, safe against removal of the
430	* current node.
431	*
432	* @param pList List to enumerate.
433	* @param pIterator The iterator variable name.
434	* @param pIterNext The name of the variable saving the pointer to
435	* the next element.
436	* @param Type Structure the list node is a member of.
437	* @param Member The list node member name.
438	*/
439	#define RTListForEachSafe(pList, pIterator, pIterNext, Type, Member) \
440	for (pIterator = RTListNodeGetNext(pList, Type, Member), \
441	pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member); \
442	!RTListNodeIsDummy(pList, pIterator, Type, Member); \
443	pIterator = pIterNext, \
444	pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
445	/** @copydoc RTListForEachSafe */
446	#define RTListForEachSafeCpp(pList, pIterator, pIterNext, Type, Member) \
447	for (pIterator = RTListNodeGetNextCpp(pList, Type, Member), \
448	pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member); \
449	!RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
450	pIterator = pIterNext, \
451	pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
452
453
454	/**
455	* Enumerate the list in reverse order (tail to head).
456	*
457	* @param pList List to enumerate.
458	* @param pIterator The iterator variable name.
459	* @param Type Structure the list node is a member of.
460	* @param Member The list node member name.
461	*/
462	#define RTListForEachReverse(pList, pIterator, Type, Member) \
463	for (pIterator = RTListNodeGetPrev(pList, Type, Member); \
464	!RTListNodeIsDummy(pList, pIterator, Type, Member); \
465	pIterator = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
466	/** @copydoc RTListForEachReverse */
467	#define RTListForEachReverseCpp(pList, pIterator, Type, Member) \
468	for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member); \
469	!RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
470	pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
471
472
473	/**
474	* Enumerate the list in reverse order (tail to head).
475	*
476	* @param pList List to enumerate.
477	* @param pIterator The iterator variable name.
478	* @param pIterPrev The name of the variable saving the pointer to
479	* the previous element.
480	* @param Type Structure the list node is a member of.
481	* @param Member The list node member name.
482	*/
483	#define RTListForEachReverseSafe(pList, pIterator, pIterPrev, Type, Member) \
484	for (pIterator = RTListNodeGetPrev(pList, Type, Member), \
485	pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member); \
486	!RTListNodeIsDummy(pList, pIterator, Type, Member); \
487	pIterator = pIterPrev, \
488	pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
489	/** @copydoc RTListForEachReverseSafe */
490	#define RTListForEachReverseSafeCpp(pList, pIterator, pIterPrev, Type, Member) \
491	for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member), \
492	pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member); \
493	!RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
494	pIterator = pIterPrev, \
495	pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
496
497
498	/**
499	* Move the given list to a new list header.
500	*
501	* @param pListDst The new list.
502	* @param pListSrc The list to move.
503	*/
504	DECLINLINE(void) RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
505	{
506	if (!RTListIsEmpty(pListSrc))
507	{
508	pListDst->pNext = pListSrc->pNext;
509	pListDst->pPrev = pListSrc->pPrev;
510
511	/* Adjust the first and last element links */
512	pListDst->pNext->pPrev = pListDst;
513	pListDst->pPrev->pNext = pListDst;
514
515	/* Finally remove the elements from the source list */
516	RTListInit(pListSrc);
517	}
518	else
519	RTListInit(pListDst);
520	}
521
522	/**
523	* List concatenation.
524	*
525	* @returns nothing.
526	* @param pListDst The destination list.
527	* @param pListSrc The source list to concatenate.
528	*/
529	DECLINLINE(void) RTListConcatenate(PRTLISTANCHOR pListDst, PRTLISTANCHOR pListSrc)
530	{
531	if (!RTListIsEmpty(pListSrc))
532	{
533	PRTLISTNODE pFirst = pListSrc->pNext;
534	PRTLISTNODE pLast = pListSrc->pPrev;
535
536	pListDst->pPrev->pNext = pFirst;
537	pFirst->pPrev = pListDst->pPrev;
538	pLast->pNext = pListDst;
539	pListDst->pPrev = pLast;
540
541	/* Finally remove the elements from the source list */
542	RTListInit(pListSrc);
543	}
544	}
545
546	RT_C_DECLS_END
547
548	/** @} */
549
550	#endif /* !IPRT_INCLUDED_list_h */

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

source: vbox/trunk/include/iprt/list.h@ 90062

Download in other formats: