/** * @file llskipmap.h * @brief Associative container based on the skiplist algorithm. * * $LicenseInfo:firstyear=2003&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_LLSKIPMAP_H #define LL_LLSKIPMAP_H #include "llerror.h" template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH = 8> class LLSkipMap { public: // basic constructor LLSkipMap(); // basic constructor including sorter LLSkipMap(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second), BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)); ~LLSkipMap(); void setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second)); void setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)); DATA_TYPE &addData(const INDEX_TYPE &index, DATA_TYPE datap); DATA_TYPE &addData(const INDEX_TYPE &index); DATA_TYPE &getData(const INDEX_TYPE &index); DATA_TYPE &operator[](const INDEX_TYPE &index); // If index present, returns data. // If index not present, adds <index,NULL> and returns NULL. DATA_TYPE &getData(const INDEX_TYPE &index, BOOL &b_new_entry); // Returns TRUE if data present in map. BOOL checkData(const INDEX_TYPE &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_TYPE &index); // If there, returns the data. // If not, returns NULL. // Never adds entries to the map. DATA_TYPE getIfThere(const INDEX_TYPE &index); INDEX_TYPE reverseLookup(const DATA_TYPE datap); // returns number of items in the list S32 getLength(); // WARNING! getLength is O(n), not O(1)! BOOL removeData(const INDEX_TYPE &index); // remove all nodes from the list but do not delete data void removeAllData(); // place mCurrentp on first node void resetList(); // return the data currently pointed to DATA_TYPE getCurrentDataWithoutIncrement(); // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp DATA_TYPE getCurrentData(); // same as getCurrentData() but a more intuitive name for the operation DATA_TYPE getNextData(); INDEX_TYPE getNextKey(); // return the key currently pointed to INDEX_TYPE getCurrentKeyWithoutIncrement(); // The internal iterator is at the end of the list. BOOL notDone() const; // 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_TYPE getFirstData(); INDEX_TYPE getFirstKey(); class LLSkipMapNode { public: LLSkipMapNode() { S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mForward[i] = NULL; } U8 *zero = (U8 *)&mIndex; for (i = 0; i < (S32)sizeof(INDEX_TYPE); i++) { *(zero + i) = 0; } zero = (U8 *)&mData; for (i = 0; i < (S32)sizeof(DATA_TYPE); i++) { *(zero + i) = 0; } } LLSkipMapNode(const INDEX_TYPE &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_TYPE); i++) { *(zero + i) = 0; } } LLSkipMapNode(const INDEX_TYPE &index, DATA_TYPE datap) : mIndex(index) { S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mForward[i] = NULL; } mData = datap; } ~LLSkipMapNode() { } INDEX_TYPE mIndex; DATA_TYPE mData; LLSkipMapNode *mForward[BINARY_DEPTH]; private: // Disallow copying of LLSkipMapNodes by not implementing these methods. LLSkipMapNode(const LLSkipMapNode &); LLSkipMapNode &operator=(const LLSkipMapNode &rhs); }; static BOOL defaultEquals(const INDEX_TYPE &first, const INDEX_TYPE &second) { return first == second; } private: // don't generate implicit copy constructor or copy assignment LLSkipMap(const LLSkipMap &); LLSkipMap &operator=(const LLSkipMap &); private: LLSkipMapNode mHead; LLSkipMapNode *mUpdate[BINARY_DEPTH]; LLSkipMapNode *mCurrentp; LLSkipMapNode *mCurrentOperatingp; S32 mLevel; BOOL (*mInsertFirst)(const INDEX_TYPE &first, const INDEX_TYPE &second); BOOL (*mEquals)(const INDEX_TYPE &first, const INDEX_TYPE &second); S32 mNumberOfSteps; }; ////////////////////////////////////////////////// // // LLSkipMap implementation // template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::LLSkipMap() : mInsertFirst(NULL), mEquals(defaultEquals) { // Skipmaps must have binary depth of at least 2 cassert(BINARY_DEPTH >= 2); S32 i; for (i = 0; i < BINARY_DEPTH; i++) { mUpdate[i] = NULL; } mLevel = 1; mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::LLSkipMap(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second), BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)) : mInsertFirst(insert_first), mEquals(equals) { // Skipmaps must have binary depth of at least 2 cassert(BINARY_DEPTH >= 2); 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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::~LLSkipMap() { removeAllData(); } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second)) { mInsertFirst = insert_first; } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)) { mEquals = equals; } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::addData(const INDEX_TYPE &index, DATA_TYPE datap) { S32 level; LLSkipMapNode *current = &mHead; LLSkipMapNode *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 (rand() & 1) { break; } } LLSkipMapNode *snode = new LLSkipMapNode(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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::addData(const INDEX_TYPE &index) { S32 level; LLSkipMapNode *current = &mHead; LLSkipMapNode *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 (rand() & 1) break; } LLSkipMapNode *snode = new LLSkipMapNode(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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getData(const INDEX_TYPE &index) { S32 level; LLSkipMapNode *current = &mHead; LLSkipMapNode *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 (rand() & 1) break; } LLSkipMapNode *snode = new LLSkipMapNode(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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::operator[](const INDEX_TYPE &index) { return getData(index); } // If index present, returns data. // If index not present, adds <index,NULL> and returns NULL. template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getData(const INDEX_TYPE &index, BOOL &b_new_entry) { S32 level; LLSkipMapNode *current = &mHead; LLSkipMapNode *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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::checkData(const INDEX_TYPE &index) { S32 level; LLSkipMapNode *current = &mHead; LLSkipMapNode *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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::checkKey(const INDEX_TYPE &index) { S32 level; LLSkipMapNode *current = &mHead; LLSkipMapNode *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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getIfThere(const INDEX_TYPE &index) { S32 level; LLSkipMapNode *current = &mHead; LLSkipMapNode *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_TYPE(); } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::reverseLookup(const DATA_TYPE datap) { LLSkipMapNode *current = &mHead; while (current) { if (datap == current->mData) { return current->mIndex; } current = *current->mForward; } // not found! return NULL return INDEX_TYPE(); } // returns number of items in the list template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline S32 LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getLength() { U32 length = 0; for (LLSkipMapNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) { length++; } return length; } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeData(const INDEX_TYPE &index) { S32 level; LLSkipMapNode *current = &mHead; LLSkipMapNode *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); } 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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeAllData() { LLSkipMapNode *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 INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::resetList() { mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); } // return the data currently pointed to template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentDataWithoutIncrement() { if (mCurrentOperatingp) { return mCurrentOperatingp->mData; } else { return DATA_TYPE(); } } // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentData() { if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mData; } else { // Basic types, like int, have default constructors that initialize // them to zero. g++ 2.95 supports this. "int()" is zero. // This also is nice for LLUUID() return DATA_TYPE(); } } // same as getCurrentData() but a more intuitive name for the operation template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getNextData() { if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mData; } else { // Basic types, like int, have default constructors that initialize // them to zero. g++ 2.95 supports this. "int()" is zero. // This also is nice for LLUUID() return DATA_TYPE(); } } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, 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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentKeyWithoutIncrement() { if (mCurrentOperatingp) { return mCurrentOperatingp->mIndex; } else { // See comment for getNextData() return INDEX_TYPE(); } } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::notDone() const { if (mCurrentOperatingp) { return TRUE; } else { return FALSE; } } // remove the Node at mCurentOperatingp // leave mCurrentp and mCurentOperatingp on the next entry template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeCurrentData() { if (mCurrentOperatingp) { removeData(mCurrentOperatingp->mIndex); } } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, 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_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getFirstData() { mCurrentp = *(mHead.mForward); mCurrentOperatingp = *(mHead.mForward); if (mCurrentp) { mCurrentOperatingp = mCurrentp; mCurrentp = mCurrentp->mForward[0]; return mCurrentOperatingp->mData; } else { // See comment for getNextData() return DATA_TYPE(); } } template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH> inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, 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