1 | /** @file
|
---|
2 | * IPRT - Generic Doubly Linked List.
|
---|
3 | */
|
---|
4 |
|
---|
5 | /*
|
---|
6 | * Copyright (C) 2010-2011 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 |
|
---|
42 | RT_C_DECLS_BEGIN
|
---|
43 |
|
---|
44 | /**
|
---|
45 | * A list node of a doubly linked list.
|
---|
46 | */
|
---|
47 | typedef 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. */
|
---|
55 | typedef RTLISTNODE *PRTLISTNODE;
|
---|
56 | /** Pointer to a list node pointer. */
|
---|
57 | typedef 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. */
|
---|
64 | typedef RTLISTNODE RTLISTANCHOR;
|
---|
65 | /** Pointer to a doubly linked list anchor. */
|
---|
66 | typedef RTLISTANCHOR *PRTLISTANCHOR;
|
---|
67 |
|
---|
68 |
|
---|
69 | /**
|
---|
70 | * Initialize a list.
|
---|
71 | *
|
---|
72 | * @param pList Pointer to an unitialised list.
|
---|
73 | */
|
---|
74 | DECLINLINE(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 | */
|
---|
86 | DECLINLINE(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 | */
|
---|
100 | DECLINLINE(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 | */
|
---|
114 | DECLINLINE(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 | */
|
---|
125 | DECLINLINE(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 | */
|
---|
135 | DECLINLINE(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 | /** @copydoc RTListNodeIsDummy */
|
---|
187 | #define RTListNodeIsDummyCpp(pList, pNode, Type, Member) \
|
---|
188 | ( (pNode) == RT_FROM_CPP_MEMBER((pList), Type, Member) )
|
---|
189 |
|
---|
190 | /**
|
---|
191 | * Checks if a list is empty.
|
---|
192 | *
|
---|
193 | * @retval @c true if the list is empty.
|
---|
194 | * @retval @c false otherwise.
|
---|
195 | *
|
---|
196 | * @param pList The list to check.
|
---|
197 | */
|
---|
198 | #define RTListIsEmpty(pList) ((pList)->pPrev == (pList))
|
---|
199 |
|
---|
200 | /**
|
---|
201 | * Returns the next node in the list.
|
---|
202 | *
|
---|
203 | * @returns The next node.
|
---|
204 | *
|
---|
205 | * @param pCurNode The current node.
|
---|
206 | * @param Type Structure the list node is a member of.
|
---|
207 | * @param Member The list node member.
|
---|
208 | */
|
---|
209 | #define RTListNodeGetNext(pCurNode, Type, Member) \
|
---|
210 | RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
|
---|
211 | /** @copydoc RTListNodeGetNext */
|
---|
212 | #define RTListNodeGetNextCpp(pCurNode, Type, Member) \
|
---|
213 | RT_FROM_CPP_MEMBER((pCurNode)->pNext, Type, Member)
|
---|
214 |
|
---|
215 | /**
|
---|
216 | * Returns the previous node in the list.
|
---|
217 | *
|
---|
218 | * @returns The previous node.
|
---|
219 | *
|
---|
220 | * @param pCurNode The current node.
|
---|
221 | * @param Type Structure the list node is a member of.
|
---|
222 | * @param Member The list node member.
|
---|
223 | */
|
---|
224 | #define RTListNodeGetPrev(pCurNode, Type, Member) \
|
---|
225 | RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
|
---|
226 | /** @copydoc RTListNodeGetPrev */
|
---|
227 | #define RTListNodeGetPrevCpp(pCurNode, Type, Member) \
|
---|
228 | RT_FROM_CPP_MEMBER((pCurNode)->pPrev, Type, Member)
|
---|
229 |
|
---|
230 | /**
|
---|
231 | * Returns the first element in the list (checks for empty list).
|
---|
232 | *
|
---|
233 | * @retval Pointer to the first list element.
|
---|
234 | * @retval NULL if the list is empty.
|
---|
235 | *
|
---|
236 | * @param pList List to get the first element from.
|
---|
237 | * @param Type Structure the list node is a member of.
|
---|
238 | * @param Member The list node member.
|
---|
239 | */
|
---|
240 | #define RTListGetFirst(pList, Type, Member) \
|
---|
241 | (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
|
---|
242 | /** @copydoc RTListGetFirst */
|
---|
243 | #define RTListGetFirstCpp(pList, Type, Member) \
|
---|
244 | (!RTListIsEmpty(pList) ? RTListNodeGetNextCpp(pList, Type, Member) : NULL)
|
---|
245 |
|
---|
246 | /**
|
---|
247 | * Returns the last element in the list (checks for empty list).
|
---|
248 | *
|
---|
249 | * @retval Pointer to the last list element.
|
---|
250 | * @retval NULL if the list is empty.
|
---|
251 | *
|
---|
252 | * @param pList List to get the last element from.
|
---|
253 | * @param Type Structure the list node is a member of.
|
---|
254 | * @param Member The list node member.
|
---|
255 | */
|
---|
256 | #define RTListGetLast(pList, Type, Member) \
|
---|
257 | (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
|
---|
258 | /** @copydoc RTListGetLast */
|
---|
259 | #define RTListGetLastCpp(pList, Type, Member) \
|
---|
260 | (!RTListIsEmpty(pList) ? RTListNodeGetPrevCpp(pList, Type, Member) : NULL)
|
---|
261 |
|
---|
262 | /**
|
---|
263 | * Returns the next node in the list or NULL if the end has been reached.
|
---|
264 | *
|
---|
265 | * @returns The next node or NULL.
|
---|
266 | *
|
---|
267 | * @param pList The list @a pCurNode is linked on.
|
---|
268 | * @param pCurNode The current node, of type @a Type.
|
---|
269 | * @param Type Structure the list node is a member of.
|
---|
270 | * @param Member The list node member.
|
---|
271 | */
|
---|
272 | #define RTListGetNext(pList, pCurNode, Type, Member) \
|
---|
273 | ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
|
---|
274 | /** @copydoc RTListGetNext */
|
---|
275 | #define RTListGetNextCpp(pList, pCurNode, Type, Member) \
|
---|
276 | ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
|
---|
277 |
|
---|
278 | /**
|
---|
279 | * Returns the previous node in the list or NULL if the start has been reached.
|
---|
280 | *
|
---|
281 | * @returns The previous node or NULL.
|
---|
282 | *
|
---|
283 | * @param pList The list @a pCurNode is linked on.
|
---|
284 | * @param pCurNode The current node, of type @a Type.
|
---|
285 | * @param Type Structure the list node is a member of.
|
---|
286 | * @param Member The list node member.
|
---|
287 | */
|
---|
288 | #define RTListGetPrev(pList, pCurNode, Type, Member) \
|
---|
289 | ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
|
---|
290 | /** @copydoc RTListGetPrev */
|
---|
291 | #define RTListGetPrevCpp(pList, pCurNode, Type, Member) \
|
---|
292 | ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
|
---|
293 |
|
---|
294 | /**
|
---|
295 | * Enumerate the list in head to tail order.
|
---|
296 | *
|
---|
297 | * @param pList List to enumerate.
|
---|
298 | * @param pIterator The iterator variable name.
|
---|
299 | * @param Type Structure the list node is a member of.
|
---|
300 | * @param Member The list node member name.
|
---|
301 | */
|
---|
302 | #define RTListForEach(pList, pIterator, Type, Member) \
|
---|
303 | for (pIterator = RTListNodeGetNext(pList, Type, Member); \
|
---|
304 | !RTListNodeIsDummy(pList, pIterator, Type, Member); \
|
---|
305 | pIterator = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
|
---|
306 | /** @copydoc RTListForEach */
|
---|
307 | #define RTListForEachCpp(pList, pIterator, Type, Member) \
|
---|
308 | for (pIterator = RTListNodeGetNextCpp(pList, Type, Member); \
|
---|
309 | !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
|
---|
310 | pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
|
---|
311 |
|
---|
312 |
|
---|
313 | /**
|
---|
314 | * Enumerate the list in head to tail order, safe against removal of the
|
---|
315 | * current node.
|
---|
316 | *
|
---|
317 | * @param pList List to enumerate.
|
---|
318 | * @param pIterator The iterator variable name.
|
---|
319 | * @param pIterNext The name of the variable saving the pointer to
|
---|
320 | * the next element.
|
---|
321 | * @param Type Structure the list node is a member of.
|
---|
322 | * @param Member The list node member name.
|
---|
323 | */
|
---|
324 | #define RTListForEachSafe(pList, pIterator, pIterNext, Type, Member) \
|
---|
325 | for (pIterator = RTListNodeGetNext(pList, Type, Member), \
|
---|
326 | pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member); \
|
---|
327 | !RTListNodeIsDummy(pList, pIterator, Type, Member); \
|
---|
328 | pIterator = pIterNext, \
|
---|
329 | pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
|
---|
330 | /** @copydoc RTListForEachSafe */
|
---|
331 | #define RTListForEachSafeCpp(pList, pIterator, pIterNext, Type, Member) \
|
---|
332 | for (pIterator = RTListNodeGetNextCpp(pList, Type, Member), \
|
---|
333 | pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member); \
|
---|
334 | !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
|
---|
335 | pIterator = pIterNext, \
|
---|
336 | pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
|
---|
337 |
|
---|
338 |
|
---|
339 | /**
|
---|
340 | * Enumerate the list in reverse order (tail to head).
|
---|
341 | *
|
---|
342 | * @param pList List to enumerate.
|
---|
343 | * @param pIterator The iterator variable name.
|
---|
344 | * @param Type Structure the list node is a member of.
|
---|
345 | * @param Member The list node member name.
|
---|
346 | */
|
---|
347 | #define RTListForEachReverse(pList, pIterator, Type, Member) \
|
---|
348 | for (pIterator = RTListNodeGetPrev(pList, Type, Member); \
|
---|
349 | !RTListNodeIsDummy(pList, pIterator, Type, Member); \
|
---|
350 | pIterator = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
|
---|
351 | /** @copydoc RTListForEachReverse */
|
---|
352 | #define RTListForEachReverseCpp(pList, pIterator, Type, Member) \
|
---|
353 | for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member); \
|
---|
354 | !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
|
---|
355 | pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
|
---|
356 |
|
---|
357 |
|
---|
358 | /**
|
---|
359 | * Enumerate the list in reverse order (tail to head).
|
---|
360 | *
|
---|
361 | * @param pList List to enumerate.
|
---|
362 | * @param pIterator The iterator variable name.
|
---|
363 | * @param pIterPrev The name of the variable saving the pointer to
|
---|
364 | * the previous element.
|
---|
365 | * @param Type Structure the list node is a member of.
|
---|
366 | * @param Member The list node member name.
|
---|
367 | */
|
---|
368 | #define RTListForEachReverseSafe(pList, pIterator, pIterPrev, Type, Member) \
|
---|
369 | for (pIterator = RTListNodeGetPrev(pList, Type, Member), \
|
---|
370 | pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member); \
|
---|
371 | !RTListNodeIsDummy(pList, pIterator, Type, Member); \
|
---|
372 | pIterator = pIterPrev, \
|
---|
373 | pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
|
---|
374 | /** @copydoc RTListForEachReverseSafe */
|
---|
375 | #define RTListForEachReverseSafeCpp(pList, pIterator, pIterPrev, Type, Member) \
|
---|
376 | for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member), \
|
---|
377 | pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member); \
|
---|
378 | !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
|
---|
379 | pIterator = pIterPrev, \
|
---|
380 | pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
|
---|
381 |
|
---|
382 |
|
---|
383 | /**
|
---|
384 | * Move the given list to a new list header.
|
---|
385 | *
|
---|
386 | * @param pListDst The new list.
|
---|
387 | * @param pListSrc The list to move.
|
---|
388 | */
|
---|
389 | DECLINLINE(void) RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
|
---|
390 | {
|
---|
391 | if (!RTListIsEmpty(pListSrc))
|
---|
392 | {
|
---|
393 | pListDst->pNext = pListSrc->pNext;
|
---|
394 | pListDst->pPrev = pListSrc->pPrev;
|
---|
395 |
|
---|
396 | /* Adjust the first and last element links */
|
---|
397 | pListDst->pNext->pPrev = pListDst;
|
---|
398 | pListDst->pPrev->pNext = pListDst;
|
---|
399 |
|
---|
400 | /* Finally remove the elements from the source list */
|
---|
401 | RTListInit(pListSrc);
|
---|
402 | }
|
---|
403 | }
|
---|
404 |
|
---|
405 | RT_C_DECLS_END
|
---|
406 |
|
---|
407 | /** @} */
|
---|
408 |
|
---|
409 | #endif
|
---|