#! perl -slw
use strict;
use Inline C => Config => BUILD_NOISY => 1;
use Inline C => <<'END_C',  NAME => 'Lookup64', CLEAN_AFTER_BUILD =>0, TYPEMAPS => './lookup64.typemap';
#include "C\mytypes.h"
#include "C\rand64.h"
#include <time.h>

#define N (200000033)



U64 *a;
void build( int M ) {
    U32 i;

    a = calloc( N, sizeof( U64 ) );

    srand64( __rdtsc(), _time64( NULL ) );

    for( i=0; i < M; ++i ) {
        U64 r = rand64();
        U32 modr = r % N, n = modr, c = 0;

        while( a[n] && ++c < N ) {
            n = ( n + modr ) % N;
        }
        a[ n ] = r;
        if( ( i % 1000000 ) == 0 ) printf( "%I64u @ %u\n", r, n );
    }
}

int lookup( U64 v ) {
    U32 modr = v % N, n = modr, c = 0;
    while( a[n] != v && a[n] != 0 && ++c < N ) {
        n = ( n + modr ) % N;
    }
    if( a[n] != v ) return 0;
    return n;
}

END_C
package main;
use Time::HiRes qw[ time ];

our $N //= 1000;

<STDIN>;

my $start = time;
build( $N );
my $end = time;
printf( "Inserting $N U64s took %.9f seconds\n", $end-$start );

$start = time;
while( my $v = <STDIN> ) {
    chomp( $v );
    $start = time;
    my $p = lookup( $v );
    $end = time;
    printf "%u @ %u in %.9f s\n", $v, $p, $end - $start;
}