diff options
Diffstat (limited to 'indra/llcommon')
| -rw-r--r-- | indra/llcommon/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | indra/llcommon/llfasttimer.cpp | 13 | ||||
| -rw-r--r-- | indra/llcommon/llptrskiplist.h | 724 | ||||
| -rw-r--r-- | indra/llcommon/llptrskipmap.h | 1239 | ||||
| -rw-r--r-- | indra/llcommon/llskiplist.h | 517 | ||||
| -rw-r--r-- | indra/llcommon/llskipmap.h | 1020 | ||||
| -rw-r--r-- | indra/llcommon/lltrace.h | 31 | ||||
| -rw-r--r-- | indra/llcommon/lltracerecording.cpp | 55 | ||||
| -rw-r--r-- | indra/llcommon/lltracerecording.h | 99 | ||||
| -rw-r--r-- | indra/llcommon/lluuidhashmap.h | 583 |
10 files changed, 81 insertions, 4205 deletions
diff --git a/indra/llcommon/CMakeLists.txt b/indra/llcommon/CMakeLists.txt index f8f1c010f7..5117224ddb 100644 --- a/indra/llcommon/CMakeLists.txt +++ b/indra/llcommon/CMakeLists.txt @@ -212,8 +212,6 @@ set(llcommon_HEADER_FILES llpriqueuemap.h llprocess.h llprocessor.h - llptrskiplist.h - llptrskipmap.h llptrto.h llqueuedthread.h llrand.h @@ -230,8 +228,6 @@ set(llcommon_HEADER_FILES llsecondlifeurls.h llsimplehash.h llsingleton.h - llskiplist.h - llskipmap.h llsortedvector.h llstack.h llstacktrace.h @@ -255,7 +251,6 @@ set(llcommon_HEADER_FILES llunit.h lluri.h lluuid.h - lluuidhashmap.h llversionserver.h llversionviewer.h llwin32headers.h diff --git a/indra/llcommon/llfasttimer.cpp b/indra/llcommon/llfasttimer.cpp index b40aec4886..5dc5fdd5be 100644 --- a/indra/llcommon/llfasttimer.cpp +++ b/indra/llcommon/llfasttimer.cpp @@ -176,11 +176,14 @@ TimeBlockTreeNode& TimeBlock::getTreeNode() const TimeBlockTreeNode* nodep = LLTrace::get_thread_recorder()->getTimeBlockTreeNode(getIndex()); llassert(nodep); return *nodep; - } +} + +static LLFastTimer::DeclareTimer FTM_PROCESS_TIMES("Process FastTimer Times"); //static void TimeBlock::processTimes() { + LLFastTimer _(FTM_PROCESS_TIMES); get_clock_count(); // good place to calculate clock frequency U64 cur_time = getCPUClockCount64(); @@ -329,12 +332,12 @@ void TimeBlock::logStats() { TimeBlock& timer = *it; LLTrace::PeriodicRecording& frame_recording = LLTrace::get_frame_recording(); - sd[timer.getName()]["Time"] = (LLSD::Real) (frame_recording.getLastRecordingPeriod().getSum(timer).value()); - sd[timer.getName()]["Calls"] = (LLSD::Integer) (frame_recording.getLastRecordingPeriod().getSum(timer.callCount())); + sd[timer.getName()]["Time"] = (LLSD::Real) (frame_recording.getLastRecording().getSum(timer).value()); + sd[timer.getName()]["Calls"] = (LLSD::Integer) (frame_recording.getLastRecording().getSum(timer.callCount())); // computing total time here because getting the root timer's getCountHistory // doesn't work correctly on the first frame - total_time += frame_recording.getLastRecordingPeriod().getSum(timer); + total_time += frame_recording.getLastRecording().getSum(timer); } } @@ -353,7 +356,7 @@ void TimeBlock::logStats() void TimeBlock::dumpCurTimes() { LLTrace::PeriodicRecording& frame_recording = LLTrace::get_frame_recording(); - LLTrace::Recording& last_frame_recording = frame_recording.getLastRecordingPeriod(); + LLTrace::Recording& last_frame_recording = frame_recording.getLastRecording(); // walk over timers in depth order and output timings for(timer_tree_dfs_iterator_t it = begin_timer_tree(TimeBlock::getRootTimeBlock()); diff --git a/indra/llcommon/llptrskiplist.h b/indra/llcommon/llptrskiplist.h deleted file mode 100644 index 67c7cde352..0000000000 --- a/indra/llcommon/llptrskiplist.h +++ /dev/null @@ -1,724 +0,0 @@ -/** - * @file llptrskiplist.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_LLPTRSKIPLIST_H -#define LL_LLPTRSKIPLIST_H - -#include "llerror.h" -#include "llrand.h" -//#include "vmath.h" -#include "llrand.h" - -///////////////////////////////////////////// -// -// LLPtrSkipList implementation - skip list for pointers to objects -// - -template <class DATA_TYPE, S32 BINARY_DEPTH = 8> -class LLPtrSkipList -{ -public: - friend class LLPtrSkipNode; - - // basic constructor - LLPtrSkipList(); - // basic constructor including sorter - LLPtrSkipList(BOOL (*insert_first)(DATA_TYPE *first, DATA_TYPE *second), - BOOL (*equals)(DATA_TYPE *first, DATA_TYPE *second)); - ~LLPtrSkipList(); - - inline void setInsertFirst(BOOL (*insert_first)(const DATA_TYPE *first, const DATA_TYPE *second)); - inline void setEquals(BOOL (*equals)(const DATA_TYPE *first, const DATA_TYPE *second)); - - inline BOOL addData(DATA_TYPE *data); - - inline BOOL checkData(const DATA_TYPE *data); - - inline S32 getLength(); // returns number of items in the list - NOT constant time! - - inline BOOL removeData(const DATA_TYPE *data); - - // note that b_sort is ignored - inline BOOL moveData(const DATA_TYPE *data, LLPtrSkipList *newlist, BOOL b_sort); - - inline BOOL moveCurrentData(LLPtrSkipList *newlist, BOOL b_sort); - - // resort -- use when the value we're sorting by changes - /* IW 12/6/02 - This doesn't work! - Instead, remove the data BEFORE you change it - Then re-insert it after you change it - BOOL resortData(DATA_TYPE *data) - */ - - // remove all nodes from the list but do not delete data - inline void removeAllNodes(); - - inline BOOL deleteData(const DATA_TYPE *data); - - // remove all nodes from the list and delete data - inline void deleteAllData(); - - // 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(); - - // delete the Node at mCurentOperatingp - // leave mCurrentp and mCurentOperatingp on the next entry - inline void deleteCurrentData(); - - // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - inline DATA_TYPE *getFirstData(); - - // TRUE if nodes are not in sorted order - inline BOOL corrupt(); - -protected: - class LLPtrSkipNode - { - public: - LLPtrSkipNode() - : mData(NULL) - { - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - } - - LLPtrSkipNode(DATA_TYPE *data) - : mData(data) - { - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - } - - ~LLPtrSkipNode() - { - if (mData) - { - llerror("Attempting to call LLPtrSkipNode destructor with a non-null mDatap!", 1); - } - } - - // delete associated data and NULLs out pointer - void deleteData() - { - delete mData; - mData = NULL; - } - - // NULLs out pointer - void removeData() - { - mData = NULL; - } - - DATA_TYPE *mData; - LLPtrSkipNode *mForward[BINARY_DEPTH]; - }; - - static BOOL defaultEquals(const DATA_TYPE *first, const DATA_TYPE *second) - { - return first == second; - } - - - LLPtrSkipNode mHead; - LLPtrSkipNode *mUpdate[BINARY_DEPTH]; - LLPtrSkipNode *mCurrentp; - LLPtrSkipNode *mCurrentOperatingp; - S32 mLevel; - BOOL (*mInsertFirst)(const DATA_TYPE *first, const DATA_TYPE *second); - BOOL (*mEquals)(const DATA_TYPE *first, const DATA_TYPE *second); -}; - - -// basic constructor -template <class DATA_TYPE, S32 BINARY_DEPTH> -LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::LLPtrSkipList() - : mInsertFirst(NULL), mEquals(defaultEquals) -{ - 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); -} - -// basic constructor including sorter -template <class DATA_TYPE, S32 BINARY_DEPTH> -LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::LLPtrSkipList(BOOL (*insert_first)(DATA_TYPE *first, DATA_TYPE *second), - BOOL (*equals)(DATA_TYPE *first, DATA_TYPE *second)) - :mInsertFirst(insert_first), mEquals(equals) -{ - 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 DATA_TYPE, S32 BINARY_DEPTH> -inline LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::~LLPtrSkipList() -{ - removeAllNodes(); -} - -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::setInsertFirst(BOOL (*insert_first)(const DATA_TYPE *first, const DATA_TYPE *second)) -{ - mInsertFirst = insert_first; -} - -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::setEquals(BOOL (*equals)(const DATA_TYPE *first, const DATA_TYPE *second)) -{ - mEquals = equals; -} - -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::addData(DATA_TYPE *data) -{ - S32 level; - LLPtrSkipNode *current = &mHead; - LLPtrSkipNode *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; - } - - LLPtrSkipNode *snode = new LLPtrSkipNode(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 LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::checkData(const DATA_TYPE *data) -{ - S32 level; - LLPtrSkipNode *current = &mHead; - LLPtrSkipNode *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); - } - else - { - return FALSE; - } -} - -// returns number of items in the list -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline S32 LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::getLength() -{ - U32 length = 0; - for (LLPtrSkipNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) - { - length++; - } - return length; -} - -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::removeData(const DATA_TYPE *data) -{ - S32 level; - LLPtrSkipNode *current = &mHead; - LLPtrSkipNode *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 - { - // 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; -} - -// note that b_sort is ignored -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::moveData(const DATA_TYPE *data, LLPtrSkipList *newlist, BOOL b_sort) -{ - BOOL removed = removeData(data); - BOOL added = newlist->addData(data); - return removed && added; -} - -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::moveCurrentData(LLPtrSkipList *newlist, BOOL b_sort) -{ - if (mCurrentOperatingp) - { - mCurrentp = mCurrentOperatingp->mForward[0]; - BOOL removed = removeData(mCurrentOperatingp); - BOOL added = newlist->addData(mCurrentOperatingp); - mCurrentOperatingp = mCurrentp; - return removed && added; - } - return FALSE; -} - -// resort -- use when the value we're sorting by changes -/* IW 12/6/02 - This doesn't work! - Instead, remove the data BEFORE you change it - Then re-insert it after you change it -BOOL resortData(DATA_TYPE *data) -{ - removeData(data); - addData(data); -} -*/ - -// remove all nodes from the list but do not delete data -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::removeAllNodes() -{ - LLPtrSkipNode *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 DATA_TYPE, S32 BINARY_DEPTH> -inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::deleteData(const DATA_TYPE *data) -{ - S32 level; - LLPtrSkipNode *current = &mHead; - LLPtrSkipNode *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 - current->deleteData(); - delete current; - - // clean up mHead - while ( (mLevel > 1) - &&(!mHead.mForward[mLevel - 1])) - { - mLevel--; - } - } - return TRUE; -} - -// remove all nodes from the list and delete data -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::deleteAllData() -{ - LLPtrSkipNode *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 DATA_TYPE, S32 BINARY_DEPTH> -inline void LLPtrSkipList<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 *LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::getCurrentData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = *mCurrentp->mForward; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return 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 *LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::getNextData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = *mCurrentp->mForward; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return 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 LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::removeCurrentData() -{ - if (mCurrentOperatingp) - { - removeData(mCurrentOperatingp->mData); - } -} - -// delete the Node at mCurentOperatingp -// leave mCurrentp and mCurentOperatingp on the next entry -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline void LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::deleteCurrentData() -{ - if (mCurrentOperatingp) - { - deleteData(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 *LLPtrSkipList<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 0; // equivalent, but no warning - } -} - -template <class DATA_TYPE, S32 BINARY_DEPTH> -inline BOOL LLPtrSkipList<DATA_TYPE, BINARY_DEPTH>::corrupt() -{ - LLPtrSkipNode *previous = mHead.mForward[0]; - - // Empty lists are not corrupt. - if (!previous) return FALSE; - - LLPtrSkipNode *current = previous->mForward[0]; - while(current) - { - if (!mInsertFirst(previous->mData, current->mData)) - { - // prev shouldn't be in front of cur! - return TRUE; - } - current = current->mForward[0]; - } - return FALSE; -} - -#endif diff --git a/indra/llcommon/llptrskipmap.h b/indra/llcommon/llptrskipmap.h deleted file mode 100644 index 94bc71ec55..0000000000 --- a/indra/llcommon/llptrskipmap.h +++ /dev/null @@ -1,1239 +0,0 @@ -/** - * @file llptrskipmap.h - * @brief Just like a LLSkipMap, but since it's pointers, you can call - * deleteAllData - * - * $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_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 diff --git a/indra/llcommon/llskiplist.h b/indra/llcommon/llskiplist.h deleted file mode 100644 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 diff --git a/indra/llcommon/llskipmap.h b/indra/llcommon/llskipmap.h deleted file mode 100644 index ed53973baa..0000000000 --- a/indra/llcommon/llskipmap.h +++ /dev/null @@ -1,1020 +0,0 @@ -/** - * @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) -{ - llstatic_assert(BINARY_DEPTH >= 2, "Skipmaps must have binary depth of at least 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) -{ - llstatic_assert(BINARY_DEPTH >= 2, "Skipmaps must have binary depth of at least 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 diff --git a/indra/llcommon/lltrace.h b/indra/llcommon/lltrace.h index a574be02da..376248c87a 100644 --- a/indra/llcommon/lltrace.h +++ b/indra/llcommon/lltrace.h @@ -231,15 +231,6 @@ private: template<typename ACCUMULATOR> size_t AccumulatorBuffer<ACCUMULATOR>::sNextStorageSlot = 0; - - -//TODO: replace with decltype when C++11 is enabled -template<typename T> -struct MeanValueType -{ - typedef F64 type; -}; - template<typename ACCUMULATOR> class TraceType : public LLInstanceTracker<TraceType<ACCUMULATOR>, std::string> @@ -382,6 +373,7 @@ private: U32 mNumSamples; }; + template<typename T> class CountAccumulator { @@ -457,13 +449,6 @@ public: }; - -template<> -struct MeanValueType<TraceType<TimeBlockAccumulator> > -{ - typedef LLUnit<LLUnits::Seconds, F64> type; -}; - template<> class TraceType<TimeBlockAccumulator::CallCountAspect> : public TraceType<TimeBlockAccumulator> @@ -476,13 +461,6 @@ public: }; template<> -struct MeanValueType<TraceType<TimeBlockAccumulator::CallCountAspect> > -{ - typedef F64 type; -}; - - -template<> class TraceType<TimeBlockAccumulator::SelfTimeAspect> : public TraceType<TimeBlockAccumulator> { @@ -493,13 +471,6 @@ public: {} }; -template<> -struct MeanValueType<TraceType<TimeBlockAccumulator::SelfTimeAspect> > -{ - typedef LLUnit<LLUnits::Seconds, F64> type; -}; - - class TimeBlock; class TimeBlockTreeNode { diff --git a/indra/llcommon/lltracerecording.cpp b/indra/llcommon/lltracerecording.cpp index f78b7942a7..21156b4d61 100644 --- a/indra/llcommon/lltracerecording.cpp +++ b/indra/llcommon/lltracerecording.cpp @@ -360,8 +360,7 @@ U32 Recording::getSampleCount( const TraceType<MeasurementAccumulator<S64> >& st PeriodicRecording::PeriodicRecording( U32 num_periods, EPlayState state) : mAutoResize(num_periods == 0), - mCurPeriod(0), - mTotalValid(false) + mCurPeriod(0) { if (num_periods) { @@ -373,7 +372,7 @@ PeriodicRecording::PeriodicRecording( U32 num_periods, EPlayState state) void PeriodicRecording::nextPeriod() { EPlayState play_state = getPlayState(); - Recording& old_recording = getCurRecordingPeriod(); + Recording& old_recording = getCurRecording(); if (mAutoResize) { mRecordingPeriods.push_back(Recording()); @@ -382,87 +381,59 @@ void PeriodicRecording::nextPeriod() mCurPeriod = (num_periods > 0) ? (mCurPeriod + 1) % num_periods : mCurPeriod + 1; - old_recording.splitTo(getCurRecordingPeriod()); + old_recording.splitTo(getCurRecording()); switch(play_state) { case STOPPED: - getCurRecordingPeriod().stop(); + getCurRecording().stop(); break; case PAUSED: - getCurRecordingPeriod().pause(); + getCurRecording().pause(); break; case STARTED: break; } - // new period, need to recalculate total - mTotalValid = false; -} - -Recording& PeriodicRecording::getTotalRecording() -{ - if (!mTotalValid) - { - mTotalRecording.reset(); - U32 num_periods = mRecordingPeriods.size(); - - if (num_periods) - { - for (S32 i = mCurPeriod + 1; i < mCurPeriod + num_periods; i++) - { - mTotalRecording.appendRecording(mRecordingPeriods[i % num_periods]); - } - } - else - { - for (S32 i = 0; i < mCurPeriod; i++) - { - mTotalRecording.appendRecording(mRecordingPeriods[i]); - } - } - } - mTotalValid = true; - return mTotalRecording; } void PeriodicRecording::start() { - getCurRecordingPeriod().start(); + getCurRecording().start(); } void PeriodicRecording::stop() { - getCurRecordingPeriod().stop(); + getCurRecording().stop(); } void PeriodicRecording::pause() { - getCurRecordingPeriod().pause(); + getCurRecording().pause(); } void PeriodicRecording::resume() { - getCurRecordingPeriod().resume(); + getCurRecording().resume(); } void PeriodicRecording::restart() { - getCurRecordingPeriod().restart(); + getCurRecording().restart(); } void PeriodicRecording::reset() { - getCurRecordingPeriod().reset(); + getCurRecording().reset(); } void PeriodicRecording::splitTo(PeriodicRecording& other) { - getCurRecordingPeriod().splitTo(other.getCurRecordingPeriod()); + getCurRecording().splitTo(other.getCurRecording()); } void PeriodicRecording::splitFrom(PeriodicRecording& other) { - getCurRecordingPeriod().splitFrom(other.getCurRecordingPeriod()); + getCurRecording().splitFrom(other.getCurRecording()); } diff --git a/indra/llcommon/lltracerecording.h b/indra/llcommon/lltracerecording.h index 68f437a231..4419a22bbe 100644 --- a/indra/llcommon/lltracerecording.h +++ b/indra/llcommon/lltracerecording.h @@ -254,108 +254,123 @@ namespace LLTrace void nextPeriod(); U32 getNumPeriods() { return mRecordingPeriods.size(); } - Recording& getLastRecordingPeriod() + Recording& getLastRecording() { U32 num_periods = mRecordingPeriods.size(); return mRecordingPeriods[(mCurPeriod + num_periods - 1) % num_periods]; } - const Recording& getLastRecordingPeriod() const + const Recording& getLastRecording() const { - return getPrevRecordingPeriod(1); + return getPrevRecording(1); } - Recording& getCurRecordingPeriod() + Recording& getCurRecording() { return mRecordingPeriods[mCurPeriod]; } - const Recording& getCurRecordingPeriod() const + const Recording& getCurRecording() const { return mRecordingPeriods[mCurPeriod]; } - Recording& getPrevRecordingPeriod(U32 offset) + Recording& getPrevRecording(U32 offset) { U32 num_periods = mRecordingPeriods.size(); offset = llclamp(offset, 0u, num_periods - 1); return mRecordingPeriods[(mCurPeriod + num_periods - offset) % num_periods]; } - const Recording& getPrevRecordingPeriod(U32 offset) const + const Recording& getPrevRecording(U32 offset) const { U32 num_periods = mRecordingPeriods.size(); offset = llclamp(offset, 0u, num_periods - 1); return mRecordingPeriods[(mCurPeriod + num_periods - offset) % num_periods]; } - Recording snapshotCurRecordingPeriod() const + Recording snapshotCurRecording() const { - Recording recording_copy(getCurRecordingPeriod()); + Recording recording_copy(getCurRecording()); recording_copy.stop(); return recording_copy; } - Recording& getTotalRecording(); - template <typename T> - typename T::value_t getPeriodMin(const TraceType<T>& stat) const + typename T::value_t getPeriodMin(const TraceType<T>& stat, U32 num_periods = S32_MAX) const { + size_t total_periods = mRecordingPeriods.size(); + num_periods = llmin(num_periods, total_periods); + typename T::value_t min_val = (std::numeric_limits<typename T::value_t>::max)(); - U32 num_periods = mRecordingPeriods.size(); - for (S32 i = 0; i < num_periods; i++) + for (S32 i = 1; i <= num_periods; i++) { - min_val = llmin(min_val, mRecordingPeriods[(mCurPeriod + i) % num_periods].getSum(stat)); + S32 index = (mCurPeriod + total_periods - i) % total_periods; + min_val = llmin(min_val, mRecordingPeriods[index].getSum(stat)); } return min_val; } template <typename T> - F64 getPeriodMinPerSec(const TraceType<T>& stat) const + F64 getPeriodMinPerSec(const TraceType<T>& stat, U32 num_periods = S32_MAX) const { + size_t total_periods = mRecordingPeriods.size(); + num_periods = llmin(num_periods, total_periods); + F64 min_val = (std::numeric_limits<F64>::max)(); - U32 num_periods = mRecordingPeriods.size(); - for (S32 i = 0; i < num_periods; i++) + for (S32 i = 1; i <= num_periods; i++) { - min_val = llmin(min_val, mRecordingPeriods[(mCurPeriod + i) % num_periods].getPerSec(stat)); + S32 index = (mCurPeriod + total_periods - i) % total_periods; + min_val = llmin(min_val, mRecordingPeriods[index].getPerSec(stat)); } return min_val; } template <typename T> - typename T::value_t getPeriodMax(const TraceType<T>& stat) const + typename T::value_t getPeriodMax(const TraceType<T>& stat, U32 num_periods = S32_MAX) const { + size_t total_periods = mRecordingPeriods.size(); + num_periods = llmin(num_periods, total_periods); + typename T::value_t max_val = (std::numeric_limits<typename T::value_t>::min)(); - U32 num_periods = mRecordingPeriods.size(); - for (S32 i = 0; i < num_periods; i++) + for (S32 i = 1; i <= num_periods; i++) { - max_val = llmax(max_val, mRecordingPeriods[(mCurPeriod + i) % num_periods].getSum(stat)); + S32 index = (mCurPeriod + total_periods - i) % total_periods; + max_val = llmax(max_val, mRecordingPeriods[index].getSum(stat)); } return max_val; } template <typename T> - F64 getPeriodMaxPerSec(const TraceType<T>& stat) const + F64 getPeriodMaxPerSec(const TraceType<T>& stat, U32 num_periods = S32_MAX) const { + size_t total_periods = mRecordingPeriods.size(); + num_periods = llmin(num_periods, total_periods); + F64 max_val = (std::numeric_limits<F64>::min)(); - U32 num_periods = mRecordingPeriods.size(); - for (S32 i = 1; i < num_periods; i++) + for (S32 i = 1; i <= num_periods; i++) { - max_val = llmax(max_val, mRecordingPeriods[(mCurPeriod + i) % num_periods].getPerSec(stat)); + S32 index = (mCurPeriod + total_periods - i) % total_periods; + max_val = llmax(max_val, mRecordingPeriods[index].getPerSec(stat)); } return max_val; } template <typename T> - typename MeanValueType<TraceType<T> >::type getPeriodMean(const TraceType<T>& stat) const + typename T::value_t getPeriodMean(const TraceType<T>& stat, U32 num_periods = S32_MAX) const { - typename MeanValueType<TraceType<T> >::type mean = 0.0; - U32 num_periods = mRecordingPeriods.size(); - for (S32 i = 0; i < num_periods; i++) + size_t total_periods = mRecordingPeriods.size(); + num_periods = llmin(num_periods, total_periods); + + typename T::value_t mean = 0.0; + if (num_periods <= 0) { return mean; } + + for (S32 i = 1; i <= num_periods; i++) { - if (mRecordingPeriods[(mCurPeriod + i) % num_periods].getDuration() > 0.f) + S32 index = (mCurPeriod + total_periods - i) % total_periods; + if (mRecordingPeriods[index].getDuration() > 0.f) { - mean += mRecordingPeriods[(mCurPeriod + i) % num_periods].getSum(stat); + mean += mRecordingPeriods[index].getSum(stat); } } mean /= num_periods; @@ -363,15 +378,20 @@ namespace LLTrace } template <typename T> - typename MeanValueType<TraceType<T> >::type getPeriodMeanPerSec(const TraceType<T>& stat) const + typename T::value_t getPeriodMeanPerSec(const TraceType<T>& stat, U32 num_periods = S32_MAX) const { - typename MeanValueType<TraceType<T> >::type mean = 0.0; - U32 num_periods = mRecordingPeriods.size(); - for (S32 i = 0; i < num_periods; i++) + size_t total_periods = mRecordingPeriods.size(); + num_periods = llmin(num_periods, total_periods); + + typename T::value_t mean = 0.0; + if (num_periods <= 0) { return mean; } + + for (S32 i = 1; i <= num_periods; i++) { - if (mRecordingPeriods[i].getDuration() > 0.f) + S32 index = (mCurPeriod + total_periods - i) % total_periods; + if (mRecordingPeriods[index].getDuration() > 0.f) { - mean += mRecordingPeriods[(mCurPeriod + i) % num_periods].getPerSec(stat); + mean += mRecordingPeriods[index].getPerSec(stat); } } mean /= num_periods; @@ -391,7 +411,6 @@ namespace LLTrace private: std::vector<Recording> mRecordingPeriods; Recording mTotalRecording; - bool mTotalValid; const bool mAutoResize; S32 mCurPeriod; }; diff --git a/indra/llcommon/lluuidhashmap.h b/indra/llcommon/lluuidhashmap.h deleted file mode 100644 index e294670030..0000000000 --- a/indra/llcommon/lluuidhashmap.h +++ /dev/null @@ -1,583 +0,0 @@ -/** - * @file lluuidhashmap.h - * @brief A uuid based hash map. - * - * $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_LLUUIDHASHMAP_H -#define LL_LLUUIDHASHMAP_H - -#include "stdtypes.h" -#include "llerror.h" -#include "lluuid.h" - -// UUID hash map - - /* - LLUUIDHashMap<uuid_pair, 32> foo(test_equals); - LLUUIDHashMapIter<uuid_pair, 32> bar(&foo); - - LLDynamicArray<LLUUID> source_ids; - const S32 COUNT = 100000; - S32 q; - for (q = 0; q < COUNT; q++) - { - llinfos << "Creating" << llendl; - LLUUID id; - id.generate(); - //llinfos << q << ":" << id << llendl; - uuid_pair pair; - pair.mUUID = id; - pair.mValue = q; - foo.set(id, pair); - source_ids.put(id); - //ms_sleep(1); - } - - uuid_pair cur; - llinfos << "Iterating" << llendl; - for (cur = bar.first(); !bar.done(); cur = bar.next()) - { - if (source_ids[cur.mValue] != cur.mUUID) - { - llerrs << "Incorrect value iterated!" << llendl; - } - //llinfos << cur.mValue << ":" << cur.mUUID << llendl; - //ms_sleep(1); - } - - llinfos << "Finding" << llendl; - for (q = 0; q < COUNT; q++) - { - cur = foo.get(source_ids[q]); - if (source_ids[cur.mValue] != cur.mUUID) - { - llerrs << "Incorrect value found!" << llendl; - } - //llinfos << res.mValue << ":" << res.mUUID << llendl; - //ms_sleep(1); - } - - llinfos << "Removing" << llendl; - for (q = 0; q < COUNT/2; q++) - { - if (!foo.remove(source_ids[q])) - { - llerrs << "Remove failed!" << llendl; - } - //ms_sleep(1); - } - - llinfos << "Iterating" << llendl; - for (cur = bar.first(); !bar.done(); cur = bar.next()) - { - if (source_ids[cur.mValue] != cur.mUUID) - { - llerrs << "Incorrect value found!" << llendl; - } - //llinfos << cur.mValue << ":" << cur.mUUID << llendl; - //ms_sleep(1); - } - llinfos << "Done with UUID map test" << llendl; - - return 0; - */ - - -// -// LLUUIDHashNode -// - -template <class DATA, int SIZE> -class LLUUIDHashNode -{ -public: - LLUUIDHashNode(); - -public: - S32 mCount; - U8 mKey[SIZE]; - DATA mData[SIZE]; - LLUUIDHashNode<DATA, SIZE> *mNextNodep; -}; - - -// -// LLUUIDHashNode implementation -// -template <class DATA, int SIZE> -LLUUIDHashNode<DATA, SIZE>::LLUUIDHashNode() -{ - mCount = 0; - mNextNodep = NULL; -} - - -template <class DATA_TYPE, int SIZE> -class LLUUIDHashMap -{ -public: - // basic constructor including sorter - LLUUIDHashMap(BOOL (*equals)(const LLUUID &uuid, const DATA_TYPE &data), - const DATA_TYPE &null_data); - ~LLUUIDHashMap(); - - inline DATA_TYPE &get(const LLUUID &uuid); - inline BOOL check(const LLUUID &uuid) const; - inline DATA_TYPE &set(const LLUUID &uuid, const DATA_TYPE &type); - inline BOOL remove(const LLUUID &uuid); - void removeAll(); - - inline S32 getLength() const; // Warning, NOT O(1!) -public: - BOOL (*mEquals)(const LLUUID &uuid, const DATA_TYPE &data); - LLUUIDHashNode<DATA_TYPE, SIZE> mNodes[256]; - - S32 mIterCount; -protected: - DATA_TYPE mNull; -}; - - -// -// LLUUIDHashMap implementation -// - -template <class DATA_TYPE, int SIZE> -LLUUIDHashMap<DATA_TYPE, SIZE>::LLUUIDHashMap(BOOL (*equals)(const LLUUID &uuid, const DATA_TYPE &data), - const DATA_TYPE &null_data) -: mEquals(equals), - mIterCount(0), - mNull(null_data) -{ } - -template <class DATA_TYPE, int SIZE> -LLUUIDHashMap<DATA_TYPE, SIZE>::~LLUUIDHashMap() -{ - removeAll(); -} - -template <class DATA_TYPE, int SIZE> -void LLUUIDHashMap<DATA_TYPE, SIZE>::removeAll() -{ - S32 bin; - for (bin = 0; bin < 256; bin++) - { - LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[bin]; - - BOOL first = TRUE; - while (nodep) - { - S32 i; - const S32 count = nodep->mCount; - - // Iterate through all members of this node - for (i = 0; i < count; i++) - { - nodep->mData[i] = mNull; - } - - nodep->mCount = 0; - // Done with all objects in this node, go to the next. - - LLUUIDHashNode<DATA_TYPE, SIZE>* curp = nodep; - nodep = nodep->mNextNodep; - - // Delete the node if it's not the first node - if (first) - { - first = FALSE; - curp->mNextNodep = NULL; - } - else - { - delete curp; - } - } - } -} - -template <class DATA_TYPE, int SIZE> -inline S32 LLUUIDHashMap<DATA_TYPE, SIZE>::getLength() const -{ - S32 count = 0; - S32 bin; - for (bin = 0; bin < 256; bin++) - { - LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = (LLUUIDHashNode<DATA_TYPE, SIZE>*) &mNodes[bin]; - while (nodep) - { - count += nodep->mCount; - nodep = nodep->mNextNodep; - } - } - return count; -} - -template <class DATA_TYPE, int SIZE> -inline DATA_TYPE &LLUUIDHashMap<DATA_TYPE, SIZE>::get(const LLUUID &uuid) -{ - LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[uuid.mData[0]]; - - // Grab the second byte of the UUID, which is the key for the node data - const S32 second_byte = uuid.mData[1]; - while (nodep) - { - S32 i; - const S32 count = nodep->mCount; - - // Iterate through all members of this node - for (i = 0; i < count; i++) - { - if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) - { - // The second byte matched, and our equality test passed. - // We found it. - return nodep->mData[i]; - } - } - - // Done with all objects in this node, go to the next. - nodep = nodep->mNextNodep; - } - return mNull; -} - - -template <class DATA_TYPE, int SIZE> -inline BOOL LLUUIDHashMap<DATA_TYPE, SIZE>::check(const LLUUID &uuid) const -{ - const LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[uuid.mData[0]]; - - // Grab the second byte of the UUID, which is the key for the node data - const S32 second_byte = uuid.mData[1]; - while (nodep) - { - S32 i; - const S32 count = nodep->mCount; - - // Iterate through all members of this node - for (i = 0; i < count; i++) - { - if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) - { - // The second byte matched, and our equality test passed. - // We found it. - return TRUE; - } - } - - // Done with all objects in this node, go to the next. - nodep = nodep->mNextNodep; - } - - // Didn't find anything - return FALSE; -} - - -template <class DATA_TYPE, int SIZE> -inline DATA_TYPE &LLUUIDHashMap<DATA_TYPE, SIZE>::set(const LLUUID &uuid, const DATA_TYPE &data) -{ - // Set is just like a normal find, except that if we find a match - // we replace it with the input value. - // If we don't find a match, we append to the end of the list. - - LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[uuid.mData[0]]; - - const S32 second_byte = uuid.mData[1]; - while (1) - { - const S32 count = nodep->mCount; - - S32 i; - for (i = 0; i < count; i++) - { - if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) - { - // We found a match for this key, replace the data with - // the incoming data. - nodep->mData[i] = data; - return nodep->mData[i]; - } - } - if (!nodep->mNextNodep) - { - // We've iterated through all of the keys without finding a match - if (i < SIZE) - { - // There's still some space on this node, append - // the key and data to it. - nodep->mKey[i] = second_byte; - nodep->mData[i] = data; - nodep->mCount++; - - return nodep->mData[i]; - } - else - { - // This node is full, append a new node to the end. - nodep->mNextNodep = new LLUUIDHashNode<DATA_TYPE, SIZE>; - nodep->mNextNodep->mKey[0] = second_byte; - nodep->mNextNodep->mData[0] = data; - nodep->mNextNodep->mCount = 1; - - return nodep->mNextNodep->mData[0]; - } - } - - // No match on this node, go to the next - nodep = nodep->mNextNodep; - } -} - - -template <class DATA_TYPE, int SIZE> -inline BOOL LLUUIDHashMap<DATA_TYPE, SIZE>::remove(const LLUUID &uuid) -{ - if (mIterCount) - { - // We don't allow remove when we're iterating, it's bad karma! - llerrs << "Attempted remove while an outstanding iterator in LLUUIDHashMap!" << llendl; - } - // Remove is the trickiest operation. - // What we want to do is swap the last element of the last - // node if we find the one that we want to remove, but we have - // to deal with deleting the node from the tail if it's empty, but - // NOT if it's the only node left. - - LLUUIDHashNode<DATA_TYPE, SIZE> *nodep = &mNodes[uuid.mData[0]]; - - // Not empty, we need to search through the nodes - const S32 second_byte = uuid.mData[1]; - - // A modification of the standard search algorithm. - while (nodep) - { - const S32 count = nodep->mCount; - - S32 i; - for (i = 0; i < count; i++) - { - if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) - { - // We found the node that we want to remove. - // Find the last (and next-to-last) node, and the index of the last - // element. We could conceviably start from the node we're on, - // but that makes it more complicated, this is easier. - - LLUUIDHashNode<DATA_TYPE, SIZE> *prevp = &mNodes[uuid.mData[0]]; - LLUUIDHashNode<DATA_TYPE, SIZE> *lastp = prevp; - - // Find the last and next-to-last - while (lastp->mNextNodep) - { - prevp = lastp; - lastp = lastp->mNextNodep; - } - - // First, swap in the last to the current location. - nodep->mKey[i] = lastp->mKey[lastp->mCount - 1]; - nodep->mData[i] = lastp->mData[lastp->mCount - 1]; - - // Now, we delete the entry - lastp->mCount--; - lastp->mData[lastp->mCount] = mNull; - - if (!lastp->mCount) - { - // We deleted the last element! - if (lastp != &mNodes[uuid.mData[0]]) - { - // Only blitz the node if it's not the head - // Set the previous node to point to NULL, then - // blitz the empty last node - prevp->mNextNodep = NULL; - delete lastp; - } - } - return TRUE; - } - } - - // Iterate to the next node, we've scanned all the entries in this one. - nodep = nodep->mNextNodep; - } - return FALSE; -} - - -// -// LLUUIDHashMapIter -// - -template <class DATA_TYPE, int SIZE> -class LLUUIDHashMapIter -{ -public: - LLUUIDHashMapIter(LLUUIDHashMap<DATA_TYPE, SIZE> *hash_mapp); - ~LLUUIDHashMapIter(); - - - inline void reset(); - inline void first(); - inline void next(); - inline BOOL done() const; - - DATA_TYPE& operator*() const - { - return mCurHashNodep->mData[mCurHashNodeKey]; - } - DATA_TYPE* operator->() const - { - return &(operator*()); - } - -protected: - LLUUIDHashMap<DATA_TYPE, SIZE> *mHashMapp; - LLUUIDHashNode<DATA_TYPE, SIZE> *mCurHashNodep; - - S32 mCurHashMapNodeNum; - S32 mCurHashNodeKey; - - DATA_TYPE mNull; -}; - - -// -// LLUUIDHashMapIter Implementation -// -template <class DATA_TYPE, int SIZE> -LLUUIDHashMapIter<DATA_TYPE, SIZE>::LLUUIDHashMapIter(LLUUIDHashMap<DATA_TYPE, SIZE> *hash_mapp) -{ - mHashMapp = hash_mapp; - mCurHashNodep = NULL; - mCurHashMapNodeNum = 0; - mCurHashNodeKey = 0; -} - -template <class DATA_TYPE, int SIZE> -LLUUIDHashMapIter<DATA_TYPE, SIZE>::~LLUUIDHashMapIter() -{ - reset(); -} - -template <class DATA_TYPE, int SIZE> -inline void LLUUIDHashMapIter<DATA_TYPE, SIZE>::reset() -{ - if (mCurHashNodep) - { - // We're partway through an iteration, we can clean up now - mHashMapp->mIterCount--; - mCurHashNodep = NULL; - } -} - -template <class DATA_TYPE, int SIZE> -inline void LLUUIDHashMapIter<DATA_TYPE, SIZE>::first() -{ - // Iterate through until we find the first non-empty node; - S32 i; - for (i = 0; i < 256; i++) - { - if (mHashMapp->mNodes[i].mCount) - { - if (!mCurHashNodep) - { - // Increment, since it's no longer safe for us to do a remove - mHashMapp->mIterCount++; - } - - mCurHashNodep = &mHashMapp->mNodes[i]; - mCurHashMapNodeNum = i; - mCurHashNodeKey = 0; - //return mCurHashNodep->mData[0]; - return; - } - } - - // Completely empty! - mCurHashNodep = NULL; - //return mNull; - return; -} - -template <class DATA_TYPE, int SIZE> -inline BOOL LLUUIDHashMapIter<DATA_TYPE, SIZE>::done() const -{ - return mCurHashNodep ? FALSE : TRUE; -} - -template <class DATA_TYPE, int SIZE> -inline void LLUUIDHashMapIter<DATA_TYPE, SIZE>::next() -{ - // No current entry, this iterator is done - if (!mCurHashNodep) - { - //return mNull; - return; - } - - // Go to the next element - mCurHashNodeKey++; - if (mCurHashNodeKey < mCurHashNodep->mCount) - { - // We're not done with this node, return the current element - //return mCurHashNodep->mData[mCurHashNodeKey]; - return; - } - - // Done with this node, move to the next - mCurHashNodep = mCurHashNodep->mNextNodep; - if (mCurHashNodep) - { - // Return the first element - mCurHashNodeKey = 0; - //return mCurHashNodep->mData[0]; - return; - } - - // Find the next non-empty node (keyed on the first byte) - mCurHashMapNodeNum++; - - S32 i; - for (i = mCurHashMapNodeNum; i < 256; i++) - { - if (mHashMapp->mNodes[i].mCount) - { - // We found one that wasn't empty - mCurHashNodep = &mHashMapp->mNodes[i]; - mCurHashMapNodeNum = i; - mCurHashNodeKey = 0; - //return mCurHashNodep->mData[0]; - return; - } - } - - // OK, we're done, nothing else to iterate - mCurHashNodep = NULL; - mHashMapp->mIterCount--; // Decrement since we're safe to do removes now - //return mNull; -} - -#endif // LL_LLUUIDHASHMAP_H |