VirtualBox

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

Last change on this file since 27345 was 26813, checked in by vboxsync, 15 years ago

IPRT/List: Add a method to move the list to a new header

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.4 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 list is empty.
144 *
145 * @retval @c true if the list is empty.
146 * @retval @c false otherwise.
147 *
148 * @param pList The list to check.
149 */
150#define RTListIsEmpty(pList) ((pList)->pPrev == (pList))
151
152/**
153 * Returns the next node in the list.
154 *
155 * @returns The next node.
156 *
157 * @param pCurNode The current node.
158 * @param Type Structure the list node is a member of.
159 * @param Member The list node member.
160 */
161#define RTListNodeGetNext(pCurNode, Type, Member) \
162 RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
163
164/**
165 * Returns the previous node in the list.
166 *
167 * @returns The previous node.
168 *
169 * @param pCurNode The current node.
170 * @param Type Structure the list node is a member of.
171 * @param Member The list node member.
172 */
173#define RTListNodeGetPrev(pCurNode, Type, Member) \
174 RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
175
176/**
177 * Returns the first element in the list (checks for empty list).
178 *
179 * @retval Pointer to the first list element.
180 * @retval NULL if the list is empty.
181 *
182 * @param pList List to get the first element from.
183 * @param Type Structure the list node is a member of.
184 * @param Member The list node member.
185 */
186#define RTListNodeGetFirst(pList, Type, Member) \
187 (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
188
189/**
190 * Returns the last element in the list (checks for empty list).
191 *
192 * @retval Pointer to the last list element.
193 * @retval NULL if the list is empty.
194 *
195 * @param pList List to get the last element from.
196 * @param Type Structure the list node is a member of.
197 * @param Member The list node member.
198 */
199#define RTListNodeGetLast(pList, Type, Member) \
200 (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
201
202/**
203 * Move the given list to a new list header.
204 *
205 * @param pListDst The new list.
206 * @param pListSrc The list to move.
207 */
208DECLINLINE(void) RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
209{
210 if (!RTListIsEmpty(pListSrc))
211 {
212 pListDst->pNext = pListSrc->pNext;
213 pListDst->pPrev = pListSrc->pPrev;
214
215 /* Adjust the first and last element links */
216 pListDst->pNext->pPrev = pListDst;
217 pListDst->pPrev->pNext = pListDst;
218
219 /* Finally remove the elements from the source list */
220 RTListInit(pListSrc);
221 }
222}
223
224RT_C_DECLS_END
225
226/** @} */
227
228#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