/** * @file llptrskipmap.h * @brief Just like a LLSkipMap, but since it's pointers, you can call * deleteAllData * * $LicenseInfo:firstyear=2003&license=viewergpl$ * * Copyright (c) 2003-2009, Linden Research, Inc. * * Second Life Viewer Source Code * The source code in this file ("Source Code") is provided by Linden Lab * to you under the terms of the GNU General Public License, version 2.0 * ("GPL"), unless you have obtained a separate licensing agreement * ("Other License"), formally executed by you and Linden Lab. Terms of * the GPL can be found in doc/GPL-license.txt in this distribution, or * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2 * * There are special exceptions to the terms and conditions of the GPL as * it is applied to this Source Code. View the full text of the exception * in the file doc/FLOSS-exception.txt in this software distribution, or * online at * http://secondlifegrid.net/programs/open_source/licensing/flossexception * * By copying, modifying or distributing this software, you acknowledge * that you have read and understood your obligations described above, * and agree to abide by those obligations. * * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY, * COMPLETENESS OR PERFORMANCE. * $/LicenseInfo$ */ #ifndef LL_LLPTRSKIPMAP_H #define LL_LLPTRSKIPMAP_H #include "llerror.h" #include "llrand.h" template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH = 8> class LLPtrSkipMapNode { public: LLPtrSkipMapNode() { S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mForward[i] = NULL; } U8 *zero = (U8 *)&mIndex; for (i = 0; i < (S32)sizeof(INDEX_T); i++) { *(zero + i) = 0; } zero = (U8 *)&mData; for (i = 0; i < (S32)sizeof(DATA_T); i++) { *(zero + i) = 0; } } LLPtrSkipMapNode(const INDEX_T &index) : mIndex(index) { S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mForward[i] = NULL; } U8 *zero = (U8 *)&mData; for (i = 0; i < (S32)sizeof(DATA_T); i++) { *(zero + i) = 0; } } LLPtrSkipMapNode(const INDEX_T &index, DATA_T datap) : mIndex(index) { S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mForward[i] = NULL; } mData = datap; } ~LLPtrSkipMapNode() { } // delete associated data and NULLs out pointer void deleteData() { delete mData; mData = 0; } // NULLs out pointer void removeData() { mData = 0; } INDEX_T mIndex; DATA_T mData; LLPtrSkipMapNode *mForward[BINARY_DEPTH]; private: // Disallow copying of LLPtrSkipMapNodes by not implementing these methods. LLPtrSkipMapNode(const LLPtrSkipMapNode &); LLPtrSkipMapNode &operator=(const LLPtrSkipMapNode &rhs); }; //--------------------------------------------------------------------------- template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH = 8> class LLPtrSkipMap { public: typedef BOOL (*compare)(const DATA_T& first, const DATA_T& second); typedef compare insert_func; typedef compare equals_func; void init(); // basic constructor LLPtrSkipMap(); // basic constructor including sorter LLPtrSkipMap(insert_func insert_first, equals_func equals); ~LLPtrSkipMap(); void setInsertFirst(insert_func insert_first); void setEquals(equals_func equals); DATA_T &addData(const INDEX_T &index, DATA_T datap); DATA_T &addData(const INDEX_T &index); DATA_T &getData(const INDEX_T &index); DATA_T &operator[](const INDEX_T &index); // If index present, returns data. // If index not present, adds <index,NULL> and returns NULL. DATA_T &getData(const INDEX_T &index, BOOL &b_new_entry); // returns data entry before and after index BOOL getInterval(const INDEX_T &index, INDEX_T &index_before, INDEX_T &index_after, DATA_T &data_before, DATA_T &data_after ); // Returns TRUE if data present in map. BOOL checkData(const INDEX_T &index); // Returns TRUE if key is present in map. This is useful if you // are potentially storing NULL pointers in the map BOOL checkKey(const INDEX_T &index); // If there, returns the data. // If not, returns NULL. // Never adds entries to the map. DATA_T getIfThere(const INDEX_T &index); INDEX_T reverseLookup(const DATA_T datap); // returns number of items in the list S32 getLength(); // WARNING! getLength is O(n), not O(1)! BOOL removeData(const INDEX_T &index); BOOL deleteData(const INDEX_T &index); // remove all nodes from the list but do not delete data void removeAllData(); void deleteAllData(); // place mCurrentp on first node void resetList(); // return the data currently pointed to DATA_T getCurrentDataWithoutIncrement(); // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp DATA_T getCurrentData(); // same as getCurrentData() but a more intuitive name for the operation DATA_T getNextData(); INDEX_T getNextKey(); // return the key currently pointed to INDEX_T getCurrentKeyWithoutIncrement(); // remove the Node at mCurentOperatingp // leave mCurrentp and mCurentOperatingp on the next entry void removeCurrentData(); void deleteCurrentData(); // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp DATA_T getFirstData(); INDEX_T getFirstKey(); static BOOL defaultEquals(const INDEX_T &first, const INDEX_T &second) { return first == second; } private: // don't generate implicit copy constructor or copy assignment LLPtrSkipMap(const LLPtrSkipMap &); LLPtrSkipMap &operator=(const LLPtrSkipMap &); private: LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *mUpdate[BINARY_DEPTH]; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *mCurrentp; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *mCurrentOperatingp; S32 mLevel; BOOL (*mInsertFirst)(const INDEX_T &first, const INDEX_T &second); BOOL (*mEquals)(const INDEX_T &first, const INDEX_T &second); S32 mNumberOfSteps; }; ////////////////////////////////////////////////// // // LLPtrSkipMap implementation // // template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::LLPtrSkipMap() : mInsertFirst(NULL), mEquals(defaultEquals), mNumberOfSteps(0) { if (BINARY_DEPTH < 2) { llerrs << "Trying to create skip list with too little depth, " "must be 2 or greater" << llendl; } S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mUpdate[i] = NULL; } mLevel = 1; mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::LLPtrSkipMap(insert_func insert_first, equals_func equals) : mInsertFirst(insert_first), mEquals(equals), mNumberOfSteps(0) { if (BINARY_DEPTH < 2) { llerrs << "Trying to create skip list with too little depth, " "must be 2 or greater" << llendl; } mLevel = 1; S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mHead.mForward[i] = NULL; mUpdate[i] = NULL; } mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::~LLPtrSkipMap() { removeAllData(); } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::setInsertFirst(insert_func insert_first) { mInsertFirst = insert_first; } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::setEquals(equals_func equals) { mEquals = equals; } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::addData(const INDEX_T &index, DATA_T datap) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *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->mIndex, index))) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { 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; // replace the existing data if a node is already there if ( (current) &&(mEquals(current->mIndex, index))) { current->mData = datap; return current->mData; } // now add the new node S32 newlevel; for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) { if (ll_frand() < 0.5f) { break; } } LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *snode = new LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>(index, datap); 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 snode->mData; } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::addData(const INDEX_T &index) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *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->mIndex, index))) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { 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; } LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *snode = new LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>(index); 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 snode->mData; } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getData(const INDEX_T &index) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp; mNumberOfSteps = 0; // 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->mIndex, index))) { current = temp; temp = *(current->mForward + level); mNumberOfSteps++; } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { current = temp; temp = *(current->mForward + level); mNumberOfSteps++; } *(mUpdate + level) = current; } } // we're now just in front of where we want to be . . . take one step forward current = *current->mForward; mNumberOfSteps++; if ( (current) &&(mEquals(current->mIndex, index))) { return current->mData; } // now add the new node S32 newlevel; for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) { if (ll_frand() < 0.5f) break; } LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *snode = new LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>(index); 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 snode->mData; } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getInterval(const INDEX_T &index, INDEX_T &index_before, INDEX_T &index_after, DATA_T &data_before, DATA_T &data_after) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp; mNumberOfSteps = 0; // 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->mIndex, index))) { current = temp; temp = *(current->mForward + level); mNumberOfSteps++; } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { current = temp; temp = *(current->mForward + level); mNumberOfSteps++; } *(mUpdate + level) = current; } } BOOL both_found = TRUE; if (current != &mHead) { index_before = current->mIndex; data_before = current->mData; } else { data_before = 0; index_before = 0; both_found = FALSE; } // we're now just in front of where we want to be . . . take one step forward mNumberOfSteps++; current = *current->mForward; if (current) { data_after = current->mData; index_after = current->mIndex; } else { data_after = 0; index_after = 0; both_found = FALSE; } return both_found; } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::operator[](const INDEX_T &index) { return getData(index); } // If index present, returns data. // If index not present, adds <index,NULL> and returns NULL. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getData(const INDEX_T &index, BOOL &b_new_entry) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp; mNumberOfSteps = 0; // 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->mIndex, index))) { current = temp; temp = *(current->mForward + level); mNumberOfSteps++; } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { current = temp; temp = *(current->mForward + level); mNumberOfSteps++; } *(mUpdate + level) = current; } } // we're now just in front of where we want to be . . . take one step forward mNumberOfSteps++; current = *current->mForward; if ( (current) &&(mEquals(current->mIndex, index))) { return current->mData; } b_new_entry = TRUE; addData(index); return current->mData; } // Returns TRUE if data present in map. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::checkData(const INDEX_T &index) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *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->mIndex, index))) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { 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) { // Gets rid of some compiler ambiguity for the LLPointer<> templated class. if (current->mData) { return mEquals(current->mIndex, index); } } return FALSE; } // Returns TRUE if key is present in map. This is useful if you // are potentially storing NULL pointers in the map template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::checkKey(const INDEX_T &index) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *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->mIndex, index))) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { 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->mIndex, index); } return FALSE; } // If there, returns the data. // If not, returns NULL. // Never adds entries to the map. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getIfThere(const INDEX_T &index) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp; mNumberOfSteps = 0; // 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->mIndex, index))) { current = temp; temp = *(current->mForward + level); mNumberOfSteps++; } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { current = temp; temp = *(current->mForward + level); mNumberOfSteps++; } *(mUpdate + level) = current; } } // we're now just in front of where we want to be . . . take one step forward mNumberOfSteps++; current = *current->mForward; if (current) { if (mEquals(current->mIndex, index)) { return current->mData; } } // Avoid Linux compiler warning on returning NULL. return (DATA_T)0; } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::reverseLookup(const DATA_T datap) { LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; while (current) { if (datap == current->mData) { return current->mIndex; } current = *current->mForward; } // not found! return NULL return INDEX_T(); } // returns number of items in the list template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline S32 LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getLength() { U32 length = 0; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>* temp; for (temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) { length++; } return length; } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::removeData(const INDEX_T &index) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *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->mIndex, index))) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { 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->mIndex, index)) { // nope! return FALSE; } else { // do we need to fix current or currentop? if (current == mCurrentp) { mCurrentp = *current->mForward; } if (current == mCurrentOperatingp) { mCurrentOperatingp = *current->mForward; } // 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 current->removeData(); delete current; // clean up mHead while ( (mLevel > 1) &&(!*(mHead.mForward + mLevel - 1))) { mLevel--; } } return TRUE; } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::deleteData(const INDEX_T &index) { S32 level; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead; LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *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->mIndex, index))) { current = temp; temp = *(current->mForward + level); } *(mUpdate + level) = current; } } else { for (level = mLevel - 1; level >= 0; level--) { temp = *(current->mForward + level); while ( (temp) &&(temp->mIndex < index)) { 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->mIndex, index)) { // nope! return FALSE; } else { // do we need to fix current or currentop? if (current == mCurrentp) { mCurrentp = *current->mForward; } if (current == mCurrentOperatingp) { mCurrentOperatingp = *current->mForward; } // 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 current->deleteData(); 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 INDEX_T, class DATA_T, S32 BINARY_DEPTH> void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::removeAllData() { LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp; // reset mCurrentp mCurrentp = *(mHead.mForward); while (mCurrentp) { temp = mCurrentp->mForward[0]; mCurrentp->removeData(); 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); } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::deleteAllData() { LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp; // reset mCurrentp mCurrentp = *(mHead.mForward); while (mCurrentp) { temp = mCurrentp->mForward[0]; mCurrentp->deleteData(); 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 INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::resetList() { mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); } // return the data currently pointed to template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getCurrentDataWithoutIncrement() { if (mCurrentOperatingp) { return mCurrentOperatingp->mData; } else { //return NULL; // causes warning return (DATA_T)0; // equivalent, but no warning } } // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getCurrentData() { if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mData; } else { //return NULL; // causes warning return (DATA_T)0; // equivalent, but no warning } } // same as getCurrentData() but a more intuitive name for the operation template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getNextData() { if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mData; } else { //return NULL; // causes compile warning return (DATA_T)0; // equivalent, but removes warning } } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getNextKey() { if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mIndex; } else { return mHead.mIndex; } } // return the key currently pointed to template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getCurrentKeyWithoutIncrement() { if (mCurrentOperatingp) { return mCurrentOperatingp->mIndex; } else { //return NULL; // causes compile warning return (INDEX_T)0; // equivalent, but removes warning } } // remove the Node at mCurentOperatingp // leave mCurrentp and mCurentOperatingp on the next entry template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::removeCurrentData() { if (mCurrentOperatingp) { removeData(mCurrentOperatingp->mIndex); } } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::deleteCurrentData() { if (mCurrentOperatingp) { deleteData(mCurrentOperatingp->mIndex); } } // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, 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_T)0; // equivalent, but removes warning } } template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH> inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getFirstKey() { mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mIndex; } else { return mHead.mIndex; } } #endif