の完全なまたは完全なハッシュに近いアドレス

Question

0xc0003000から0xc04a0144までのメモリアドレスのリストがあり、リストには多くのギャップと< 4096のエントリがあります。それはコンパイル時に知られており、私はそれを完璧にハッシュしたい。

しかし、完全なハッシュをオンラインで検索すると、ほとんどがハッシュ文字列に関連した情報が得られ、翻訳がうまくいかないようです。

明確にするには、実行時にメモリアドレスを取得し、ハッシュにすぐに入っていることを確認したいと思います。現在私は答えを見つけるために平均で約8ループのバイナリ検索を使用しています。

どのようなツリーを私は樹皮すべきですか？

Answer 1

ここにgperfのサンプルプログラムがあります。サンプルデータにNULと改行を含めて、失敗を起こさないことを証明しました。 addrs.gperfとして

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

保存し、コンパイルして、Bツリーや赤、黒のようなバランスの取れた木は約

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