/*
|r1 |r2 |r3
#|012 34|01 234|0 1234
0|111 00|00 001|0 0010
Massimo indice possibile:
0|111 00|00 011|0 0000 = 2^14+2^13+2^12+2^6+2^5 = 28768
*/
#include <stdio.h>
#define HT_SIZE 232
int HT_SHIFTS[ 232 ] = { 0 , 0 , 0 , 0 , 1 , 0 , 12 , 6 , 10 , 4 , 3 , 0 , 0 , 15 , 1 , 51 , 62 , 34 , 4 , 4 , 0 , 4 , 78 , 11 , 37 , 6 , 13 , 12 , 22 , 0 , 0 , 135 , 118 , 71 , 54 , 0 , 10 , 1 , 0 , 10 , 7 , 7 , 2 , 0 , 2 , 0 , 3 , 63 , 6 , 9 , 18 , 5 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 6 , 6 , 0 , 3 , 0 , 0 , 0 , 0 , 0 , 7 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 4 , 0 , 1 , 0 , 8 , 19 , 10 , 0 , 0 , 0 , 0 , 0 , 0 , 25 , 7 , 9 , 0 , 0 , 0 , 17 , 0 , 0 , 0 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 0 , 1 , 5 , 0 , 0 , 2 , 10 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 4 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } ;
int HT_TABLE[ 232 ] ;
#define HT_lookup(i) HT_TABLE[((i)+HT_SHIFTS[(i)/HT_SIZE])%HT_SIZE]
int * next;
void lookup_init( )
{
}
void lookup_update(
const int kFirst,
const int kSecond,
const int kThird,
int * firstRow,
int * secondRow,
int * thirdRow
) {
/* Gli esempi pratici sono:
1 combo) azbdce||dfef
2 combo) azbd|ce|dfef
3 combo) az|bdce|dfef
Quindi trasformo le "tabelle" in stringhe così da poterle convertire
in hash. */
int key = 0 ;
for ( int i = 0 ; i < kFirst; i++ ) {
key |= 1 << firstRow[ i ] ;
}
key = key<< 5 ;
for ( int i = 0 ; i < kSecond; i++ ) {
key |= 1 << secondRow[ i ] ;
}
key = key<< 5 ;
for ( int i = 0 ; i < kThird; i++ ) {
key |= 1 << thirdRow[ i ] ;
}
next = & HT_lookup( key) ;
++ ( * next) ;
}
void lookup_free( )
{
}
int main( void )
{
/*
Ipotizzando di avere una tabella da 3 righe e 5 colonne:
+----+----+----+----+----+
| | | | | |
+----+----+----+----+----+
| | | | | |
+----+----+----+----+----+
| | | | | |
+----+----+----+----+----+
e di riempirla casualmente (popolandola da sinistra a destra con un
indice che corrisponde ad una lettera della array "ab")
static char* ab[] = {
"az", "bd", "ce", "df", "ef", "fd", "gl"
*/
int _1row[ 5 ] ;
int _2row[ 5 ] ;
int _3row[ 5 ] ;
lookup_init( ) ;
/*
Prima combinazione:
+----+----+----+----+----+
| az | bd | ce | | |
+----+----+----+----+----+
| | | | | |
+----+----+----+----+----+
| df | ef | | | |
+----+----+----+----+----+
*/
_1row[ 0 ] = 0 ;
_1row[ 1 ] = 1 ;
_1row[ 2 ] = 2 ;
_3row[ 0 ] = 3 ;
_3row[ 1 ] = 4 ;
for ( int c = 0 ; c < 5 ; c++ ) {
/* Verifico che la combinazione esista già, se non esiste la creo
altrimenti aggiorno il campo "data".
In questo la prima combinazione avrà il campo "data" con il valore
4 (visto che incrementerà ad ogni "lookup_update") */
lookup_update( 3 , 0 , 2 , _1row, _2row, _3row ) ;
}
/*
Seconda combinazione:
+----+----+----+----+----+
| az | bd | | | |
+----+----+----+----+----+
| ce | | | | |
+----+----+----+----+----+
| df | ef | | | |
+----+----+----+----+----+
Campo "data" con valore 1.
*/
_1row[ 0 ] = 0 ;
_1row[ 1 ] = 1 ;
_2row[ 0 ] = 2 ;
_3row[ 0 ] = 3 ;
_3row[ 1 ] = 4 ;
for ( int c = 0 ; c < 2 ; c++ ) {
lookup_update( 2 , 1 , 2 , _1row, _2row, _3row ) ;
}
/*
Terza combinazione:
+----+----+----+----+----+
| az | | | | |
+----+----+----+----+----+
| bd | ce | | | |
+----+----+----+----+----+
| df | ef | | | |
+----+----+----+----+----+
Campo "data" con valore 2.
*/
_1row[ 0 ] = 0 ;
_2row[ 0 ] = 1 ;
_2row[ 1 ] = 2 ;
_3row[ 0 ] = 3 ;
_3row[ 1 ] = 4 ;
for ( int c = 0 ; c < 3 ; c++ ) {
lookup_update( 1 , 2 , 2 , _1row, _2row, _3row ) ;
}
/*
Questa è sempre la seconda combinazione, perciò incrementa il campo
"data" di 15 valori.
*/
_1row[ 0 ] = 0 ;
_1row[ 1 ] = 1 ;
_2row[ 0 ] = 2 ;
_3row[ 0 ] = 3 ;
_3row[ 1 ] = 4 ;
for ( int c = 0 ; c < 15 ; c++ ) {
lookup_update( 2 , 1 , 2 , _1row, _2row, _3row ) ;
}
lookup_free( ) ;
}
LyoKIHxyMSAgIHxyMiAgICAgIHxyMwojfDAxMiAzNHwwMSAgMjM0fDAgMTIzNAowfDExMSAwMHwwMCAgMDAxfDAgMDAxMAoKTWFzc2ltbyBpbmRpY2UgcG9zc2liaWxlOgowfDExMSAwMHwwMCAgMDExfDAgMDAwMCA9IDJeMTQrMl4xMysyXjEyKzJeNisyXjUgPSAyODc2OAoqLwoKI2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIEhUX1NJWkUgMjMyCmludCBIVF9TSElGVFNbMjMyXSA9IHswLCAwLCAwLCAwLCAxLCAwLCAxMiwgNiwgMTAsIDQsIDMsIDAsIDAsIDE1LCAxLCA1MSwgNjIsIDM0LCA0LCA0LCAwLCA0LCA3OCwgMTEsIDM3LCA2LCAxMywgMTIsIDIyLCAwLCAwLCAxMzUsIDExOCwgNzEsIDU0LCAwLCAxMCwgMSwgMCwgMTAsIDcsIDcsIDIsIDAsIDIsIDAsIDMsIDYzLCA2LCA5LCAxOCwgNSwgMCwgMCwgMCwgMCwgMCwgMSwgMCwgMSwgMCwgNiwgNiwgMCwgMywgMCwgMCwgMCwgMCwgMCwgNywgMCwgMCwgMCwgMCwgMSwgMCwgMCwgMCwgNCwgMCwgMSwgMCwgOCwgMTksIDEwLCAwLCAwLCAwLCAwLCAwLCAwLCAyNSwgNywgOSwgMCwgMCwgMCwgMTcsIDAsIDAsIDAsIDAsIDAsIDAsIDMsIDAsIDAsIDAsIDAsIDEsIDUsIDAsIDAsIDIsIDEwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCA0LCAyLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwLCAwfTsKaW50IEhUX1RBQkxFWzIzMl0gOwojZGVmaW5lIEhUX2xvb2t1cChpKSBIVF9UQUJMRVsoKGkpK0hUX1NISUZUU1soaSkvSFRfU0laRV0pJUhUX1NJWkVdCgppbnQgKm5leHQ7Cgp2b2lkIGxvb2t1cF9pbml0KCkKewp9CnZvaWQgbG9va3VwX3VwZGF0ZSgKICAgIGNvbnN0IGludCBrRmlyc3QsCiAgICBjb25zdCBpbnQga1NlY29uZCwKICAgIGNvbnN0IGludCBrVGhpcmQsCiAgICBpbnQqIGZpcnN0Um93LAogICAgaW50KiBzZWNvbmRSb3csCiAgICBpbnQqIHRoaXJkUm93CikgewogCiAgICAvKiBHbGkgZXNlbXBpIHByYXRpY2kgc29ubzoKICAgICAgIDEgY29tYm8pIGF6YmRjZXx8ZGZlZgogICAgICAgMiBjb21ibykgYXpiZHxjZXxkZmVmCiAgICAgICAzIGNvbWJvKSBhenxiZGNlfGRmZWYKIAogICAgICAgUXVpbmRpIHRyYXNmb3JtbyBsZSAidGFiZWxsZSIgaW4gc3RyaW5naGUgY29zw6wgZGEgcG90ZXJsZSBjb252ZXJ0aXJlCiAgICAgICBpbiBoYXNoLiAqLwogICAgaW50IGtleSA9IDA7CiAgICBmb3IgKCBpbnQgaSA9IDA7IGkgPCBrRmlyc3Q7IGkrKyApIHsKICAgICAgICBrZXkgfD0gMTw8Zmlyc3RSb3dbIGkgXTsKICAgIH0KICAgIGtleSA9IGtleTw8NTsKICAgIGZvciAoIGludCBpID0gMDsgaSA8IGtTZWNvbmQ7IGkrKyApIHsKICAgICAgICBrZXkgfD0gMTw8c2Vjb25kUm93WyBpIF07CiAgICB9CiAgICBrZXkgPSBrZXk8PDU7CiAgICBmb3IgKCBpbnQgaSA9IDA7IGkgPCBrVGhpcmQ7IGkrKyApIHsKICAgICAgICBrZXkgfD0gMTw8dGhpcmRSb3dbIGkgXTsKICAgIH0KICAgIAogICAgbmV4dCA9ICZIVF9sb29rdXAoa2V5KTsKIAogICAgKysoKm5leHQpOwp9Cgp2b2lkIGxvb2t1cF9mcmVlKCkKewogICAgCn0KIAppbnQgbWFpbih2b2lkKQp7CiAgICAvKgogICAgICAgIElwb3RpenphbmRvIGRpIGF2ZXJlIHVuYSB0YWJlbGxhIGRhIDMgcmlnaGUgZSA1IGNvbG9ubmU6CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKICAgICAgICB8ICAgIHwgICAgfCAgICB8ICAgIHwgICAgfAogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAgICAgICAgfCAgICB8ICAgIHwgICAgfCAgICB8ICAgIHwKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogICAgICAgIHwgICAgfCAgICB8ICAgIHwgICAgfCAgICB8CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKIAogICAgICAgIGUgZGkgcmllbXBpcmxhIGNhc3VhbG1lbnRlIChwb3BvbGFuZG9sYSBkYSBzaW5pc3RyYSBhIGRlc3RyYSBjb24gdW4KICAgICAgICBpbmRpY2UgY2hlIGNvcnJpc3BvbmRlIGFkIHVuYSBsZXR0ZXJhIGRlbGxhIGFycmF5ICJhYiIpCiAKICAgICAgICBzdGF0aWMgY2hhciogYWJbXSA9IHsKICAgICAgICAgICAgImF6IiwgImJkIiwgImNlIiwgImRmIiwgImVmIiwgImZkIiwgImdsIgogICAgKi8KICAgIGludCBfMXJvd1s1XTsKICAgIGludCBfMnJvd1s1XTsKICAgIGludCBfM3Jvd1s1XTsKIAogICAgbG9va3VwX2luaXQoKTsKIAogICAgLyoKICAgICAgICBQcmltYSBjb21iaW5hemlvbmU6CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKICAgICAgICB8IGF6IHwgYmQgfCBjZSB8ICAgIHwgICAgfAogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAgICAgICAgfCAgICB8ICAgIHwgICAgfCAgICB8ICAgIHwKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogICAgICAgIHwgZGYgfCBlZiB8ICAgIHwgICAgfCAgICB8CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKICAgICovCiAgICBfMXJvd1swXSA9IDA7CiAgICBfMXJvd1sxXSA9IDE7CiAgICBfMXJvd1syXSA9IDI7CiAgICBfM3Jvd1swXSA9IDM7CiAgICBfM3Jvd1sxXSA9IDQ7CiAgICBmb3IgKCBpbnQgYyA9IDA7IGMgPCA1OyBjKysgKSB7CiAgICAgICAgLyogVmVyaWZpY28gY2hlIGxhIGNvbWJpbmF6aW9uZSBlc2lzdGEgZ2nDoCwgc2Ugbm9uIGVzaXN0ZSBsYSBjcmVvCiAgICAgICAgICAgYWx0cmltZW50aSBhZ2dpb3JubyBpbCBjYW1wbyAiZGF0YSIuCiAgICAgICAgICAgSW4gcXVlc3RvIGxhIHByaW1hIGNvbWJpbmF6aW9uZSBhdnLDoCBpbCBjYW1wbyAiZGF0YSIgY29uIGlsIHZhbG9yZQogICAgICAgICAgIDQgKHZpc3RvIGNoZSBpbmNyZW1lbnRlcsOgIGFkIG9nbmkgImxvb2t1cF91cGRhdGUiKSAqLwogICAgICAgIGxvb2t1cF91cGRhdGUoIDMsIDAsIDIsIF8xcm93LCBfMnJvdywgXzNyb3cgKTsKICAgIH0KIAogICAgLyoKICAgICAgICBTZWNvbmRhIGNvbWJpbmF6aW9uZToKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogICAgICAgIHwgYXogfCBiZCB8ICAgIHwgICAgfCAgICB8CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKICAgICAgICB8IGNlIHwgICAgfCAgICB8ICAgIHwgICAgfAogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAgICAgICAgfCBkZiB8IGVmIHwgICAgfCAgICB8ICAgIHwKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogCiAgICAgICAgQ2FtcG8gImRhdGEiIGNvbiB2YWxvcmUgMS4KICAgICovCiAgICBfMXJvd1swXSA9IDA7CiAgICBfMXJvd1sxXSA9IDE7CiAgICBfMnJvd1swXSA9IDI7CiAgICBfM3Jvd1swXSA9IDM7CiAgICBfM3Jvd1sxXSA9IDQ7CiAgICBmb3IgKCBpbnQgYyA9IDA7IGMgPCAyOyBjKysgKSB7CiAgICAgICAgbG9va3VwX3VwZGF0ZSggMiwgMSwgMiwgXzFyb3csIF8ycm93LCBfM3JvdyApOwogICAgfQogCiAgICAvKgogICAgICAgIFRlcnphIGNvbWJpbmF6aW9uZToKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogICAgICAgIHwgYXogfCAgICB8ICAgIHwgICAgfCAgICB8CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKICAgICAgICB8IGJkIHwgY2UgfCAgICB8ICAgIHwgICAgfAogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAgICAgICAgfCBkZiB8IGVmIHwgICAgfCAgICB8ICAgIHwKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogCiAgICAgICAgQ2FtcG8gImRhdGEiIGNvbiB2YWxvcmUgMi4KICAgICovCiAgICBfMXJvd1swXSA9IDA7CiAgICBfMnJvd1swXSA9IDE7CiAgICBfMnJvd1sxXSA9IDI7CiAgICBfM3Jvd1swXSA9IDM7CiAgICBfM3Jvd1sxXSA9IDQ7CiAgICBmb3IgKCBpbnQgYyA9IDA7IGMgPCAzOyBjKyspIHsKICAgICAgICBsb29rdXBfdXBkYXRlKCAxLCAyLCAyLCBfMXJvdywgXzJyb3csIF8zcm93ICk7CiAgICB9CiAKICAgIC8qCiAgICAgICAgUXVlc3RhIMOoIHNlbXByZSBsYSBzZWNvbmRhIGNvbWJpbmF6aW9uZSwgcGVyY2nDsiBpbmNyZW1lbnRhIGlsIGNhbXBvCiAgICAgICAgImRhdGEiIGRpIDE1IHZhbG9yaS4KICAgICovCiAgICBfMXJvd1swXSA9IDA7CiAgICBfMXJvd1sxXSA9IDE7CiAgICBfMnJvd1swXSA9IDI7CiAgICBfM3Jvd1swXSA9IDM7CiAgICBfM3Jvd1sxXSA9IDQ7CiAgICBmb3IgKCBpbnQgYyA9IDA7IGMgPCAxNTsgYysrICkgewogICAgICAgIGxvb2t1cF91cGRhdGUoIDIsIDEsIDIsIF8xcm93LCBfMnJvdywgXzNyb3cgKTsKICAgIH0KIAogICAgcHJpbnRmKCIlZCIsICpuZXh0KTsKIAogICAgbG9va3VwX2ZyZWUoKTsKfQ==