/** * @file doublelinkedlist.h * @brief Provides a standard doubly linked list for fun and profit. * * $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_DOUBLELINKEDLIST_H #define LL_DOUBLELINKEDLIST_H #include "llerror.h" #include "llrand.h" // node that actually contains the data template <class DATA_TYPE> class LLDoubleLinkedNode { public: DATA_TYPE *mDatap; LLDoubleLinkedNode *mNextp; LLDoubleLinkedNode *mPrevp; public: // assign the mDatap pointer LLDoubleLinkedNode(DATA_TYPE *data); // destructor does not, by default, destroy associated data // however, the mDatap must be NULL to ensure that we aren't causing memory leaks ~LLDoubleLinkedNode(); // delete associated data and NULL out pointer void deleteData(); // remove associated data and NULL out pointer void removeData(); }; const U32 LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH = 4; template <class DATA_TYPE> class LLDoubleLinkedList { private: LLDoubleLinkedNode<DATA_TYPE> mHead; // head node LLDoubleLinkedNode<DATA_TYPE> mTail; // tail node LLDoubleLinkedNode<DATA_TYPE> *mQueuep; // The node in the batter's box LLDoubleLinkedNode<DATA_TYPE> *mCurrentp; // The node we're talking about // The state stack allows nested exploration of the LLDoubleLinkedList // but should be used with great care LLDoubleLinkedNode<DATA_TYPE> *mQueuepStack[LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH]; LLDoubleLinkedNode<DATA_TYPE> *mCurrentpStack[LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH]; U32 mStateStackDepth; U32 mCount; // mInsertBefore is a pointer to a user-set function that returns // TRUE if "first" should be located before "second" // NOTE: mInsertBefore() should never return TRUE when ("first" == "second") // or never-ending loops can occur BOOL (*mInsertBefore)(DATA_TYPE *first, DATA_TYPE *second); public: LLDoubleLinkedList(); // destructor destroys list and nodes, but not data in nodes ~LLDoubleLinkedList(); // put data into a node and stick it at the front of the list // set mCurrentp to mQueuep void addData(DATA_TYPE *data); // put data into a node and stick it at the end of the list // set mCurrentp to mQueuep void addDataAtEnd(DATA_TYPE *data); S32 getLength() const; // search the list starting at mHead.mNextp and remove the link with mDatap == data // set mCurrentp to mQueuep // return TRUE if found, FALSE if not found BOOL removeData(const DATA_TYPE *data); // search the list starting at mHead.mNextp and delete the link with mDatap == data // set mCurrentp to mQueuep // return TRUE if found, FALSE if not found BOOL deleteData(DATA_TYPE *data); // remove all nodes from the list and delete the associated data void deleteAllData(); // remove all nodes from the list but do not delete data void removeAllNodes(); BOOL isEmpty(); // check to see if data is in list // set mCurrentp and mQueuep to the target of search if found, otherwise set mCurrentp to mQueuep // return TRUE if found, FALSE if not found BOOL checkData(const DATA_TYPE *data); // NOTE: This next two funtions are only included here // for those too familiar with the LLLinkedList template class. // They are depreciated. resetList() is unecessary while // getCurrentData() is identical to getNextData() and has // a misleading name. // // The recommended way to loop through a list is as follows: // // datap = list.getFirstData(); // while (datap) // { // /* do stuff */ // datap = list.getNextData(); // } // place mQueuep on mHead node void resetList(); // return the data currently pointed to, // set mCurrentp to that node and bump mQueuep down the list // NOTE: this function is identical to getNextData() DATA_TYPE *getCurrentData(); // reset the list and return the data currently pointed to, // set mCurrentp to that node and bump mQueuep down the list DATA_TYPE *getFirstData(); // reset the list and return the data at position n, set mCurentp // to that node and bump mQueuep down the list // Note: n=0 will behave like getFirstData() DATA_TYPE *getNthData(U32 n); // reset the list and return the last data in it, // set mCurrentp to that node and bump mQueuep up the list DATA_TYPE *getLastData(); // return data in mQueuep, // set mCurrentp mQueuep and bump mQueuep down the list DATA_TYPE *getNextData(); // return the data in mQueuep, // set mCurrentp to mQueuep and bump mQueuep up the list DATA_TYPE *getPreviousData(); // remove the Node at mCurrentp // set mCurrentp to mQueuep void removeCurrentData(); // delete the Node at mCurrentp // set mCurrentp to mQueuep void deleteCurrentData(); // remove the Node at mCurrentp and insert it into newlist // set mCurrentp to mQueuep void moveCurrentData(LLDoubleLinkedList<DATA_TYPE> *newlist); // insert the node in front of mCurrentp // set mCurrentp to mQueuep void insertNode(LLDoubleLinkedNode<DATA_TYPE> *node); // insert the data in front of mCurrentp // set mCurrentp to mQueuep void insertData(DATA_TYPE *data); // if mCurrentp has a previous node then : // * swaps mCurrentp with its previous // * set mCurrentp to mQueuep // (convenient for forward bubble-sort) // otherwise does nothing void swapCurrentWithPrevious(); // if mCurrentp has a next node then : // * swaps mCurrentp with its next // * set mCurrentp to mQueuep // (convenient for backwards bubble-sort) // otherwise does nothing void swapCurrentWithNext(); // move mCurrentp to the front of the list // set mCurrentp to mQueuep void moveCurrentToFront(); // move mCurrentp to the end of the list // set mCurrentp to mQueuep void moveCurrentToEnd(); // set mInsertBefore void setInsertBefore(BOOL (*insert_before)(DATA_TYPE *first, DATA_TYPE *second)); // add data in front of first node for which mInsertBefore(datap, node->mDatap) returns TRUE // set mCurrentp to mQueuep BOOL addDataSorted(DATA_TYPE *datap); // sort the list using bubble-sort // Yes, this is a different name than the same function in LLLinkedList. // When it comes time for a name consolidation hopefully this one will win. BOOL bubbleSort(); // does a single bubble sort pass on the list BOOL lazyBubbleSort(); // returns TRUE if state successfully pushed (state stack not full) BOOL pushState(); // returns TRUE if state successfully popped (state stack not empty) BOOL popState(); // empties the state stack void clearStateStack(); // randomly move the the links in the list for debug or (Discordian) purposes // sets mCurrentp and mQueuep to top of list void scramble(); private: // add node to beginning of list // set mCurrentp to mQueuep void addNode(LLDoubleLinkedNode<DATA_TYPE> *node); // add node to end of list // set mCurrentp to mQueuep void addNodeAtEnd(LLDoubleLinkedNode<DATA_TYPE> *node); }; //#endif //////////////////////////////////////////////////////////////////////////////////////////// // doublelinkedlist.cpp // LLDoubleLinkedList template class implementation file. // Provides a standard doubly linked list for fun and profit. // // Copyright 2001, Linden Research, Inc. //#include "llerror.h" //#include "doublelinkedlist.h" ////////////////////////////////////////////////////////////////////////////////////////// // LLDoubleLinkedNode ////////////////////////////////////////////////////////////////////////////////////////// // assign the mDatap pointer template <class DATA_TYPE> LLDoubleLinkedNode<DATA_TYPE>::LLDoubleLinkedNode(DATA_TYPE *data) : mDatap(data), mNextp(NULL), mPrevp(NULL) { } // destructor does not, by default, destroy associated data // however, the mDatap must be NULL to ensure that we aren't causing memory leaks template <class DATA_TYPE> LLDoubleLinkedNode<DATA_TYPE>::~LLDoubleLinkedNode() { if (mDatap) { llerror("Attempting to call LLDoubleLinkedNode destructor with a non-null mDatap!", 1); } } // delete associated data and NULL out pointer template <class DATA_TYPE> void LLDoubleLinkedNode<DATA_TYPE>::deleteData() { delete mDatap; mDatap = NULL; } template <class DATA_TYPE> void LLDoubleLinkedNode<DATA_TYPE>::removeData() { mDatap = NULL; } ////////////////////////////////////////////////////////////////////////////////////// // LLDoubleLinkedList ////////////////////////////////////////////////////////////////////////////////////// // <------- up ------- // // mCurrentp // mQueuep | // | | // | | // .------. .------. .------. .------. // | |---->| |---->| |----->| |-----> NULL // NULL <-----| |<----| |<----| |<-----| | // _'------' '------' '------' '------:_ // .------. /| | | |\ .------. // NULL <-----|mHead |/ | mQueuep \|mTail |-----> NULL // | | mCurrentp | | // '------' '------' // -------- down ---------> template <class DATA_TYPE> LLDoubleLinkedList<DATA_TYPE>::LLDoubleLinkedList() : mHead(NULL), mTail(NULL), mQueuep(NULL) { mCurrentp = mHead.mNextp; mQueuep = mHead.mNextp; mStateStackDepth = 0; mCount = 0; mInsertBefore = NULL; } // destructor destroys list and nodes, but not data in nodes template <class DATA_TYPE> LLDoubleLinkedList<DATA_TYPE>::~LLDoubleLinkedList() { removeAllNodes(); } // put data into a node and stick it at the front of the list // doesn't change mCurrentp nor mQueuep template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::addData(DATA_TYPE *data) { // don't allow NULL to be passed to addData if (!data) { llerror("NULL pointer passed to LLDoubleLinkedList::addData()", 0); } // make the new node LLDoubleLinkedNode<DATA_TYPE> *temp = new LLDoubleLinkedNode<DATA_TYPE> (data); // add the node to the front of the list temp->mPrevp = NULL; temp->mNextp = mHead.mNextp; mHead.mNextp = temp; // if there's something in the list, fix its back pointer if (temp->mNextp) { temp->mNextp->mPrevp = temp; } // otherwise, fix the tail of the list else { mTail.mPrevp = temp; } mCount++; } // put data into a node and stick it at the end of the list template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::addDataAtEnd(DATA_TYPE *data) { // don't allow NULL to be passed to addData if (!data) { llerror("NULL pointer passed to LLDoubleLinkedList::addData()", 0); } // make the new node LLDoubleLinkedNode<DATA_TYPE> *nodep = new LLDoubleLinkedNode<DATA_TYPE>(data); addNodeAtEnd(nodep); mCount++; } // search the list starting at mHead.mNextp and remove the link with mDatap == data // set mCurrentp to mQueuep, or NULL if mQueuep points to node with mDatap == data // return TRUE if found, FALSE if not found template <class DATA_TYPE> BOOL LLDoubleLinkedList<DATA_TYPE>::removeData(const DATA_TYPE *data) { BOOL b_found = FALSE; // don't allow NULL to be passed to addData if (!data) { llerror("NULL pointer passed to LLDoubleLinkedList::removeData()", 0); } mCurrentp = mHead.mNextp; while (mCurrentp) { if (mCurrentp->mDatap == data) { b_found = TRUE; // if there is a next one, fix it if (mCurrentp->mNextp) { mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; } else // we are at end of list { mTail.mPrevp = mCurrentp->mPrevp; } // if there is a previous one, fix it if (mCurrentp->mPrevp) { mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; } else // we are at beginning of list { mHead.mNextp = mCurrentp->mNextp; } // remove the node mCurrentp->removeData(); delete mCurrentp; mCount--; break; } mCurrentp = mCurrentp->mNextp; } // reset the list back to where it was if (mCurrentp == mQueuep) { mCurrentp = mQueuep = NULL; } else { mCurrentp = mQueuep; } return b_found; } // search the list starting at mHead.mNextp and delete the link with mDatap == data // set mCurrentp to mQueuep, or NULL if mQueuep points to node with mDatap == data // return TRUE if found, FALSE if not found template <class DATA_TYPE> BOOL LLDoubleLinkedList<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 LLDoubleLinkedList::deleteData()", 0); } mCurrentp = mHead.mNextp; while (mCurrentp) { if (mCurrentp->mDatap == data) { b_found = TRUE; // if there is a next one, fix it if (mCurrentp->mNextp) { mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; } else // we are at end of list { mTail.mPrevp = mCurrentp->mPrevp; } // if there is a previous one, fix it if (mCurrentp->mPrevp) { mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; } else // we are at beginning of list { mHead.mNextp = mCurrentp->mNextp; } // remove the node mCurrentp->deleteData(); delete mCurrentp; mCount--; break; } mCurrentp = mCurrentp->mNextp; } // reset the list back to where it was if (mCurrentp == mQueuep) { mCurrentp = mQueuep = NULL; } else { mCurrentp = mQueuep; } return b_found; } // remove all nodes from the list and delete the associated data template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::deleteAllData() { mCurrentp = mHead.mNextp; while (mCurrentp) { mQueuep = mCurrentp->mNextp; mCurrentp->deleteData(); delete mCurrentp; mCurrentp = mQueuep; } // reset mHead and mQueuep mHead.mNextp = NULL; mTail.mPrevp = NULL; mCurrentp = mHead.mNextp; mQueuep = mHead.mNextp; mStateStackDepth = 0; mCount = 0; } // remove all nodes from the list but do not delete associated data template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::removeAllNodes() { mCurrentp = mHead.mNextp; while (mCurrentp) { mQueuep = mCurrentp->mNextp; mCurrentp->removeData(); delete mCurrentp; mCurrentp = mQueuep; } // reset mHead and mCurrentp mHead.mNextp = NULL; mTail.mPrevp = NULL; mCurrentp = mHead.mNextp; mQueuep = mHead.mNextp; mStateStackDepth = 0; mCount = 0; } template <class DATA_TYPE> S32 LLDoubleLinkedList<DATA_TYPE>::getLength() const { // U32 length = 0; // for (LLDoubleLinkedNode<DATA_TYPE>* temp = mHead.mNextp; temp != NULL; temp = temp->mNextp) // { // length++; // } return mCount; } // check to see if data is in list // set mCurrentp and mQueuep to the target of search if found, otherwise set mCurrentp to mQueuep // return TRUE if found, FALSE if not found template <class DATA_TYPE> BOOL LLDoubleLinkedList<DATA_TYPE>::checkData(const DATA_TYPE *data) { mCurrentp = mHead.mNextp; while (mCurrentp) { if (mCurrentp->mDatap == data) { mQueuep = mCurrentp; return TRUE; } mCurrentp = mCurrentp->mNextp; } mCurrentp = mQueuep; return FALSE; } // NOTE: This next two funtions are only included here // for those too familiar with the LLLinkedList template class. // They are depreciated. resetList() is unecessary while // getCurrentData() is identical to getNextData() and has // a misleading name. // // The recommended way to loop through a list is as follows: // // datap = list.getFirstData(); // while (datap) // { // /* do stuff */ // datap = list.getNextData(); // } // place mCurrentp and mQueuep on first node template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::resetList() { mCurrentp = mHead.mNextp; mQueuep = mHead.mNextp; mStateStackDepth = 0; } // return the data currently pointed to, // set mCurrentp to that node and bump mQueuep down the list template <class DATA_TYPE> DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getCurrentData() { if (mQueuep) { mCurrentp = mQueuep; mQueuep = mQueuep->mNextp; return mCurrentp->mDatap; } else { return NULL; } } // reset the list and return the data currently pointed to, // set mCurrentp to that node and bump mQueuep down the list template <class DATA_TYPE> DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getFirstData() { mQueuep = mHead.mNextp; mCurrentp = mQueuep; if (mQueuep) { mQueuep = mQueuep->mNextp; return mCurrentp->mDatap; } else { return NULL; } } // reset the list and return the data at position n, set mCurentp // to that node and bump mQueuep down the list // Note: n=0 will behave like getFirstData() template <class DATA_TYPE> DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getNthData(U32 n) { mCurrentp = mHead.mNextp; if (mCurrentp) { for (U32 i=0; i<n; i++) { mCurrentp = mCurrentp->mNextp; if (!mCurrentp) { break; } } } if (mCurrentp) { // bump mQueuep down the list mQueuep = mCurrentp->mNextp; return mCurrentp->mDatap; } else { mQueuep = NULL; return NULL; } } // reset the list and return the last data in it, // set mCurrentp to that node and bump mQueuep up the list template <class DATA_TYPE> DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getLastData() { mQueuep = mTail.mPrevp; mCurrentp = mQueuep; if (mQueuep) { mQueuep = mQueuep->mPrevp; return mCurrentp->mDatap; } else { return NULL; } } // return the data in mQueuep, // set mCurrentp to mQueuep and bump mQueuep down the list template <class DATA_TYPE> DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getNextData() { if (mQueuep) { mCurrentp = mQueuep; mQueuep = mQueuep->mNextp; return mCurrentp->mDatap; } else { return NULL; } } // return the data in mQueuep, // set mCurrentp to mQueuep and bump mQueuep up the list template <class DATA_TYPE> DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getPreviousData() { if (mQueuep) { mCurrentp = mQueuep; mQueuep = mQueuep->mPrevp; return mCurrentp->mDatap; } else { return NULL; } } // remove the Node at mCurrentp // set mCurrentp to mQueuep, or NULL if (mCurrentp == mQueuep) template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::removeCurrentData() { if (mCurrentp) { // if there is a next one, fix it if (mCurrentp->mNextp) { mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; } else // otherwise we are at end of list { mTail.mPrevp = mCurrentp->mPrevp; } // if there is a previous one, fix it if (mCurrentp->mPrevp) { mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; } else // otherwise we are at beginning of list { mHead.mNextp = mCurrentp->mNextp; } // remove the node mCurrentp->removeData(); delete mCurrentp; mCount--; // check for redundant pointing if (mCurrentp == mQueuep) { mCurrentp = mQueuep = NULL; } else { mCurrentp = mQueuep; } } } // delete the Node at mCurrentp // set mCurrentp to mQueuep, or NULL if (mCurrentp == mQueuep) template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::deleteCurrentData() { if (mCurrentp) { // remove the node // if there is a next one, fix it if (mCurrentp->mNextp) { mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; } else // otherwise we are at end of list { mTail.mPrevp = mCurrentp->mPrevp; } // if there is a previous one, fix it if (mCurrentp->mPrevp) { mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; } else // otherwise we are at beginning of list { mHead.mNextp = mCurrentp->mNextp; } // remove the LLDoubleLinkedNode mCurrentp->deleteData(); delete mCurrentp; mCount--; // check for redundant pointing if (mCurrentp == mQueuep) { mCurrentp = mQueuep = NULL; } else { mCurrentp = mQueuep; } } } // remove the Node at mCurrentp and insert it into newlist // set mCurrentp to mQueuep, or NULL if (mCurrentp == mQueuep) template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::moveCurrentData(LLDoubleLinkedList<DATA_TYPE> *newlist) { if (mCurrentp) { // remove the node // if there is a next one, fix it if (mCurrentp->mNextp) { mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; } else // otherwise we are at end of list { mTail.mPrevp = mCurrentp->mPrevp; } // if there is a previous one, fix it if (mCurrentp->mPrevp) { mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; } else // otherwise we are at beginning of list { mHead.mNextp = mCurrentp->mNextp; } // move the node to the new list newlist->addNode(mCurrentp); // check for redundant pointing if (mCurrentp == mQueuep) { mCurrentp = mQueuep = NULL; } else { mCurrentp = mQueuep; } } } // Inserts the node previous to mCurrentp // set mCurrentp to mQueuep template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::insertNode(LLDoubleLinkedNode<DATA_TYPE> *nodep) { // don't allow pointer to NULL to be passed if (!nodep) { llerror("NULL pointer passed to LLDoubleLinkedList::insertNode()", 0); } if (!nodep->mDatap) { llerror("NULL data pointer passed to LLDoubleLinkedList::insertNode()", 0); } if (mCurrentp) { if (mCurrentp->mPrevp) { nodep->mPrevp = mCurrentp->mPrevp; nodep->mNextp = mCurrentp; mCurrentp->mPrevp->mNextp = nodep; mCurrentp->mPrevp = nodep; } else // at beginning of list { nodep->mPrevp = NULL; nodep->mNextp = mCurrentp; mHead.mNextp = nodep; mCurrentp->mPrevp = nodep; } mCurrentp = mQueuep; } else // add to front of list { addNode(nodep); } } // insert the data in front of mCurrentp // set mCurrentp to mQueuep template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::insertData(DATA_TYPE *data) { if (!data) { llerror("NULL data pointer passed to LLDoubleLinkedList::insertNode()", 0); } LLDoubleLinkedNode<DATA_TYPE> *node = new LLDoubleLinkedNode<DATA_TYPE>(data); insertNode(node); mCount++; } // if mCurrentp has a previous node then : // * swaps mCurrentp with its previous // * set mCurrentp to mQueuep // otherwise does nothing template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::swapCurrentWithPrevious() { if (mCurrentp) { if (mCurrentp->mPrevp) { // Pull mCurrentp out of list mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; if (mCurrentp->mNextp) { mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; } else // mCurrentp was at end of list { mTail.mPrevp = mCurrentp->mPrevp; } // Fix mCurrentp's pointers mCurrentp->mNextp = mCurrentp->mPrevp; mCurrentp->mPrevp = mCurrentp->mNextp->mPrevp; mCurrentp->mNextp->mPrevp = mCurrentp; if (mCurrentp->mPrevp) { // Fix the backward pointer of mCurrentp's new previous mCurrentp->mPrevp->mNextp = mCurrentp; } else // mCurrentp is now at beginning of list { mHead.mNextp = mCurrentp; } // Set the list back to the way it was mCurrentp = mQueuep; } } } // if mCurrentp has a next node then : // * swaps mCurrentp with its next // * set mCurrentp to mQueuep // otherwise does nothing template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::swapCurrentWithNext() { if (mCurrentp) { if (mCurrentp->mNextp) { // Pull mCurrentp out of list mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; if (mCurrentp->mPrevp) { mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; } else // mCurrentp was at beginning of list { mHead.mNextp = mCurrentp->mNextp; } // Fix mCurrentp's pointers mCurrentp->mPrevp = mCurrentp->mNextp; mCurrentp->mNextp = mCurrentp->mPrevp->mNextp; mCurrentp->mPrevp->mNextp = mCurrentp; if (mCurrentp->mNextp) { // Fix the back pointer of mCurrentp's new next mCurrentp->mNextp->mPrevp = mCurrentp; } else // mCurrentp is now at end of list { mTail.mPrevp = mCurrentp; } // Set the list back to the way it was mCurrentp = mQueuep; } } } // move mCurrentp to the front of the list // set mCurrentp to mQueuep template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::moveCurrentToFront() { if (mCurrentp) { // if there is a previous one, fix it if (mCurrentp->mPrevp) { mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; } else // otherwise we are at beginning of list { // check for redundant pointing if (mCurrentp == mQueuep) { mCurrentp = mQueuep = NULL; } else { mCurrentp = mQueuep; } return; } // if there is a next one, fix it if (mCurrentp->mNextp) { mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; } else // otherwise we are at end of list { mTail.mPrevp = mCurrentp->mPrevp; } // add mCurrentp to beginning of list mCurrentp->mNextp = mHead.mNextp; mHead.mNextp->mPrevp = mCurrentp; // mHead.mNextp MUST be valid, // or the list had only one node // and we would have returned already mCurrentp->mPrevp = NULL; mHead.mNextp = mCurrentp; // check for redundant pointing if (mCurrentp == mQueuep) { mCurrentp = mQueuep = NULL; } else { mCurrentp = mQueuep; } } } // move mCurrentp to the end of the list // set mCurrentp to mQueuep template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::moveCurrentToEnd() { if (mCurrentp) { // if there is a next one, fix it if (mCurrentp->mNextp) { mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; } else // otherwise we are at end of list and we're done { // check for redundant pointing if (mCurrentp == mQueuep) { mCurrentp = mQueuep = NULL; } else { mCurrentp = mQueuep; } return; } // if there is a previous one, fix it if (mCurrentp->mPrevp) { mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; } else // otherwise we are at beginning of list { mHead.mNextp = mCurrentp->mNextp; } // add mCurrentp to end of list mCurrentp->mPrevp = mTail.mPrevp; mTail.mPrevp->mNextp = mCurrentp; // mTail.mPrevp MUST be valid, // or the list had only one node // and we would have returned already mCurrentp->mNextp = NULL; mTail.mPrevp = mCurrentp; // check for redundant pointing if (mCurrentp == mQueuep) { mCurrentp = mQueuep = NULL; } else { mCurrentp = mQueuep; } } } template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::setInsertBefore(BOOL (*insert_before)(DATA_TYPE *first, DATA_TYPE *second) ) { mInsertBefore = insert_before; } // add data in front of the first node for which mInsertBefore(datap, node->mDatap) returns TRUE // set mCurrentp to mQueuep template <class DATA_TYPE> BOOL LLDoubleLinkedList<DATA_TYPE>::addDataSorted(DATA_TYPE *datap) { // don't allow NULL to be passed to addData() if (!datap) { llerror("NULL pointer passed to LLDoubleLinkedList::addDataSorted()", 0); } // has mInsertBefore not been set? if (!mInsertBefore) { addData(datap); return FALSE; } // is the list empty? if (!mHead.mNextp) { addData(datap); return TRUE; } // Note: this step has been added so that the behavior of LLDoubleLinkedList // is as rigorous as the LLLinkedList class about adding duplicate nodes. // Duplicate nodes can cause a problem when sorting if mInsertBefore(foo, foo) // returns TRUE. However, if mInsertBefore(foo, foo) returns FALSE, then there // shouldn't be any reason to exclude duplicate nodes (as we do here). if (checkData(datap)) { return FALSE; } mCurrentp = mHead.mNextp; while (mCurrentp) { // check to see if datap is already in the list if (datap == mCurrentp->mDatap) { return FALSE; } else if (mInsertBefore(datap, mCurrentp->mDatap)) { insertData(datap); return TRUE; } mCurrentp = mCurrentp->mNextp; } addDataAtEnd(datap); return TRUE; } // bubble-sort until sorted and return TRUE if anything was sorted // leaves mQueuep pointing at last node that was swapped with its mNextp // // NOTE: if you find this function looping for really long times, then you // probably need to check your implementation of mInsertBefore(a,b) and make // sure it does not return TRUE when (a == b)! template <class DATA_TYPE> BOOL LLDoubleLinkedList<DATA_TYPE>::bubbleSort() { BOOL b_swapped = FALSE; U32 count = 0; while (lazyBubbleSort()) { b_swapped = TRUE; if (count++ > 0x7FFFFFFF) { llwarning("LLDoubleLinkedList::bubbleSort() : too many passes...", 1); llwarning(" make sure the mInsertBefore(a, b) does not return TRUE for a == b", 1); break; } } return b_swapped; } // do a single bubble-sort pass and return TRUE if anything was sorted // leaves mQueuep pointing at last node that was swapped with its mNextp template <class DATA_TYPE> BOOL LLDoubleLinkedList<DATA_TYPE>::lazyBubbleSort() { // has mInsertBefore been set? if (!mInsertBefore) { return FALSE; } // is list empty? mCurrentp = mHead.mNextp; if (!mCurrentp) { return FALSE; } BOOL b_swapped = FALSE; // the sort will exit after 0x7FFFFFFF nodes or the end of the list, whichever is first S32 length = 0x7FFFFFFF; S32 count = 0; while (mCurrentp && mCurrentp->mNextp && count<length) { if (mInsertBefore(mCurrentp->mNextp->mDatap, mCurrentp->mDatap)) { b_swapped = TRUE; mQueuep = mCurrentp; swapCurrentWithNext(); // sets mCurrentp to mQueuep } count++; mCurrentp = mCurrentp->mNextp; } return b_swapped; } template <class DATA_TYPE> BOOL LLDoubleLinkedList<DATA_TYPE>::pushState() { if (mStateStackDepth < LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH) { *(mQueuepStack + mStateStackDepth) = mQueuep; *(mCurrentpStack + mStateStackDepth) = mCurrentp; mStateStackDepth++; return TRUE; } return FALSE; } template <class DATA_TYPE> BOOL LLDoubleLinkedList<DATA_TYPE>::popState() { if (mStateStackDepth > 0) { mStateStackDepth--; mQueuep = *(mQueuepStack + mStateStackDepth); mCurrentp = *(mCurrentpStack + mStateStackDepth); return TRUE; } return FALSE; } template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::clearStateStack() { mStateStackDepth = 0; } ////////////////////////////////////////////////////////////////////////////////////////// // private members ////////////////////////////////////////////////////////////////////////////////////////// // add node to beginning of list // set mCurrentp to mQueuep template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::addNode(LLDoubleLinkedNode<DATA_TYPE> *nodep) { // add the node to the front of the list nodep->mPrevp = NULL; nodep->mNextp = mHead.mNextp; mHead.mNextp = nodep; // if there's something in the list, fix its back pointer if (nodep->mNextp) { nodep->mNextp->mPrevp = nodep; } else // otherwise fix the tail node { mTail.mPrevp = nodep; } mCurrentp = mQueuep; } // add node to end of list // set mCurrentp to mQueuep template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::addNodeAtEnd(LLDoubleLinkedNode<DATA_TYPE> *node) { // add the node to the end of the list node->mNextp = NULL; node->mPrevp = mTail.mPrevp; mTail.mPrevp = node; // if there's something in the list, fix its back pointer if (node->mPrevp) { node->mPrevp->mNextp = node; } else // otherwise fix the head node { mHead.mNextp = node; } mCurrentp = mQueuep; } // randomly move nodes in the list for DEBUG (or Discordian) purposes // sets mCurrentp and mQueuep to top of list template <class DATA_TYPE> void LLDoubleLinkedList<DATA_TYPE>::scramble() { S32 random_number; DATA_TYPE *datap = getFirstData(); while(datap) { random_number = ll_rand(5); if (0 == random_number) { removeCurrentData(); addData(datap); } else if (1 == random_number) { removeCurrentData(); addDataAtEnd(datap); } else if (2 == random_number) { swapCurrentWithPrevious(); } else if (3 == random_number) { swapCurrentWithNext(); } datap = getNextData(); } mQueuep = mHead.mNextp; mCurrentp = mQueuep; } template <class DATA_TYPE> BOOL LLDoubleLinkedList<DATA_TYPE>::isEmpty() { return (mCount == 0); } #endif