diff options
Diffstat (limited to 'indra/llcommon/llskiplist.h')
| -rwxr-xr-x | indra/llcommon/llskiplist.h | 517 |
1 files changed, 0 insertions, 517 deletions
diff --git a/indra/llcommon/llskiplist.h b/indra/llcommon/llskiplist.h deleted file mode 100755 index ed132381f9..0000000000 --- a/indra/llcommon/llskiplist.h +++ /dev/null @@ -1,517 +0,0 @@ -/** - * @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 |