/* ********************************************************** * Copyright 2006 - 2010 VMware, Inc. All rights reserved. * **********************************************************/ /* ********************************************************** * Portions of the code in this file require the following * copyright notice to be displayed: * * Copyright (C) 1985, 1988 Regents of the University of California * Permission to use, copy, modify, and distribute this * software and its documentation for any purpose and without * fee is hereby granted, provided that the above copyright * notice appear in all copies. The University of California * makes no representations about the suitability of this * software for any purpose. It is provided "as is" without * express or implied warranty. * **********************************************************/ /* * @VMKAPIMOD_LICENSE@ */ /* *********************************************************************** * List */ /** * \addtogroup Lib * @{ * \defgroup List Doubly-Linked Lists * * The following are interfaces for a list abstraction which enables * arbitrary data structures to be linked together into a doubly-linked * circular list. * * A list is composed of a sentinel header and its real members, if any. * Thus, an empty list consists of a single header element whose nextPtr * and prevPtr fields point to itself. * * The links are contained in a two-element structure called vmk_ListLinks. * A list joins vmk_ListLinks records (that is, each vmk_ListLinks structure * points to other vmk_ListLinks structures), but if the vmk_ListLinks is the * first field within a larger structure, then the larger structures are * effectively linked together as follows: * * \code * header * (vmk_ListLinks) First element Second Element * ----------------- ------------------ ----------------- * ..-> | nextPtr | ----> | vmk_ListLinks | ----> | vmk_ListLinks | ----.. * | - - - - - - - | | | | | * ..-- | prevPtr | <---- | | <---- | | <---.. * ----------------- - --- --- --- - - --- --- --- - * | rest of | | rest of | * | structure | | structure | * | | | | * | ... | | ... | * ----------------- ----------------- * \endcode * * It is possible to link structures through vmk_ListLinks fields that are * not at the beginning of the larger structure, but it is then necessary * to use VMK_LIST_ENTRY to extract the surrounding structure from * the list element. * * \par A typical structure might be something like: * * \code * typedef struct { * vmk_ListLinks links; * char ch; * integer flags; * } Example; * \endcode * * @{ *********************************************************************** */ #ifndef _VMKAPI_LIST_H_ #define _VMKAPI_LIST_H_ /** \cond never */ #ifndef VMK_HEADER_INCLUDED_FROM_VMKAPI_H #error This vmkapi file should never be included directly but only via vmkapi.h #endif /** \endcond never */ /** * \brief List links container. */ typedef struct vmk_ListLinks { struct vmk_ListLinks *prevPtr; struct vmk_ListLinks *nextPtr; } vmk_ListLinks; /* *********************************************************************** * VMK_LIST_ENTRY -- */ /** * * \brief Get a pointer to the structure containing a given list * element. * * \param[in] itemPtr List element that is contained by * another structure. * \param[in] containerType C type of the container. * \param[in] fieldInContainer Name of the structure field in the * container that itemPtr is pointing to. * * This macro allows a list pointer embedded in a structure to be * somwhere other than the initial item in the structure. * * \par Example: * \code * typedef struct * { * int a; * vmk_ListLinks links; * int b; * } * myType; * * myType example; * myType *ptr; * vmk_ListLinks *listElem; * * listElem = &(example.links); * ptr = VMK_LIST_ENTRY(listElem, myType, links); * \endcode * "ptr" should now point at "example" * *********************************************************************** */ #define VMK_LIST_ENTRY(itemPtr, containerType, fieldInContainer) \ ((containerType *) ((vmk_uint8 *) (itemPtr) - \ ((unsigned long) &((containerType *)0)->fieldInContainer))) /* *********************************************************************** * vmk_ListInit -- */ /** * * \brief Initialize a header pointer to point to an empty list. * * \param[in] headerPtr List header to initialize. * *********************************************************************** */ static inline void vmk_ListInit(vmk_ListLinks *headerPtr) { VMK_ASSERT(headerPtr != NULL); headerPtr->nextPtr = headerPtr; headerPtr->prevPtr = headerPtr; } /* *********************************************************************** * vmk_ListInitElement -- */ /** * * \brief Initialize a list element. * * \param[in] elementPtr List element to initialize. * *********************************************************************** */ static inline void vmk_ListInitElement(vmk_ListLinks *elementPtr) { elementPtr->prevPtr = (vmk_ListLinks *) NULL; elementPtr->nextPtr = (vmk_ListLinks *) NULL; } /* *********************************************************************** * vmk_ListIsUnlinkedElement -- */ /** * * \brief Check whether a given element is part of a list or not. * * \param[in] elementPtr List element to check. * * \retval VMK_TRUE The element is not in a list. * \retval VMK_FALSE The element is linked into a list. * *********************************************************************** */ static inline vmk_Bool vmk_ListIsUnlinkedElement(vmk_ListLinks *elementPtr) { return (elementPtr->prevPtr == (vmk_ListLinks *) NULL && elementPtr->nextPtr == (vmk_ListLinks *) NULL); } /* *********************************************************************** * VMK_LIST_FORALL -- */ /** * * \brief for-loop replacement macro to scan through a list from * the first to the last list member. * * \param[in] headerPtr The list to scan * \param[out] itemPtr Loop pointer that is updated with the current * list member each time through the loop. * * \note This macro does not tolerate the removal of itemPtr from * the list during the loop. * * \sa VMK_LIST_FORALL_SAFE * *********************************************************************** */ #define VMK_LIST_FORALL(headerPtr, itemPtr) \ for (itemPtr = vmk_ListFirst(headerPtr); \ !vmk_ListIsAtEnd((headerPtr),itemPtr); \ itemPtr = vmk_ListNext(itemPtr)) /* *********************************************************************** * VMK_LIST_FORALL_REVERSE -- */ /** * * \brief for-loop replacement macro to scan through a list from * the last to the first list member. * * \param[in] headerPtr The list to scan * \param[out] itemPtr Loop pointer that is updated with the current * list member each time through the loop. * * \note This macro does not tolerate the removal of itemPtr from * the list during the loop. * * \sa VMK_LIST_FORALL_REVERSE_SAFE * *********************************************************************** */ #define VMK_LIST_FORALL_REVERSE(headerPtr, itemPtr) \ for (itemPtr = vmk_ListLast(headerPtr); \ !vmk_ListIsAtEnd((headerPtr),itemPtr); \ itemPtr = vmk_ListPrev(itemPtr)) /* *********************************************************************** * VMK_LIST_FORALL_SAFE -- */ /** * * \brief for-loop replacement macro to scan through a list from * the first to the last list member. * * \param[in] headerPtr The list to scan. * \param[out] itemPtr Loop pointer that is updated each time * through the loop with the current list member. * \param[out] nextPtr Loop pointer that is updated each time * through the loop with the next list member. * * \note This macro should be used if itemPtr must be removed from * the list during the loop. * *********************************************************************** */ #define VMK_LIST_FORALL_SAFE(headerPtr, itemPtr, nextPtr) \ for (itemPtr = vmk_ListFirst(headerPtr), nextPtr = vmk_ListNext(itemPtr); \ !vmk_ListIsAtEnd((headerPtr),itemPtr); \ itemPtr = nextPtr, nextPtr = vmk_ListNext(nextPtr)) /* *********************************************************************** * VMK_LIST_FORALL_REVERSE_SAFE -- */ /** * * \brief for-loop replacement macro to scan through a list from * the last to the first list member. * * \param[in] headerPtr The list to scan. * \param[out] itemPtr Loop pointer that is updated each time * through the loop with the current list member. * \param[out] prevPtr Loop pointer that is updated each time * through the loop with the next list member. * * \note This macro should be used if itemPtr must be removed from * the list during the loop. * *********************************************************************** */ #define VMK_LIST_FORALL_REVERSE_SAFE(headerPtr, itemPtr, prevPtr) \ for (itemPtr = vmk_ListLast(headerPtr), prevPtr = vmk_ListPrev(itemPtr); \ !vmk_ListIsAtEnd((headerPtr),itemPtr); \ itemPtr = prevPtr, prevPtr = vmk_ListPrev(prevPtr)) /* *********************************************************************** * VMK_LIST_ITER -- */ /** * * \brief while-loop replacement macro to scan through a list from * a given list member to the last list member. * * \param[in] headerPtr The list to scan. * \param[in,out] itemPtr The first list member to scan. This pointer * is also updated with the current list member * each time through the loop. * * \note This macro does not tolerate the removal of itemPtr from the * list during the loop. * * \sa VMK_LIST_ITER_SAFE * *********************************************************************** */ #define VMK_LIST_ITER(headerPtr, itemPtr) \ for (; \ !vmk_ListIsAtEnd((headerPtr),itemPtr); \ itemPtr = vmk_ListNext(itemPtr)) /* *********************************************************************** * VMK_LIST_ITER_REVERSE -- */ /** * * \brief while-loop replacement macro to scan through a list from * a given list member to the first list member. * * \param[in] headerPtr The list to scan. * \param[in,out] itemPtr The first list member to scan. This pointer * is also updated with the current list member * each time through the loop. * * \note This macro does not tolerate the removal of itemPtr from the * list during the loop. * * \sa VMK_LIST_ITER_REVERSE_SAFE * *********************************************************************** */ #define VMK_LIST_ITER_REVERSE(headerPtr, itemPtr) \ for (; \ !vmk_ListIsAtEnd((headerPtr),itemPtr); \ itemPtr = vmk_ListPrev(itemPtr)) /* *********************************************************************** * VMK_LIST_ITER_SAFE -- */ /** * * \brief while-loop replacement macro to scan through a list from * a given list member to the last list member. * * \param[in] headerPtr The list to scan. * \param[in,out] itemPtr The first list member to scan. This pointer * is also updated with the current list member * each time through the loop. * \param[out] nextPtr Loop pointer that is updated each time through * the loop with the next list member. * * \note This macro should be used if itemPtr must be removed from * the list during the loop. * *********************************************************************** */ #define VMK_LIST_ITER_SAFE(headerPtr, itemPtr, nextPtr) \ for (nextPtr = vmk_ListNext(itemPtr); \ !vmk_ListIsAtEnd((headerPtr),itemPtr); \ itemPtr = nextPtr, nextPtr = vmk_ListNext(nextPtr)) /* *********************************************************************** * VMK_LIST_ITER_REVERSE_SAFE -- */ /** * * \brief while-loop replacement macro to scan through a list from * a given list member to the first list member. * * \param[in] headerPtr The list to scan. * \param[in,out] itemPtr The first list member to scan. This pointer * is also updated with the current list member * each time through the loop. * \param[out] prevPtr Loop pointer that is updated each time through * the loop with the next list member. * * \note This macro should be used if itemPtr must be removed from * the list during the loop. * *********************************************************************** */ #define VMK_LIST_ITER_REVERSE_SAFE(headerPtr, itemPtr, prevPtr) \ for (prevPtr = vmk_ListPrev(itemPtr); \ !vmk_ListIsAtEnd((headerPtr),itemPtr); \ itemPtr = prevPtr, prevPtr = vmk_ListPrev(prevPtr)) /* *********************************************************************** * vmk_ListIsEmpty -- */ /** * * \brief Check if a list does not contain any members. * * \param[in] headerPtr The head of the list to check * * \retval VMK_TRUE The list is empty * \retval VMK_FALSE The list is not empty * *********************************************************************** */ static inline vmk_Bool vmk_ListIsEmpty(vmk_ListLinks *headerPtr) { return (headerPtr == headerPtr->nextPtr); } /* *********************************************************************** * vmk_ListIsAtEnd -- */ /** * * \brief Check if itemPtr is pointing just past the last list element. * * This function is useful for loops where it can be used to check if * the loop has scanned all the list elements by checking to see if * the loop's list pointer has scanned past the end of the list. * * \param[in] headerPtr The head of the list to check. * \param[in] itemPtr The list entry pointer to check. * * \retval VMK_TRUE itemPtr points past the last list element. * \retval VMK_FALSE itemPtr does not point past the last * list element. * *********************************************************************** */ static inline vmk_Bool vmk_ListIsAtEnd(vmk_ListLinks *headerPtr, vmk_ListLinks *itemPtr) { return (itemPtr == headerPtr); } /* *********************************************************************** * vmk_ListFirst -- */ /** * * \brief Get the first list member in a list. * * \param[in] headerPtr The list from which to retrieve the element. * * \return A pointer to the first member in the list. * *********************************************************************** */ static inline vmk_ListLinks * vmk_ListFirst(vmk_ListLinks *headerPtr) { return (headerPtr->nextPtr); } /* *********************************************************************** * vmk_ListLast -- */ /** * * \brief Get the last list member in a list. * * \param[in] headerPtr The list from which to retrieve the element. * * \return A pointer to the last member in the list * *********************************************************************** */ static inline vmk_ListLinks * vmk_ListLast(vmk_ListLinks *headerPtr) { return (headerPtr->prevPtr); } /* *********************************************************************** * vmk_ListPrev -- */ /** * * \brief Return the preceeding list memeber. * * This function will return the list header if the memeber is the * first list member. * * \param[in] itemPtr The list member from which to get the * previous member. * * \return A pointer to the preceeding list member * *********************************************************************** */ static inline vmk_ListLinks * vmk_ListPrev(vmk_ListLinks *itemPtr) { return (itemPtr->prevPtr); } /* *********************************************************************** * vmk_ListNext -- */ /** * * \brief Return the following list memeber . * * This function will return the list header if the memeber is the * last list member. * * \param[in] itemPtr The list member from which to get the * following member. * * \return A pointer to the following list member. * *********************************************************************** */ static inline vmk_ListLinks * vmk_ListNext(vmk_ListLinks *itemPtr) { return (itemPtr->nextPtr); } /* *********************************************************************** * vmk_ListInsert -- */ /** * * \brief Insert a list element into a list after another element. * * vmk_ListAfter, vmk_ListBefore, vmk_ListAtFront, and * vmk_ListAtRear can be used to determine destPtr. * * \par For example: * \code * vmk_ListInsert(myElement, vmk_ListAtFront(myList)); * \endcode * * \param[in] itemPtr List element to insert in the list. * \param[in] destPtr List member to insert after. * *********************************************************************** */ static inline void vmk_ListInsert(vmk_ListLinks *itemPtr, vmk_ListLinks *destPtr) { VMK_ASSERT(itemPtr != NULL && destPtr != NULL); VMK_ASSERT(itemPtr != destPtr); /* Can't insert something after itself. */ itemPtr->nextPtr = destPtr->nextPtr; itemPtr->prevPtr = destPtr; destPtr->nextPtr->prevPtr = itemPtr; destPtr->nextPtr = itemPtr; } /* *********************************************************************** * vmk_ListAfter -- */ /** * * \brief Get the appropriate itemPtr for vmk_ListInsert * so that insertion will take place after a given element. * * \param[in] itemPtr List member to insert after. * * \return A pointer to a list element that will allow list * insertion after the given list member. * *********************************************************************** */ static inline vmk_ListLinks * vmk_ListAfter(vmk_ListLinks *itemPtr) { return itemPtr; } /* *********************************************************************** * vmk_ListBefore -- */ /** * * \brief Get the appropriate itemPtr for vmk_ListInsert() * so that insertion will take place before a given element. * * \param[in] itemPtr List member to insert before. * * \return A pointer to a list element that will allow list * insertion before the given list member. * *********************************************************************** */ static inline vmk_ListLinks * vmk_ListBefore(vmk_ListLinks *itemPtr) { return itemPtr->prevPtr; } /* *********************************************************************** * vmk_ListAtFront -- */ /** * * \brief Get the appropriate itemPtr for vmk_ListInsert() to insert * at the head of a given list. * * \param[in] headerPtr List on which the insertion will take place. * * \return A pointer to a list element that will allow list insertion * at the head of the given list. * *********************************************************************** */ static inline vmk_ListLinks * vmk_ListAtFront(vmk_ListLinks *headerPtr) { return headerPtr; } /* *********************************************************************** * vmk_ListAtRear -- */ /** * * \brief Get the appropriate itemPtr for vmk_ListInsert() to insert * at the tail of a given list. * * \param[in] headerPtr List on which the insertion will take place. * * \return A pointer to the list element that will allow list insertion * at the tail of the given list. * *********************************************************************** */ static inline vmk_ListLinks * vmk_ListAtRear(vmk_ListLinks *headerPtr) { return headerPtr->prevPtr; } /* *********************************************************************** * vmk_ListRemove -- */ /** * * \brief Remove a list element from the list in which it is contained. * * \param[in] itemPtr List element to be removed. * *********************************************************************** */ static inline void vmk_ListRemove(vmk_ListLinks *itemPtr) { VMK_ASSERT(itemPtr != NULL && itemPtr != itemPtr->nextPtr); VMK_ASSERT(itemPtr->prevPtr->nextPtr == itemPtr && itemPtr->nextPtr->prevPtr == itemPtr); itemPtr->prevPtr->nextPtr = itemPtr->nextPtr; itemPtr->nextPtr->prevPtr = itemPtr->prevPtr; vmk_ListInitElement(itemPtr); } /* *********************************************************************** * vmk_ListSplitBefore -- */ /** * * \brief Remove items from the head of a list up to and including * a given list member and put them at the head of another list. * * \param[in] headerPtr The source list from which the members will * be moved. * \param[in] headerPtr2 The destination list to which the members * will be moved. * \param[in] itemPtr The list member in the source list that is * the last element to be moved. * *********************************************************************** */ static inline void vmk_ListSplitBefore(vmk_ListLinks *headerPtr, vmk_ListLinks *headerPtr2, vmk_ListLinks *itemPtr) { VMK_ASSERT(headerPtr); VMK_ASSERT(headerPtr2); VMK_ASSERT(headerPtr != headerPtr2); VMK_ASSERT(vmk_ListIsEmpty(headerPtr2)); /* set up new list */ headerPtr2->nextPtr = headerPtr->nextPtr; headerPtr2->prevPtr = itemPtr; /* fix old list */ headerPtr->nextPtr = itemPtr->nextPtr; itemPtr->nextPtr->prevPtr = headerPtr; /* fix rest of new list entries */ itemPtr->nextPtr = headerPtr2; headerPtr2->nextPtr->prevPtr = headerPtr2; } /* *********************************************************************** * vmk_ListSplitAfter -- */ /** * * \brief Remove items from the tail of a list up to and including * a given list member and puts them at the tail of another list. * * \param[in] headerPtr The non-empty source list from which the * members will be moved. * \param[in] headerPtr2 The empty destination list to which the * members will be moved. * \param[in] itemPtr The list member in the source list that is * the first element to be moved. * *********************************************************************** */ static inline void vmk_ListSplitAfter(vmk_ListLinks *headerPtr, vmk_ListLinks *headerPtr2, vmk_ListLinks *itemPtr) { VMK_ASSERT(headerPtr); VMK_ASSERT(headerPtr2); VMK_ASSERT(headerPtr != headerPtr2); VMK_ASSERT(!vmk_ListIsEmpty(headerPtr)); VMK_ASSERT(vmk_ListIsEmpty(headerPtr2)); /* set up new list */ headerPtr2->prevPtr = headerPtr->prevPtr; headerPtr2->nextPtr = itemPtr; /* fix old list */ headerPtr->prevPtr = itemPtr->prevPtr; itemPtr->prevPtr->nextPtr = headerPtr; /* fix rest of new list entries */ itemPtr->prevPtr = headerPtr2; headerPtr2->prevPtr->nextPtr = headerPtr2; } #endif /* _VMKAPI_LIST_H_ */ /** @} */ /** @} */