Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A test case for nanahan::Map
#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