quasi perfetto o perfetto hash di indirizzi di memoria in c

Question

Ho una lista di indirizzi di memoria da 0xc0003000 a 0xc04a0144 ci sono molte lacune e < 4096 voci nella lista. È noto al momento della compilazione e voglio fare un hash perfetto per questo.

Tuttavia, cercare l'hashing perfetto in linea mi fornisce informazioni per lo più correlate alle stringhe di hashing e non sembrano tradurre bene.

Per essere chiari, voglio essere in grado di ottenere l'indirizzo di memoria in fase di esecuzione e controllare che sia rapidamente nell'hash. Attualmente sto usando una ricerca binaria che è in media circa 8 cicli per trovare la risposta.

Qualche idea su quale albero dovrei abbaiare?

Answer 1

Ecco un esempio di programma gperf. Ho incluso un NUL e una nuova riga nei dati di esempio per dimostrare che non causano il fallimento.

%{ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <inttypes.h> 
#include <arpa/inet.h> 
%} 
%% 
"\xc0\x01\x02\x03" 
"\xc0\xff\xff\xff" 
"\xc0\xff\x00\xff" 
"\xc0\x0a\xff\xff" 
%% 
int main(int argc, const char **argv) 
{ 
    int i; 

    for(i=1;i<argc;++i) { 
     uint32_t addr = ntohl(strtoul(argv[i], 0, 16)); 
     if(in_word_set((char *)&addr, 4)) 
      printf("0x%08"PRIx32" is in the list.\n", htonl(addr)); 
     else 
      printf("0x%08"PRIx32" is not in the list.\n", htonl(addr)); 
    } 
    return 0; 
} 

Salva come addrs.gperf, compilare e test con

gperf -l addrs.gperf > addrs.c 
gcc addrs.c -o addrs 
./addrs c0000000 c0010203 c0ffffff c00affff c0ff0aff c0ffff00 c0ff00ff