From ae028e79872f166db8e514ca3b442c7807d6ebdb Mon Sep 17 00:00:00 2001 From: Richard Linden Date: Thu, 11 Apr 2013 19:08:57 -0700 Subject: removed unused data structures --- indra/llcharacter/llmotioncontroller.h | 1 - indra/llcommon/CMakeLists.txt | 5 - indra/llcommon/llptrskiplist.h | 724 ---------------- indra/llcommon/llptrskipmap.h | 1239 ---------------------------- indra/llcommon/llskiplist.h | 517 ------------ indra/llcommon/llskipmap.h | 1020 ----------------------- indra/llcommon/lluuidhashmap.h | 583 ------------- indra/newview/llviewerprecompiledheaders.h | 1 - indra/test/CMakeLists.txt | 1 - indra/test/lluuidhashmap_tut.cpp | 455 ---------- 10 files changed, 4546 deletions(-) delete mode 100644 indra/llcommon/llptrskiplist.h delete mode 100644 indra/llcommon/llptrskipmap.h delete mode 100644 indra/llcommon/llskiplist.h delete mode 100644 indra/llcommon/llskipmap.h delete mode 100644 indra/llcommon/lluuidhashmap.h delete mode 100644 indra/test/lluuidhashmap_tut.cpp 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 #include -#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/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 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 -LLPtrSkipList::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 -LLPtrSkipList::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 -inline LLPtrSkipList::~LLPtrSkipList() -{ - removeAllNodes(); -} - -template -inline void LLPtrSkipList::setInsertFirst(BOOL (*insert_first)(const DATA_TYPE *first, const DATA_TYPE *second)) -{ - mInsertFirst = insert_first; -} - -template -inline void LLPtrSkipList::setEquals(BOOL (*equals)(const DATA_TYPE *first, const DATA_TYPE *second)) -{ - mEquals = equals; -} - -template -inline BOOL LLPtrSkipList::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 -inline BOOL LLPtrSkipList::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 -inline S32 LLPtrSkipList::getLength() -{ - U32 length = 0; - for (LLPtrSkipNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) - { - length++; - } - return length; -} - -template -inline BOOL LLPtrSkipList::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 -inline BOOL LLPtrSkipList::moveData(const DATA_TYPE *data, LLPtrSkipList *newlist, BOOL b_sort) -{ - BOOL removed = removeData(data); - BOOL added = newlist->addData(data); - return removed && added; -} - -template -inline BOOL LLPtrSkipList::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 -inline void LLPtrSkipList::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 -inline BOOL LLPtrSkipList::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 -inline void LLPtrSkipList::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 -inline void LLPtrSkipList::resetList() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_TYPE *LLPtrSkipList::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 -inline DATA_TYPE *LLPtrSkipList::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 -inline void LLPtrSkipList::removeCurrentData() -{ - if (mCurrentOperatingp) - { - removeData(mCurrentOperatingp->mData); - } -} - -// delete the Node at mCurentOperatingp -// leave mCurrentp and mCurentOperatingp on the next entry -template -inline void LLPtrSkipList::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 -inline DATA_TYPE *LLPtrSkipList::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 -inline BOOL LLPtrSkipList::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 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 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 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 mHead; - LLPtrSkipMapNode *mUpdate[BINARY_DEPTH]; - LLPtrSkipMapNode *mCurrentp; - LLPtrSkipMapNode *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 -inline LLPtrSkipMap::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 -inline LLPtrSkipMap::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 -inline LLPtrSkipMap::~LLPtrSkipMap() -{ - removeAllData(); -} - -template -inline void LLPtrSkipMap::setInsertFirst(insert_func insert_first) -{ - mInsertFirst = insert_first; -} - -template -inline void LLPtrSkipMap::setEquals(equals_func equals) -{ - mEquals = equals; -} - -template -inline DATA_T &LLPtrSkipMap::addData(const INDEX_T &index, DATA_T datap) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 *snode - = new LLPtrSkipMapNode(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 -inline DATA_T &LLPtrSkipMap::addData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 *snode - = new LLPtrSkipMapNode(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 -inline DATA_T &LLPtrSkipMap::getData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 *snode - = new LLPtrSkipMapNode(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 -inline BOOL LLPtrSkipMap::getInterval(const INDEX_T &index, - INDEX_T &index_before, - INDEX_T &index_after, - DATA_T &data_before, - DATA_T &data_after) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 -inline DATA_T &LLPtrSkipMap::operator[](const INDEX_T &index) -{ - - return getData(index); -} - -// If index present, returns data. -// If index not present, adds and returns NULL. -template -inline DATA_T &LLPtrSkipMap::getData(const INDEX_T &index, BOOL &b_new_entry) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 -inline BOOL LLPtrSkipMap::checkData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 -inline BOOL LLPtrSkipMap::checkKey(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 -inline DATA_T LLPtrSkipMap::getIfThere(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 -inline INDEX_T LLPtrSkipMap::reverseLookup(const DATA_T datap) -{ - LLPtrSkipMapNode *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 -inline S32 LLPtrSkipMap::getLength() -{ - U32 length = 0; - LLPtrSkipMapNode* temp; - for (temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) - { - length++; - } - - return length; -} - -template -inline BOOL LLPtrSkipMap::removeData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 -inline BOOL LLPtrSkipMap::deleteData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *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 -void LLPtrSkipMap::removeAllData() -{ - LLPtrSkipMapNode *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 -inline void LLPtrSkipMap::deleteAllData() -{ - LLPtrSkipMapNode *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 -inline void LLPtrSkipMap::resetList() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - - -// return the data currently pointed to -template -inline DATA_T LLPtrSkipMap::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 -inline DATA_T LLPtrSkipMap::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 -inline DATA_T LLPtrSkipMap::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 -inline INDEX_T LLPtrSkipMap::getNextKey() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mIndex; - } - else - { - return mHead.mIndex; - } -} - -// return the key currently pointed to -template -inline INDEX_T LLPtrSkipMap::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 -inline void LLPtrSkipMap::removeCurrentData() -{ - if (mCurrentOperatingp) - { - removeData(mCurrentOperatingp->mIndex); - } -} - -template -inline void LLPtrSkipMap::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 -inline DATA_T LLPtrSkipMap::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 -inline INDEX_T LLPtrSkipMap::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 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 -inline void LLSkipList::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 -inline LLSkipList::LLSkipList() -: mInsertFirst(NULL), - mEquals(defaultEquals) -{ - init(); -} - -// basic constructor including sorter -template -inline LLSkipList::LLSkipList(insert_func insert, - equals_func equals) -: mInsertFirst(insert), - mEquals(equals) -{ - init(); -} - -template -inline LLSkipList::~LLSkipList() -{ - removeAllNodes(); -} - -template -inline void LLSkipList::setInsertFirst(insert_func insert_first) -{ - mInsertFirst = insert_first; -} - -template -inline void LLSkipList::setEquals(equals_func equals) -{ - mEquals = equals; -} - -template -inline BOOL LLSkipList::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 -inline BOOL LLSkipList::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 -inline S32 LLSkipList::getLength() const -{ - U32 length = 0; - for (LLSkipNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) - { - length++; - } - return length; -} - - -template -inline BOOL LLSkipList::moveData(const DATA_TYPE& data, LLSkipList *newlist) -{ - BOOL removed = removeData(data); - BOOL added = newlist->addData(data); - return removed && added; -} - - -template -inline BOOL LLSkipList::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 -inline void LLSkipList::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 -inline void LLSkipList::resetList() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_TYPE LLSkipList::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 -inline DATA_TYPE LLSkipList::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 -inline void LLSkipList::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 -inline DATA_TYPE LLSkipList::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 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 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 -inline LLSkipMap::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 -inline LLSkipMap::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 -inline LLSkipMap::~LLSkipMap() -{ - removeAllData(); -} - -template -inline void LLSkipMap::setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second)) -{ - mInsertFirst = insert_first; -} - -template -inline void LLSkipMap::setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)) -{ - mEquals = equals; -} - -template -inline DATA_TYPE &LLSkipMap::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 -inline DATA_TYPE &LLSkipMap::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 -inline DATA_TYPE &LLSkipMap::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 -inline DATA_TYPE &LLSkipMap::operator[](const INDEX_TYPE &index) -{ - - return getData(index); -} - -// If index present, returns data. -// If index not present, adds and returns NULL. -template -inline DATA_TYPE &LLSkipMap::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 -inline BOOL LLSkipMap::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 -inline BOOL LLSkipMap::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 -inline DATA_TYPE LLSkipMap::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 -inline INDEX_TYPE LLSkipMap::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 -inline S32 LLSkipMap::getLength() -{ - U32 length = 0; - for (LLSkipMapNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) - { - length++; - } - - return length; -} - -template -inline BOOL LLSkipMap::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 -void LLSkipMap::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 -inline void LLSkipMap::resetList() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - - -// return the data currently pointed to -template -inline DATA_TYPE LLSkipMap::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 -inline DATA_TYPE LLSkipMap::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 -inline DATA_TYPE LLSkipMap::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 -inline INDEX_TYPE LLSkipMap::getNextKey() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mIndex; - } - else - { - return mHead.mIndex; - } -} - -// return the key currently pointed to -template -inline INDEX_TYPE LLSkipMap::getCurrentKeyWithoutIncrement() -{ - if (mCurrentOperatingp) - { - return mCurrentOperatingp->mIndex; - } - else - { - // See comment for getNextData() - return INDEX_TYPE(); - } -} - -template -inline BOOL LLSkipMap::notDone() const -{ - if (mCurrentOperatingp) - { - return TRUE; - } - else - { - return FALSE; - } -} - - -// remove the Node at mCurentOperatingp -// leave mCurrentp and mCurentOperatingp on the next entry -template -inline void LLSkipMap::removeCurrentData() -{ - if (mCurrentOperatingp) - { - removeData(mCurrentOperatingp->mIndex); - } -} - -template -inline void LLSkipMap::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 -inline DATA_TYPE LLSkipMap::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 -inline INDEX_TYPE LLSkipMap::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/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 foo(test_equals); - LLUUIDHashMapIter bar(&foo); - - LLDynamicArray 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 LLUUIDHashNode -{ -public: - LLUUIDHashNode(); - -public: - S32 mCount; - U8 mKey[SIZE]; - DATA mData[SIZE]; - LLUUIDHashNode *mNextNodep; -}; - - -// -// LLUUIDHashNode implementation -// -template -LLUUIDHashNode::LLUUIDHashNode() -{ - mCount = 0; - mNextNodep = NULL; -} - - -template -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 mNodes[256]; - - S32 mIterCount; -protected: - DATA_TYPE mNull; -}; - - -// -// LLUUIDHashMap implementation -// - -template -LLUUIDHashMap::LLUUIDHashMap(BOOL (*equals)(const LLUUID &uuid, const DATA_TYPE &data), - const DATA_TYPE &null_data) -: mEquals(equals), - mIterCount(0), - mNull(null_data) -{ } - -template -LLUUIDHashMap::~LLUUIDHashMap() -{ - removeAll(); -} - -template -void LLUUIDHashMap::removeAll() -{ - S32 bin; - for (bin = 0; bin < 256; bin++) - { - LLUUIDHashNode* 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* 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 -inline S32 LLUUIDHashMap::getLength() const -{ - S32 count = 0; - S32 bin; - for (bin = 0; bin < 256; bin++) - { - LLUUIDHashNode* nodep = (LLUUIDHashNode*) &mNodes[bin]; - while (nodep) - { - count += nodep->mCount; - nodep = nodep->mNextNodep; - } - } - return count; -} - -template -inline DATA_TYPE &LLUUIDHashMap::get(const LLUUID &uuid) -{ - LLUUIDHashNode* 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 -inline BOOL LLUUIDHashMap::check(const LLUUID &uuid) const -{ - const LLUUIDHashNode* 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 -inline DATA_TYPE &LLUUIDHashMap::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* 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; - 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 -inline BOOL LLUUIDHashMap::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 *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 *prevp = &mNodes[uuid.mData[0]]; - LLUUIDHashNode *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 LLUUIDHashMapIter -{ -public: - LLUUIDHashMapIter(LLUUIDHashMap *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 *mHashMapp; - LLUUIDHashNode *mCurHashNodep; - - S32 mCurHashMapNodeNum; - S32 mCurHashNodeKey; - - DATA_TYPE mNull; -}; - - -// -// LLUUIDHashMapIter Implementation -// -template -LLUUIDHashMapIter::LLUUIDHashMapIter(LLUUIDHashMap *hash_mapp) -{ - mHashMapp = hash_mapp; - mCurHashNodep = NULL; - mCurHashMapNodeNum = 0; - mCurHashNodeKey = 0; -} - -template -LLUUIDHashMapIter::~LLUUIDHashMapIter() -{ - reset(); -} - -template -inline void LLUUIDHashMapIter::reset() -{ - if (mCurHashNodep) - { - // We're partway through an iteration, we can clean up now - mHashMapp->mIterCount--; - mCurHashNodep = NULL; - } -} - -template -inline void LLUUIDHashMapIter::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 -inline BOOL LLUUIDHashMapIter::done() const -{ - return mCurHashNodep ? FALSE : TRUE; -} - -template -inline void LLUUIDHashMapIter::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/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/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 -#include "linden_common.h" -#include "lluuidhashmap.h" -#include "llsdserialize.h" -#include "lldir.h" -#include "stringize.h" -#include -#include - -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 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 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 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 5; - std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 10; - std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 10; - std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 256; - std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - LLUUIDHashMapIter hashIter(&hashTable); - const int numElementsToCheck = 256; - std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - LLUUIDHashMapIter hashIter(&hashTable); - const int numElementsToCheck = 256; - std::vector 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); - } -} -- cgit v1.2.3