hachage presque parfait ou parfait des adresses mémoire dans c

Question

J'ai une liste d'adresses mémoire de 0xc0003000 à 0xc04a0144. Il y a beaucoup de trous et < 4096 entrées dans la liste. Cette liste est connue au moment de la compilation et je veux en faire un hachage parfait.

Cependant, la recherche d'un hachage parfait en ligne me donne des informations principalement liées aux chaînes de hachage et elles ne semblent pas se traduire correctement.

Pour être clair, je veux pouvoir obtenir l'adresse mémoire au moment de l'exécution et vérifier rapidement qu'elle se trouve dans le hachage. Actuellement, j'utilise une recherche binaire qui nécessite en moyenne 8 boucles pour trouver la réponse.

Une idée de l'arbre que je devrais écorcer ?

Answer 1

Voici un exemple de programme gperf. J'ai inclus un NUL et une nouvelle ligne dans les données de l'échantillon pour prouver qu'ils ne font pas échouer le programme.

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

Enregistrer sous addrs.gperf , compiler et tester avec

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