VirtualBox

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

Last change on this file since 44023 was 39509, checked in by vboxsync, 13 years ago

iprt/list.h: RTLISTANCHOR.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.8 KB
Line 
1/** @file
2 * IPRT - Generic Doubly Linked List.
3 */
4
5/*
6 * Copyright (C) 2010 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_h
27#define ___iprt_list_h
28
29#include <iprt/types.h>
30
31/** @defgroup grp_rt_list RTList - Generic Doubly Linked List
32 * @ingroup grp_rt
33 *
34 * The list implementation is circular without any type wise distintion between
35 * the list and its nodes. This can be confusing since the list head usually
36 * resides in a different structure than the nodes, so care must be taken when
37 * walking the list.
38 *
39 * @{
40 */
41
42RT_C_DECLS_BEGIN
43
44/**
45 * A list node of a doubly linked list.
46 */
47typedef struct RTLISTNODE
48{
49 /** Pointer to the next list node. */
50 struct RTLISTNODE *pNext;
51 /** Pointer to the previous list node. */
52 struct RTLISTNODE *pPrev;
53} RTLISTNODE;
54/** Pointer to a list node. */
55typedef RTLISTNODE *PRTLISTNODE;
56/** Pointer to a list node pointer. */
57typedef PRTLISTNODE *PPRTLISTNODE;
58
59/** The anchor (head/tail) of a doubly linked list.
60 *
61 * @remarks Please use this instead of RTLISTNODE to indicate a list
62 * head/tail. It makes the code so much easier to read. Also,
63 * always mention the actual list node type(s) in the comment. */
64typedef RTLISTNODE RTLISTANCHOR;
65/** Pointer to a doubly linked list anchor. */
66typedef RTLISTANCHOR *PRTLISTANCHOR;
67
68
69/**
70 * Initialize a list.
71 *
72 * @param pList Pointer to an unitialised list.
73 */
74DECLINLINE(void) RTListInit(PRTLISTNODE pList)
75{
76 pList->pNext = pList;
77 pList->pPrev = pList;
78}
79
80/**
81 * Append a node to the end of the list.
82 *
83 * @param pList The list to append the node to.
84 * @param pNode The node to append.
85 */
86DECLINLINE(void) RTListAppend(PRTLISTNODE pList, PRTLISTNODE pNode)
87{
88 pList->pPrev->pNext = pNode;
89 pNode->pPrev = pList->pPrev;
90 pNode->pNext = pList;
91 pList->pPrev = pNode;
92}
93
94/**
95 * Add a node as the first element of the list.
96 *
97 * @param pList The list to prepend the node to.
98 * @param pNode The node to prepend.
99 */
100DECLINLINE(void) RTListPrepend(PRTLISTNODE pList, PRTLISTNODE pNode)
101{
102 pList->pNext->pPrev = pNode;
103 pNode->pNext = pList->pNext;
104 pNode->pPrev = pList;
105 pList->pNext = pNode;
106}
107
108/**
109 * Inserts a node after the specified one.
110 *
111 * @param pCurNode The current node.
112 * @param pNewNode The node to insert.
113 */
114DECLINLINE(void) RTListNodeInsertAfter(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
115{
116 RTListPrepend(pCurNode, pNewNode);
117}
118
119/**
120 * Inserts a node before the specified one.
121 *
122 * @param pCurNode The current node.
123 * @param pNewNode The node to insert.
124 */
125DECLINLINE(void) RTListNodeInsertBefore(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
126{
127 RTListAppend(pCurNode, pNewNode);
128}
129
130/**
131 * Remove a node from a list.
132 *
133 * @param pNode The node to remove.
134 */
135DECLINLINE(void) RTListNodeRemove(PRTLISTNODE pNode)
136{
137 PRTLISTNODE pPrev = pNode->pPrev;
138 PRTLISTNODE pNext = pNode->pNext;
139
140 pPrev->pNext = pNext;
141 pNext->pPrev = pPrev;
142
143 /* poison */
144 pNode->pNext = NULL;
145 pNode->pPrev = NULL;
146}
147
148/**
149 * Checks if a node is the last element in the list.
150 *
151 * @retval @c true if the node is the last element in the list.
152 * @retval @c false otherwise
153 *
154 * @param pList The list.
155 * @param pNode The node to check.
156 */
157#define RTListNodeIsLast(pList, pNode) ((pNode)->pNext == (pList))
158
159/**
160 * Checks if a node is the first element in the list.
161 *
162 * @retval @c true if the node is the first element in the list.
163 * @retval @c false otherwise.
164 *
165 * @param pList The list.
166 * @param pNode The node to check.
167 */
168#define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList))
169
170/**
171 * Checks if a type converted node is actually the dummy element (@a pList).
172 *
173 * @retval @c true if the node is the dummy element in the list.
174 * @retval @c false otherwise.
175 *
176 * @param pList The list.
177 * @param pNodeStruct The node structure to check. Typically
178 * something obtained from RTListNodeGetNext() or
179 * RTListNodeGetPrev(). This is NOT a PRTLISTNODE
180 * but something that contains a RTLISTNODE member!
181 * @param Type Structure the list node is a member of.
182 * @param Member The list node member.
183 */
184#define RTListNodeIsDummy(pList, pNode, Type, Member) \
185 ( (pNode) == RT_FROM_MEMBER((pList), Type, Member) )
186
187/**
188 * Checks if a list is empty.
189 *
190 * @retval @c true if the list is empty.
191 * @retval @c false otherwise.
192 *
193 * @param pList The list to check.
194 */
195#define RTListIsEmpty(pList) ((pList)->pPrev == (pList))
196
197/**
198 * Returns the next node in the list.
199 *
200 * @returns The next node.
201 *
202 * @param pCurNode The current node.
203 * @param Type Structure the list node is a member of.
204 * @param Member The list node member.
205 */
206#define RTListNodeGetNext(pCurNode, Type, Member) \
207 RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
208
209/**
210 * Returns the previous node in the list.
211 *
212 * @returns The previous node.
213 *
214 * @param pCurNode The current node.
215 * @param Type Structure the list node is a member of.
216 * @param Member The list node member.
217 */
218#define RTListNodeGetPrev(pCurNode, Type, Member) \
219 RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
220
221/**
222 * Returns the first element in the list (checks for empty list).
223 *
224 * @retval Pointer to the first list element.
225 * @retval NULL if the list is empty.
226 *
227 * @param pList List to get the first element from.
228 * @param Type Structure the list node is a member of.
229 * @param Member The list node member.
230 */
231#define RTListGetFirst(pList, Type, Member) \
232 (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
233
234/**
235 * Returns the last element in the list (checks for empty list).
236 *
237 * @retval Pointer to the last list element.
238 * @retval NULL if the list is empty.
239 *
240 * @param pList List to get the last element from.
241 * @param Type Structure the list node is a member of.
242 * @param Member The list node member.
243 */
244#define RTListGetLast(pList, Type, Member) \
245 (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
246
247/**
248 * Returns the next node in the list or NULL if the end has been reached.
249 *
250 * @returns The next node or NULL.
251 *
252 * @param pList The list @a pCurNode is linked on.
253 * @param pCurNode The current node, of type @a Type.
254 * @param Type Structure the list node is a member of.
255 * @param Member The list node member.
256 */
257#define RTListGetNext(pList, pCurNode, Type, Member) \
258 ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
259
260/**
261 * Returns the previous node in the list or NULL if the start has been reached.
262 *
263 * @returns The previous node or NULL.
264 *
265 * @param pList The list @a pCurNode is linked on.
266 * @param pCurNode The current node, of type @a Type.
267 * @param Type Structure the list node is a member of.
268 * @param Member The list node member.
269 */
270#define RTListGetPrev(pList, pCurNode, Type, Member) \
271 ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
272
273/**
274 * Enumerate the list in head to tail order.
275 *
276 * @param pList List to enumerate.
277 * @param pIterator The iterator variable name.
278 * @param Type Structure the list node is a member of.
279 * @param Member The list node member name.
280 */
281#define RTListForEach(pList, pIterator, Type, Member) \
282 for (pIterator = RTListNodeGetNext(pList, Type, Member); \
283 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
284 pIterator = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
285
286
287/**
288 * Enumerate the list in head to tail order, safe against removal of the
289 * current node.
290 *
291 * @param pList List to enumerate.
292 * @param pIterator The iterator variable name.
293 * @param pIterNext The name of the variable saving the pointer to
294 * the next element.
295 * @param Type Structure the list node is a member of.
296 * @param Member The list node member name.
297 */
298#define RTListForEachSafe(pList, pIterator, pIterNext, Type, Member) \
299 for (pIterator = RTListNodeGetNext(pList, Type, Member), \
300 pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member); \
301 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
302 pIterator = pIterNext, \
303 pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
304
305
306/**
307 * Enumerate the list in reverse order (tail to head).
308 *
309 * @param pList List to enumerate.
310 * @param pIterator The iterator variable name.
311 * @param Type Structure the list node is a member of.
312 * @param Member The list node member name.
313 */
314#define RTListForEachReverse(pList, pIterator, Type, Member) \
315 for (pIterator = RTListNodeGetPrev(pList, Type, Member); \
316 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
317 pIterator = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
318
319
320/**
321 * Enumerate the list in reverse order (tail to head).
322 *
323 * @param pList List to enumerate.
324 * @param pIterator The iterator variable name.
325 * @param pIterPrev The name of the variable saving the pointer to
326 * the previous element.
327 * @param Type Structure the list node is a member of.
328 * @param Member The list node member name.
329 */
330#define RTListForEachReverseSafe(pList, pIterator, pIterPrev, Type, Member) \
331 for (pIterator = RTListNodeGetPrev(pList, Type, Member), \
332 pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member); \
333 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
334 pIterator = pIterPrev, \
335 pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
336
337
338/**
339 * Move the given list to a new list header.
340 *
341 * @param pListDst The new list.
342 * @param pListSrc The list to move.
343 */
344DECLINLINE(void) RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
345{
346 if (!RTListIsEmpty(pListSrc))
347 {
348 pListDst->pNext = pListSrc->pNext;
349 pListDst->pPrev = pListSrc->pPrev;
350
351 /* Adjust the first and last element links */
352 pListDst->pNext->pPrev = pListDst;
353 pListDst->pPrev->pNext = pListDst;
354
355 /* Finally remove the elements from the source list */
356 RTListInit(pListSrc);
357 }
358}
359
360RT_C_DECLS_END
361
362/** @} */
363
364#endif
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette