/** * @file lluuidhashmap.h * @brief A uuid based hash map. * * $LicenseInfo:firstyear=2003&license=viewerlgpl$ * Second Life Viewer Source Code * Copyright (C) 2010, Linden Research, Inc. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; * version 2.1 of the License only. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA * $/LicenseInfo$ */ #ifndef LL_LLUUIDHASHMAP_H #define LL_LLUUIDHASHMAP_H #include "stdtypes.h" #include "llerror.h" #include "lluuid.h" // UUID hash map /* LLUUIDHashMap<uuid_pair, 32> foo(test_equals); LLUUIDHashMapIter<uuid_pair, 32> bar(&foo); LLDynamicArray<LLUUID> source_ids; const S32 COUNT = 100000; S32 q; for (q = 0; q < COUNT; q++) { llinfos << "Creating" << llendl; LLUUID id; id.generate(); //llinfos << q << ":" << id << llendl; uuid_pair pair; pair.mUUID = id; pair.mValue = q; foo.set(id, pair); source_ids.put(id); //ms_sleep(1); } uuid_pair cur; llinfos << "Iterating" << llendl; for (cur = bar.first(); !bar.done(); cur = bar.next()) { if (source_ids[cur.mValue] != cur.mUUID) { llerrs << "Incorrect value iterated!" << llendl; } //llinfos << cur.mValue << ":" << cur.mUUID << llendl; //ms_sleep(1); } llinfos << "Finding" << llendl; for (q = 0; q < COUNT; q++) { cur = foo.get(source_ids[q]); if (source_ids[cur.mValue] != cur.mUUID) { llerrs << "Incorrect value found!" << llendl; } //llinfos << res.mValue << ":" << res.mUUID << llendl; //ms_sleep(1); } llinfos << "Removing" << llendl; for (q = 0; q < COUNT/2; q++) { if (!foo.remove(source_ids[q])) { llerrs << "Remove failed!" << llendl; } //ms_sleep(1); } llinfos << "Iterating" << llendl; for (cur = bar.first(); !bar.done(); cur = bar.next()) { if (source_ids[cur.mValue] != cur.mUUID) { llerrs << "Incorrect value found!" << llendl; } //llinfos << cur.mValue << ":" << cur.mUUID << llendl; //ms_sleep(1); } llinfos << "Done with UUID map test" << llendl; return 0; */ // // LLUUIDHashNode // template <class DATA, int SIZE> class LLUUIDHashNode { public: LLUUIDHashNode(); public: S32 mCount; U8 mKey[SIZE]; DATA mData[SIZE]; LLUUIDHashNode<DATA, SIZE> *mNextNodep; }; // // LLUUIDHashNode implementation // template <class DATA, int SIZE> LLUUIDHashNode<DATA, SIZE>::LLUUIDHashNode() { mCount = 0; mNextNodep = NULL; } template <class DATA_TYPE, int SIZE> class LLUUIDHashMap { public: // basic constructor including sorter LLUUIDHashMap(BOOL (*equals)(const LLUUID &uuid, const DATA_TYPE &data), const DATA_TYPE &null_data); ~LLUUIDHashMap(); inline DATA_TYPE &get(const LLUUID &uuid); inline BOOL check(const LLUUID &uuid) const; inline DATA_TYPE &set(const LLUUID &uuid, const DATA_TYPE &type); inline BOOL remove(const LLUUID &uuid); void removeAll(); inline S32 getLength() const; // Warning, NOT O(1!) public: BOOL (*mEquals)(const LLUUID &uuid, const DATA_TYPE &data); LLUUIDHashNode<DATA_TYPE, SIZE> mNodes[256]; S32 mIterCount; protected: DATA_TYPE mNull; }; // // LLUUIDHashMap implementation // template <class DATA_TYPE, int SIZE> LLUUIDHashMap<DATA_TYPE, SIZE>::LLUUIDHashMap(BOOL (*equals)(const LLUUID &uuid, const DATA_TYPE &data), const DATA_TYPE &null_data) : mEquals(equals), mIterCount(0), mNull(null_data) { } template <class DATA_TYPE, int SIZE> LLUUIDHashMap<DATA_TYPE, SIZE>::~LLUUIDHashMap() { removeAll(); } template <class DATA_TYPE, int SIZE> void LLUUIDHashMap<DATA_TYPE, SIZE>::removeAll() { S32 bin; for (bin = 0; bin < 256; bin++) { LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[bin]; BOOL first = TRUE; while (nodep) { S32 i; const S32 count = nodep->mCount; // Iterate through all members of this node for (i = 0; i < count; i++) { nodep->mData[i] = mNull; } nodep->mCount = 0; // Done with all objects in this node, go to the next. LLUUIDHashNode<DATA_TYPE, SIZE>* curp = nodep; nodep = nodep->mNextNodep; // Delete the node if it's not the first node if (first) { first = FALSE; curp->mNextNodep = NULL; } else { delete curp; } } } } template <class DATA_TYPE, int SIZE> inline S32 LLUUIDHashMap<DATA_TYPE, SIZE>::getLength() const { S32 count = 0; S32 bin; for (bin = 0; bin < 256; bin++) { LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = (LLUUIDHashNode<DATA_TYPE, SIZE>*) &mNodes[bin]; while (nodep) { count += nodep->mCount; nodep = nodep->mNextNodep; } } return count; } template <class DATA_TYPE, int SIZE> inline DATA_TYPE &LLUUIDHashMap<DATA_TYPE, SIZE>::get(const LLUUID &uuid) { LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[uuid.mData[0]]; // Grab the second byte of the UUID, which is the key for the node data const S32 second_byte = uuid.mData[1]; while (nodep) { S32 i; const S32 count = nodep->mCount; // Iterate through all members of this node for (i = 0; i < count; i++) { if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) { // The second byte matched, and our equality test passed. // We found it. return nodep->mData[i]; } } // Done with all objects in this node, go to the next. nodep = nodep->mNextNodep; } return mNull; } template <class DATA_TYPE, int SIZE> inline BOOL LLUUIDHashMap<DATA_TYPE, SIZE>::check(const LLUUID &uuid) const { const LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[uuid.mData[0]]; // Grab the second byte of the UUID, which is the key for the node data const S32 second_byte = uuid.mData[1]; while (nodep) { S32 i; const S32 count = nodep->mCount; // Iterate through all members of this node for (i = 0; i < count; i++) { if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) { // The second byte matched, and our equality test passed. // We found it. return TRUE; } } // Done with all objects in this node, go to the next. nodep = nodep->mNextNodep; } // Didn't find anything return FALSE; } template <class DATA_TYPE, int SIZE> inline DATA_TYPE &LLUUIDHashMap<DATA_TYPE, SIZE>::set(const LLUUID &uuid, const DATA_TYPE &data) { // Set is just like a normal find, except that if we find a match // we replace it with the input value. // If we don't find a match, we append to the end of the list. LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[uuid.mData[0]]; const S32 second_byte = uuid.mData[1]; while (1) { const S32 count = nodep->mCount; S32 i; for (i = 0; i < count; i++) { if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) { // We found a match for this key, replace the data with // the incoming data. nodep->mData[i] = data; return nodep->mData[i]; } } if (!nodep->mNextNodep) { // We've iterated through all of the keys without finding a match if (i < SIZE) { // There's still some space on this node, append // the key and data to it. nodep->mKey[i] = second_byte; nodep->mData[i] = data; nodep->mCount++; return nodep->mData[i]; } else { // This node is full, append a new node to the end. nodep->mNextNodep = new LLUUIDHashNode<DATA_TYPE, SIZE>; nodep->mNextNodep->mKey[0] = second_byte; nodep->mNextNodep->mData[0] = data; nodep->mNextNodep->mCount = 1; return nodep->mNextNodep->mData[0]; } } // No match on this node, go to the next nodep = nodep->mNextNodep; } } template <class DATA_TYPE, int SIZE> inline BOOL LLUUIDHashMap<DATA_TYPE, SIZE>::remove(const LLUUID &uuid) { if (mIterCount) { // We don't allow remove when we're iterating, it's bad karma! llerrs << "Attempted remove while an outstanding iterator in LLUUIDHashMap!" << llendl; } // Remove is the trickiest operation. // What we want to do is swap the last element of the last // node if we find the one that we want to remove, but we have // to deal with deleting the node from the tail if it's empty, but // NOT if it's the only node left. LLUUIDHashNode<DATA_TYPE, SIZE> *nodep = &mNodes[uuid.mData[0]]; // Not empty, we need to search through the nodes const S32 second_byte = uuid.mData[1]; // A modification of the standard search algorithm. while (nodep) { const S32 count = nodep->mCount; S32 i; for (i = 0; i < count; i++) { if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) { // We found the node that we want to remove. // Find the last (and next-to-last) node, and the index of the last // element. We could conceviably start from the node we're on, // but that makes it more complicated, this is easier. LLUUIDHashNode<DATA_TYPE, SIZE> *prevp = &mNodes[uuid.mData[0]]; LLUUIDHashNode<DATA_TYPE, SIZE> *lastp = prevp; // Find the last and next-to-last while (lastp->mNextNodep) { prevp = lastp; lastp = lastp->mNextNodep; } // First, swap in the last to the current location. nodep->mKey[i] = lastp->mKey[lastp->mCount - 1]; nodep->mData[i] = lastp->mData[lastp->mCount - 1]; // Now, we delete the entry lastp->mCount--; lastp->mData[lastp->mCount] = mNull; if (!lastp->mCount) { // We deleted the last element! if (lastp != &mNodes[uuid.mData[0]]) { // Only blitz the node if it's not the head // Set the previous node to point to NULL, then // blitz the empty last node prevp->mNextNodep = NULL; delete lastp; } } return TRUE; } } // Iterate to the next node, we've scanned all the entries in this one. nodep = nodep->mNextNodep; } return FALSE; } // // LLUUIDHashMapIter // template <class DATA_TYPE, int SIZE> class LLUUIDHashMapIter { public: LLUUIDHashMapIter(LLUUIDHashMap<DATA_TYPE, SIZE> *hash_mapp); ~LLUUIDHashMapIter(); inline void reset(); inline void first(); inline void next(); inline BOOL done() const; DATA_TYPE& operator*() const { return mCurHashNodep->mData[mCurHashNodeKey]; } DATA_TYPE* operator->() const { return &(operator*()); } protected: LLUUIDHashMap<DATA_TYPE, SIZE> *mHashMapp; LLUUIDHashNode<DATA_TYPE, SIZE> *mCurHashNodep; S32 mCurHashMapNodeNum; S32 mCurHashNodeKey; DATA_TYPE mNull; }; // // LLUUIDHashMapIter Implementation // template <class DATA_TYPE, int SIZE> LLUUIDHashMapIter<DATA_TYPE, SIZE>::LLUUIDHashMapIter(LLUUIDHashMap<DATA_TYPE, SIZE> *hash_mapp) { mHashMapp = hash_mapp; mCurHashNodep = NULL; mCurHashMapNodeNum = 0; mCurHashNodeKey = 0; } template <class DATA_TYPE, int SIZE> LLUUIDHashMapIter<DATA_TYPE, SIZE>::~LLUUIDHashMapIter() { reset(); } template <class DATA_TYPE, int SIZE> inline void LLUUIDHashMapIter<DATA_TYPE, SIZE>::reset() { if (mCurHashNodep) { // We're partway through an iteration, we can clean up now mHashMapp->mIterCount--; mCurHashNodep = NULL; } } template <class DATA_TYPE, int SIZE> inline void LLUUIDHashMapIter<DATA_TYPE, SIZE>::first() { // Iterate through until we find the first non-empty node; S32 i; for (i = 0; i < 256; i++) { if (mHashMapp->mNodes[i].mCount) { if (!mCurHashNodep) { // Increment, since it's no longer safe for us to do a remove mHashMapp->mIterCount++; } mCurHashNodep = &mHashMapp->mNodes[i]; mCurHashMapNodeNum = i; mCurHashNodeKey = 0; //return mCurHashNodep->mData[0]; return; } } // Completely empty! mCurHashNodep = NULL; //return mNull; return; } template <class DATA_TYPE, int SIZE> inline BOOL LLUUIDHashMapIter<DATA_TYPE, SIZE>::done() const { return mCurHashNodep ? FALSE : TRUE; } template <class DATA_TYPE, int SIZE> inline void LLUUIDHashMapIter<DATA_TYPE, SIZE>::next() { // No current entry, this iterator is done if (!mCurHashNodep) { //return mNull; return; } // Go to the next element mCurHashNodeKey++; if (mCurHashNodeKey < mCurHashNodep->mCount) { // We're not done with this node, return the current element //return mCurHashNodep->mData[mCurHashNodeKey]; return; } // Done with this node, move to the next mCurHashNodep = mCurHashNodep->mNextNodep; if (mCurHashNodep) { // Return the first element mCurHashNodeKey = 0; //return mCurHashNodep->mData[0]; return; } // Find the next non-empty node (keyed on the first byte) mCurHashMapNodeNum++; S32 i; for (i = mCurHashMapNodeNum; i < 256; i++) { if (mHashMapp->mNodes[i].mCount) { // We found one that wasn't empty mCurHashNodep = &mHashMapp->mNodes[i]; mCurHashMapNodeNum = i; mCurHashNodeKey = 0; //return mCurHashNodep->mData[0]; return; } } // OK, we're done, nothing else to iterate mCurHashNodep = NULL; mHashMapp->mIterCount--; // Decrement since we're safe to do removes now //return mNull; } #endif // LL_LLUUIDHASHMAP_H