atest.C

/**
| Tests a container.
| Tries to find an as simple as possible sequence that raises an error.
*/

// if defined checks for uninitialed variable access
// undefined for use similar to simpletest.
#define CHECK_INIT

// if defined traces memory use
// only on GNU/Unix systems, must be compiled with '-g'
//#define MEM_TRACE

#include "Container.h"
#include "CONTAINERTYPE.H"

#include <set>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <random>

#ifdef MEM_TRACE
  #include <map>
  #include <execinfo.h>

  bool trace = false;
  #define MAX_BACKTRACE 10
  #define TRACE_ON { trace = true; }
  #define TRACE_OFF { trace = false; }
  class MemEntry {
  public :
     size_t size;
     void ** trace_p;
     int trace_n;
  };
  std::map<void *, MemEntry *> memory;
  char * arg0;
#else
  #define TRACE_ON
  #define TRACE_OFF
#endif

#ifdef CHECK_INIT
  #define ETYPE UInt
  #define EVAL( e ) ( ( e ).value() )
#else
  #define ETYPE unsigned int
  #define EVAL( e ) ( e )
#endif


using namespace std;

#ifdef MEM_TRACE
void * operator new( size_t size )
{
    void *p = malloc( size );
    memset( p, 0xaa, size );

    if( trace ) {
        TRACE_OFF;
        MemEntry * me = new MemEntry;
        me->size = size;
        me->trace_p = new void*[ MAX_BACKTRACE ];
        me->trace_n = backtrace( me->trace_p, MAX_BACKTRACE );
        memory[ p ] = me;
        TRACE_ON;
    }

    return p;
}

void * operator new[ ](size_t size )
{
    void *p = malloc( size );
    memset( p, 0xaa, size );

    if( trace ) {
        TRACE_OFF;
        MemEntry * me = new MemEntry;
        me->size = size;
        me->trace_p = new void*[ MAX_BACKTRACE ];
        me->trace_n = backtrace( me->trace_p, MAX_BACKTRACE );
        memory[ p ] = me;
        TRACE_ON;
    }

    return p;
}

void operator delete( void *p )
{
   if (!p) return;
   if( trace ) {
       TRACE_OFF;
       MemEntry * me = memory[p];
       delete me->trace_p;
       memory.erase( p );
       delete me;
       TRACE_ON;
   }

   free( p );
}

void operator delete[ ]( void *p )
{
   if (!p) return;
   if( trace ) {
       TRACE_OFF;
       MemEntry * me = memory[p];
       delete me->trace_p;
       memory.erase( p );
       delete me;
       TRACE_ON;
   }

   free( p );
}

#endif


// an unsigned integer wrapper
class UInt
{
    unsigned int val;
    bool init;

public :

    UInt() : init(false) {};
  
    UInt(unsigned int val) : val(val), init(true) {};

    unsigned int value() const
    {
       if( !init ) {
          cout << "value() called on uninitialized value!\n";
          exit( 1 );
       }

       return val;
    }

    bool operator == ( const UInt& u ) const
    {
       if( !init ) {
          cout << "== called with uninitialized left side!\n";
          exit( 1 );
       }
       
       if( !u.init ) {
          cout << "== called with uninitialized right side!\n";
          exit( 1 );
       }

       return val == u.val;
    }

    bool operator > ( const UInt& u ) const
    {
       if( !init ) {
          cout << "> called with uninitialized left side!\n";
          exit( 1 );
       }
       
       if( !u.init ) {
          cout << "> called with uninitialized right side!\n";
          exit( 1 );
       }

       return val > u.val;
    }

    std::ostream& print( std::ostream& o ) const
    {
       if ( !init ) {
           return o << "(NOT INIT)";
       }

        return o << val;
    }

    std::istream& read( std::istream& i )
    {
        init = true;

        return i >> val;
    }

    friend double doubleValue<UInt>( const UInt& u );
    friend unsigned long hashValue<UInt>( const UInt& u );
    friend unsigned long ordinalValue<UInt>( const UInt& u );
};

inline std::ostream& operator << ( std::ostream& o, const UInt& u )
{
   return u.print( o );
}

inline std::istream& operator>>( std::istream& i, UInt& u )
{
   return u.read( i );
}

