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