Created
August 6, 2012 03:44
-
-
Save Cryolite/3269831 to your computer and use it in GitHub Desktop.
A test case for nanahan::Map
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <map/map.hpp> | |
#include <boost/functional/hash.hpp> | |
#include <boost/unordered_map.hpp> | |
#include <boost/random/mersenne_twister.hpp> | |
#include <boost/random/uniform_smallint.hpp> | |
#include <boost/random/uniform_real.hpp> | |
#include <ext/throw_allocator.h> | |
#include <cstddef> | |
#include <ctime> | |
#include <utility> | |
#include <functional> | |
#include <map> | |
#include <iterator> | |
typedef std::pair<const int, int> MapValue; | |
typedef __gnu_cxx::throw_allocator_random<MapValue> MapAllocator; | |
#if 1 | |
typedef nanahan::Map<int, | |
int, | |
boost::hash<int>, | |
std::equal_to<int>, | |
MapAllocator> Map; | |
typedef Map::iterator ConstIterator; | |
#else | |
typedef boost::unordered_map<int, | |
int, | |
boost::hash<int>, | |
std::equal_to<int>, | |
MapAllocator> Map; | |
typedef Map::const_iterator ConstIterator; | |
#endif | |
typedef Map::iterator Iterator; | |
typedef std::pair<int, Iterator> AnswerData; | |
typedef std::map<int, AnswerData, std::less<int> > AnswerMap; | |
typedef AnswerMap::iterator AnswerIterator; | |
typedef AnswerMap::const_iterator AnswerConstIterator; | |
typedef boost::mt19937 URNG; | |
void check_integrity(const Map& m, const AnswerMap& answer) | |
{ | |
// Check the existence of bijection between `m' and `answer'. | |
for(ConstIterator it = m.begin(); it != m.end(); ++it){ | |
if(m.find(it->first) != it){ abort(); } | |
AnswerConstIterator jt = answer.find(it->first); | |
if(jt == answer.end()){ abort(); } | |
if(jt->second.first != it->second){ abort(); } | |
if(jt->second.second != it){ abort(); } | |
} | |
for(AnswerConstIterator it = answer.begin(); it != answer.end(); ++it){ | |
ConstIterator jt = m.find(it->first); | |
if(m.find(jt->first) != jt){ abort(); } | |
if(jt == m.end()){ abort(); } | |
if(jt != it->second.second){ abort(); } | |
if(jt->first != it->first){ abort(); } | |
if(jt->second != it->second.first){ abort(); } | |
} | |
} | |
Iterator iterator_random_select(Map& m, URNG& urng) | |
{ | |
// Randomly choose an iterator from the range [m.begin(), m.end()). | |
assert(!m.empty()); | |
Iterator it = m.begin(); | |
#if 1 | |
for(int i = boost::uniform_smallint<>(0, m.size() - 1)(urng); i > 0; --i, ++it); | |
#else | |
std::advance(it, boost::uniform_smallint<>(0, m.size() - 1)(urng)); | |
#endif | |
return it; | |
} | |
void insert(int& global_key, Map& m, AnswerMap& answer, URNG& urng) | |
{ | |
// Try to insert a new key at nearly 50 percent chance, otherwise try to | |
// insert a key that was inserted into `m' at least once (but was possibly | |
// erased afterward). | |
const int key = boost::uniform_real<>(0.0, 1.0)(urng) < 0.5 ? | |
global_key : boost::uniform_smallint<>(0, global_key)(urng); | |
const int val = urng(); | |
try{ | |
std::pair<Iterator, bool> result = m.insert(std::make_pair(key,val)); | |
if(result.second != (answer.find(key) == answer.end())){ abort(); } | |
if(result.first->first != key){ abort(); } | |
if(result.second && result.first->second != val){ abort(); } | |
// TODO: Take care of an exception thrown from the next line. | |
answer.insert(std::make_pair(key,AnswerData(val,result.first))); | |
} | |
catch(const __gnu_cxx::forced_error&){ | |
// Catch the exception thrown by `m.insert(...)'. | |
check_integrity(m, answer); | |
return; | |
} | |
check_integrity(m, answer); | |
if(key == global_key){ | |
++global_key; | |
} | |
} | |
void find(const std::size_t global_key, const Map& m, const AnswerMap& answer, URNG& urng) | |
{ | |
const int key = boost::uniform_real<>(0.0, 1.0)(urng) < 0.5 ? | |
boost::uniform_smallint<>(0, global_key)(urng) : urng(); | |
if((m.find(key) == m.end()) != (answer.find(key) == answer.end())){ | |
abort(); | |
} | |
} | |
void erase(Map& m, AnswerMap& answer, URNG& urng) | |
{ | |
if(m.empty()){ | |
// no-op when empty. | |
return; | |
} | |
const Iterator it = iterator_random_select(m, urng); | |
if(answer.find(it->first) == answer.end()){ abort(); } | |
answer.erase(answer.find(it->first)); | |
m.erase(it); | |
check_integrity(m, answer); | |
} | |
int main() | |
{ | |
URNG urng(std::time(0)); | |
// Set the probability of mimic allocation failure. | |
MapAllocator::set_probability(0.1); | |
Map m; | |
AnswerMap answer; | |
boost::uniform_smallint<> uniform04(0, 4); | |
for(int global_key = 0; m.size() < 1000;){ | |
int action = uniform04(urng); | |
switch(action){ | |
case 0: | |
case 3: | |
case 4: | |
// Fail to insert an element with a probability of up to 50 percent. | |
// Therefore, in order to sustain stable growth of the size of `m' | |
// (it is critical for test coverage for the size and thus loop | |
// termination condition), insertion should have a probability of more | |
// than double the one for erasion. | |
insert(global_key, m, answer, urng); | |
break; | |
case 1: | |
find(global_key, m, answer, urng); | |
break; | |
case 2: | |
erase(m, answer, urng); | |
break; | |
} | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment