/** * @file llskiplist.h * @brief skip list implementation * * $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_LLSKIPLIST_H #define LL_LLSKIPLIST_H #include "llrand.h" #include "llrand.h" // NOTA BENE: Insert first needs to be < NOT <= // Binary depth must be >= 2 template <class DATA_TYPE, S32 BINARY_DEPTH = 10> class LLSkipList { public: typedef BOOL (*compare)(const DATA_TYPE& first, const DATA_TYPE& second); typedef compare insert_func; typedef compare equals_func; void init(); // basic constructor LLSkipList(); // basic constructor including sorter LLSkipList(insert_func insert_first, equals_func equals); ~LLSkipList(); inline void setInsertFirst(insert_func insert_first); inline void setEquals(equals_func equals); inline BOOL addData(const DATA_TYPE& data); inline BOOL checkData(const DATA_TYPE& data); // returns number of items in the list inline S32 getLength() const; // NOT a constant time operation, traverses entire list! inline BOOL moveData(const DATA_TYPE& data, LLSkipList *newlist); inline BOOL removeData(const DATA_TYPE& data); // remove all nodes from the list but do not delete data inline void removeAllNodes(); // 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(); // remove the Node at mCurentOperatingp // leave mCurrentp and mCurentOperatingp on the next entry inline void removeCurrentData(); // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp inline DATA_TYPE getFirstData(); class LLSkipNode { public: LLSkipNode() : mData(0) { S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mForward[i] = NULL; } } LLSkipNode(DATA_TYPE data) : mData(data) { S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mForward[i] = NULL; } } ~LLSkipNode() { } DATA_TYPE mData; LLSkipNode *mForward[BINARY_DEPTH]; private: // Disallow copying of LLSkipNodes by not implementing these methods. LLSkipNode(const LLSkipNode &); LLSkipNode &operator=(const LLSkipNode &); }; static BOOL defaultEquals(const DATA_TYPE& first, const DATA_TYPE& second) { return first == second; } private: LLSkipNode mHead; LLSkipNode *mUpdate[BINARY_DEPTH]; LLSkipNode *mCurrentp; LLSkipNode *mCurrentOperatingp; S32 mLevel; insert_func mInsertFirst; equals_func mEquals; private: // Disallow copying of LLSkipNodes by not implementing these methods. LLSkipList(const LLSkipList &); LLSkipList &operator=(const LLSkipList &); }; /////////////////////// // // Implementation // // Binary depth must be >= 2 template <class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::init() { S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mHead.mForward[i] = NULL; mUpdate[i] = NULL; } mLevel = 1; mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); } // basic constructor template <class DATA_TYPE, S32 BINARY_DEPTH> inline LLSkipList<DATA_TYPE, BINARY_DEPTH>::LLSkipList() : mInsertFirst(NULL), mEquals(defaultEquals) { init(); } // basic constructor including sorter template <class DATA_TYPE, S32 BINARY_DEPTH> inline LLSkipList<DATA_TYPE, BINARY_DEPTH>::LLSkipList(insert_func insert, equals_func equals) : mInsertFirst(insert), mEquals(equals) { init(); } template <class DATA_TYPE, S32 BINARY_DEPTH> inline LLSkipList<DATA_TYPE, BINARY_DEPTH>::~LLSkipList() { removeAllNodes(); } template <class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::setInsertFirst(insert_func insert_first) { mInsertFirst = insert_first; } template <class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::setEquals(equals_func equals) { mEquals = equals; } template <class DATA_TYPE, S32 BINARY_DEPTH> inline BOOL LLSkipList<DATA_TYPE, BINARY_DEPTH>::addData(const DATA_TYPE& data) { S32 level; LLSkipNode *current = &mHead; LLSkipNode *temp; // find the pointer one in front of the one we want if (mInsertFirst) { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(mInsertFirst(temp->mData, data))) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mData < data)) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } // we're now just in front of where we want to be . . . take one step forward current = *current->mForward; // now add the new node S32 newlevel; for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) { if (ll_frand() < 0.5f) break; } LLSkipNode *snode = new LLSkipNode(data); if (newlevel > mLevel) { mHead.mForward[mLevel] = NULL; mUpdate[mLevel] = &mHead; mLevel = newlevel; } for (level = 0; level < newlevel; level++) { snode->mForward[level] = mUpdate[level]->mForward[level]; mUpdate[level]->mForward[level] = snode; } return TRUE; } template <class DATA_TYPE, S32 BINARY_DEPTH> inline BOOL LLSkipList<DATA_TYPE, BINARY_DEPTH>::checkData(const DATA_TYPE& data) { S32 level; LLSkipNode *current = &mHead; LLSkipNode *temp; // find the pointer one in front of the one we want if (mInsertFirst) { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(mInsertFirst(temp->mData, data))) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mData < data)) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } // we're now just in front of where we want to be . . . take one step forward current = *current->mForward; if (current) { return mEquals(current->mData, data); } return FALSE; } // returns number of items in the list template <class DATA_TYPE, S32 BINARY_DEPTH> inline S32 LLSkipList<DATA_TYPE, BINARY_DEPTH>::getLength() const { U32 length = 0; for (LLSkipNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) { length++; } return length; } template <class DATA_TYPE, S32 BINARY_DEPTH> inline BOOL LLSkipList<DATA_TYPE, BINARY_DEPTH>::moveData(const DATA_TYPE& data, LLSkipList *newlist) { BOOL removed = removeData(data); BOOL added = newlist->addData(data); return removed && added; } template <class DATA_TYPE, S32 BINARY_DEPTH> inline BOOL LLSkipList<DATA_TYPE, BINARY_DEPTH>::removeData(const DATA_TYPE& data) { S32 level; LLSkipNode *current = &mHead; LLSkipNode *temp; // find the pointer one in front of the one we want if (mInsertFirst) { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(mInsertFirst(temp->mData, data))) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mData < data)) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } // we're now just in front of where we want to be . . . take one step forward current = *current->mForward; if (!current) { // empty list or beyond the end! return FALSE; } // is this the one we want? if (!mEquals(current->mData, data)) { // nope! return FALSE; } else { // do we need to fix current or currentop? if (current == mCurrentp) { mCurrentp = current->mForward[0]; } if (current == mCurrentOperatingp) { mCurrentOperatingp = current->mForward[0]; } // yes it is! change pointers as required for (level = 0; level < mLevel; level++) { if (mUpdate[level]->mForward[level] != current) { // cool, we've fixed all the pointers! break; } mUpdate[level]->mForward[level] = current->mForward[level]; } // clean up cuurent delete current; // clean up mHead while ( (mLevel > 1) &&(!mHead.mForward[mLevel - 1])) { mLevel--; } } return TRUE; } // remove all nodes from the list but do not delete data template <class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::removeAllNodes() { LLSkipNode *temp; // reset mCurrentp mCurrentp = *(mHead.mForward); while (mCurrentp) { temp = mCurrentp->mForward[0]; delete mCurrentp; mCurrentp = temp; } S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mHead.mForward[i] = NULL; mUpdate[i] = NULL; } mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); } // place mCurrentp on first node template <class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::resetList() { mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); } // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp template <class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE LLSkipList<DATA_TYPE, BINARY_DEPTH>::getCurrentData() { if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mData; } else { //return NULL; // causes compile warning return (DATA_TYPE)0; // equivalent, but no warning } } // same as getCurrentData() but a more intuitive name for the operation template <class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE LLSkipList<DATA_TYPE, BINARY_DEPTH>::getNextData() { if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mData; } else { //return NULL; // causes compile warning return (DATA_TYPE)0; // equivalent, but no warning } } // remove the Node at mCurentOperatingp // leave mCurrentp and mCurentOperatingp on the next entry template <class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::removeCurrentData() { if (mCurrentOperatingp) { removeData(mCurrentOperatingp->mData); } } // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp template <class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE LLSkipList<DATA_TYPE, BINARY_DEPTH>::getFirstData() { mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mData; } else { //return NULL; // causes compile warning return (DATA_TYPE)0; // equivalent, but no warning } } #endif