summaryrefslogtreecommitdiffstats
path: root/include/iprt/list.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/iprt/list.h')
-rw-r--r--include/iprt/list.h560
1 files changed, 560 insertions, 0 deletions
diff --git a/include/iprt/list.h b/include/iprt/list.h
new file mode 100644
index 00000000..dbc1946f
--- /dev/null
+++ b/include/iprt/list.h
@@ -0,0 +1,560 @@
+/** @file
+ * IPRT - Generic Doubly Linked List.
+ */
+
+/*
+ * Copyright (C) 2010-2022 Oracle and/or its affiliates.
+ *
+ * This file is part of VirtualBox base platform packages, as
+ * available from https://www.virtualbox.org.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation, in version 3 of the
+ * License.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <https://www.gnu.org/licenses>.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
+ * in the VirtualBox distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ *
+ * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
+ */
+
+#ifndef IPRT_INCLUDED_list_h
+#define IPRT_INCLUDED_list_h
+#ifndef RT_WITHOUT_PRAGMA_ONCE
+# pragma once
+#endif
+
+#include <iprt/types.h>
+
+/** @defgroup grp_rt_list RTList - Generic Doubly Linked List
+ * @ingroup grp_rt
+ *
+ * The list implementation is circular without any type wise distintion between
+ * the list and its nodes. This can be confusing since the list head usually
+ * resides in a different structure than the nodes, so care must be taken when
+ * walking the list.
+ *
+ * @{
+ */
+
+RT_C_DECLS_BEGIN
+
+/**
+ * A list node of a doubly linked list.
+ */
+typedef struct RTLISTNODE
+{
+ /** Pointer to the next list node. */
+ struct RTLISTNODE *pNext;
+ /** Pointer to the previous list node. */
+ struct RTLISTNODE *pPrev;
+} RTLISTNODE;
+/** Pointer to a list node. */
+typedef RTLISTNODE *PRTLISTNODE;
+/** Pointer to a const list node. */
+typedef RTLISTNODE const *PCRTLISTNODE;
+/** Pointer to a list node pointer. */
+typedef PRTLISTNODE *PPRTLISTNODE;
+
+/** The anchor (head/tail) of a doubly linked list.
+ *
+ * @remarks Please use this instead of RTLISTNODE to indicate a list
+ * head/tail. It makes the code so much easier to read. Also,
+ * always mention the actual list node type(s) in the comment. */
+typedef RTLISTNODE RTLISTANCHOR;
+/** Pointer to a doubly linked list anchor. */
+typedef RTLISTANCHOR *PRTLISTANCHOR;
+/** Pointer to a const doubly linked list anchor. */
+typedef RTLISTANCHOR const *PCRTLISTANCHOR;
+
+/** Version of RTLISTNODE for holding a ring-3 only list in data which gets
+ * shared between multiple contexts. */
+#ifdef IN_RING3
+typedef RTLISTNODE RTLISTNODER3;
+#else
+typedef struct { RTR3PTR aOffLimits[2]; } RTLISTNODER3;
+#endif
+/** Version of RTLISTANCHOR for holding a ring-3 only list in data which gets
+ * shared between multiple contexts. */
+typedef RTLISTNODER3 RTLISTANCHORR3;
+
+/** Version of RTLISTNODE for holding a ring-0 only list in data which gets
+ * shared between multiple contexts. */
+#ifdef IN_RING0
+typedef RTLISTNODE RTLISTNODER0;
+#else
+typedef struct { RTR0PTR aOffLimits[2]; } RTLISTNODER0;
+#endif
+/** Version of RTLISTANCHOR for holding a ring-0 only list in data which gets
+ * shared between multiple contexts. */
+typedef RTLISTNODER0 RTLISTANCHORR0;
+
+
+/**
+ * Initialize a list.
+ *
+ * @param pList Pointer to an unitialised list.
+ */
+DECLINLINE(void) RTListInit(PRTLISTNODE pList)
+{
+ pList->pNext = pList;
+ pList->pPrev = pList;
+}
+
+/**
+ * Append a node to the end of the list.
+ *
+ * @param pList The list to append the node to.
+ * @param pNode The node to append.
+ */
+DECLINLINE(void) RTListAppend(PRTLISTNODE pList, PRTLISTNODE pNode)
+{
+ pList->pPrev->pNext = pNode;
+ pNode->pPrev = pList->pPrev;
+ pNode->pNext = pList;
+ pList->pPrev = pNode;
+}
+
+/**
+ * Add a node as the first element of the list.
+ *
+ * @param pList The list to prepend the node to.
+ * @param pNode The node to prepend.
+ */
+DECLINLINE(void) RTListPrepend(PRTLISTNODE pList, PRTLISTNODE pNode)
+{
+ pList->pNext->pPrev = pNode;
+ pNode->pNext = pList->pNext;
+ pNode->pPrev = pList;
+ pList->pNext = pNode;
+}
+
+/**
+ * Inserts a node after the specified one.
+ *
+ * @param pCurNode The current node.
+ * @param pNewNode The node to insert.
+ */
+DECLINLINE(void) RTListNodeInsertAfter(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
+{
+ RTListPrepend(pCurNode, pNewNode);
+}
+
+/**
+ * Inserts a node before the specified one.
+ *
+ * @param pCurNode The current node.
+ * @param pNewNode The node to insert.
+ */
+DECLINLINE(void) RTListNodeInsertBefore(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
+{
+ RTListAppend(pCurNode, pNewNode);
+}
+
+/**
+ * Remove a node from a list.
+ *
+ * @param pNode The node to remove.
+ */
+DECLINLINE(void) RTListNodeRemove(PRTLISTNODE pNode)
+{
+ PRTLISTNODE pPrev = pNode->pPrev;
+ PRTLISTNODE pNext = pNode->pNext;
+
+ pPrev->pNext = pNext;
+ pNext->pPrev = pPrev;
+
+ /* poison */
+ pNode->pNext = NULL;
+ pNode->pPrev = NULL;
+}
+
+
+/**
+ * Remove a node from a list, returns value.
+ *
+ * @returns pNode
+ * @param pNode The node to remove.
+ */
+DECLINLINE(PRTLISTNODE) RTListNodeRemoveRet(PRTLISTNODE pNode)
+{
+ PRTLISTNODE pPrev = pNode->pPrev;
+ PRTLISTNODE pNext = pNode->pNext;
+
+ pPrev->pNext = pNext;
+ pNext->pPrev = pPrev;
+
+ /* poison */
+ pNode->pNext = NULL;
+ pNode->pPrev = NULL;
+
+ return pNode;
+}
+
+/**
+ * Checks if a node is the last element in the list.
+ *
+ * @retval true if the node is the last element in the list.
+ * @retval false otherwise
+ *
+ * @param pList The list.
+ * @param pNode The node to check.
+ */
+#define RTListNodeIsLast(pList, pNode) ((pNode)->pNext == (pList))
+
+/**
+ * Checks if a node is the first element in the list.
+ *
+ * @retval true if the node is the first element in the list.
+ * @retval false otherwise.
+ *
+ * @param pList The list.
+ * @param pNode The node to check.
+ */
+#define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList))
+
+/**
+ * Checks if a type converted node is actually the dummy element (@a pList).
+ *
+ * @retval true if the node is the dummy element in the list.
+ * @retval false otherwise.
+ *
+ * @param pList The list.
+ * @param pNode The node structure to check. Typically
+ * something obtained from RTListNodeGetNext() or
+ * RTListNodeGetPrev(). This is NOT a PRTLISTNODE
+ * but something that contains a RTLISTNODE member!
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListNodeIsDummy(pList, pNode, Type, Member) \
+ ( (pNode) == RT_FROM_MEMBER((pList), Type, Member) )
+/** @copydoc RTListNodeIsDummy */
+#define RTListNodeIsDummyCpp(pList, pNode, Type, Member) \
+ ( (pNode) == RT_FROM_CPP_MEMBER((pList), Type, Member) )
+
+/**
+ * Checks if a list is empty.
+ *
+ * @retval true if the list is empty.
+ * @retval false otherwise.
+ *
+ * @param pList The list to check.
+ */
+#define RTListIsEmpty(pList) ((pList)->pPrev == (pList))
+
+/**
+ * Returns the next node in the list.
+ *
+ * @returns The next node.
+ *
+ * @param pCurNode The current node.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListNodeGetNext(pCurNode, Type, Member) \
+ RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
+/** @copydoc RTListNodeGetNext */
+#define RTListNodeGetNextCpp(pCurNode, Type, Member) \
+ RT_FROM_CPP_MEMBER((pCurNode)->pNext, Type, Member)
+
+/**
+ * Returns the previous node in the list.
+ *
+ * @returns The previous node.
+ *
+ * @param pCurNode The current node.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListNodeGetPrev(pCurNode, Type, Member) \
+ RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
+/** @copydoc RTListNodeGetPrev */
+#define RTListNodeGetPrevCpp(pCurNode, Type, Member) \
+ RT_FROM_CPP_MEMBER((pCurNode)->pPrev, Type, Member)
+
+/**
+ * Returns the first element in the list (checks for empty list).
+ *
+ * @returns Pointer to the first list element, or NULL if empty list.
+ *
+ * @param pList List to get the first element from.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListGetFirst(pList, Type, Member) \
+ (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
+/** @copydoc RTListGetFirst */
+#define RTListGetFirstCpp(pList, Type, Member) \
+ (!RTListIsEmpty(pList) ? RTListNodeGetNextCpp(pList, Type, Member) : NULL)
+
+/**
+ * Returns the last element in the list (checks for empty list).
+ *
+ * @returns Pointer to the last list element, or NULL if empty list.
+ *
+ * @param pList List to get the last element from.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListGetLast(pList, Type, Member) \
+ (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
+/** @copydoc RTListGetLast */
+#define RTListGetLastCpp(pList, Type, Member) \
+ (!RTListIsEmpty(pList) ? RTListNodeGetPrevCpp(pList, Type, Member) : NULL)
+
+/**
+ * Returns the next node in the list or NULL if the end has been reached.
+ *
+ * @returns The next node, or NULL if end of list.
+ *
+ * @param pList The list @a pCurNode is linked on.
+ * @param pCurNode The current node, of type @a Type.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListGetNext(pList, pCurNode, Type, Member) \
+ ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
+/** @copydoc RTListGetNext */
+#define RTListGetNextCpp(pList, pCurNode, Type, Member) \
+ ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
+
+/**
+ * Returns the previous node in the list or NULL if the start has been reached.
+ *
+ * @returns The previous node, or NULL if end of list.
+ *
+ * @param pList The list @a pCurNode is linked on.
+ * @param pCurNode The current node, of type @a Type.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListGetPrev(pList, pCurNode, Type, Member) \
+ ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
+/** @copydoc RTListGetPrev */
+#define RTListGetPrevCpp(pList, pCurNode, Type, Member) \
+ ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
+
+
+/**
+ * Removes and returns the first element in the list (checks for empty list).
+ *
+ * @returns Pointer to the first list element, or NULL if empty list.
+ *
+ * @param pList List to get the first element from.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListRemoveFirst(pList, Type, Member) \
+ (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
+/** @copydoc RTListRemoveFirst */
+#define RTListRemoveFirstCpp(pList, Type, Member) \
+ (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
+
+/**
+ * Removes and returns the last element in the list (checks for empty list).
+ *
+ * @returns Pointer to the last list element, or NULL if empty list.
+ *
+ * @param pList List to get the last element from.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListRemoveLast(pList, Type, Member) \
+ (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
+/** @copydoc RTListRemoveLast */
+#define RTListRemoveLastCpp(pList, Type, Member) \
+ (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
+
+/**
+ * Removes and returns the next node in the list or NULL if the end has been
+ * reached.
+ *
+ * @returns The next node, or NULL if end of list.
+ *
+ * @param pList The list @a pCurNode is linked on.
+ * @param pCurNode The current node, of type @a Type.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListRemoveNext(pList, pCurNode, Type, Member) \
+ ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
+/** @copydoc RTListRemoveNext */
+#define RTListRemoveNextCpp(pList, pCurNode, Type, Member) \
+ ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
+
+/**
+ * Removes and returns the previous node in the list or NULL if the start has
+ * been reached.
+ *
+ * @returns The previous node, or NULL if end of list.
+ *
+ * @param pList The list @a pCurNode is linked on.
+ * @param pCurNode The current node, of type @a Type.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member.
+ */
+#define RTListRemovePrev(pList, pCurNode, Type, Member) \
+ ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
+/** @copydoc RTListRemovePrev */
+#define RTListRemovePrevCpp(pList, pCurNode, Type, Member) \
+ ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
+
+
+/**
+ * Enumerate the list in head to tail order.
+ *
+ * @param pList List to enumerate.
+ * @param pIterator The iterator variable name.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member name.
+ */
+#define RTListForEach(pList, pIterator, Type, Member) \
+ for (pIterator = RTListNodeGetNext(pList, Type, Member); \
+ !RTListNodeIsDummy(pList, pIterator, Type, Member); \
+ pIterator = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
+/** @copydoc RTListForEach */
+#define RTListForEachCpp(pList, pIterator, Type, Member) \
+ for (pIterator = RTListNodeGetNextCpp(pList, Type, Member); \
+ !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
+ pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
+
+
+/**
+ * Enumerate the list in head to tail order, safe against removal of the
+ * current node.
+ *
+ * @param pList List to enumerate.
+ * @param pIterator The iterator variable name.
+ * @param pIterNext The name of the variable saving the pointer to
+ * the next element.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member name.
+ */
+#define RTListForEachSafe(pList, pIterator, pIterNext, Type, Member) \
+ for (pIterator = RTListNodeGetNext(pList, Type, Member), \
+ pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member); \
+ !RTListNodeIsDummy(pList, pIterator, Type, Member); \
+ pIterator = pIterNext, \
+ pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
+/** @copydoc RTListForEachSafe */
+#define RTListForEachSafeCpp(pList, pIterator, pIterNext, Type, Member) \
+ for (pIterator = RTListNodeGetNextCpp(pList, Type, Member), \
+ pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member); \
+ !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
+ pIterator = pIterNext, \
+ pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )
+
+
+/**
+ * Enumerate the list in reverse order (tail to head).
+ *
+ * @param pList List to enumerate.
+ * @param pIterator The iterator variable name.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member name.
+ */
+#define RTListForEachReverse(pList, pIterator, Type, Member) \
+ for (pIterator = RTListNodeGetPrev(pList, Type, Member); \
+ !RTListNodeIsDummy(pList, pIterator, Type, Member); \
+ pIterator = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
+/** @copydoc RTListForEachReverse */
+#define RTListForEachReverseCpp(pList, pIterator, Type, Member) \
+ for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member); \
+ !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
+ pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
+
+
+/**
+ * Enumerate the list in reverse order (tail to head).
+ *
+ * @param pList List to enumerate.
+ * @param pIterator The iterator variable name.
+ * @param pIterPrev The name of the variable saving the pointer to
+ * the previous element.
+ * @param Type Structure the list node is a member of.
+ * @param Member The list node member name.
+ */
+#define RTListForEachReverseSafe(pList, pIterator, pIterPrev, Type, Member) \
+ for (pIterator = RTListNodeGetPrev(pList, Type, Member), \
+ pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member); \
+ !RTListNodeIsDummy(pList, pIterator, Type, Member); \
+ pIterator = pIterPrev, \
+ pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
+/** @copydoc RTListForEachReverseSafe */
+#define RTListForEachReverseSafeCpp(pList, pIterator, pIterPrev, Type, Member) \
+ for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member), \
+ pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member); \
+ !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
+ pIterator = pIterPrev, \
+ pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )
+
+
+/**
+ * Move the given list to a new list header.
+ *
+ * @param pListDst The new list.
+ * @param pListSrc The list to move.
+ */
+DECLINLINE(void) RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
+{
+ if (!RTListIsEmpty(pListSrc))
+ {
+ pListDst->pNext = pListSrc->pNext;
+ pListDst->pPrev = pListSrc->pPrev;
+
+ /* Adjust the first and last element links */
+ pListDst->pNext->pPrev = pListDst;
+ pListDst->pPrev->pNext = pListDst;
+
+ /* Finally remove the elements from the source list */
+ RTListInit(pListSrc);
+ }
+ else
+ RTListInit(pListDst);
+}
+
+/**
+ * List concatenation.
+ *
+ * @returns nothing.
+ * @param pListDst The destination list.
+ * @param pListSrc The source list to concatenate.
+ */
+DECLINLINE(void) RTListConcatenate(PRTLISTANCHOR pListDst, PRTLISTANCHOR pListSrc)
+{
+ if (!RTListIsEmpty(pListSrc))
+ {
+ PRTLISTNODE pFirst = pListSrc->pNext;
+ PRTLISTNODE pLast = pListSrc->pPrev;
+
+ pListDst->pPrev->pNext = pFirst;
+ pFirst->pPrev = pListDst->pPrev;
+ pLast->pNext = pListDst;
+ pListDst->pPrev = pLast;
+
+ /* Finally remove the elements from the source list */
+ RTListInit(pListSrc);
+ }
+}
+
+RT_C_DECLS_END
+
+/** @} */
+
+#endif /* !IPRT_INCLUDED_list_h */