Index: /trunk/include/iprt/list.h =================================================================== --- /trunk/include/iprt/list.h (revision 26739) +++ /trunk/include/iprt/list.h (revision 26740) @@ -1,8 +1,8 @@ /** @file - * IPRT - List handling functions. + * IPRT - Generic Doubly Linked List. */ /* - * Copyright (C) 2006-2007 Sun Microsystems, Inc. + * Copyright (C) 2010 Sun Microsystems, Inc. * * This file is part of VirtualBox Open Source Edition (OSE), as @@ -32,8 +32,13 @@ #include -#include - -/** @defgroup grp_rt_list RTList - Generic List Interface. + +/** @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. + * * @{ */ @@ -42,5 +47,5 @@ /** - * A list node of a double linked list. + * A list node of a doubly linked list. */ typedef struct RTLISTNODE @@ -59,6 +64,5 @@ * Initialize a list. * - * @returns nothing. - * @param pList Pointer to an unitialised list. + * @param pList Pointer to an unitialised list. */ DECLINLINE(void) RTListInit(PRTLISTNODE pList) @@ -69,9 +73,8 @@ /** - * Append a node to the end of the list - * - * @returns nothing. - * @param pList The list to append the node to. - * @param pNode The node to append. + * 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) @@ -84,9 +87,8 @@ /** - * Add a node as the first element of the list - * - * @returns nothing. - * @param pList The list to prepend the node to. - * @param pNode The node to prepend. + * 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) @@ -101,6 +103,5 @@ * Remove a node from a list. * - * @returns nothing. - * @param pNode The node to remove. + * @param pNode The node to remove. */ DECLINLINE(void) RTListNodeRemove(PRTLISTNODE pNode) @@ -111,78 +112,91 @@ pPrev->pNext = pNext; pNext->pPrev = pPrev; -} - -/** - * Checks if a node is the last element in the list - * - * @returns true if the node is the last element in the list. - * false otherwise - * @param list The list. - * @param node The node to check. - */ -#define RTListNodeIsLast(list, node) ((node)->pNext == list) - -/** - * Checks if a node is the first element in the list - * - * @returns true if the node is the first element in the list. - * false otherwise - * @param list The list. - * @param node The node to check. - */ -#define RTListNodeIsFirst(list, node) ((node)->pPrev == list) + + /* poison */ + pNode->pNext = NULL; + pNode->pPrev = NULL; +} + +/** + * Checks if a node is the last element in the list. + * + * @retval @c true if the node is the last element in the list. + * @retval @c 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 @c true if the node is the first element in the list. + * @retval @c false otherwise. + * + * @param pList The list. + * @param pNode The node to check. + */ +#define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList)) /** * Checks if a list is empty. * - * @returns true if the list is empty - * false otherwise - * @param list The list to check. - */ -#define RTListIsEmpty(list) ((list)->pPrev == list) + * @retval @c true if the list is empty. + * @retval @c false otherwise. + * + * @param pList The list to check. + */ +#define RTListIsEmpty(pList) ((pList)->pPrev == (pList)) /** * Returns the next node in the list. * - * @returns Next node. - * @param node The current node. - * @param type Structure the list node is a member of. - * @param member The list node member. - */ -#define RTListNodeGetNext(node, type, member) ((type *)((uint8_t *)((node)->pNext) - RT_OFFSETOF(type, member))) + * @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) /** * Returns the previous node in the list. * - * @returns Next node. - * @param node The current node. - * @param type Structure the list node is a member of. - * @param member The list node member. - */ -#define RTListNodeGetPrev(node, type, member) ((type *)((uint8_t *)((node)->pPrev) - RT_OFFSETOF(type, member))) - -/** - * Returns the first element in the list - * or NULL if the list is empty. - * - * @returns Pointer to the first list element - * or NULL if the list is empty. - * @param list List to get the first element from. - * @param type Structure the list node is a member of. - * @param member The list node member. - */ -#define RTListNodeGetFirst(list, type, member) (RTListIsEmpty(list) ? NULL : RTListNodeGetNext(list, type, member)) - -/** - * Returns the last element in the list - * or NULL if the list is empty. - * - * @returns Pointer to the last list element - * or NULL if the list is empty. - * @param list List to get the first element from. - * @param type Structure the list node is a member of. - * @param member The list node member. - */ -#define RTListNodeGetLast(list, type, member) (RTListIsEmpty(list) ? NULL : RTListNodeGetPrev(list, type, member)) + * @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) + +/** + * Returns the first element in the list (checks for empty list). + * + * @retval Pointer to the first list element. + * @retval NULL if the list is empty. + * + * @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 RTListNodeGetFirst(pList, Type, Member) \ + (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL) + +/** + * Returns the last element in the list (checks for empty list). + * + * @retval Pointer to the last list element. + * @retval NULL if the list is empty. + * + * @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 RTListNodeGetLast(pList, Type, Member) \ + (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL) RT_C_DECLS_END