Index: /trunk/include/iprt/list.h =================================================================== --- /trunk/include/iprt/list.h (revision 26739) +++ /trunk/include/iprt/list.h (revision 26739) @@ -0,0 +1,192 @@ +/** @file + * IPRT - List handling functions. + */ + +/* + * Copyright (C) 2006-2007 Sun Microsystems, Inc. + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * General Public License (GPL) as published by the Free Software + * Foundation, in version 2 as it comes in the "COPYING" file of the + * VirtualBox OSE distribution. VirtualBox OSE is distributed in the + * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL) only, as it comes in the "COPYING.CDDL" file of the + * VirtualBox OSE 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. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa + * Clara, CA 95054 USA or visit http://www.sun.com if you need + * additional information or have any questions. + */ + +#ifndef ___iprt_list_h +#define ___iprt_list_h + +#include +#include + +/** @defgroup grp_rt_list RTList - Generic List Interface. + * @ingroup grp_rt + * @{ + */ + +RT_C_DECLS_BEGIN + +/** + * A list node of a double 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 list node pointer. */ +typedef PRTLISTNODE *PPRTLISTNODE; + +/** + * Initialize a list. + * + * @returns nothing. + * @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 + * + * @returns nothing. + * @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 + * + * @returns nothing. + * @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; +} + +/** + * Remove a node from a list. + * + * @returns nothing. + * @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; +} + +/** + * 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) + +/** + * 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) + +/** + * 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 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)) + +RT_C_DECLS_END + +/** @} */ + +#endif Index: /trunk/src/VBox/Runtime/testcase/Makefile.kmk =================================================================== --- /trunk/src/VBox/Runtime/testcase/Makefile.kmk (revision 26738) +++ /trunk/src/VBox/Runtime/testcase/Makefile.kmk (revision 26739) @@ -118,5 +118,6 @@ tstTSC \ tstUtf8 \ - tstRTUuid + tstRTUuid \ + tstRTList # tstSems PROGRAMS.win += \ @@ -445,4 +446,5 @@ tstUtf8_SOURCES = tstUtf8.cpp +tstRTList_SOURCES = tstRTList.cpp # Index: /trunk/src/VBox/Runtime/testcase/tstRTList.cpp =================================================================== --- /trunk/src/VBox/Runtime/testcase/tstRTList.cpp (revision 26739) +++ /trunk/src/VBox/Runtime/testcase/tstRTList.cpp (revision 26739) @@ -0,0 +1,173 @@ +/* $Id$ */ +/** @file + * IPRT Testcase - List interface. + */ + +/* + * Copyright (C) 2009 Sun Microsystems, Inc. + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * General Public License (GPL) as published by the Free Software + * Foundation, in version 2 as it comes in the "COPYING" file of the + * VirtualBox OSE distribution. VirtualBox OSE is distributed in the + * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL) only, as it comes in the "COPYING.CDDL" file of the + * VirtualBox OSE 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. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa + * Clara, CA 95054 USA or visit http://www.sun.com if you need + * additional information or have any questions. + */ + +/******************************************************************************* +* Header Files * +*******************************************************************************/ +#include +#include +#include +#include +#include +#include + +typedef struct LISTELEM +{ + /** Test data */ + unsigned idx; + /** Node */ + RTLISTNODE Node; +} LISTELEM, *PLISTELEM; + +static void tstRTListOrder(RTTEST hTest, PRTLISTNODE pList, unsigned cElements, unsigned idxStart, unsigned idxEnd, unsigned idxStep) +{ + RTTEST_CHECK(hTest, RTListIsEmpty(pList) == false); + RTTEST_CHECK(hTest, RTListNodeGetFirst(pList, LISTELEM, Node) != NULL); + RTTEST_CHECK(hTest, RTListNodeGetLast(pList, LISTELEM, Node) != NULL); + if (cElements > 1) + RTTEST_CHECK(hTest, RTListNodeGetLast(pList, LISTELEM, Node) != RTListNodeGetFirst(pList, LISTELEM, Node)); + else + RTTEST_CHECK(hTest, RTListNodeGetLast(pList, LISTELEM, Node) == RTListNodeGetFirst(pList, LISTELEM, Node)); + + /* Check that the order is right. */ + PLISTELEM pNode = RTListNodeGetFirst(pList, LISTELEM, Node); + for (unsigned i = idxStart; i < idxEnd; i += idxStep) + { + RTTEST_CHECK(hTest, pNode->idx == i); + pNode = RTListNodeGetNext(&pNode->Node, LISTELEM, Node); + } + + RTTEST_CHECK(hTest, pNode->idx == idxEnd); + RTTEST_CHECK(hTest, RTListNodeGetLast(pList, LISTELEM, Node) == pNode); + RTTEST_CHECK(hTest, RTListNodeIsLast(pList, &pNode->Node) == true); + + /* Check reverse order */ + pNode = RTListNodeGetLast(pList, LISTELEM, Node); + for (unsigned i = idxEnd; i > idxStart; i -= idxStep) + { + RTTEST_CHECK(hTest, pNode->idx == i); + pNode = RTListNodeGetPrev(&pNode->Node, LISTELEM, Node); + } + + RTTEST_CHECK(hTest, pNode->idx == idxStart); + RTTEST_CHECK(hTest, RTListNodeGetFirst(pList, LISTELEM, Node) == pNode); + RTTEST_CHECK(hTest, RTListNodeIsFirst(pList, &pNode->Node) == true); +} + +static void tstRTListCreate(RTTEST hTest, unsigned cElements) +{ + RTTestISubF("RTList - Test with %u elements", cElements); + + RTLISTNODE ListHead; + + RTListInit(&ListHead); + RTTEST_CHECK(hTest, RTListIsEmpty(&ListHead) == true); + RTTEST_CHECK(hTest, RTListNodeGetFirst(&ListHead, LISTELEM, Node) == NULL); + RTTEST_CHECK(hTest, RTListNodeGetLast(&ListHead, LISTELEM, Node) == NULL); + + /* Create the list */ + for (unsigned i = 0; i< cElements; i++) + { + PLISTELEM pNode = (PLISTELEM)RTMemAlloc(sizeof(LISTELEM)); + + pNode->idx = i; + pNode->Node.pPrev = NULL; + pNode->Node.pNext = NULL; + RTListAppend(&ListHead, &pNode->Node); + } + + tstRTListOrder(hTest, &ListHead, cElements, 0, cElements-1, 1); + + /* Remove elements now */ + if (cElements > 1) + { + /* Remove every second */ + RTTestISub("Remove every second node"); + + PLISTELEM pNode = RTListNodeGetFirst(&ListHead, LISTELEM, Node); + for (unsigned i = 0; i < cElements; i++) + { + PLISTELEM pNext = RTListNodeGetNext(&pNode->Node, LISTELEM, Node); + + if (!(pNode->idx % 2)) + { + RTListNodeRemove(&pNode->Node); + RTMemFree(pNode); + } + + pNode = pNext; + } + + bool fElementsEven = (cElements % 2) == 0; + unsigned idxEnd = fElementsEven ? cElements - 1 : cElements - 2; + + cElements /= 2; + tstRTListOrder(hTest, &ListHead, cElements, 1, idxEnd, 2); + } + + /* Remove the rest now. */ + RTTestISub("Remove all nodes"); + PLISTELEM pNode = RTListNodeGetFirst(&ListHead, LISTELEM, Node); + for (unsigned i = 0; i < cElements; i++) + { + PLISTELEM pNext = RTListNodeGetNext(&pNode->Node, LISTELEM, Node); + + RTListNodeRemove(&pNode->Node); + RTMemFree(pNode); + pNode = pNext; + } + + /* List should be empty again */ + RTTEST_CHECK(hTest, RTListIsEmpty(&ListHead) == true); + RTTEST_CHECK(hTest, RTListNodeGetFirst(&ListHead, LISTELEM, Node) == NULL); + RTTEST_CHECK(hTest, RTListNodeGetLast(&ListHead, LISTELEM, Node) == NULL); +} + +int main() +{ + RTTEST hTest; + int rc = RTTestInitAndCreate("tstRTList", &hTest); + if (rc) + return rc; + RTTestBanner(hTest); + + tstRTListCreate(hTest, 1); + tstRTListCreate(hTest, 2); + tstRTListCreate(hTest, 3); + tstRTListCreate(hTest, 99); + tstRTListCreate(hTest, 100); + tstRTListCreate(hTest, 101); + + /* + * Summary. + */ + return RTTestSummaryAndDestroy(hTest); +} +