A test case for nanahan::Map

gistfile1.cpp

#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;
}