#! perl -slw
package BiMap; use strict; #use Config;
use Inline C => Config => BUILD_NOISY => 1; #, ccflags => $Config{ccflags} . '-D_CRT_SECURE_NO_WARNINGS';
use Inline C => <<'END_C',  NAME => 'BiMap_t', CLEAN_AFTER_BUILD =>0, TYPEMAPS => '/test/BiMap.typemap';;

#undef malloc
#undef calloc
#undef free
# define TAG printf( "%s[%u]\n", __FILE__, __LINE__ )

#define CLASS "BiMap"
#define HASH_SEED 0xc0d1f1ed
#define U64_HIBIT 0x8000000000000000ull


U32 __inline hash( const unsigned char *str, const STRLEN len) {
    const unsigned char * const end = (const unsigned char *)str + len;
    U32 hash = HASH_SEED;

    while (str < end) {
        hash += *str++;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

U32 __inline nextPowerOfTwo( U32 v ) {
    v--;
    v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;
    v += (v == 0);
    return ++v;
}

typedef unsigned __int64 U64;

typedef struct {
    U64 addr;
    char *name;
} PAIR;

typedef struct {
    PAIR **byInt;
    U32   *byStr;
    U32    size;
    U32    used;
    double factor;
} BIMAP;

void dump( BIMAP *bm, int dumpBody ) {
    U32 i;
    printf( "\n\nObject:%8p byInt:%8p byStr:%8p size:%u used:%u\n", bm, bm->byInt, bm->byStr, bm->size, bm->used );
    if( dumpBody )
        for( i = 0; i < bm->size; ++i ) {
            PAIR *pair = bm->byInt[ i ];
            if( !pair ) printf( "%4u:[EMPTY SLOT]                                   ", i );
            else {
                char *name = ( (U64)pair->name & U64_HIBIT ? (char*)&pair->name : pair->name );
                U64 addr = pair->addr;

                printf( "%4d: pair:[%p] %10.10I64u %-10s ", i ,pair, addr, name );
            }
            printf( "[ byStr: %6u ]\n",  bm->byStr[ i ] );
        }
}

BIMAP *new( U32 initSize, double factor ) {
    BIMAP *bm = (BIMAP*)malloc( sizeof( BIMAP ) );
    initSize  = nextPowerOfTwo( initSize );
    bm->byInt = (PAIR**)calloc( initSize, sizeof( PAIR ) );
    bm->byStr = (U32*)calloc( initSize, sizeof( U32 ) );
    bm->size  = initSize;
    bm->used  = 0;
    bm->factor = factor;
    return bm;
}

U32 used( BIMAP *bm ) { return bm->used; }
U32 size( BIMAP *bm ) { return bm->size; }
double factor( BIMAP *bm ) { return bm->factor; }
U32 addPair( BIMAP *bm, PAIR *pair );
U32 add( BIMAP *bm, U64 i, SV *sv );


void resize( BIMAP *bm, U32 newSize ) {
    BIMAP *newBm = new( newSize, bm->factor );
    U32 i;

//    printf( "Resize: from %u(%u) to %u\n", bm->size, bm->used, newSize );

    for( i = 0; i < bm->size; ++i ) {
        if( bm->byInt[ i ] ) {
            addPair( newBm, bm->byInt[ i ] );
        }
    }
    free( bm->byInt );
    free( bm->byStr );
    bm->byInt = newBm->byInt;
    bm->byStr = newBm->byStr;
    bm->size  = newBm->size;
    bm->used  = newBm->used;
    free( newBm );
    return;
}

U32 __inline addPair( BIMAP *bm, PAIR *pair ) {
    U32 nameLen = (U32)strlen( (U64)pair->name & U64_HIBIT ? (char*)&pair->name : pair->name );
    register U32 mask = bm->size - 1;
    register U32 iHash = hash( (char*)&pair->addr, 8 ) & mask,
                 sHash = hash( (U64)pair->name & U64_HIBIT ? (char*)&pair->name : pair->name, nameLen ) & mask;
    U32 iIters = 0, sIters = 0;

    if( bm->used > (U32)( bm->size * bm->factor ) ) {
        resize( bm, bm->size * 2 );
        mask = bm->size - 1;
        iHash = hash( (char*)&pair->addr, 8 ) & mask;
        sHash = hash( (U64)pair->name & U64_HIBIT ? (char*)&pair->name : pair->name, nameLen ) & mask;
    }

    while( bm->byInt[ iHash ] ) {
        ++iIters;
        iHash = ( iHash + 1 ) & mask;
    }
    while( bm->byStr[ sHash ] ) {
        ++sIters;
        sHash = ( sHash + 1 ) & mask;
    }

    bm->byInt[ iHash ] = pair;
    bm->byStr[ sHash ] = iHash+1;
    bm->used++;

    return iIters + sIters;
}

U32 add( BIMAP *bm, U64 i, SV *sv ) {
    STRLEN l;
    char *s = SvPV( sv, l );
    PAIR *pair = (PAIR*)calloc( 1, sizeof( PAIR ) );

    pair->addr = i;

    if( l < 7 ) {
        strncpy( (char*)(&pair->name), s, l );
        (U64)pair->name |= U64_HIBIT;
    }
    else {
        pair->name = _strdup( s );
    }
    return addPair( bm, pair );
}

U64 findByStr( BIMAP *bm, char *s ) {
    U32 sLen = (U32)strlen( s );
    register U32 mask = bm->size - 1, sIters = 0;
    register U32 sHash = hash( s, sLen ) & mask;
    register PAIR **byInt = bm->byInt;
    register U32   *byStr = bm->byStr;
    register char *name;

    if( !byStr[ sHash ] ) return -1;

    name = (U64)byInt[ byStr[ sHash ]-1 ]->name & U64_HIBIT
         ? (char*)&(U64)byInt[ byStr[ sHash ]-1 ]->name
         : byInt[ byStr[ sHash ]-1 ]->name;

    while( strcmp( name, s ) ) {
        sHash = ( sHash + 1 ) & mask;
        if( !byStr[ sHash ] || !byInt[ byStr[ sHash ]-1 ] ) return -1;
        name = (U64)byInt[ byStr[ sHash ]-1 ]->name & U64_HIBIT
             ? (char*)&(U64)byInt[ byStr[ sHash ]-1 ]->name
             : byInt[ byStr[ sHash ]-1 ]->name;
    }
    return byInt[ byStr[ sHash ]-1 ]->addr;
}

char *findByInt( BIMAP *bm, U64 i ) {
    register U32 mask = bm->size - 1;
    register U32 iHash = hash( (char*)&i, 8 ) & mask;
    register PAIR **byInt = bm->byInt;

    if( !byInt[ iHash ] ) return "$^&* NOT FOUND ON FIRST TRY *&^$";

    while( byInt[ iHash ]->addr != i ) {
        if( ! byInt[ iHash = ( iHash + 1 ) & mask ] ) return "$^&* NOT FOUND AT ALL *&^$";
    }
    return (U64)( byInt[ iHash ]->name ) & U64_HIBIT ? (char*)&byInt[ iHash ]->name : byInt[ iHash ]->name;
}

void DESTROY ( BIMAP *bm ) {
    U32 i;

    for( i=0; i < bm->size; ++i ) {
        if( bm->byInt[ i ] ) {
            if( !( (U64)bm->byInt[ i ]->name & ~U64_HIBIT ) ) free( bm->byInt[ i ]->name );
            free( bm->byInt[ i ] );
        }
    }
    free( bm->byInt );
    free( bm->byStr );
    free( bm );
}

END_C

sub CLONE { print "CLONE called [@_]"; }
sub CLONE_SKIP { print "CLONE_SKIP called [@_]"; 0 }

package main;
use threads;
use threads::shared;
use Time::HiRes qw[ time ];
use Data::Dump qw[ pp ];
use List::Util qw[ sum ];
use Devel::Peek;

$|++;
our $S //= 4;
our $F //= 0.9;
our $I //= 26**$S;

my $flag :shared = 0;

my $t = async {
    my $bm = BiMap::new( $I, $F );
    pp $bm;

    my $i = 1;
    $bm->add( $i++, $_ ) for 'a' x $S .. 'z' x $S;

#    printf "$_ : %I64x\n", $bm->findByStr( $_ ) for 'a'x$S .. 'z'x$S;

    $bm->dump( 1 );
    $flag = 1;
    Dump( $bm );
    return $bm;
};

sleep 1 until $flag;

my $bm = $t->join;
pp $bm; Dump( $bm );
$bm->dump( 1 );

#printf "$_ : %I64x\n", $bm->findByStr( $_ ) for 'a'x$S .. 'z'x$S;