diff options
Diffstat (limited to 'indra/llcommon/lllocalidhashmap.h')
| -rwxr-xr-x | indra/llcommon/lllocalidhashmap.h | 895 |
1 files changed, 0 insertions, 895 deletions
diff --git a/indra/llcommon/lllocalidhashmap.h b/indra/llcommon/lllocalidhashmap.h deleted file mode 100755 index 8f4f91a560..0000000000 --- a/indra/llcommon/lllocalidhashmap.h +++ /dev/null @@ -1,895 +0,0 @@ -/** - * @file lllocalidhashmap.h - * @brief Map specialized for dealing with local ids - * - * $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_LLLOCALIDHASHMAP_H -#define LL_LLLOCALIDHASHMAP_H - -#include "stdtypes.h" -#include "llerror.h" - -const S32 MAX_ITERS = 4; -// LocalID hash map - -// -// LLLocalIDHashNode -// - -template <class DATA, int SIZE> -class LLLocalIDHashNode -{ -public: - LLLocalIDHashNode(); - -public: - S32 mCount; - U32 mKey[SIZE]; - DATA mData[SIZE]; - LLLocalIDHashNode<DATA, SIZE> *mNextNodep; -}; - - -// -// LLLocalIDHashNode implementation -// -template <class DATA, int SIZE> -LLLocalIDHashNode<DATA, SIZE>::LLLocalIDHashNode() -{ - mCount = 0; - mNextNodep = NULL; -} - -// -// LLLocalIDHashMapIter -// -template <class DATA_TYPE, int SIZE> -class LLLocalIDHashMap; - -template <class DATA_TYPE, int SIZE> -class LLLocalIDHashMapIter -{ -public: - LLLocalIDHashMapIter(LLLocalIDHashMap<DATA_TYPE, SIZE> *hash_mapp); - ~LLLocalIDHashMapIter(); - - void setMap(LLLocalIDHashMap<DATA_TYPE, SIZE> *hash_mapp); - inline void first(); - inline void next(); - inline DATA_TYPE& current(); // *NOTE: Deprecate? Phoenix 2005-04-15 - inline BOOL done() const; - inline S32 currentBin() const; - inline void setBin(S32 bin); - - DATA_TYPE& operator*() const - { - return mCurHashNodep->mData[mCurHashNodeKey]; - } - DATA_TYPE* operator->() const - { - return &(operator*()); - } - - LLLocalIDHashMap<DATA_TYPE, SIZE> *mHashMapp; - LLLocalIDHashNode<DATA_TYPE, SIZE> *mCurHashNodep; - - S32 mCurHashMapNodeNum; - S32 mCurHashNodeKey; - - DATA_TYPE mNull; - - S32 mIterID; -}; - - - -template <class DATA_TYPE, int SIZE> -class LLLocalIDHashMap -{ -public: - friend class LLLocalIDHashMapIter<DATA_TYPE, SIZE>; - - LLLocalIDHashMap(); // DO NOT use this unless you explicitly setNull, or the data type constructs a "null" - // object by default - // basic constructor including sorter - LLLocalIDHashMap(const DATA_TYPE &null_data); - // Hack, this should really be a const ref, but I'm not doing it that way because the sim - // usually uses pointers. - ~LLLocalIDHashMap(); - - inline DATA_TYPE &get(const U32 local_id); - inline BOOL check(const U32 local_id) const; - inline DATA_TYPE &set(const U32 local_id, const DATA_TYPE data); - inline BOOL remove(const U32 local_id); - void removeAll(); - - void setNull(const DATA_TYPE data) { mNull = data; } - - inline S32 getLength() const; // Warning, NOT O(1!) - - void dumpIter(); - void dumpBin(U32 bin); - -protected: - // Only used by the iterator. - void addIter(LLLocalIDHashMapIter<DATA_TYPE, SIZE> *iter); - void removeIter(LLLocalIDHashMapIter<DATA_TYPE, SIZE> *iter); - - // Remove the item and shift all items afterward down the list, - // fixing up iterators as we go. - BOOL removeWithShift(const U32 local_id); - -protected: - LLLocalIDHashNode<DATA_TYPE, SIZE> mNodes[256]; - - S32 mIterCount; - LLLocalIDHashMapIter<DATA_TYPE, SIZE> *mIters[MAX_ITERS]; - - DATA_TYPE mNull; -}; - - -// -// LLLocalIDHashMap implementation -// - -template <class DATA_TYPE, int SIZE> -LLLocalIDHashMap<DATA_TYPE, SIZE>::LLLocalIDHashMap() -: mIterCount(0), - mNull() -{ - S32 i; - for (i = 0; i < MAX_ITERS; i++) - { - mIters[i] = NULL; - } -} - -template <class DATA_TYPE, int SIZE> -LLLocalIDHashMap<DATA_TYPE, SIZE>::LLLocalIDHashMap(const DATA_TYPE &null_data) -: mIterCount(0), - mNull(null_data) -{ - S32 i; - for (i = 0; i < MAX_ITERS; i++) - { - mIters[i] = NULL; - } -} - -template <class DATA_TYPE, int SIZE> -LLLocalIDHashMap<DATA_TYPE, SIZE>::~LLLocalIDHashMap() -{ - S32 i; - for (i = 0; i < MAX_ITERS; i++) - { - if (mIters[i]) - { - mIters[i]->mHashMapp = NULL; - mIterCount--; - } - } - removeAll(); -} - -template <class DATA_TYPE, int SIZE> -void LLLocalIDHashMap<DATA_TYPE, SIZE>::removeAll() -{ - S32 bin; - for (bin = 0; bin < 256; bin++) - { - LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[bin]; - - BOOL first = TRUE; - do // First node guaranteed to be there - { - 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. - - LLLocalIDHashNode<DATA_TYPE, SIZE>* curp = nodep; - nodep = nodep->mNextNodep; - - // Delete the node if it's not the first node - if (first) - { - first = FALSE; - curp->mNextNodep = NULL; - } - else - { - delete curp; - } - } while (nodep); - } -} - -template <class DATA_TYPE, int SIZE> -void LLLocalIDHashMap<DATA_TYPE, SIZE>::dumpIter() -{ - std::cout << "Hash map with " << mIterCount << " iterators" << std::endl; - - std::cout << "Hash Map Iterators:" << std::endl; - S32 i; - for (i = 0; i < MAX_ITERS; i++) - { - if (mIters[i]) - { - llinfos << i << " " << mIters[i]->mCurHashNodep << " " << mIters[i]->mCurHashNodeKey << llendl; - } - else - { - llinfos << i << "null" << llendl; - } - } -} - -template <class DATA_TYPE, int SIZE> -void LLLocalIDHashMap<DATA_TYPE, SIZE>::dumpBin(U32 bin) -{ - std::cout << "Dump bin " << bin << std::endl; - - LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[bin]; - S32 node = 0; - do // First node guaranteed to be there. - { - std::cout << "Bin " << bin - << " node " << node - << " count " << nodep->mCount - << " contains " << std::flush; - - S32 i; - for (i = 0; i < nodep->mCount; i++) - { - std::cout << nodep->mData[i] << " " << std::flush; - } - - std::cout << std::endl; - - nodep = nodep->mNextNodep; - node++; - } while (nodep); -} - -template <class DATA_TYPE, int SIZE> -inline S32 LLLocalIDHashMap<DATA_TYPE, SIZE>::getLength() const -{ - S32 count = 0; - S32 bin; - for (bin = 0; bin < 256; bin++) - { - const LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[bin]; - while (nodep) - { - count += nodep->mCount; - nodep = nodep->mNextNodep; - } - } - return count; -} - -template <class DATA_TYPE, int SIZE> -inline DATA_TYPE &LLLocalIDHashMap<DATA_TYPE, SIZE>::get(const U32 local_id) -{ - LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[local_id & 0xff]; - - do // First node guaranteed to be there - { - S32 i; - const S32 count = nodep->mCount; - - // Iterate through all members of this node - for (i = 0; i < count; i++) - { - if (nodep->mKey[i] == local_id) - { - // We found it. - return nodep->mData[i]; - } - } - - // Done with all objects in this node, go to the next. - nodep = nodep->mNextNodep; - } while (nodep); - - return mNull; -} - - -template <class DATA_TYPE, int SIZE> -inline BOOL LLLocalIDHashMap<DATA_TYPE, SIZE>::check(const U32 local_id) const -{ - const LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[local_id & 0xff]; - - do // First node guaranteed to be there - { - S32 i; - const S32 count = nodep->mCount; - - // Iterate through all members of this node - for (i = 0; i < count; i++) - { - if (nodep->mKey[i] == local_id) - { - // We found it. - return TRUE; - } - } - - // Done with all objects in this node, go to the next. - nodep = nodep->mNextNodep; - } while (nodep); - - // Didn't find anything - return FALSE; -} - - -template <class DATA_TYPE, int SIZE> -inline DATA_TYPE &LLLocalIDHashMap<DATA_TYPE, SIZE>::set(const U32 local_id, 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. - - LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[local_id & 0xff]; - - while (1) - { - const S32 count = nodep->mCount; - - S32 i; - for (i = 0; i < count; i++) - { - if (nodep->mKey[i] == local_id) - { - // 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] = local_id; - 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 LLLocalIDHashNode<DATA_TYPE, SIZE>; - nodep->mNextNodep->mKey[0] = local_id; - nodep->mNextNodep->mData[0] = data; - nodep->mNextNodep->mCount = 1; - - return nodep->mNextNodep->mData[0]; - } - } - - // No match on this node, go to the next - nodep = nodep->mNextNodep; - } -} - - -template <class DATA_TYPE, int SIZE> -inline BOOL LLLocalIDHashMap<DATA_TYPE, SIZE>::remove(const U32 local_id) -{ - // 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. - - const S32 node_index = local_id & 0xff; - - LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[node_index]; - - // A modification of the standard search algorithm. - do // First node guaranteed to be there - { - const S32 count = nodep->mCount; - - S32 i; - for (i = 0; i < count; i++) - { - if (nodep->mKey[i] == local_id) - { - // If we're removing the item currently pointed to by one - // or more iterators, we can just swap in the last item - // and back the iterator(s) up by one. - // Otherwise, we need to do a slow and safe shift of all - // items back to one position to fill the hole and fix up - // all iterators we find. - BOOL need_shift = FALSE; - S32 cur_iter; - if (mIterCount) - { - for (cur_iter = 0; cur_iter < MAX_ITERS; cur_iter++) - { - if (mIters[cur_iter]) - { - // We only care if the hash map node is on the one - // that we're working on. If it's before, we've already - // traversed it, if it's after, changing the order doesn't - // matter. - if (mIters[cur_iter]->mCurHashMapNodeNum == node_index) - { - if ((mIters[cur_iter]->mCurHashNodep == nodep) - && (mIters[cur_iter]->mCurHashNodeKey == i)) - { - // it's on the one we're deleting, we'll - // fix the iterator quickly below. - } - else - { - // We're trying to remove an item on this - // iterator's chain that this - // iterator doesn't point to! We need to do - // the slow remove-and-shift-down case. - need_shift = TRUE; - } - } - } - } - } - - // Removing an item that isn't pointed to by all iterators - if (need_shift) - { - return removeWithShift(local_id); - } - - // Fix the iterators that point to this node/i pair, the - // one we're deleting - for (cur_iter = 0; cur_iter < MAX_ITERS; cur_iter++) - { - if (mIters[cur_iter]) - { - // We only care if the hash map node is on the one - // that we're working on. If it's before, we've already - // traversed it, if it's after, changing the order doesn't - // matter. - if (mIters[cur_iter]->mCurHashMapNodeNum == node_index) - { - if ((mIters[cur_iter]->mCurHashNodep == nodep) - && (mIters[cur_iter]->mCurHashNodeKey == i)) - { - // We can handle the case where we're deleting - // the element we're on trivially (sort of). - if (nodep->mCount > 1) - { - // If we're not going to delete this node, - // it's OK. - mIters[cur_iter]->mCurHashNodeKey--; - } - else - { - // We're going to delete this node, because this - // is the last element on it. - - // Find the next node, and then back up one. - mIters[cur_iter]->next(); - mIters[cur_iter]->mCurHashNodeKey--; - } - } - } - } - } - - // 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. - - LLLocalIDHashNode<DATA_TYPE, SIZE> *prevp = &mNodes[node_index]; - LLLocalIDHashNode<DATA_TYPE, SIZE> *lastp = prevp; - - // Find the last and next-to-last - while (lastp->mNextNodep) - { - prevp = lastp; - lastp = lastp->mNextNodep; - } - - // First, swap in the last to the current location. - nodep->mKey[i] = lastp->mKey[lastp->mCount - 1]; - nodep->mData[i] = lastp->mData[lastp->mCount - 1]; - - // Now, we delete the entry - lastp->mCount--; - lastp->mData[lastp->mCount] = mNull; - - if (!lastp->mCount) - { - // We deleted the last element! - if (lastp != &mNodes[local_id & 0xff]) - { - // 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; - } while (nodep); - - return FALSE; -} - -template <class DATA_TYPE, int SIZE> -BOOL LLLocalIDHashMap<DATA_TYPE, SIZE>::removeWithShift(const U32 local_id) -{ - const S32 node_index = local_id & 0xFF; - LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[node_index]; - LLLocalIDHashNode<DATA_TYPE, SIZE>* prevp = NULL; - BOOL found = FALSE; - - do // First node guaranteed to be there - { - const S32 count = nodep->mCount; - S32 i; - for (i = 0; i < count; i++) - { - if (nodep->mKey[i] == local_id) - { - // Found the item. Start shifting items from later - // in the list over this item. - found = TRUE; - } - - if (found) - { - // If there is an iterator on this node, we need to - // back it up. - S32 cur_iter; - for (cur_iter = 0; cur_iter <MAX_ITERS; cur_iter++) - { - LLLocalIDHashMapIter<DATA_TYPE, SIZE>* iter; - iter = mIters[cur_iter]; - // If an iterator is on this node,i pair, then back it up. - if (iter - && iter->mCurHashMapNodeNum == node_index - && iter->mCurHashNodep == nodep - && iter->mCurHashNodeKey == i) - { - if (i > 0) - { - // Don't need to move iterator nodep, since - // we're in the same node. - iter->mCurHashNodeKey--; - } - else if (prevp) - { - // need to go the previous node, last item - iter->mCurHashNodep = prevp; - iter->mCurHashNodeKey = prevp->mCount - 1; - } - else - { - // we're on the first item in the list, but - // need to go back anyhow. - - // BUG: If this deletion empties the list, - // iter->done() will be wrong until - // iter->next() is called. - iter->mCurHashNodeKey = -1; - } - } - } - - // Copy data from the next position into this position. - if (i < count-1) - { - // we're not on the last item in the node, - // so we can copy within the node - nodep->mKey[i] = nodep->mKey[i+1]; - nodep->mData[i] = nodep->mData[i+1]; - } - else if (nodep->mNextNodep) - { - // we're on the last item in the node, - // but there's a next node we can copy from - nodep->mKey[i] = nodep->mNextNodep->mKey[0]; - nodep->mData[i] = nodep->mNextNodep->mData[0]; - } - else - { - // We're on the last position in the list. - // No one to copy from. Replace with nothing. - nodep->mKey[i] = 0; - nodep->mData[i] = mNull; - } - } - } - - // Last node in chain, so delete the last node - if (found - && !nodep->mNextNodep) - { - // delete the last item off the last node - nodep->mCount--; - - if (nodep->mCount == 0) - { - // We deleted the last element! - if (nodep != &mNodes[node_index]) - { - // Always have a prevp if we're not the head. - llassert(prevp); - - // 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 nodep; - nodep = NULL; - } - } - - // Deleted last item in chain, so we're done. - return found; - } - - prevp = nodep; - nodep = nodep->mNextNodep; - } while (nodep); - - return found; -} - -template <class DATA_TYPE, int SIZE> -void LLLocalIDHashMap<DATA_TYPE, SIZE>::removeIter(LLLocalIDHashMapIter<DATA_TYPE, SIZE> *iter) -{ - S32 i; - for (i = 0; i < MAX_ITERS; i++) - { - if (mIters[i] == iter) - { - mIters[i] = NULL; - mIterCount--; - return; - } - } - llerrs << "Iterator " << iter << " not found for removal in hash map!" << llendl; -} - -template <class DATA_TYPE, int SIZE> -void LLLocalIDHashMap<DATA_TYPE, SIZE>::addIter(LLLocalIDHashMapIter<DATA_TYPE, SIZE> *iter) -{ - S32 i; - for (i = 0; i < MAX_ITERS; i++) - { - if (mIters[i] == NULL) - { - mIters[i] = iter; - mIterCount++; - return; - } - } - llerrs << "More than " << MAX_ITERS << " iterating over a map simultaneously!" << llendl; -} - - - -// -// LLLocalIDHashMapIter Implementation -// -template <class DATA_TYPE, int SIZE> -LLLocalIDHashMapIter<DATA_TYPE, SIZE>::LLLocalIDHashMapIter(LLLocalIDHashMap<DATA_TYPE, SIZE> *hash_mapp) -{ - mHashMapp = NULL; - setMap(hash_mapp); -} - -template <class DATA_TYPE, int SIZE> -LLLocalIDHashMapIter<DATA_TYPE, SIZE>::~LLLocalIDHashMapIter() -{ - if (mHashMapp) - { - mHashMapp->removeIter(this); - } -} - -template <class DATA_TYPE, int SIZE> -void LLLocalIDHashMapIter<DATA_TYPE, SIZE>::setMap(LLLocalIDHashMap<DATA_TYPE, SIZE> *hash_mapp) -{ - if (mHashMapp) - { - mHashMapp->removeIter(this); - } - mHashMapp = hash_mapp; - if (mHashMapp) - { - mHashMapp->addIter(this); - } - - mCurHashNodep = NULL; - mCurHashMapNodeNum = -1; - mCurHashNodeKey = 0; -} - -template <class DATA_TYPE, int SIZE> -inline void LLLocalIDHashMapIter<DATA_TYPE, SIZE>::first() -{ - // Iterate through until we find the first non-empty node; - S32 i; - for (i = 0; i < 256; i++) - { - if (mHashMapp->mNodes[i].mCount) - { - - mCurHashNodep = &mHashMapp->mNodes[i]; - mCurHashMapNodeNum = i; - mCurHashNodeKey = 0; - //return mCurHashNodep->mData[0]; - return; - } - } - - // Completely empty! - mCurHashNodep = NULL; - //return mNull; - return; -} - -template <class DATA_TYPE, int SIZE> -inline BOOL LLLocalIDHashMapIter<DATA_TYPE, SIZE>::done() const -{ - return mCurHashNodep ? FALSE : TRUE; -} - -template <class DATA_TYPE, int SIZE> -inline S32 LLLocalIDHashMapIter<DATA_TYPE, SIZE>::currentBin() const -{ - if ( (mCurHashMapNodeNum > 255) - ||(mCurHashMapNodeNum < 0)) - { - return 0; - } - else - { - return mCurHashMapNodeNum; - } -} - -template <class DATA_TYPE, int SIZE> -inline void LLLocalIDHashMapIter<DATA_TYPE, SIZE>::setBin(S32 bin) -{ - // Iterate through until we find the first non-empty node; - S32 i; - bin = llclamp(bin, 0, 255); - for (i = bin; i < 256; i++) - { - if (mHashMapp->mNodes[i].mCount) - { - - mCurHashNodep = &mHashMapp->mNodes[i]; - mCurHashMapNodeNum = i; - mCurHashNodeKey = 0; - return; - } - } - for (i = 0; i < bin; i++) - { - if (mHashMapp->mNodes[i].mCount) - { - - mCurHashNodep = &mHashMapp->mNodes[i]; - mCurHashMapNodeNum = i; - mCurHashNodeKey = 0; - return; - } - } - // Completely empty! - mCurHashNodep = NULL; -} - -template <class DATA_TYPE, int SIZE> -inline DATA_TYPE &LLLocalIDHashMapIter<DATA_TYPE, SIZE>::current() -{ - if (!mCurHashNodep) - { - return mNull; - } - return mCurHashNodep->mData[mCurHashNodeKey]; -} - -template <class DATA_TYPE, int SIZE> -inline void LLLocalIDHashMapIter<DATA_TYPE, SIZE>::next() -{ - // No current entry, this iterator is done - if (!mCurHashNodep) - { - //return mNull; - return; - } - - // Go to the next element - mCurHashNodeKey++; - if (mCurHashNodeKey < mCurHashNodep->mCount) - { - // We're not done with this node, return the current element - //return mCurHashNodep->mData[mCurHashNodeKey]; - return; - } - - // Done with this node, move to the next - mCurHashNodep = mCurHashNodep->mNextNodep; - if (mCurHashNodep) - { - // Return the first element - mCurHashNodeKey = 0; - //return mCurHashNodep->mData[0]; - return; - } - - // Find the next non-empty node (keyed on the first byte) - mCurHashMapNodeNum++; - - S32 i; - for (i = mCurHashMapNodeNum; i < 256; i++) - { - if (mHashMapp->mNodes[i].mCount) - { - // We found one that wasn't empty - mCurHashNodep = &mHashMapp->mNodes[i]; - mCurHashMapNodeNum = i; - mCurHashNodeKey = 0; - //return mCurHashNodep->mData[0]; - return; - } - } - - // OK, we're done, nothing else to iterate - mCurHashNodep = NULL; - mHashMapp->mIterCount--; // Decrement since we're safe to do removes now - //return mNull; - return; -} - -#endif // LL_LLLOCALIDHASHMAP_H |