cerca de perfecto o perfecto hash de direcciones de memoria en c

Question

Tengo una lista de direcciones de memoria de 0xc0003000 a 0xc04a0144 hay muchas lagunas y < 4096 entradas en la lista. Es conocido en tiempo de compilación y quiero hacer un hash perfecto para ello.

Sin embargo, buscar el hashing perfecto en línea me da información principalmente relacionada con las cadenas hash y no parecen traducirse bien.

Para ser claro, quiero ser capaz de obtener la dirección de la memoria en tiempo de ejecución y verificar que esté en el hash rápidamente. Actualmente estoy usando una búsqueda binaria que es en promedio de 8 bucles para encontrar la respuesta.

¿Alguna idea de qué árbol debería ladrar?

Answer 1

Aquí hay un programa de ejemplo de gperf. Incluí un NUL y una nueva línea en los datos de muestra para probar que no causan que falle.

%{ 
#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; 
} 

Guardar como addrs.gperf, compilar y probar con

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