template <> inline double doubleValue( const UInt& u )
{
    if( !u.init ) {
       cout << "doubleValue() called on uninitialized value!\n";
       exit( 1 );
    }
    return doubleValue( u.val );
}

template <> inline unsigned long ordinalValue( const UInt& u )
{
    if( !u.init ) {
       cout << "ordinalValue() called on uninitialized value!\n";
       exit( 1 );
    }
    return ordinalValue( u.val );
}

template <> inline unsigned long hashValue( const UInt& u )
{
    if( !u.init ) {
       cout << "hashValue called on uninitialized value!\n";
       exit( 1 );
    }
    return hashValue( u.val );
}

// default values, description see help in struct Arg belowa
bool verbose            = true;
bool testApply          = true;
bool testRemove         = true;
bool testMember         = true;
unsigned int dataStart  =    1;
unsigned int dataStop   =  100;
unsigned int dataStep   =    1;
unsigned int rangeStart =    1;
unsigned int rangeStop  =  100;
unsigned int rangeStep  =    1;
unsigned int seedStart  =    1;
unsigned int seedStop   =    5;
unsigned int seedStep   =    1;

// a general command line parameter
class Arg
{
   // indents show() and helpout() outputs
   const static unsigned int indent = 8;

public :
   string name;
   string help;

   // constructor
   Arg( const char *name, const char *help ) :
       name( name ),
       help( help )
   { }

   // shows current setting
   virtual void show( )
   {
       cout << "  " << name << ": ";
       
       if( name.length( ) >= indent ) {
           return;
       }

       for( unsigned int i = 0; i < indent - name.length( ); i++ )
       {
           cout << " ";
       }
   }

   // shows help string
   void helpout( )
   {
       cout << "  " << name << ": ";

       if ( name.length( ) >= indent ) {
           return;
       }

       for( unsigned int i = 0; i < indent - name.length( ); i++ )
       {
           cout << " ";
       }
       cout << help << "\n";
   }

   // sets the parameter
   virtual bool set( string &arg ) = 0;
};

// a boolean command line parameter
class ArgBool : public Arg
{
   bool *p;

public:

   // constructor
   ArgBool( const char *name, const char *help, bool *p ) :
       Arg( name, help ),
       p( p )
   { }

   // shows current setting
   virtual void show( )
   {
       Arg::show( );
       
       cout << ( *p ? "true" : "false" ) << "\n";
   }

   // sets the parameter
   virtual bool set( string &arg )
   {
       if( arg == "true"  || arg == "yes" ) {
           *p = true;
           return true;
       }
       
       if( arg == "false" || arg == "no" ) {
           *p = false;
           return true;
       }
       
       return false;
   }
};

// a range command line parameter
class ArgRange : public Arg
{
   unsigned int *start, *stop, *step;

public:

   // constructor
   ArgRange(
       const char *name,
       const char *help,
       unsigned int *start,
       unsigned int *stop,
       unsigned int *step
   ) :
       Arg( name, help ),
       start( start ),
       stop( stop ),
       step( step )
   { }

   // shows current setting
   virtual void show( )
   {
       Arg::show( );
       cout << *start << "-" << *stop << "+" << *step << "\n";
   }

   // sets the parameter
   virtual bool set( string &arg )
   {
       size_t p = arg.find_first_of( "-" );

       string sstart( arg, 0, p == string::npos ? -1 : p );
       istringstream istart( sstart );
       istart >> ( *start );

       if( p == string::npos )
       {
           *stop = *start + 1;
           *step = 1;
           return true;
       }

       arg.assign( arg, p + 1, -1 );
       p = arg.find_first_of( "+" );
       string sstop( arg, 0, p == string::npos ? -1 : p );
       istringstream istop( sstop );
       istop >> ( *stop );
       (*stop)++;

       if( p == string::npos )
       {
           return true;
       }

       arg.assign( arg, p + 1, -1 );
       istringstream istep( arg );
       istep >> ( *step );

       return true;
   }
};

class Arg *args[ ] =
{
   new class ArgBool (
       "verbose",
       "if true babbles a lot",
       &verbose
   ),

   new class ArgBool (
       "remove",
       "if true also calls remove()",
       &testRemove
   ),

   new class ArgBool (
       "member",
       "if true tests member() for all values in range",
       &testMember
   ),

