From d644fc64407dcd14ffcee6a0e9fbe28ee3a4e9bd Mon Sep 17 00:00:00 2001 From: Jacek Antonelli Date: Fri, 15 Aug 2008 23:45:02 -0500 Subject: Second Life viewer sources 1.18.0.6 --- linden/indra/test/lluuidhashmap_tut.cpp | 359 ++++++++++++++++++++++++++++++++ 1 file changed, 359 insertions(+) create mode 100644 linden/indra/test/lluuidhashmap_tut.cpp (limited to 'linden/indra/test/lluuidhashmap_tut.cpp') diff --git a/linden/indra/test/lluuidhashmap_tut.cpp b/linden/indra/test/lluuidhashmap_tut.cpp new file mode 100644 index 0000000..a787326 --- /dev/null +++ b/linden/indra/test/lluuidhashmap_tut.cpp @@ -0,0 +1,359 @@ +/** + * @file lluuidhashmap_tut.cpp + * @author Adroit + * @date 2007-02 + * @brief Test cases for LLUUIDHashMap + * + * Copyright (c) 2007-2007, Linden Research, Inc. + * + * Second Life Viewer Source Code + * The source code in this file ("Source Code") is provided by Linden Lab + * to you under the terms of the GNU General Public License, version 2.0 + * ("GPL"), unless you have obtained a separate licensing agreement + * ("Other License"), formally executed by you and Linden Lab. Terms of + * the GPL can be found in doc/GPL-license.txt in this distribution, or + * online at http://secondlife.com/developers/opensource/gplv2 + * + * There are special exceptions to the terms and conditions of the GPL as + * it is applied to this Source Code. View the full text of the exception + * in the file doc/FLOSS-exception.txt in this software distribution, or + * online at http://secondlife.com/developers/opensource/flossexception + * + * By copying, modifying or distributing this software, you acknowledge + * that you have read and understood your obligations described above, + * and agree to abide by those obligations. + * + * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO + * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY, + * COMPLETENESS OR PERFORMANCE. + */ + +#include +#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 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); + const int numElementsToCheck = 32*256*32; + std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); + const int numElementsToCheck = 5; + std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); + const int numElementsToCheck = 10; + std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); + const int numElementsToCheck = 10; + std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); + const int numElementsToCheck = 256; + std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); + LLUUIDHashMapIter hashIter(&hashTable); + const int numElementsToCheck = 256; + std::vector 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 hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); + LLUUIDHashMapIter hashIter(&hashTable); + const int numElementsToCheck = 256; + std::vector 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); + } +} -- cgit v1.1