summaryrefslogtreecommitdiff
path: root/indra/llcommon/lluuidhashmap.h
diff options
context:
space:
mode:
Diffstat (limited to 'indra/llcommon/lluuidhashmap.h')
-rw-r--r--indra/llcommon/lluuidhashmap.h557
1 files changed, 557 insertions, 0 deletions
diff --git a/indra/llcommon/lluuidhashmap.h b/indra/llcommon/lluuidhashmap.h
new file mode 100644
index 0000000000..f7d32b1fe0
--- /dev/null
+++ b/indra/llcommon/lluuidhashmap.h
@@ -0,0 +1,557 @@
+/**
+ * @file lluuidhashmap.h
+ * @brief A uuid based hash map.
+ *
+ * Copyright (c) 2003-$CurrentYear$, Linden Research, Inc.
+ * $License$
+ */
+
+#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 = &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 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()
+{
+ if (mCurHashNodep)
+ {
+ // We're partway through an iteration, we can clean up now
+ mHashMapp->mIterCount--;
+ }
+}
+
+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
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-29 03:13:39 +0000