Print done when done.

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