VirtualBox

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

Last change on this file since 28794 was 28615, checked in by vboxsync, 15 years ago

iprt/list.h: RTListForEachReverse use the right macro, no NULLs.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.3 KB
Line 
1/** @file
2 * IPRT - Generic Doubly Linked List.
3 */
4
5/*
6 * Copyright (C) 2010 Sun Microsystems, Inc.
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 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
26 * Clara, CA 95054 USA or visit http://www.sun.com if you need
27 * additional information or have any questions.
28 */
29
30#ifndef ___iprt_list_h
31#define ___iprt_list_h
32
33#include <iprt/types.h>
34
35/** @defgroup grp_rt_list RTList - Generic Doubly Linked List
36 * @ingroup grp_rt
37 *
38 * The list implementation is circular without any type wise distintion between
39 * the list and its nodes. This can be confusing since the list head usually
40 * resides in a different structure than the nodes, so care must be taken when
41 * walking the list.
42 *
43 * @{
44 */
45
46RT_C_DECLS_BEGIN
47
48/**
49 * A list node of a doubly linked list.
50 */
51typedef struct RTLISTNODE
52{
53 /** Pointer to the next list node. */
54 struct RTLISTNODE *pNext;
55 /** Pointer to the previous list node. */
56 struct RTLISTNODE *pPrev;
57} RTLISTNODE;
58/** Pointer to a list node. */
59typedef RTLISTNODE *PRTLISTNODE;
60/** Pointer to a list node pointer. */
61typedef PRTLISTNODE *PPRTLISTNODE;
62
63/**
64 * Initialize a list.
65 *
66 * @param pList Pointer to an unitialised list.
67 */
68DECLINLINE(void) RTListInit(PRTLISTNODE pList)
69{
70 pList->pNext = pList;
71 pList->pPrev = pList;
72}
73
74/**
75 * Append a node to the end of the list.
76 *
77 * @param pList The list to append the node to.
78 * @param pNode The node to append.
79 */
80DECLINLINE(void) RTListAppend(PRTLISTNODE pList, PRTLISTNODE pNode)
81{
82 pList->pPrev->pNext = pNode;
83 pNode->pPrev = pList->pPrev;
84 pNode->pNext = pList;
85 pList->pPrev = pNode;
86}
87
88/**
89 * Add a node as the first element of the list.
90 *
91 * @param pList The list to prepend the node to.
92 * @param pNode The node to prepend.
93 */
94DECLINLINE(void) RTListPrepend(PRTLISTNODE pList, PRTLISTNODE pNode)
95{
96 pList->pNext->pPrev = pNode;
97 pNode->pNext = pList->pNext;
98 pNode->pPrev = pList;
99 pList->pNext = pNode;
100}
101
102/**
103 * Remove a node from a list.
104 *
105 * @param pNode The node to remove.
106 */
107DECLINLINE(void) RTListNodeRemove(PRTLISTNODE pNode)
108{
109 PRTLISTNODE pPrev = pNode->pPrev;
110 PRTLISTNODE pNext = pNode->pNext;
111
112 pPrev->pNext = pNext;
113 pNext->pPrev = pPrev;
114
115 /* poison */
116 pNode->pNext = NULL;
117 pNode->pPrev = NULL;
118}
119
120/**
121 * Checks if a node is the last element in the list.
122 *
123 * @retval @c true if the node is the last element in the list.
124 * @retval @c false otherwise
125 *
126 * @param pList The list.
127 * @param pNode The node to check.
128 */
129#define RTListNodeIsLast(pList, pNode) ((pNode)->pNext == (pList))
130
131/**
132 * Checks if a node is the first element in the list.
133 *
134 * @retval @c true if the node is the first element in the list.
135 * @retval @c false otherwise.
136 *
137 * @param pList The list.
138 * @param pNode The node to check.
139 */
140#define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList))
141
142/**
143 * Checks if a type converted node is actually the dummy element (@a pList).
144 *
145 * @retval @c true if the node is the dummy element in the list.
146 * @retval @c false otherwise.
147 *
148 * @param pList The list.
149 * @param pNodeStruct The node structure to check. Typically
150 * something obtained from RTListNodeGetNext() or
151 * RTListNodeGetPrev(). This is NOT a PRTLISTNODE
152 * but something that contains a RTLISTNODE member!
153 * @param Type Structure the list node is a member of.
154 * @param Member The list node member.
155 */
156#define RTListNodeIsDummy(pList, pNode, Type, Member) \
157 ( (pNode) == RT_FROM_MEMBER((pList), Type, Member) )
158
159/**
160 * Checks if a list is empty.
161 *
162 * @retval @c true if the list is empty.
163 * @retval @c false otherwise.
164 *
165 * @param pList The list to check.
166 */
167#define RTListIsEmpty(pList) ((pList)->pPrev == (pList))
168
169/**
170 * Returns the next node in the list.
171 *
172 * @returns The next node.
173 *
174 * @param pCurNode The current node.
175 * @param Type Structure the list node is a member of.
176 * @param Member The list node member.
177 */
178#define RTListNodeGetNext(pCurNode, Type, Member) \
179 RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
180
181/**
182 * Returns the previous node in the list.
183 *
184 * @returns The previous node.
185 *
186 * @param pCurNode The current node.
187 * @param Type Structure the list node is a member of.
188 * @param Member The list node member.
189 */
190#define RTListNodeGetPrev(pCurNode, Type, Member) \
191 RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
192
193/**
194 * Returns the first element in the list (checks for empty list).
195 *
196 * @retval Pointer to the first list element.
197 * @retval NULL if the list is empty.
198 *
199 * @param pList List to get the first element from.
200 * @param Type Structure the list node is a member of.
201 * @param Member The list node member.
202 */
203#define RTListNodeGetFirst(pList, Type, Member) \
204 (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
205
206/**
207 * Returns the last element in the list (checks for empty list).
208 *
209 * @retval Pointer to the last list element.
210 * @retval NULL if the list is empty.
211 *
212 * @param pList List to get the last element from.
213 * @param Type Structure the list node is a member of.
214 * @param Member The list node member.
215 */
216#define RTListNodeGetLast(pList, Type, Member) \
217 (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
218
219/**
220 * Enumerate the list in head to tail order.
221 *
222 * @param pList List to enumerate.
223 * @param pIterator The iterator variable name.
224 * @param Type Structure the list node is a member of.
225 * @param Member The list node member name.
226 */
227#define RTListForEach(pList, pIterator, Type, Member) \
228 for (pIterator = RTListNodeGetNext(pList, Type, Member); \
229 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
230 pIterator = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
231
232
233/**
234 * Enumerate the list in reverse order (tail to head).
235 *
236 * @param pList List to enumerate.
237 * @param pIterator The iterator variable name.
238 * @param Type Structure the list node is a member of.
239 * @param Member The list node member name.
240 */
241#define RTListForEachReverse(pList, pIterator, Type, Member) \
242 for (pIterator = RTListNodeGetPrev(pList, Type, Member); \
243 !RTListNodeIsDummy(pList, pIterator, Type, Member); \
244 pIterator = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
245
246
247/**
248 * Move the given list to a new list header.
249 *
250 * @param pListDst The new list.
251 * @param pListSrc The list to move.
252 */
253DECLINLINE(void) RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
254{
255 if (!RTListIsEmpty(pListSrc))
256 {
257 pListDst->pNext = pListSrc->pNext;
258 pListDst->pPrev = pListSrc->pPrev;
259
260 /* Adjust the first and last element links */
261 pListDst->pNext->pPrev = pListDst;
262 pListDst->pPrev->pNext = pListDst;
263
264 /* Finally remove the elements from the source list */
265 RTListInit(pListSrc);
266 }
267}
268
269RT_C_DECLS_END
270
271/** @} */
272
273#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