ubuntu/vbox/vboxguest/include/iprt/list.h

   1 /** @file
   2  * IPRT - Generic Doubly Linked List.
   3  */
   4
   5 /*
   6  * Copyright (C) 2010-2017 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 const list node. */
  57 typedef RTLISTNODE const *PCRTLISTNODE;
  58 /** Pointer to a list node pointer. */
  59 typedef PRTLISTNODE *PPRTLISTNODE;
  60
  61 /** The anchor (head/tail) of a doubly linked list.
  62  *
  63  * @remarks Please use this instead of RTLISTNODE to indicate a list
  64  *          head/tail.  It makes the code so much easier to read.  Also,
  65  *          always mention the actual list node type(s) in the comment.  */
  66 typedef RTLISTNODE RTLISTANCHOR;
  67 /** Pointer to a doubly linked list anchor. */
  68 typedef RTLISTANCHOR *PRTLISTANCHOR;
  69 /** Pointer to a const doubly linked list anchor. */
  70 typedef RTLISTANCHOR const *PCRTLISTANCHOR;
  71
  72 /** Version of RTLISTNODE for holding a ring-3 only list in data which gets
  73  * shared between multiple contexts */
  74 #if defined(IN_RING3)
  75 typedef RTLISTNODE RTLISTNODER3;
  76 #else
  77 typedef struct { RTR3PTR aOffLimits[2]; } RTLISTNODER3;
  78 #endif
  79 /** Version of RTLISTANCHOR for holding a ring-3 only list in data which gets
  80  * shared between multiple contexts */
  81 typedef RTLISTNODER3 RTLISTANCHORR3;
  82
  83
  84 /**
  85  * Initialize a list.
  86  *
  87  * @param   pList               Pointer to an unitialised list.
  88  */
  89 DECLINLINE(void) RTListInit(PRTLISTNODE pList)
  90 {
  91     pList->pNext = pList;
  92     pList->pPrev = pList;
  93 }
  94
  95 /**
  96  * Append a node to the end of the list.
  97  *
  98  * @param   pList               The list to append the node to.
  99  * @param   pNode               The node to append.
 100  */
 101 DECLINLINE(void) RTListAppend(PRTLISTNODE pList, PRTLISTNODE pNode)
 102 {
 103     pList->pPrev->pNext = pNode;
 104     pNode->pPrev        = pList->pPrev;
 105     pNode->pNext        = pList;
 106     pList->pPrev        = pNode;
 107 }
 108
 109 /**
 110  * Add a node as the first element of the list.
 111  *
 112  * @param   pList               The list to prepend the node to.
 113  * @param   pNode               The node to prepend.
 114  */
 115 DECLINLINE(void) RTListPrepend(PRTLISTNODE pList, PRTLISTNODE pNode)
 116 {
 117     pList->pNext->pPrev = pNode;
 118     pNode->pNext        = pList->pNext;
 119     pNode->pPrev        = pList;
 120     pList->pNext        = pNode;
 121 }
 122
 123 /**
 124  * Inserts a node after the specified one.
 125  *
 126  * @param   pCurNode            The current node.
 127  * @param   pNewNode            The node to insert.
 128  */
 129 DECLINLINE(void) RTListNodeInsertAfter(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
 130 {
 131     RTListPrepend(pCurNode, pNewNode);
 132 }
 133
 134 /**
 135  * Inserts a node before the specified one.
 136  *
 137  * @param   pCurNode            The current node.
 138  * @param   pNewNode            The node to insert.
 139  */
 140 DECLINLINE(void) RTListNodeInsertBefore(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
 141 {
 142     RTListAppend(pCurNode, pNewNode);
 143 }
 144
 145 /**
 146  * Remove a node from a list.
 147  *
 148  * @param   pNode               The node to remove.
 149  */
 150 DECLINLINE(void) RTListNodeRemove(PRTLISTNODE pNode)
 151 {
 152     PRTLISTNODE pPrev = pNode->pPrev;
 153     PRTLISTNODE pNext = pNode->pNext;
 154
 155     pPrev->pNext = pNext;
 156     pNext->pPrev = pPrev;
 157
 158     /* poison */
 159     pNode->pNext = NULL;
 160     pNode->pPrev = NULL;
 161 }
 162
 163
 164 /**
 165  * Remove a node from a list, returns value.
 166  *
 167  * @returns pNode
 168  * @param   pNode               The node to remove.
 169  */
 170 DECLINLINE(PRTLISTNODE) RTListNodeRemoveRet(PRTLISTNODE pNode)
 171 {
 172     PRTLISTNODE pPrev = pNode->pPrev;
 173     PRTLISTNODE pNext = pNode->pNext;
 174
 175     pPrev->pNext = pNext;
 176     pNext->pPrev = pPrev;
 177
 178     /* poison */
 179     pNode->pNext = NULL;
 180     pNode->pPrev = NULL;
 181
 182     return pNode;
 183 }
 184
 185 /**
 186  * Checks if a node is the last element in the list.
 187  *
 188  * @retval  true if the node is the last element in the list.
 189  * @retval  false otherwise
 190  *
 191  * @param   pList               The list.
 192  * @param   pNode               The node to check.
 193  */
 194 #define RTListNodeIsLast(pList, pNode)  ((pNode)->pNext == (pList))
 195
 196 /**
 197  * Checks if a node is the first element in the list.
 198  *
 199  * @retval  true if the node is the first element in the list.
 200  * @retval  false otherwise.
 201  *
 202  * @param   pList               The list.
 203  * @param   pNode               The node to check.
 204  */
 205 #define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList))
 206
 207 /**
 208  * Checks if a type converted node is actually the dummy element (@a pList).
 209  *
 210  * @retval  true if the node is the dummy element in the list.
 211  * @retval  false otherwise.
 212  *
 213  * @param   pList               The list.
 214  * @param   pNode               The node structure to check.  Typically
 215  *                              something obtained from RTListNodeGetNext() or
 216  *                              RTListNodeGetPrev().  This is NOT a PRTLISTNODE
 217  *                              but something that contains a RTLISTNODE member!
 218  * @param   Type                Structure the list node is a member of.
 219  * @param   Member              The list node member.
 220  */
 221 #define RTListNodeIsDummy(pList, pNode, Type, Member) \
 222          ( (pNode) == RT_FROM_MEMBER((pList), Type, Member) )
 223 /** @copydoc RTListNodeIsDummy */
 224 #define RTListNodeIsDummyCpp(pList, pNode, Type, Member) \
 225          ( (pNode) == RT_FROM_CPP_MEMBER((pList), Type, Member) )
 226
 227 /**
 228  * Checks if a list is empty.
 229  *
 230  * @retval  true if the list is empty.
 231  * @retval  false otherwise.
 232  *
 233  * @param   pList               The list to check.
 234  */
 235 #define RTListIsEmpty(pList)            ((pList)->pPrev == (pList))
 236
 237 /**
 238  * Returns the next node in the list.
 239  *
 240  * @returns The next node.
 241  *
 242  * @param   pCurNode            The current node.
 243  * @param   Type                Structure the list node is a member of.
 244  * @param   Member              The list node member.
 245  */
 246 #define RTListNodeGetNext(pCurNode, Type, Member) \
 247     RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
 248 /** @copydoc RTListNodeGetNext */
 249 #define RTListNodeGetNextCpp(pCurNode, Type, Member) \
 250     RT_FROM_CPP_MEMBER((pCurNode)->pNext, Type, Member)
 251
 252 /**
 253  * Returns the previous node in the list.
 254  *
 255  * @returns The previous node.
 256  *
 257  * @param   pCurNode            The current node.
 258  * @param   Type                Structure the list node is a member of.
 259  * @param   Member              The list node member.
 260  */
 261 #define RTListNodeGetPrev(pCurNode, Type, Member) \
 262     RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
 263 /** @copydoc RTListNodeGetPrev */
 264 #define RTListNodeGetPrevCpp(pCurNode, Type, Member) \
 265     RT_FROM_CPP_MEMBER((pCurNode)->pPrev, Type, Member)
 266
 267 /**
 268  * Returns the first element in the list (checks for empty list).
 269  *
 270  * @returns Pointer to the first list element, or NULL if empty list.
 271  *
 272  * @param   pList               List to get the first element from.
 273  * @param   Type                Structure the list node is a member of.
 274  * @param   Member              The list node member.
 275  */
 276 #define RTListGetFirst(pList, Type, Member) \
 277     (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
 278 /** @copydoc RTListGetFirst */
 279 #define RTListGetFirstCpp(pList, Type, Member) \
 280     (!RTListIsEmpty(pList) ? RTListNodeGetNextCpp(pList, Type, Member) : NULL)
 281
 282 /**
 283  * Returns the last element in the list (checks for empty list).
 284  *
 285  * @returns Pointer to the last list element, or NULL if empty list.
 286  *
 287  * @param   pList               List to get the last element from.
 288  * @param   Type                Structure the list node is a member of.
 289  * @param   Member              The list node member.
 290  */
 291 #define RTListGetLast(pList, Type, Member) \
 292     (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
 293 /** @copydoc RTListGetLast */
 294 #define RTListGetLastCpp(pList, Type, Member) \
 295     (!RTListIsEmpty(pList) ? RTListNodeGetPrevCpp(pList, Type, Member) : NULL)
 296
 297 /**
 298  * Returns the next node in the list or NULL if the end has been reached.
 299  *
 300  * @returns The next node, or NULL if end of list.
 301  *
 302  * @param   pList               The list @a pCurNode is linked on.
 303  * @param   pCurNode            The current node, of type @a Type.
 304  * @param   Type                Structure the list node is a member of.
 305  * @param   Member              The list node member.
 306  */
 307 #define RTListGetNext(pList, pCurNode, Type, Member) \
 308     ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
 309 /** @copydoc RTListGetNext */
 310 #define RTListGetNextCpp(pList, pCurNode, Type, Member) \
 311     ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
 312
 313 /**
 314  * Returns the previous node in the list or NULL if the start has been reached.
 315  *
 316  * @returns The previous node, or NULL if end of list.
 317  *
 318  * @param   pList               The list @a pCurNode is linked on.
 319  * @param   pCurNode            The current node, of type @a Type.
 320  * @param   Type                Structure the list node is a member of.
 321  * @param   Member              The list node member.
 322  */
 323 #define RTListGetPrev(pList, pCurNode, Type, Member) \
 324     ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
 325 /** @copydoc RTListGetPrev */
 326 #define RTListGetPrevCpp(pList, pCurNode, Type, Member) \
 327     ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
 328
 329
 330 /**
 331  * Removes and returns the first element in the list (checks for empty list).
 332  *
 333  * @returns Pointer to the first list element, or NULL if empty list.
 334  *
 335  * @param   pList               List to get the first element from.
 336  * @param   Type                Structure the list node is a member of.
 337  * @param   Member              The list node member.
 338  */
 339 #define RTListRemoveFirst(pList, Type, Member) \
 340     (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
 341 /** @copydoc RTListRemoveFirst */
 342 #define RTListRemoveFirstCpp(pList, Type, Member) \
 343     (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
 344
 345 /**
 346  * Removes and returns the last element in the list (checks for empty list).
 347  *
 348  * @returns Pointer to the last list element, or NULL if empty list.
 349  *
 350  * @param   pList               List to get the last element from.
 351  * @param   Type                Structure the list node is a member of.
 352  * @param   Member              The list node member.
 353  */
 354 #define RTListRemoveLast(pList, Type, Member) \
 355     (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
 356 /** @copydoc RTListRemoveLast */
 357 #define RTListRemoveLastCpp(pList, Type, Member) \
 358     (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
 359
 360 /**
 361  * Removes and returns the next node in the list or NULL if the end has been
 362  * reached.
 363  *
 364  * @returns The next node, or NULL if end of list.
 365  *
 366  * @param   pList               The list @a pCurNode is linked on.
 367  * @param   pCurNode            The current node, of type @a Type.
 368  * @param   Type                Structure the list node is a member of.
 369  * @param   Member              The list node member.
 370  */
 371 #define RTListRemoveNext(pList, pCurNode, Type, Member) \
 372     ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
 373 /** @copydoc RTListRemoveNext */
 374 #define RTListRemoveNextCpp(pList, pCurNode, Type, Member) \
 375     ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
 376
 377 /**
 378  * Removes and returns the previous node in the list or NULL if the start has
 379  * been reached.
 380  *
 381  * @returns The previous node, or NULL if end of list.
 382  *
 383  * @param   pList               The list @a pCurNode is linked on.
 384  * @param   pCurNode            The current node, of type @a Type.
 385  * @param   Type                Structure the list node is a member of.
 386  * @param   Member              The list node member.
 387  */
 388 #define RTListRemovePrev(pList, pCurNode, Type, Member) \
 389     ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
 390 /** @copydoc RTListRemovePrev */
 391 #define RTListRemovePrevCpp(pList, pCurNode, Type, Member) \
 392     ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
 393
 394
 395 /**
 396  * Enumerate the list in head to tail order.
 397  *
 398  * @param   pList               List to enumerate.
 399  * @param   pIterator           The iterator variable name.
 400  * @param   Type                Structure the list node is a member of.
 401  * @param   Member              The list node member name.
 402  */
 403 #define RTListForEach(pList, pIterator, Type, Member) \
 404     for (pIterator = RTListNodeGetNext(pList, Type, Member); \
 405          !RTListNodeIsDummy(pList, pIterator, Type, Member); \
 406          pIterator = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
 407 /** @copydoc RTListForEach */
 408 #define RTListForEachCpp(pList, pIterator, Type, Member) \
 409     for (pIterator = RTListNodeGetNextCpp(pList, Type, Member); \
 410          !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
 411          pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
 412
 413
 414 /**
 415  * Enumerate the list in head to tail order, safe against removal of the
 416  * current node.
 417  *
 418  * @param   pList               List to enumerate.
 419  * @param   pIterator           The iterator variable name.
 420  * @param   pIterNext           The name of the variable saving the pointer to
 421  *                              the next element.
 422  * @param   Type                Structure the list node is a member of.
 423  * @param   Member              The list node member name.
 424  */
 425 #define RTListForEachSafe(pList, pIterator, pIterNext, Type, Member) \
 426     for (pIterator = RTListNodeGetNext(pList, Type, Member), \
 427          pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member); \
 428          !RTListNodeIsDummy(pList, pIterator, Type, Member); \
 429          pIterator = pIterNext, \
 430          pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
 431 /** @copydoc RTListForEachSafe */
 432 #define RTListForEachSafeCpp(pList, pIterator, pIterNext, Type, Member) \
 433     for (pIterator = RTListNodeGetNextCpp(pList, Type, Member), \
 434          pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member); \
 435          !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
 436          pIterator = pIterNext, \
 437          pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
 438
 439
 440 /**
 441  * Enumerate the list in reverse order (tail to head).
 442  *
 443  * @param   pList               List to enumerate.
 444  * @param   pIterator           The iterator variable name.
 445  * @param   Type                Structure the list node is a member of.
 446  * @param   Member              The list node member name.
 447  */
 448 #define RTListForEachReverse(pList, pIterator, Type, Member) \
 449     for (pIterator = RTListNodeGetPrev(pList, Type, Member); \
 450          !RTListNodeIsDummy(pList, pIterator, Type, Member); \
 451          pIterator = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
 452 /** @copydoc RTListForEachReverse */
 453 #define RTListForEachReverseCpp(pList, pIterator, Type, Member) \
 454     for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member); \
 455          !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
 456          pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
 457
 458
 459 /**
 460  * Enumerate the list in reverse order (tail to head).
 461  *
 462  * @param   pList               List to enumerate.
 463  * @param   pIterator           The iterator variable name.
 464  * @param   pIterPrev           The name of the variable saving the pointer to
 465  *                              the previous element.
 466  * @param   Type                Structure the list node is a member of.
 467  * @param   Member              The list node member name.
 468  */
 469 #define RTListForEachReverseSafe(pList, pIterator, pIterPrev, Type, Member) \
 470     for (pIterator = RTListNodeGetPrev(pList, Type, Member), \
 471          pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member); \
 472          !RTListNodeIsDummy(pList, pIterator, Type, Member); \
 473          pIterator = pIterPrev, \
 474          pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
 475 /** @copydoc RTListForEachReverseSafe */
 476 #define RTListForEachReverseSafeCpp(pList, pIterator, pIterPrev, Type, Member) \
 477     for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member), \
 478          pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member); \
 479          !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
 480          pIterator = pIterPrev, \
 481          pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
 482
 483
 484 /**
 485  * Move the given list to a new list header.
 486  *
 487  * @param   pListDst            The new list.
 488  * @param   pListSrc            The list to move.
 489  */
 490 DECLINLINE(void) RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
 491 {
 492     if (!RTListIsEmpty(pListSrc))
 493     {
 494         pListDst->pNext = pListSrc->pNext;
 495         pListDst->pPrev = pListSrc->pPrev;
 496
 497         /* Adjust the first and last element links */
 498         pListDst->pNext->pPrev = pListDst;
 499         pListDst->pPrev->pNext = pListDst;
 500
 501         /* Finally remove the elements from the source list */
 502         RTListInit(pListSrc);
 503     }
 504 }
 505
 506 /**
 507  * List concatenation.
 508  *
 509  * @returns nothing.
 510  * @param   pListDst            The destination list.
 511  * @param   pListSrc            The source list to concatenate.
 512  */
 513 DECLINLINE(void) RTListConcatenate(PRTLISTANCHOR pListDst, PRTLISTANCHOR pListSrc)
 514 {
 515     if (!RTListIsEmpty(pListSrc))
 516     {
 517         PRTLISTNODE pFirst = pListSrc->pNext;
 518         PRTLISTNODE pLast = pListSrc->pPrev;
 519
 520         pListDst->pPrev->pNext = pFirst;
 521         pFirst->pPrev          = pListDst->pPrev;
 522         pLast->pNext           = pListDst;
 523         pListDst->pPrev        = pLast;
 524
 525         /* Finally remove the elements from the source list */
 526         RTListInit(pListSrc);
 527     }
 528 }
 529
 530 RT_C_DECLS_END
 531
 532 /** @} */
 533
 534 #endif