diff options
Diffstat (limited to 'indra')
24 files changed, 129 insertions, 4717 deletions
diff --git a/indra/llcharacter/llmotioncontroller.h b/indra/llcharacter/llmotioncontroller.h index 52eaf557b1..2bd5271c4f 100644 --- a/indra/llcharacter/llmotioncontroller.h +++ b/indra/llcharacter/llmotioncontroller.h @@ -34,7 +34,6 @@ #include <map> #include <deque> -#include "lluuidhashmap.h" #include "llmotion.h" #include "llpose.h" #include "llframetimer.h" 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 diff --git a/indra/llui/llstatbar.cpp b/indra/llui/llstatbar.cpp index d9f3d14ef0..70ba59b130 100644 --- a/indra/llui/llstatbar.cpp +++ b/indra/llui/llstatbar.cpp @@ -103,68 +103,63 @@ void LLStatBar::draw() max = 0.f, mean = 0.f; - S32 num_samples = 0; LLTrace::PeriodicRecording& frame_recording = LLTrace::get_frame_recording(); if (mCountFloatp) { - LLTrace::Recording& last_frame_recording = frame_recording.getLastRecordingPeriod(); + LLTrace::Recording& last_frame_recording = frame_recording.getLastRecording(); if (mPerSec) { current = last_frame_recording.getPerSec(*mCountFloatp); - min = frame_recording.getPeriodMinPerSec(*mCountFloatp); - max = frame_recording.getPeriodMaxPerSec(*mCountFloatp); - mean = frame_recording.getPeriodMeanPerSec(*mCountFloatp); - num_samples = frame_recording.getTotalRecording().getSampleCount(*mCountFloatp); + min = frame_recording.getPeriodMinPerSec(*mCountFloatp, mNumFrames); + max = frame_recording.getPeriodMaxPerSec(*mCountFloatp, mNumFrames); + mean = frame_recording.getPeriodMeanPerSec(*mCountFloatp, mNumFrames); } else { current = last_frame_recording.getSum(*mCountFloatp); - min = frame_recording.getPeriodMin(*mCountFloatp); - max = frame_recording.getPeriodMax(*mCountFloatp); - mean = frame_recording.getPeriodMean(*mCountFloatp); - num_samples = frame_recording.getTotalRecording().getSampleCount(*mCountFloatp); + min = frame_recording.getPeriodMin(*mCountFloatp, mNumFrames); + max = frame_recording.getPeriodMax(*mCountFloatp, mNumFrames); + mean = frame_recording.getPeriodMean(*mCountFloatp, mNumFrames); } } else if (mCountIntp) { - LLTrace::Recording& last_frame_recording = frame_recording.getLastRecordingPeriod(); + LLTrace::Recording& last_frame_recording = frame_recording.getLastRecording(); if (mPerSec) { current = last_frame_recording.getPerSec(*mCountIntp); - min = frame_recording.getPeriodMinPerSec(*mCountIntp); - max = frame_recording.getPeriodMaxPerSec(*mCountIntp); - mean = frame_recording.getPeriodMeanPerSec(*mCountIntp); - num_samples = frame_recording.getTotalRecording().getSampleCount(*mCountIntp); + min = frame_recording.getPeriodMinPerSec(*mCountIntp, mNumFrames); + max = frame_recording.getPeriodMaxPerSec(*mCountIntp, mNumFrames); + mean = frame_recording.getPeriodMeanPerSec(*mCountIntp, mNumFrames); } else { current = last_frame_recording.getSum(*mCountIntp); - min = frame_recording.getPeriodMin(*mCountIntp); - max = frame_recording.getPeriodMax(*mCountIntp); - mean = frame_recording.getPeriodMean(*mCountIntp); - num_samples = frame_recording.getTotalRecording().getSampleCount(*mCountIntp); + min = frame_recording.getPeriodMin(*mCountIntp, mNumFrames); + max = frame_recording.getPeriodMax(*mCountIntp, mNumFrames); + mean = frame_recording.getPeriodMean(*mCountIntp, mNumFrames); } } else if (mMeasurementFloatp) { - LLTrace::Recording& recording = frame_recording.getTotalRecording(); - current = recording.getLastValue(*mMeasurementFloatp); - min = recording.getMin(*mMeasurementFloatp); - max = recording.getMax(*mMeasurementFloatp); - mean = recording.getMean(*mMeasurementFloatp); - num_samples = frame_recording.getTotalRecording().getSampleCount(*mMeasurementFloatp); + LLTrace::Recording& last_frame_recording = frame_recording.getLastRecording(); + + current = last_frame_recording.getLastValue(*mMeasurementFloatp); + min = frame_recording.getPeriodMin(*mMeasurementFloatp, mNumFrames); + max = frame_recording.getPeriodMax(*mMeasurementFloatp, mNumFrames); + mean = frame_recording.getPeriodMean(*mMeasurementFloatp, mNumFrames); } else if (mMeasurementIntp) { - LLTrace::Recording& recording = frame_recording.getTotalRecording(); - current = recording.getLastValue(*mMeasurementIntp); - min = recording.getMin(*mMeasurementIntp); - max = recording.getMax(*mMeasurementIntp); - mean = recording.getMean(*mMeasurementIntp); - num_samples = frame_recording.getTotalRecording().getSampleCount(*mMeasurementIntp); + LLTrace::Recording& last_frame_recording = frame_recording.getLastRecording(); + + current = last_frame_recording.getLastValue(*mMeasurementIntp); + min = frame_recording.getPeriodMin(*mMeasurementIntp, mNumFrames); + max = frame_recording.getPeriodMax(*mMeasurementIntp, mNumFrames); + mean = frame_recording.getPeriodMean(*mMeasurementIntp, mNumFrames); } current *= mUnitScale; @@ -203,7 +198,7 @@ void LLStatBar::draw() const S32 tick_length = 4; const S32 tick_width = 1; - if (mScaleRange && num_samples) + if (mScaleRange && min < max) { F32 cur_max = mTickSpacing; while(max > cur_max && mMaxBar > cur_max) @@ -352,7 +347,7 @@ void LLStatBar::draw() for (i = 1; i <= max_frame; i++) { F32 offset = ((F32)i / (F32)mNumFrames) * span; - LLTrace::Recording& recording = frame_recording.getPrevRecordingPeriod(i); + LLTrace::Recording& recording = frame_recording.getPrevRecording(i); if (mPerSec) { if (mCountFloatp) diff --git a/indra/llui/llstatgraph.cpp b/indra/llui/llstatgraph.cpp index bdb378c9c5..af01e66095 100644 --- a/indra/llui/llstatgraph.cpp +++ b/indra/llui/llstatgraph.cpp @@ -66,7 +66,7 @@ void LLStatGraph::draw() range = mMax - mMin; if (mNewStatFloatp) { - LLTrace::Recording& recording = LLTrace::get_frame_recording().getLastRecordingPeriod(); + LLTrace::Recording& recording = LLTrace::get_frame_recording().getLastRecording(); if (mPerSec) { @@ -79,7 +79,7 @@ void LLStatGraph::draw() } else if (mNewStatIntp) { - LLTrace::Recording& recording = LLTrace::get_frame_recording().getLastRecordingPeriod(); + LLTrace::Recording& recording = LLTrace::get_frame_recording().getLastRecording(); if (mPerSec) { diff --git a/indra/newview/llagentcamera.cpp b/indra/newview/llagentcamera.cpp index 420220d21a..7c9fbccd7f 100644 --- a/indra/newview/llagentcamera.cpp +++ b/indra/newview/llagentcamera.cpp @@ -1082,7 +1082,7 @@ void LLAgentCamera::updateLookAt(const S32 mouse_x, const S32 mouse_y) LLQuaternion av_inv_rot = ~gAgentAvatarp->mRoot.getWorldRotation(); LLVector3 root_at = LLVector3::x_axis * gAgentAvatarp->mRoot.getWorldRotation(); - if (LLTrace::get_frame_recording().getLastRecordingPeriod().getLastValue(*gViewerWindow->getMouseVelocityStat()) < 0.01f + if (LLTrace::get_frame_recording().getLastRecording().getLastValue(*gViewerWindow->getMouseVelocityStat()) < 0.01f && (root_at * last_at_axis > 0.95f)) { LLVector3 vel = gAgentAvatarp->getVelocity(); diff --git a/indra/newview/llfasttimerview.cpp b/indra/newview/llfasttimerview.cpp index 80d845c70e..45ffe56ac1 100644 --- a/indra/newview/llfasttimerview.cpp +++ b/indra/newview/llfasttimerview.cpp @@ -333,7 +333,7 @@ static std::string get_tooltip(TimeBlock& timer, S32 history_index, PeriodicReco } else { - tooltip = llformat("%s (%d ms, %d calls)", timer.getName().c_str(), (S32)LLUnit<LLUnits::Milliseconds, F64>(frame_recording.getPrevRecordingPeriod(history_index).getSum(timer)).value(), (S32)frame_recording.getPrevRecordingPeriod(history_index).getSum(timer.callCount())); + tooltip = llformat("%s (%d ms, %d calls)", timer.getName().c_str(), (S32)LLUnit<LLUnits::Milliseconds, F64>(frame_recording.getPrevRecording(history_index).getSum(timer)).value(), (S32)frame_recording.getPrevRecording(history_index).getSum(timer.callCount())); } return tooltip; } @@ -417,7 +417,7 @@ void LLFastTimerView::draw() printLineStats(); LLView::draw(); - mAllTimeMax = llmax(mAllTimeMax, mRecording->getLastRecordingPeriod().getSum(FTM_FRAME)); + mAllTimeMax = llmax(mAllTimeMax, mRecording->getLastRecording().getSum(FTM_FRAME)); mHoverID = NULL; mHoverBarIndex = -1; } @@ -984,7 +984,7 @@ void LLFastTimerView::printLineStats() LLUnit<LLUnits::Seconds, F32> ticks; if (mPrintStats > 0) { - ticks = mRecording->getPrevRecordingPeriod(mPrintStats).getSum(*idp); + ticks = mRecording->getPrevRecording(mPrintStats).getSum(*idp); } else { @@ -1096,8 +1096,8 @@ void LLFastTimerView::drawLineGraph() j > 0; j--) { - LLUnit<LLUnits::Seconds, F32> time = llmax(mRecording->getPrevRecordingPeriod(j).getSum(*idp), LLUnit<LLUnits::Seconds, F64>(0.000001)); - U32 calls = mRecording->getPrevRecordingPeriod(j).getSum(idp->callCount()); + LLUnit<LLUnits::Seconds, F32> time = llmax(mRecording->getPrevRecording(j).getSum(*idp), LLUnit<LLUnits::Seconds, F64>(0.000001)); + U32 calls = mRecording->getPrevRecording(j).getSum(idp->callCount()); if (alpha == 1.f) { @@ -1197,8 +1197,8 @@ void LLFastTimerView::drawLegend( S32 y ) if (mHoverBarIndex > 0 && mHoverID) { S32 hidx = mScrollIndex + mHoverBarIndex; - ms = mRecording->getPrevRecordingPeriod(hidx).getSum(*idp); - calls = mRecording->getPrevRecordingPeriod(hidx).getSum(idp->callCount()); + ms = mRecording->getPrevRecording(hidx).getSum(*idp); + calls = mRecording->getPrevRecording(hidx).getSum(idp->callCount()); } else { @@ -1455,7 +1455,7 @@ S32 LLFastTimerView::updateTimerBarWidths(LLTrace::TimeBlock* time_block, std::v LLFastTimer _(FTM_UPDATE_TIMER_BAR_WIDTHS); F32 self_time_frame_fraction = history_index == -1 ? (mRecording->getPeriodMean(time_block->selfTime()) / mTotalTimeDisplay) - : (mRecording->getPrevRecordingPeriod(history_index).getSum(time_block->selfTime()) / mTotalTimeDisplay); + : (mRecording->getPrevRecording(history_index).getSum(time_block->selfTime()) / mTotalTimeDisplay); S32 self_time_width = llround(self_time_frame_fraction * (F32)mBarRect.getWidth()); S32 full_width = self_time_width; diff --git a/indra/newview/llfloaterabout.cpp b/indra/newview/llfloaterabout.cpp index 58701ca3c9..93502daac7 100644 --- a/indra/newview/llfloaterabout.cpp +++ b/indra/newview/llfloaterabout.cpp @@ -296,7 +296,7 @@ LLSD LLFloaterAbout::getInfo() if (gPacketsIn > 0) { - LLTrace::Recording cur_frame = LLTrace::get_frame_recording().snapshotCurRecordingPeriod(); + LLTrace::Recording cur_frame = LLTrace::get_frame_recording().snapshotCurRecording(); info["PACKETS_LOST"] = cur_frame.getSum(LLStatViewer::PACKETS_LOST); info["PACKETS_IN"] = F32(gPacketsIn); info["PACKETS_PCT"] = 100.f*info["PACKETS_LOST"].asReal() / info["PACKETS_IN"].asReal(); diff --git a/indra/newview/llhudnametag.cpp b/indra/newview/llhudnametag.cpp index 3ac11f906b..cdfe776589 100644 --- a/indra/newview/llhudnametag.cpp +++ b/indra/newview/llhudnametag.cpp @@ -901,7 +901,7 @@ void LLHUDNameTag::updateAll() } LLTrace::CountStatHandle<>* camera_vel_stat = LLViewerCamera::getVelocityStat(); - F32 camera_vel = LLTrace::get_frame_recording().getLastRecordingPeriod().getPerSec(*camera_vel_stat); + F32 camera_vel = LLTrace::get_frame_recording().getLastRecording().getPerSec(*camera_vel_stat); if (camera_vel > MAX_STABLE_CAMERA_VELOCITY) { return; diff --git a/indra/newview/llviewercamera.cpp b/indra/newview/llviewercamera.cpp index 9ca5f07f35..1f5bdc8589 100644 --- a/indra/newview/llviewercamera.cpp +++ b/indra/newview/llviewercamera.cpp @@ -170,7 +170,7 @@ void LLViewerCamera::updateCameraLocation(const LLVector3 ¢er, add(sVelocityStat, dpos); add(sAngularVelocityStat, drot); - mAverageSpeed = LLTrace::get_frame_recording().getPeriodMeanPerSec(sVelocityStat); + mAverageSpeed = LLTrace::get_frame_recording().getPeriodMeanPerSec(sVelocityStat, 50); mAverageAngularSpeed = LLTrace::get_frame_recording().getPeriodMeanPerSec(sAngularVelocityStat); mCosHalfCameraFOV = cosf(0.5f * getView() * llmax(1.0f, getAspect())); diff --git a/indra/newview/llviewerprecompiledheaders.h b/indra/newview/llviewerprecompiledheaders.h index 0316f79973..cafe28356d 100644 --- a/indra/newview/llviewerprecompiledheaders.h +++ b/indra/newview/llviewerprecompiledheaders.h @@ -83,7 +83,6 @@ #include "llsys.h" #include "llthread.h" #include "lltimer.h" -#include "lluuidhashmap.h" #include "stdenums.h" #include "stdtypes.h" #include "timing.h" diff --git a/indra/newview/llviewerstats.cpp b/indra/newview/llviewerstats.cpp index fa4eb73180..13a005dcbf 100644 --- a/indra/newview/llviewerstats.cpp +++ b/indra/newview/llviewerstats.cpp @@ -348,11 +348,12 @@ void update_statistics() sample(LLStatViewer::SIM_PING, LLTrace::Seconds(10)); } - add(LLStatViewer::FPS, 1); - if (LLTrace::get_frame_recording().getTotalRecording().getSampleCount(LLStatViewer::FPS)) + if (LLViewerStats::instance().getRecording().getSum(LLStatViewer::FPS)) { - sample(LLStatViewer::FPS_SAMPLE, LLTrace::get_frame_recording().getTotalRecording().getPerSec(LLStatViewer::FPS)); + sample(LLStatViewer::FPS_SAMPLE, LLTrace::get_frame_recording().getPeriodMeanPerSec(LLStatViewer::FPS)); } + add(LLStatViewer::FPS, 1); + F32 layer_bits = (F32)(gVLManager.getLandBits() + gVLManager.getWindBits() + gVLManager.getCloudBits()); add(LLStatViewer::LAYERS_KBIT, LLTrace::Bits(layer_bits)); add(LLStatViewer::OBJECT_KBIT, gObjectData); diff --git a/indra/newview/llviewertexturelist.cpp b/indra/newview/llviewertexturelist.cpp index 0066c09720..ae677f541b 100644 --- a/indra/newview/llviewertexturelist.cpp +++ b/indra/newview/llviewertexturelist.cpp @@ -617,9 +617,7 @@ void LLViewerTextureList::updateImages(F32 max_time) } cleared = FALSE; - LLTrace::Recording& recording = LLTrace::get_frame_recording().getTotalRecording(); - - LLAppViewer::getTextureFetch()->setTextureBandwidth(recording.getPerSec(LLStatViewer::TEXTURE_KBIT).value()); + LLAppViewer::getTextureFetch()->setTextureBandwidth(LLTrace::get_frame_recording().getPeriodMeanPerSec(LLStatViewer::TEXTURE_KBIT)); { using namespace LLStatViewer; diff --git a/indra/newview/pipeline.cpp b/indra/newview/pipeline.cpp index 26ceaf512a..1b5148e560 100644 --- a/indra/newview/pipeline.cpp +++ b/indra/newview/pipeline.cpp @@ -9816,7 +9816,7 @@ void LLPipeline::generateSunShadow(LLCamera& camera) { LLTrace::CountStatHandle<>* velocity_stat = LLViewerCamera::getVelocityStat(); F32 fade_amt = gFrameIntervalSeconds.value() - * llmax(LLTrace::get_frame_recording().getLastRecordingPeriod().getSum(*velocity_stat) / LLTrace::get_frame_recording().getLastRecordingPeriod().getDuration().value(), 1.0); + * llmax(LLTrace::get_frame_recording().getLastRecording().getSum(*velocity_stat) / LLTrace::get_frame_recording().getLastRecording().getDuration().value(), 1.0); //update shadow targets for (U32 i = 0; i < 2; i++) diff --git a/indra/test/CMakeLists.txt b/indra/test/CMakeLists.txt index 816f1d7175..271b7fe647 100644 --- a/indra/test/CMakeLists.txt +++ b/indra/test/CMakeLists.txt @@ -52,7 +52,6 @@ set(test_SOURCE_FILES llstreamtools_tut.cpp lltemplatemessagebuilder_tut.cpp lltut.cpp - lluuidhashmap_tut.cpp message_tut.cpp test.cpp ) diff --git a/indra/test/lluuidhashmap_tut.cpp b/indra/test/lluuidhashmap_tut.cpp deleted file mode 100644 index 9712a613f4..0000000000 --- a/indra/test/lluuidhashmap_tut.cpp +++ /dev/null @@ -1,455 +0,0 @@ -/** - * @file lluuidhashmap_tut.cpp - * @author Adroit - * @date 2007-02 - * @brief Test cases for LLUUIDHashMap - * - * $LicenseInfo:firstyear=2007&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$ - */ - -#include <tut/tut.hpp> -#include "linden_common.h" -#include "lluuidhashmap.h" -#include "llsdserialize.h" -#include "lldir.h" -#include "stringize.h" -#include <iostream> -#include <fstream> - -namespace tut -{ - class UUIDTableEntry - { - public: - UUIDTableEntry() - { - mID.setNull(); - mValue = 0; - } - - UUIDTableEntry(const LLUUID& id, U32 value) - { - mID = id; - mValue = value; - } - - ~UUIDTableEntry(){}; - - static BOOL uuidEq(const LLUUID &uuid, const UUIDTableEntry &id_pair) - { - if (uuid == id_pair.mID) - { - return TRUE; - } - return FALSE; - } - - const LLUUID& getID() { return mID; } - const U32& getValue() { return mValue; } - - protected: - LLUUID mID; - U32 mValue; - }; - - struct hashmap_test - { - }; - - typedef test_group<hashmap_test> hash_index_t; - typedef hash_index_t::object hash_index_object_t; - tut::hash_index_t tut_hash_index("hashmap_test"); - - // stress test - template<> template<> - void hash_index_object_t::test<1>() - { - set_test_name("stress test"); - // As of 2012-10-10, I (nat) have observed sporadic failures of this - // test: "set/get did not work." The trouble is that since test data - // are randomly generated with every run, it is impossible to debug a - // test failure. One is left with the uneasy suspicion that - // LLUUID::generate() can sometimes produce duplicates even within the - // moderately small number requested here. Since rerunning the test - // generally allows it to pass, it's too easy to shrug and forget it. - // The following code is intended to support reproducing such test - // failures. The idea is that, on test failure, we save the generated - // data to a canonical filename in a temp directory. Then on every - // subsequent run, we check for that filename. If it exists, we reload - // that specific data rather than generating fresh data -- which - // should presumably reproduce the same test failure. But we inform - // the user that to resume normal (random) test runs, s/he need only - // delete that file. And since it's in a temp directory, sooner or - // later the system will clean it up anyway. - const char* tempvar = "TEMP"; - const char* tempdir = getenv(tempvar); // Windows convention - if (! tempdir) - { - tempvar = "TMPDIR"; - tempdir = getenv(tempvar); // Mac convention - } - if (! tempdir) - { - // reset tempvar to the first var we check; it's just a - // recommendation - tempvar = "TEMP"; - tempdir = "/tmp"; // Posix in general - } - std::string savefile(gDirUtilp->add(tempdir, "lluuidhashmap_tut.save.txt")); - const int numElementsToCheck = 32*256*32; - std::vector<LLUUID> idList; - if ((! getenv("TEAMCITY_PROJECT_NAME")) && gDirUtilp->fileExists(savefile)) - { - // This is not a TeamCity build, and we have saved data from a - // previous failed run. Reload that data. - std::ifstream inf(savefile.c_str()); - if (! inf.is_open()) - { - fail(STRINGIZE("Although save file '" << savefile << "' exists, it cannot be opened")); - } - std::string item; - while (std::getline(inf, item)) - { - idList.push_back(LLUUID(item)); - } - std::cout << "Reloaded " << idList.size() << " items from '" << savefile << "'"; - if (idList.size() != numElementsToCheck) - { - std::cout << " (expected " << numElementsToCheck << ")"; - } - std::cout << " -- delete this file to generate new data" << std::endl; - } - else - { - // This is a TeamCity build, or (normal case) savefile does not - // exist: regenerate idList from scratch. - for (int i = 0; i < numElementsToCheck; ++i) - { - LLUUID id; - id.generate(); - idList.push_back(id); - } - } - - LLUUIDHashMap<UUIDTableEntry, 32> hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - int i; - - for (i = 0; i < idList.size(); ++i) - { - UUIDTableEntry entry(idList[i], i); - hashTable.set(idList[i], entry); - } - - try - { - for (i = 0; i < idList.size(); i++) - { - LLUUID idToCheck = idList[i]; - UUIDTableEntry entryToCheck = hashTable.get(idToCheck); - ensure_equals(STRINGIZE("set/get ID (entry " << i << ")").c_str(), - entryToCheck.getID(), idToCheck); - ensure_equals(STRINGIZE("set/get value (ID " << idToCheck << ")").c_str(), - entryToCheck.getValue(), (size_t)i); - } - - for (i = 0; i < idList.size(); i++) - { - LLUUID idToCheck = idList[i]; - if (i % 2 != 0) - { - hashTable.remove(idToCheck); - } - } - - for (i = 0; i < idList.size(); i++) - { - LLUUID idToCheck = idList[i]; - ensure("remove or check did not work", (i % 2 == 0 && hashTable.check(idToCheck)) || (i % 2 != 0 && !hashTable.check(idToCheck))); - } - } - catch (const failure&) - { - // One of the above tests failed. Try to save idList to repro with - // a later run. - std::ofstream outf(savefile.c_str()); - if (! outf.is_open()) - { - // Sigh, don't use fail() here because we want to preserve - // the original test failure. - std::cout << "Cannot open file '" << savefile - << "' to save data -- check and fix " << tempvar << std::endl; - } - else - { - // outf.is_open() - for (int i = 0; i < idList.size(); ++i) - { - outf << idList[i] << std::endl; - } - std::cout << "Saved " << idList.size() << " entries to '" << savefile - << "' -- rerun test to debug with these" << std::endl; - } - // re-raise the same exception -- we WANT this test failure to - // be reported! We just needed to save the data on the way out. - throw; - } - } - - // test removing all but one element. - template<> template<> - void hash_index_object_t::test<2>() - { - LLUUIDHashMap<UUIDTableEntry, 2> hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 5; - std::vector<LLUUID> idList(numElementsToCheck*10); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - ensure("getLength failed", hashTable.getLength() == numElementsToCheck); - - // remove all but the last element - for (i = 0; i < numElementsToCheck-1; i++) - { - LLUUID idToCheck = idList[i]; - hashTable.remove(idToCheck); - } - - // there should only be one element left now. - ensure("getLength failed", hashTable.getLength() == 1); - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - if (i != numElementsToCheck - 1) - { - ensure("remove did not work", hashTable.check(idToCheck) == FALSE); - } - else - { - UUIDTableEntry entryToCheck = hashTable.get(idToCheck); - ensure("remove did not work", entryToCheck.getID() == idToCheck && entryToCheck.getValue() == (size_t)i); - } - } - } - - // test overriding of value already set. - template<> template<> - void hash_index_object_t::test<3>() - { - LLUUIDHashMap<UUIDTableEntry, 5> hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 10; - std::vector<LLUUID> idList(numElementsToCheck); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id = idList[i]; - // set new entry with value = i+numElementsToCheck - UUIDTableEntry entry(id, i+numElementsToCheck); - hashTable.set(id, entry); - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - UUIDTableEntry entryToCheck = hashTable.get(idToCheck); - ensure("set/get did not work", entryToCheck.getID() == idToCheck && entryToCheck.getValue() == (size_t)(i+numElementsToCheck)); - } - } - - // test removeAll() - template<> template<> - void hash_index_object_t::test<4>() - { - LLUUIDHashMap<UUIDTableEntry, 5> hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 10; - std::vector<LLUUID> idList(numElementsToCheck); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - hashTable.removeAll(); - ensure("removeAll failed", hashTable.getLength() == 0); - } - - - // test sparse map - force it by creating 256 entries that fall into 256 different nodes - template<> template<> - void hash_index_object_t::test<5>() - { - LLUUIDHashMap<UUIDTableEntry, 2> hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 256; - std::vector<LLUUID> idList(numElementsToCheck); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - // LLUUIDHashMap uses mData[0] to pick the bucket - // overwrite mData[0] so that it ranges from 0 to 255 - id.mData[0] = i; - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - UUIDTableEntry entryToCheck = hashTable.get(idToCheck); - ensure("set/get did not work for sparse map", entryToCheck.getID() == idToCheck && entryToCheck.getValue() == (size_t)i); - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - if (i % 2 != 0) - { - hashTable.remove(idToCheck); - } - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - ensure("remove or check did not work for sparse map", (i % 2 == 0 && hashTable.check(idToCheck)) || (i % 2 != 0 && !hashTable.check(idToCheck))); - } - } - - // iterator - template<> template<> - void hash_index_object_t::test<6>() - { - LLUUIDHashMap<UUIDTableEntry, 2> hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - LLUUIDHashMapIter<UUIDTableEntry, 2> hashIter(&hashTable); - const int numElementsToCheck = 256; - std::vector<LLUUID> idList(numElementsToCheck); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - // LLUUIDHashMap uses mData[0] to pick the bucket - // overwrite mData[0] so that it ranges from 0 to 255 - // to create a sparse map - id.mData[0] = i; - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - hashIter.first(); - int numElementsIterated = 0; - while(!hashIter.done()) - { - numElementsIterated++; - UUIDTableEntry tableEntry = *hashIter; - LLUUID id = tableEntry.getID(); - hashIter.next(); - ensure("Iteration failed for sparse map", tableEntry.getValue() < (size_t)numElementsToCheck && idList[tableEntry.getValue()] == tableEntry.getID()); - } - - ensure("iteration count failed", numElementsIterated == numElementsToCheck); - } - - // remove after middle of iteration - template<> template<> - void hash_index_object_t::test<7>() - { - LLUUIDHashMap<UUIDTableEntry, 2> hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - LLUUIDHashMapIter<UUIDTableEntry, 2> hashIter(&hashTable); - const int numElementsToCheck = 256; - std::vector<LLUUID> idList(numElementsToCheck); - int i; - - LLUUID uuidtoSearch; - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - // LLUUIDHashMap uses mData[0] to pick the bucket - // overwrite mData[0] so that it ranges from 0 to 255 - // to create a sparse map - id.mData[0] = i; - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - - // pick uuid somewhere in the middle - if (i == 5) - { - uuidtoSearch = id; - } - } - - hashIter.first(); - int numElementsIterated = 0; - while(!hashIter.done()) - { - numElementsIterated++; - UUIDTableEntry tableEntry = *hashIter; - LLUUID id = tableEntry.getID(); - if (uuidtoSearch == id) - { - break; - } - hashIter.next(); - } - - // current iterator implementation will not allow any remove operations - // until ALL elements have been iterated over. this seems to be - // an unnecessary restriction. Iterator should have a method to - // reset() its state so that further operations (inckuding remove) - // can be performed on the HashMap without having to iterate thru - // all the remaining nodes. - -// hashIter.reset(); -// hashTable.remove(uuidtoSearch); -// ensure("remove after iteration reset failed", hashTable.check(uuidtoSearch) == FALSE); - } -} |