/*
|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 226
int HT_SHIFTS[ 226 ] = { 0 , 0 , 0 , 0 , 0 , 1 , 0 , 2 , 11 , 0 , 2 , 12 , 17 , 2 , 69 , 37 , 41 , 100 , 0 , 0 , 1 , 0 , 1 , 54 , 22 , 42 , 37 , 38 , 0 , 114 , 91 , 135 , 110 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 109 , 5 , 0 , 2 , 0 , 0 , 41 , 66 , 1 , 64 , 35 , 0 , 0 , 0 , 0 , 0 , 0 , 9 , 16 , 0 , 0 , 0 , 0 , 85 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 3 , 1 , 0 , 40 , 0 , 0 , 0 , 0 , 4 , 6 , 0 , 0 , 0 , 1 , 6 , 0 , 0 , 6 , 10 , 0 , 0 , 8 , 12 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 28 , 3 , 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[ 226 ] ;
#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+CgojZGVmaW5lIEhUX1NJWkUgMjI2CmludCBIVF9TSElGVFNbMjI2XSA9IHswLCAwLCAwLCAwLCAwLCAxLCAwLCAyLCAxMSwgMCwgMiwgMTIsIDE3LCAyLCA2OSwgMzcsIDQxLCAxMDAsIDAsIDAsIDEsIDAsIDEsIDU0LCAyMiwgNDIsIDM3LCAzOCwgMCwgMTE0LCA5MSwgMTM1LCAxMTAsIDAsIDAsIDAsIDAsIDIsIDAsIDAsIDEwOSwgNSwgMCwgMiwgMCwgMCwgNDEsIDY2LCAxLCA2NCwgMzUsIDAsIDAsIDAsIDAsIDAsIDAsIDksIDE2LCAwLCAwLCAwLCAwLCA4NSwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMywgMSwgMCwgNDAsIDAsIDAsIDAsIDAsIDQsIDYsIDAsIDAsIDAsIDEsIDYsIDAsIDAsIDYsIDEwLCAwLCAwLCA4LCAxMiwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMSwgMCwgMCwgMCwgMCwgMywgMCwgMCwgMCwgMSwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMCwgMjgsIDMsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDAsIDB9OwppbnQgSFRfVEFCTEVbMjI2XSA7CiNkZWZpbmUgSFRfbG9va3VwKGkpIEhUX1RBQkxFWygoaSkrSFRfU0hJRlRTWyhpKS9IVF9TSVpFXSklSFRfU0laRV0KCmludCAqbmV4dDsKCnZvaWQgbG9va3VwX2luaXQoKQp7Cn0Kdm9pZCBsb29rdXBfdXBkYXRlKAogICAgY29uc3QgaW50IGtGaXJzdCwKICAgIGNvbnN0IGludCBrU2Vjb25kLAogICAgY29uc3QgaW50IGtUaGlyZCwKICAgIGludCogZmlyc3RSb3csCiAgICBpbnQqIHNlY29uZFJvdywKICAgIGludCogdGhpcmRSb3cKKSB7CiAKICAgIC8qIEdsaSBlc2VtcGkgcHJhdGljaSBzb25vOgogICAgICAgMSBjb21ibykgYXpiZGNlfHxkZmVmCiAgICAgICAyIGNvbWJvKSBhemJkfGNlfGRmZWYKICAgICAgIDMgY29tYm8pIGF6fGJkY2V8ZGZlZgogCiAgICAgICBRdWluZGkgdHJhc2Zvcm1vIGxlICJ0YWJlbGxlIiBpbiBzdHJpbmdoZSBjb3PDrCBkYSBwb3RlcmxlIGNvbnZlcnRpcmUKICAgICAgIGluIGhhc2guICovCiAgICBpbnQga2V5ID0gMDsKICAgIGZvciAoIGludCBpID0gMDsgaSA8IGtGaXJzdDsgaSsrICkgewogICAgICAgIGtleSB8PSAxPDxmaXJzdFJvd1sgaSBdOwogICAgfQogICAga2V5ID0ga2V5PDw1OwogICAgZm9yICggaW50IGkgPSAwOyBpIDwga1NlY29uZDsgaSsrICkgewogICAgICAgIGtleSB8PSAxPDxzZWNvbmRSb3dbIGkgXTsKICAgIH0KICAgIGtleSA9IGtleTw8NTsKICAgIGZvciAoIGludCBpID0gMDsgaSA8IGtUaGlyZDsgaSsrICkgewogICAgICAgIGtleSB8PSAxPDx0aGlyZFJvd1sgaSBdOwogICAgfQogICAgCiAgICBuZXh0ID0gJkhUX2xvb2t1cChrZXkpOwogCiAgICArKygqbmV4dCk7Cn0KCnZvaWQgbG9va3VwX2ZyZWUoKQp7CiAgICAKfQogCmludCBtYWluKHZvaWQpCnsKICAgIC8qCiAgICAgICAgSXBvdGl6emFuZG8gZGkgYXZlcmUgdW5hIHRhYmVsbGEgZGEgMyByaWdoZSBlIDUgY29sb25uZToKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogICAgICAgIHwgICAgfCAgICB8ICAgIHwgICAgfCAgICB8CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKICAgICAgICB8ICAgIHwgICAgfCAgICB8ICAgIHwgICAgfAogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAgICAgICAgfCAgICB8ICAgIHwgICAgfCAgICB8ICAgIHwKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogCiAgICAgICAgZSBkaSByaWVtcGlybGEgY2FzdWFsbWVudGUgKHBvcG9sYW5kb2xhIGRhIHNpbmlzdHJhIGEgZGVzdHJhIGNvbiB1bgogICAgICAgIGluZGljZSBjaGUgY29ycmlzcG9uZGUgYWQgdW5hIGxldHRlcmEgZGVsbGEgYXJyYXkgImFiIikKIAogICAgICAgIHN0YXRpYyBjaGFyKiBhYltdID0gewogICAgICAgICAgICAiYXoiLCAiYmQiLCAiY2UiLCAiZGYiLCAiZWYiLCAiZmQiLCAiZ2wiCiAgICAqLwogICAgaW50IF8xcm93WzVdOwogICAgaW50IF8ycm93WzVdOwogICAgaW50IF8zcm93WzVdOwogCiAgICBsb29rdXBfaW5pdCgpOwogCiAgICAvKgogICAgICAgIFByaW1hIGNvbWJpbmF6aW9uZToKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogICAgICAgIHwgYXogfCBiZCB8IGNlIHwgICAgfCAgICB8CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKICAgICAgICB8ICAgIHwgICAgfCAgICB8ICAgIHwgICAgfAogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAgICAgICAgfCBkZiB8IGVmIHwgICAgfCAgICB8ICAgIHwKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogICAgKi8KICAgIF8xcm93WzBdID0gMDsKICAgIF8xcm93WzFdID0gMTsKICAgIF8xcm93WzJdID0gMjsKICAgIF8zcm93WzBdID0gMzsKICAgIF8zcm93WzFdID0gNDsKICAgIGZvciAoIGludCBjID0gMDsgYyA8IDU7IGMrKyApIHsKICAgICAgICAvKiBWZXJpZmljbyBjaGUgbGEgY29tYmluYXppb25lIGVzaXN0YSBnacOgLCBzZSBub24gZXNpc3RlIGxhIGNyZW8KICAgICAgICAgICBhbHRyaW1lbnRpIGFnZ2lvcm5vIGlsIGNhbXBvICJkYXRhIi4KICAgICAgICAgICBJbiBxdWVzdG8gbGEgcHJpbWEgY29tYmluYXppb25lIGF2csOgIGlsIGNhbXBvICJkYXRhIiBjb24gaWwgdmFsb3JlCiAgICAgICAgICAgNCAodmlzdG8gY2hlIGluY3JlbWVudGVyw6AgYWQgb2duaSAibG9va3VwX3VwZGF0ZSIpICovCiAgICAgICAgbG9va3VwX3VwZGF0ZSggMywgMCwgMiwgXzFyb3csIF8ycm93LCBfM3JvdyApOwogICAgfQogCiAgICAvKgogICAgICAgIFNlY29uZGEgY29tYmluYXppb25lOgogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAgICAgICAgfCBheiB8IGJkIHwgICAgfCAgICB8ICAgIHwKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogICAgICAgIHwgY2UgfCAgICB8ICAgIHwgICAgfCAgICB8CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKICAgICAgICB8IGRmIHwgZWYgfCAgICB8ICAgIHwgICAgfAogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAKICAgICAgICBDYW1wbyAiZGF0YSIgY29uIHZhbG9yZSAxLgogICAgKi8KICAgIF8xcm93WzBdID0gMDsKICAgIF8xcm93WzFdID0gMTsKICAgIF8ycm93WzBdID0gMjsKICAgIF8zcm93WzBdID0gMzsKICAgIF8zcm93WzFdID0gNDsKICAgIGZvciAoIGludCBjID0gMDsgYyA8IDI7IGMrKyApIHsKICAgICAgICBsb29rdXBfdXBkYXRlKCAyLCAxLCAyLCBfMXJvdywgXzJyb3csIF8zcm93ICk7CiAgICB9CiAKICAgIC8qCiAgICAgICAgVGVyemEgY29tYmluYXppb25lOgogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAgICAgICAgfCBheiB8ICAgIHwgICAgfCAgICB8ICAgIHwKICAgICAgICArLS0tLSstLS0tKy0tLS0rLS0tLSstLS0tKwogICAgICAgIHwgYmQgfCBjZSB8ICAgIHwgICAgfCAgICB8CiAgICAgICAgKy0tLS0rLS0tLSstLS0tKy0tLS0rLS0tLSsKICAgICAgICB8IGRmIHwgZWYgfCAgICB8ICAgIHwgICAgfAogICAgICAgICstLS0tKy0tLS0rLS0tLSstLS0tKy0tLS0rCiAKICAgICAgICBDYW1wbyAiZGF0YSIgY29uIHZhbG9yZSAyLgogICAgKi8KICAgIF8xcm93WzBdID0gMDsKICAgIF8ycm93WzBdID0gMTsKICAgIF8ycm93WzFdID0gMjsKICAgIF8zcm93WzBdID0gMzsKICAgIF8zcm93WzFdID0gNDsKICAgIGZvciAoIGludCBjID0gMDsgYyA8IDM7IGMrKykgewogICAgICAgIGxvb2t1cF91cGRhdGUoIDEsIDIsIDIsIF8xcm93LCBfMnJvdywgXzNyb3cgKTsKICAgIH0KIAogICAgLyoKICAgICAgICBRdWVzdGEgw6ggc2VtcHJlIGxhIHNlY29uZGEgY29tYmluYXppb25lLCBwZXJjacOyIGluY3JlbWVudGEgaWwgY2FtcG8KICAgICAgICAiZGF0YSIgZGkgMTUgdmFsb3JpLgogICAgKi8KICAgIF8xcm93WzBdID0gMDsKICAgIF8xcm93WzFdID0gMTsKICAgIF8ycm93WzBdID0gMjsKICAgIF8zcm93WzBdID0gMzsKICAgIF8zcm93WzFdID0gNDsKICAgIGZvciAoIGludCBjID0gMDsgYyA8IDE1OyBjKysgKSB7CiAgICAgICAgbG9va3VwX3VwZGF0ZSggMiwgMSwgMiwgXzFyb3csIF8ycm93LCBfM3JvdyApOwogICAgfQogCiAgICBwcmludGYoIiVkIiwgKm5leHQpOwogCiAgICBsb29rdXBfZnJlZSgpOwp9