Code owners
Assign users and groups as approvers for specific file changes. Learn more.
lluuidhashmap_tut.cpp 9.31 KiB
/**
* @file lluuidhashmap_tut.cpp
* @author Adroit
* @date 2007-02
* @brief Test cases for LLUUIDHashMap
*
* $LicenseInfo:firstyear=2007&license=viewerlgpl$
* Second Life Viewer Source Code
* Copyright (C) 2010, Linden Research, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation;
* version 2.1 of the License only.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
* Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA
* $/LicenseInfo$
*/
#include <tut/tut.hpp>
#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);
}
}