diff options
Diffstat (limited to 'indra/llcommon/linked_lists.h')
| -rwxr-xr-x | indra/llcommon/linked_lists.h | 937 |
1 files changed, 0 insertions, 937 deletions
diff --git a/indra/llcommon/linked_lists.h b/indra/llcommon/linked_lists.h deleted file mode 100755 index 6b25295b7b..0000000000 --- a/indra/llcommon/linked_lists.h +++ /dev/null @@ -1,937 +0,0 @@ -/** - * @file linked_lists.h - * @brief LLLinkedList class header amd implementation file. - * - * $LicenseInfo:firstyear=2001&license=viewerlgpl$ - * Second Life Viewer Source Code - * Copyright (C) 2010, Linden Research, Inc. - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; - * version 2.1 of the License only. - * - * This library 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 - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - * - * Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA - * $/LicenseInfo$ - */ - -#ifndef LL_LINKED_LISTS_H -#define LL_LINKED_LISTS_H - -/** - * Provides a standard doubly linked list for fun and profit - * Utilizes a neat trick off of Flipcode where the back pointer is a - * pointer to a pointer, allowing easier transfer of nodes between lists, &c - * And a template class, of course - */ - -#include "llerror.h" - - -template <class DATA_TYPE> class LLLinkedList -{ -public: - friend class LLLinkNode; - // External interface - - // basic constructor - LLLinkedList() : mHead(NULL), mCurrentp(NULL), mInsertBefore(NULL) - { - mCurrentp = mHead.mNextp; - mCurrentOperatingp = mHead.mNextp; - mCount = 0; - } - - // basic constructor - LLLinkedList(BOOL (*insert_before)(DATA_TYPE *data_new, DATA_TYPE *data_tested)) : mHead(NULL), mCurrentp(NULL), mInsertBefore(insert_before) - { - mCurrentp = mHead.mNextp; - mCurrentOperatingp = mHead.mNextp; - mCount = 0; - } - - // destructor destroys list and nodes, but not data in nodes - ~LLLinkedList() - { - removeAllNodes(); - } - - // set mInsertBefore - void setInsertBefore(BOOL (*insert_before)(DATA_TYPE *data_new, DATA_TYPE *data_tested)) - { - mInsertBefore = insert_before; - } - - // - // WARNING!!!!!!! - // addData and addDataSorted are NOT O(1) operations, but O(n) because they check - // for existence of the data in the linked list first. Why, I don't know - djs - // If you don't care about dupes, use addDataNoCheck - // - - // put data into a node and stick it at the front of the list - inline BOOL addData(DATA_TYPE *data); - - // put data into a node and sort into list by mInsertBefore() - // calls normal add if mInsertBefore isn't set - inline BOOL addDataSorted(DATA_TYPE *data); - - inline BOOL addDataNoCheck(DATA_TYPE *data); - - // bubbleSortList - // does an improved bubble sort of the list . . . works best with almost sorted data - // does nothing if mInsertBefore isn't set - // Nota Bene: Swaps are accomplished by swapping data pointers - inline void bubbleSortList(); - - // put data into a node and stick it at the end of the list - inline BOOL addDataAtEnd(DATA_TYPE *data); - - // returns number of items in the list - inline S32 getLength() const; - - inline BOOL isEmpty(); - - // search the list starting at mHead.mNextp and remove the link with mDatap == data - // leave mCurrentp and mCurrentOperatingp on the next entry - // return TRUE if found, FALSE if not found - inline BOOL removeData(DATA_TYPE *data); - - // search the list starting at mHead.mNextp and delete the link with mDatap == data - // leave mCurrentp and mCurrentOperatingp on the next entry - // return TRUE if found, FALSE if not found - inline BOOL deleteData(DATA_TYPE *data); - - // remove all nodes from the list and delete the associated data - inline void deleteAllData(); - - // remove all nodes from the list but do not delete data - inline void removeAllNodes(); - - // check to see if data is in list - // if TRUE then mCurrentp and mCurrentOperatingp point to data - inline BOOL checkData(DATA_TYPE *data); - - // place mCurrentp on first node - inline void resetList(); - - // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - inline DATA_TYPE *getCurrentData(); - - // same as getCurrentData() but a more intuitive name for the operation - inline DATA_TYPE *getNextData(); - - // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - inline DATA_TYPE *getFirstData(); - - // reset the list and return the data at position n, set mCurentOperatingp to that node and bump mCurrentp - // Note: n is zero-based - inline DATA_TYPE *getNthData( U32 n); - - // reset the list and return the last data in it, set mCurentOperatingp to that node and bump mCurrentp - inline DATA_TYPE *getLastData(); - - // remove the Node at mCurentOperatingp - // leave mCurrentp and mCurentOperatingp on the next entry - inline void removeCurrentData(); - - // remove the Node at mCurentOperatingp and add it to newlist - // leave mCurrentp and mCurentOperatingp on the next entry - void moveCurrentData(LLLinkedList *newlist, BOOL b_sort); - - BOOL moveData(DATA_TYPE *data, LLLinkedList *newlist, BOOL b_sort); - - // delete the Node at mCurentOperatingp - // leave mCurrentp anf mCurentOperatingp on the next entry - void deleteCurrentData(); - -private: - // node that actually contains the data - class LLLinkNode - { - public: - // assign the mDatap pointer - LLLinkNode(DATA_TYPE *data) : mDatap(data), mNextp(NULL), mPrevpp(NULL) - { - } - - // destructor does not, by default, destroy associated data - // however, the mDatap must be NULL to ensure that we aren't causing memory leaks - ~LLLinkNode() - { - if (mDatap) - { - llerror("Attempting to call LLLinkNode destructor with a non-null mDatap!", 1); - } - } - - // delete associated data and NULL out pointer - void deleteData() - { - delete mDatap; - mDatap = NULL; - } - - // NULL out pointer - void removeData() - { - mDatap = NULL; - } - - DATA_TYPE *mDatap; - LLLinkNode *mNextp; - LLLinkNode **mPrevpp; - }; - - // add a node at the front of the list - void addData(LLLinkNode *node) - { - // don't allow NULL to be passed to addData - if (!node) - { - llerror("NULL pointer passed to LLLinkedList::addData", 0); - } - - // add the node to the front of the list - node->mPrevpp = &mHead.mNextp; - node->mNextp = mHead.mNextp; - - // if there's something in the list, fix its back pointer - if (node->mNextp) - { - node->mNextp->mPrevpp = &node->mNextp; - } - - mHead.mNextp = node; - } - - LLLinkNode mHead; // fake head node. . . makes pointer operations faster and easier - LLLinkNode *mCurrentp; // mCurrentp is the Node that getCurrentData returns - LLLinkNode *mCurrentOperatingp; // this is the node that the various mumbleCurrentData functions act on - BOOL (*mInsertBefore)(DATA_TYPE *data_new, DATA_TYPE *data_tested); // user function set to allow sorted lists - U32 mCount; -}; - -template <class DATA_TYPE> -BOOL LLLinkedList<DATA_TYPE>::addData(DATA_TYPE *data) -{ - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLLinkedList::addData", 0); - } - - LLLinkNode *tcurr = mCurrentp; - LLLinkNode *tcurrop = mCurrentOperatingp; - - if ( checkData(data)) - { - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - return FALSE; - } - - // make the new node - LLLinkNode *temp = new LLLinkNode(data); - - // add the node to the front of the list - temp->mPrevpp = &mHead.mNextp; - temp->mNextp = mHead.mNextp; - - // if there's something in the list, fix its back pointer - if (temp->mNextp) - { - temp->mNextp->mPrevpp = &temp->mNextp; - } - - mHead.mNextp = temp; - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - mCount++; - return TRUE; -} - - -template <class DATA_TYPE> -BOOL LLLinkedList<DATA_TYPE>::addDataNoCheck(DATA_TYPE *data) -{ - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLLinkedList::addData", 0); - } - - LLLinkNode *tcurr = mCurrentp; - LLLinkNode *tcurrop = mCurrentOperatingp; - - // make the new node - LLLinkNode *temp = new LLLinkNode(data); - - // add the node to the front of the list - temp->mPrevpp = &mHead.mNextp; - temp->mNextp = mHead.mNextp; - - // if there's something in the list, fix its back pointer - if (temp->mNextp) - { - temp->mNextp->mPrevpp = &temp->mNextp; - } - - mHead.mNextp = temp; - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - mCount++; - return TRUE; -} - - -template <class DATA_TYPE> -BOOL LLLinkedList<DATA_TYPE>::addDataSorted(DATA_TYPE *data) -{ - LLLinkNode *tcurr = mCurrentp; - LLLinkNode *tcurrop = mCurrentOperatingp; - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLLinkedList::addDataSorted", 0); - } - - if (checkData(data)) - { - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - return FALSE; - } - - // mInsertBefore not set? - if (!mInsertBefore) - { - addData(data); - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - return FALSE; - } - - // empty list? - if (!mHead.mNextp) - { - addData(data); - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - return TRUE; - } - - // make the new node - LLLinkNode *temp = new LLLinkNode(data); - - // walk the list until mInsertBefore returns true - mCurrentp = mHead.mNextp; - while (mCurrentp->mNextp) - { - if (mInsertBefore(data, mCurrentp->mDatap)) - { - // insert before the current one - temp->mPrevpp = mCurrentp->mPrevpp; - temp->mNextp = mCurrentp; - *(temp->mPrevpp) = temp; - mCurrentp->mPrevpp = &temp->mNextp; - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - mCount++; - return TRUE; - } - else - { - mCurrentp = mCurrentp->mNextp; - } - } - - // on the last element, add before? - if (mInsertBefore(data, mCurrentp->mDatap)) - { - // insert before the current one - temp->mPrevpp = mCurrentp->mPrevpp; - temp->mNextp = mCurrentp; - *(temp->mPrevpp) = temp; - mCurrentp->mPrevpp = &temp->mNextp; - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - } - else // insert after - { - temp->mPrevpp = &mCurrentp->mNextp; - temp->mNextp = NULL; - mCurrentp->mNextp = temp; - - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - } - mCount++; - return TRUE; -} - -template <class DATA_TYPE> -void LLLinkedList<DATA_TYPE>::bubbleSortList() -{ - // mInsertBefore not set - if (!mInsertBefore) - { - return; - } - - LLLinkNode *tcurr = mCurrentp; - LLLinkNode *tcurrop = mCurrentOperatingp; - - BOOL b_swapped = FALSE; - DATA_TYPE *temp; - - // Nota Bene: This will break if more than 0x7FFFFFFF members in list! - S32 length = 0x7FFFFFFF; - S32 count = 0; - do - { - b_swapped = FALSE; - mCurrentp = mHead.mNextp; - count = 0; - while ( (count + 1 < length) - &&(mCurrentp)) - { - if (mCurrentp->mNextp) - { - if (!mInsertBefore(mCurrentp->mDatap, mCurrentp->mNextp->mDatap)) - { - // swap data pointers! - temp = mCurrentp->mDatap; - mCurrentp->mDatap = mCurrentp->mNextp->mDatap; - mCurrentp->mNextp->mDatap = temp; - b_swapped = TRUE; - } - } - else - { - break; - } - count++; - mCurrentp = mCurrentp->mNextp; - } - length = count; - } while (b_swapped); - - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; -} - - -template <class DATA_TYPE> -BOOL LLLinkedList<DATA_TYPE>::addDataAtEnd(DATA_TYPE *data) -{ - LLLinkNode *tcurr = mCurrentp; - LLLinkNode *tcurrop = mCurrentOperatingp; - - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLLinkedList::addData", 0); - } - - if (checkData(data)) - { - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - return FALSE; - } - - // make the new node - LLLinkNode *temp = new LLLinkNode(data); - - // add the node to the end of the list - - // if empty, add to the front and be done with it - if (!mHead.mNextp) - { - temp->mPrevpp = &mHead.mNextp; - temp->mNextp = NULL; - mHead.mNextp = temp; - } - else - { - // otherwise, walk to the end of the list - mCurrentp = mHead.mNextp; - while (mCurrentp->mNextp) - { - mCurrentp = mCurrentp->mNextp; - } - temp->mPrevpp = &mCurrentp->mNextp; - temp->mNextp = NULL; - mCurrentp->mNextp = temp; - } - - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - mCount++; - return TRUE; -} - - -// returns number of items in the list -template <class DATA_TYPE> -S32 LLLinkedList<DATA_TYPE>::getLength() const -{ -// S32 length = 0; -// for (LLLinkNode* temp = mHead.mNextp; temp != NULL; temp = temp->mNextp) -// { -// length++; -// } - return mCount; -} - - -template <class DATA_TYPE> -BOOL LLLinkedList<DATA_TYPE>::isEmpty() -{ - return (mCount == 0); -} - - -// search the list starting at mHead.mNextp and remove the link with mDatap == data -// leave mCurrentp and mCurrentOperatingp on the next entry -// return TRUE if found, FALSE if not found -template <class DATA_TYPE> -BOOL LLLinkedList<DATA_TYPE>::removeData(DATA_TYPE *data) -{ - BOOL b_found = FALSE; - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLLinkedList::removeData", 0); - } - - LLLinkNode *tcurr = mCurrentp; - LLLinkNode *tcurrop = mCurrentOperatingp; - - mCurrentp = mHead.mNextp; - mCurrentOperatingp = mHead.mNextp; - - while (mCurrentOperatingp) - { - if (mCurrentOperatingp->mDatap == data) - { - b_found = TRUE; - - // remove the node - - // if there is a next one, fix it - if (mCurrentOperatingp->mNextp) - { - mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp; - } - *(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp; - - // remove the LLLinkNode - - // if we were on the one we want to delete, bump the cached copies - if (mCurrentOperatingp == tcurrop) - { - tcurrop = tcurr = mCurrentOperatingp->mNextp; - } - else if (mCurrentOperatingp == tcurr) - { - tcurrop = tcurr = mCurrentOperatingp->mNextp; - } - - mCurrentp = mCurrentOperatingp->mNextp; - - mCurrentOperatingp->removeData(); - delete mCurrentOperatingp; - mCurrentOperatingp = mCurrentp; - mCount--; - break; - } - mCurrentOperatingp = mCurrentOperatingp->mNextp; - } - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - return b_found; -} - -// search the list starting at mHead.mNextp and delete the link with mDatap == data -// leave mCurrentp and mCurrentOperatingp on the next entry -// return TRUE if found, FALSE if not found -template <class DATA_TYPE> -BOOL LLLinkedList<DATA_TYPE>::deleteData(DATA_TYPE *data) -{ - BOOL b_found = FALSE; - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLLinkedList::removeData", 0); - } - - LLLinkNode *tcurr = mCurrentp; - LLLinkNode *tcurrop = mCurrentOperatingp; - - mCurrentp = mHead.mNextp; - mCurrentOperatingp = mHead.mNextp; - - while (mCurrentOperatingp) - { - if (mCurrentOperatingp->mDatap == data) - { - b_found = TRUE; - - // remove the node - // if there is a next one, fix it - if (mCurrentOperatingp->mNextp) - { - mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp; - } - *(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp; - - // delete the LLLinkNode - // if we were on the one we want to delete, bump the cached copies - if (mCurrentOperatingp == tcurrop) - { - tcurrop = tcurr = mCurrentOperatingp->mNextp; - } - - // and delete the associated data - llassert(mCurrentOperatingp); - mCurrentp = mCurrentOperatingp->mNextp; - mCurrentOperatingp->deleteData(); - delete mCurrentOperatingp; - mCurrentOperatingp = mCurrentp; - mCount--; - break; - } - mCurrentOperatingp = mCurrentOperatingp->mNextp; - } - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - return b_found; -} - - // remove all nodes from the list and delete the associated data -template <class DATA_TYPE> -void LLLinkedList<DATA_TYPE>::deleteAllData() -{ - LLLinkNode *temp; - // reset mCurrentp - mCurrentp = mHead.mNextp; - - while (mCurrentp) - { - temp = mCurrentp->mNextp; - mCurrentp->deleteData(); - delete mCurrentp; - mCurrentp = temp; - } - - // reset mHead and mCurrentp - mHead.mNextp = NULL; - mCurrentp = mHead.mNextp; - mCurrentOperatingp = mHead.mNextp; - mCount = 0; -} - -// remove all nodes from the list but do not delete data -template <class DATA_TYPE> -void LLLinkedList<DATA_TYPE>::removeAllNodes() -{ - LLLinkNode *temp; - // reset mCurrentp - mCurrentp = mHead.mNextp; - - while (mCurrentp) - { - temp = mCurrentp->mNextp; - mCurrentp->removeData(); - delete mCurrentp; - mCurrentp = temp; - } - - // reset mHead and mCurrentp - mHead.mNextp = NULL; - mCurrentp = mHead.mNextp; - mCurrentOperatingp = mHead.mNextp; - mCount = 0; -} - -// check to see if data is in list -// if TRUE then mCurrentp and mCurrentOperatingp point to data -template <class DATA_TYPE> -BOOL LLLinkedList<DATA_TYPE>::checkData(DATA_TYPE *data) -{ - // reset mCurrentp - mCurrentp = mHead.mNextp; - - while (mCurrentp) - { - if (mCurrentp->mDatap == data) - { - mCurrentOperatingp = mCurrentp; - return TRUE; - } - mCurrentp = mCurrentp->mNextp; - } - mCurrentOperatingp = mCurrentp; - return FALSE; -} - -// place mCurrentp on first node -template <class DATA_TYPE> -void LLLinkedList<DATA_TYPE>::resetList() -{ - mCurrentp = mHead.mNextp; - mCurrentOperatingp = mHead.mNextp; -} - -// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template <class DATA_TYPE> -DATA_TYPE *LLLinkedList<DATA_TYPE>::getCurrentData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mNextp; - return mCurrentOperatingp->mDatap; - } - else - { - return NULL; - } -} - -// same as getCurrentData() but a more intuitive name for the operation -template <class DATA_TYPE> -DATA_TYPE *LLLinkedList<DATA_TYPE>::getNextData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mNextp; - return mCurrentOperatingp->mDatap; - } - else - { - return NULL; - } -} - -// reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template <class DATA_TYPE> -DATA_TYPE *LLLinkedList<DATA_TYPE>::getFirstData() -{ - mCurrentp = mHead.mNextp; - mCurrentOperatingp = mHead.mNextp; - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mNextp; - return mCurrentOperatingp->mDatap; - } - else - { - return NULL; - } -} - -// Note: n is zero-based -template <class DATA_TYPE> -DATA_TYPE *LLLinkedList<DATA_TYPE>::getNthData( U32 n ) -{ - mCurrentOperatingp = mHead.mNextp; - - // if empty, return NULL - if (!mCurrentOperatingp) - { - return NULL; - } - - for( U32 i = 0; i < n; i++ ) - { - mCurrentOperatingp = mCurrentOperatingp->mNextp; - if( !mCurrentOperatingp ) - { - return NULL; - } - } - - mCurrentp = mCurrentOperatingp->mNextp; - return mCurrentOperatingp->mDatap; -} - - -// reset the list and return the last data in it, set mCurentOperatingp to that node and bump mCurrentp -template <class DATA_TYPE> -DATA_TYPE *LLLinkedList<DATA_TYPE>::getLastData() -{ - mCurrentOperatingp = mHead.mNextp; - - // if empty, return NULL - if (!mCurrentOperatingp) - return NULL; - - // walk until we're pointing at the last entry - while (mCurrentOperatingp->mNextp) - { - mCurrentOperatingp = mCurrentOperatingp->mNextp; - } - mCurrentp = mCurrentOperatingp->mNextp; - return mCurrentOperatingp->mDatap; -} - -// remove the Node at mCurentOperatingp -// leave mCurrentp and mCurentOperatingp on the next entry -// return TRUE if found, FALSE if not found -template <class DATA_TYPE> -void LLLinkedList<DATA_TYPE>::removeCurrentData() -{ - if (mCurrentOperatingp) - { - // remove the node - // if there is a next one, fix it - if (mCurrentOperatingp->mNextp) - { - mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp; - } - *(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp; - - // remove the LLLinkNode - mCurrentp = mCurrentOperatingp->mNextp; - - mCurrentOperatingp->removeData(); - delete mCurrentOperatingp; - mCount--; - mCurrentOperatingp = mCurrentp; - } -} - -// remove the Node at mCurentOperatingp and add it to newlist -// leave mCurrentp and mCurentOperatingp on the next entry -// return TRUE if found, FALSE if not found -template <class DATA_TYPE> -void LLLinkedList<DATA_TYPE>::moveCurrentData(LLLinkedList *newlist, BOOL b_sort) -{ - if (mCurrentOperatingp) - { - // remove the node - // if there is a next one, fix it - if (mCurrentOperatingp->mNextp) - { - mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp; - } - *(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp; - - // remove the LLLinkNode - mCurrentp = mCurrentOperatingp->mNextp; - // move the node to the new list - newlist->addData(mCurrentOperatingp); - if (b_sort) - bubbleSortList(); - mCurrentOperatingp = mCurrentp; - } -} - -template <class DATA_TYPE> -BOOL LLLinkedList<DATA_TYPE>::moveData(DATA_TYPE *data, LLLinkedList *newlist, BOOL b_sort) -{ - BOOL b_found = FALSE; - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLLinkedList::removeData", 0); - } - - LLLinkNode *tcurr = mCurrentp; - LLLinkNode *tcurrop = mCurrentOperatingp; - - mCurrentp = mHead.mNextp; - mCurrentOperatingp = mHead.mNextp; - - while (mCurrentOperatingp) - { - if (mCurrentOperatingp->mDatap == data) - { - b_found = TRUE; - - // remove the node - - // if there is a next one, fix it - if (mCurrentOperatingp->mNextp) - { - mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp; - } - *(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp; - - // if we were on the one we want to delete, bump the cached copies - if ( (mCurrentOperatingp == tcurrop) - ||(mCurrentOperatingp == tcurr)) - { - tcurrop = tcurr = mCurrentOperatingp->mNextp; - } - - // remove the LLLinkNode - mCurrentp = mCurrentOperatingp->mNextp; - // move the node to the new list - newlist->addData(mCurrentOperatingp); - if (b_sort) - newlist->bubbleSortList(); - mCurrentOperatingp = mCurrentp; - break; - } - mCurrentOperatingp = mCurrentOperatingp->mNextp; - } - // restore - mCurrentp = tcurr; - mCurrentOperatingp = tcurrop; - return b_found; -} - -// delete the Node at mCurentOperatingp -// leave mCurrentp anf mCurentOperatingp on the next entry -// return TRUE if found, FALSE if not found -template <class DATA_TYPE> -void LLLinkedList<DATA_TYPE>::deleteCurrentData() -{ - if (mCurrentOperatingp) - { - // remove the node - // if there is a next one, fix it - if (mCurrentOperatingp->mNextp) - { - mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp; - } - *(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp; - - // remove the LLLinkNode - mCurrentp = mCurrentOperatingp->mNextp; - - mCurrentOperatingp->deleteData(); - if (mCurrentOperatingp->mDatap) - llerror("This is impossible!", 0); - delete mCurrentOperatingp; - mCurrentOperatingp = mCurrentp; - mCount--; - } -} - -#endif |