summaryrefslogtreecommitdiff
path: root/indra/test/lluuidhashmap_tut.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'indra/test/lluuidhashmap_tut.cpp')
-rw-r--r--indra/test/lluuidhashmap_tut.cpp339
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);
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 00:24:54 +0000