svn merge --ignore-ancestry svn+ssh://svn/svn/linden/release@65088 svn+ssh://svn/svn/linden/branches/release-candidate@65078 -> release Paired by Tess and rdw.

1 files changed, 339 insertions, 0 deletions

diff --git a/indra/test/lluuidhashmap_tut.cpp b/indra/test/lluuidhashmap_tut.cpp
new file mode 100644
index 0000000000..c9736d4d4b
--- /dev/null
+++ b/indra/test/lluuidhashmap_tut.cpp
@@ -0,0 +1,339 @@
+/** 
+ * @file lluuidhashmap_tut.cpp
+ * @author Adroit
+ * @date 2007-02
+ * @brief Test cases for LLUUIDHashMap
+ *
+ * Copyright (c) 2007-$CurrentYear$, Linden Research, Inc.
+ * $License$
+ */
+
+#include <tut/tut.h>
+#include "linden_common.h"
+#include "lluuidhashmap.h"
+#include "llsdserialize.h"
+
+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<hashmap_test> 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>()
+	{
+		LLUUIDHashMap<UUIDTableEntry, 32>	hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry());
+		const int numElementsToCheck = 32*256*32;
+		std::vector<LLUUID> 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 idToCheck = idList[i];
+			UUIDTableEntry entryToCheck = hashTable.get(idToCheck);
+			ensure("set/get did not work", 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", (i % 2 == 0 && hashTable.check(idToCheck)) || (i % 2 != 0 && !hashTable.check(idToCheck)));
+		}
+	}
+
+	// test removing all but one element. 
+	template<> template<>
+	void hash_index_object_t::test<2>()
+	{
+		LLUUIDHashMap<UUIDTableEntry, 2>	hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry());
+		const int numElementsToCheck = 5;
+		std::vector<LLUUID> 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<UUIDTableEntry, 5>	hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry());
+		const int numElementsToCheck = 10;
+		std::vector<LLUUID> 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<UUIDTableEntry, 5>	hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry());
+		const int numElementsToCheck = 10;
+		std::vector<LLUUID> 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<UUIDTableEntry, 2>	hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry());
+		const int numElementsToCheck = 256;
+		std::vector<LLUUID> 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<UUIDTableEntry, 2>	hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry());
+		LLUUIDHashMapIter<UUIDTableEntry, 2> hashIter(&hashTable);
+		const int numElementsToCheck = 256;
+		std::vector<LLUUID> 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<UUIDTableEntry, 2>	hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry());
+		LLUUIDHashMapIter<UUIDTableEntry, 2> hashIter(&hashTable);
+		const int numElementsToCheck = 256;
+		std::vector<LLUUID> 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);
+	}
+}