   new class ArgBool (
       "apply",
       "if true tests apply",
       &testApply
   ),

   new class ArgRange(
       "data",
       "tests with this amounts of values",
       &dataStart, &dataStop, &dataStep
   ),

   new class ArgRange(
       "range",
       "largest possible value",
       &rangeStart, &rangeStop, &rangeStep
   ),

   new class ArgRange(
       "seed",
       "tests with theses count of values",
       &seedStart, &seedStop, &seedStep
   ),

   0
};

// called by apply()
set<unsigned int> applyData;
unsigned int applyRange;
Order applyOrder;

// called by apply()
void applyCall( const ETYPE & e )
{
    TRACE_OFF;

    if( verbose )
    {
        cout << "rcv : " << e << "\n";
    }

    if( EVAL( e ) < 0 || EVAL( e ) >= applyRange )
    {
        cout << "apply() returned out of range: " << e << "\n";
        exit( 1 );
    }

    if( !applyData.count( EVAL( e ) ) )
    {
        cout << "apply() returned wrong value: " << e << "\n";
        exit( 1 );
    }

    switch(applyOrder) {
    case ascending :
        if( EVAL( e ) != *( applyData.begin( ) ) ) {
            cout << "apply() returned out of order: " << e <<
                    " expected " << *(applyData.begin()) << "\n";
            exit( 1 );
        }
        break;

    case descending :
        if( EVAL( e ) != *( applyData.rbegin( ) ) ) {
            cout << "apply() returned out of order: " << e <<
                    " expected " << *(applyData.begin()) << "\n";
            exit( 1 );
        }
        break;

    case dontcare : 
        break;
    }

    applyData.erase( EVAL( e ) );

    TRACE_ON;
}


std::default_random_engine atestGenerator;

std::uniform_int_distribution<unsigned int> atestDistribution(
	0,(unsigned int)-1
);

unsigned int atestRand( )
{
   return atestDistribution( atestGenerator );
}

/**
| performs one test run for ndata values between 0 and range
| with seed as randomseed
*/
int test(
    unsigned int ndata,
    unsigned int range,
    unsigned int seed
)
{
   set<unsigned int> data;

   if ( verbose )
   {
       cout << "Creating a container\n" ;
   }

   TRACE_ON;
   CONTAINERTYPE<ETYPE>* c = new CONTAINERTYPE<ETYPE>;
   TRACE_OFF;

   cout << "test (" <<
           "data="  << ndata << ", " <<
           "range=" << range << ", " <<
           "seed="  << seed  << ")" << "\n" ;

	atestGenerator.seed( seed );

   // reset global random generators for cuckoo
   srand( 0 );
   //generator.seed( 0 );

   for( unsigned int i = 0; i < ndata; i++ ) {
       unsigned int w = atestRand() % range;
       if( !testRemove || atestRand() % 2 ) {
           if( verbose ) {
               cout << "add " << w << "\n";
           }
           data.insert( w );

           TRACE_ON;
           c->add( w );
           TRACE_OFF;
       } else {
           if( verbose ) {
               cout << "rem " << w << "\n";
           }
           data.erase( w );

           TRACE_ON;
           c->remove( w );
           TRACE_OFF;
       }
   }

   if( verbose ) cout << "\n"; 

   if( testMember ) {
       for( unsigned int i = 0; i < range; i++ ) {
           if( verbose ) {
               cout << "mem " << i << "\n";
           }

           TRACE_ON;
           bool val = c->member( i );
           TRACE_OFF;

           if( !!data.count( i ) != !!val ) {
               cout << "member(" << i << ") = " <<
                   (val ? "true" : "false") << " but expected " <<
                   (data.count( i ) ? "true" : "false") << "\n";
               cout << "range:" << range << "\n";
               cout << "data:"  << ndata << "\n";
               cout << "seed:" << seed << "\n";
               cout << "Container Print:\n"; 

               TRACE_ON;
               c->print( cout );
               TRACE_OFF;

               cout << "\nexpected:\n";

               bool first = true;

               for(
                   set<unsigned int>::const_iterator it = data.begin( );
                   it != data.end( );
                   it++
               ) {
                   cout << (first ? "" : ", ") << *it;
                   first = false;
               }

               cout << "\n";

               return 1;
           }
       }
   }

   if( testApply )
   {
       for( int order = dontcare; order <= descending; order++ )
   	{
           if( verbose ) {
               switch( order ) {
               case dontcare :
                   cout << "testing apply(dontcare)\n";
                   break;
               case ascending :
                   cout << "testing apply(ascending)\n";
                   break;
               case descending :
                   cout << "testing apply(descending)\n";
                   break;
               }
           }
   		applyData = data;
   		applyRange = range;
   		applyOrder = (Order) order;

           TRACE_ON;
           c->apply( applyCall, ( Order ) order );
           TRACE_OFF;

           if( !applyData.empty( ) ) {
               cout << "apply forgot :"; 
               bool first = true;
               for(
                   set<unsigned int>::const_iterator it = applyData.begin( );
                   it != applyData.end( );
                   it++
               ) {
                   cout << ( first ? "" : ", " ) << *it;
                   first = false;
               }
               cout << "\n"; 
               exit( 1 );
           }

           if( !data.empty( ) ) {
               if( verbose ) {
                   cout << "testing min\n";
               }

               TRACE_ON;
               ETYPE e = c->min( );
               TRACE_OFF;

               if( !(e == *data.begin( ) ) ) {
                   cout << "min got " << e <<
                     " expected " <<  *data.begin( ) << "\n";

                   exit( 1 );
               }

               if( verbose ) {
                   cout << "tesing max\n";
               }

               TRACE_ON;
               e = c->max( );
               TRACE_OFF;

               if( !(e == *(--data.end( ) ) ) ) {
                   cout << "max got " << e <<
                     " expected " <<  *(-- data.end( ) ) << "\n";

                   exit( 1 );
               }
           }
       }
   }

   if ( verbose )
   {
       cout << "Deleting a container\n" ;
   }

   TRACE_ON;
   delete c;
   TRACE_OFF;

#ifdef MEM_TRACE
   if( memory.size() ) {
      std::cout << "Unfreed memory!\n";
      std::map<void *, MemEntry *>::iterator it = memory.begin();
      void * p = it->first;
      MemEntry * me = it->second;
      std::cout << "first unfreed entry: " << p << "\n";

      ostringstream call;
      call << "/usr/bin/addr2line -e " << arg0;
      for( int i = 1; i < me->trace_n; i++ ) {
          call << " " << me->trace_p[ i ];
      }
      system( call.str( ).c_str( ) );
      std::cout << "\n\n";
      exit( 1 );
   }
#endif

   return 0;
}

void parseArg(string &arg)
{
   size_t p = arg.find_first_of( "=" );
   if( p == string::npos ) {
       throw "\"" + arg + "\" equal sign missing";
   }
   string aname( arg, 0, p );
   arg.assign( arg, p + 1, ( size_t ) -1 );

   struct Arg ** a;
   for ( a = args; *a && aname != ( *a )->name; a++ );

   if( !a ) {
       throw "Unknown argument \"" + aname + "\"";
   }

   if( !(*a)->set( arg ) ) {
       throw "Invalid value \"" + arg + "\"";
   }
}

int main( int argc, char **argv )
{
   std::cout << RAND_MAX;

#ifdef MEM_TRACE
   arg0 = argv[0];
#endif

   string arg;
   try {
       for( int i = 1; i < argc; i++ ) {
           parseArg(arg.assign( argv[ i ] ) );
       }
   } catch( string &e ) {
       cerr << "Error: " << e << "\n\n" <<
           "Usage: " << argv[0] << " [OPTIONS]\n\n" <<
           "Options: [NAME]=[VALUE]\n";

       for ( struct Arg ** a = args; *a; a++ ) {
           (*a)->helpout( );
       }

       cerr << "\nExample:\n  " << argv[ 0 ] << " verbose=false data=1-1000+5\n\n";

       return 1;
   }

   cout << "testing with\n";

   for( struct Arg ** a = args; *a; a++ )
   {
       (*a)->show( );
   }

   for( unsigned int ndata = dataStart; ndata < dataStop; ndata += dataStep ) {
       for( unsigned int range = rangeStart; range < rangeStop; range += rangeStep ) {
           for( unsigned int seed = seedStart; seed < seedStop; seed += seedStep ) {
              if( test(ndata, range, seed)) return 1;
           }
       }
   }

   cout << "Success!\n";

   return 0;
}