c - メモリCのIPルックアップテーブル

Question

私は現在、libpcapとさまざまなCアプリケーションを試し、次のことを実行しようとしています。プログラムの初期化時に、ファイルからIPをロードして、メモリに保存したいと思います。処理のためにパケットの詳細を受け取ったら、IPをメモリにロードされたIPのセットと比較したいと思います。

これをCで実装するための最良の方法/データ構造は何ですか？リストの増加と効率的なマッチングに対応する必要があるため、単純なルックアップ配列は間違った解決策になると思います。ヘルプ？

Answer 1

おそらく、実行時にIPを削除することはなく、追加するだけです。リストが大きくならない場合は、リストを並べ替えても大きなメリットはありません。

これらの2つの事実を考えると、私はおそらくそれらすべてを（十分なサイズの）配列にチャックし、必要に応じて線形検索を実行します。配列内のデータの終わりがどこにあるかを追跡します。そこに新しいエントリを追加するのは簡単なことです。

それが本当に遅すぎる場合は、ハッシュテーブルを作成できます。もちろん、衝突を回避するために、IPマップの一般的な内容に基づいて微調整する必要があります（Cには標準のハッシュがないため、開発およびデバッグされます）。PITAのビットですが、実行可能である必要があります。

私はその中間に何も気にしません（おそらくルックアップにバイナリ検索を使用します）。あなたがスピードを切望しているなら、あなたはずっと行くほうがよいでしょう。

Answer 2

あなたがあなたのテーブルに持っている可能性が高いIPアドレスであるかどうかは多くが数に依存します。

少数の場合、平衡二分木（AVL木など）は適切に機能するはずです。かなりのオーバーヘッド（ノードごとに2つのポインター）がありますが、ノードの数が少ない限り、おそらくそれほど問題にはなりません（メモリが制限されているシステムをターゲットにしている場合を除く）。単一ノードが最大N個のIPアドレスを配列に格納するハイブリッドを使用することもできます。Nを半慎重に選択すると、ポインタのオーバーヘッドを減らし、キャッシュの使用率を向上させることができます。

10K程度を超える可能性がある場合は、代わりにトライを使用することを検討する価値があります。

非常に大きな数になる可能性がある場合は、IPアドレスごとに1ビットの単純なビットセットを使用することを検討してください。

編集：ルックアップと比較した挿入/削除の頻度にも依存する可能性があることを追加する必要があります。多くの状況で役立つと思ったハイブリッド構造の1つは、並べ替えられたメイン配列から始めて、アイテムが追加されたら、並べ替えられていない別の配列に保持することです。セカンダリアレイが大きくなりすぎた場合は、それを並べ替えてメインアレイとマージします。

Answer 3

本当にまともなパフォーマンスのために、絶対に最小限の作業量は、おそらく、の配列を使用することですuint32_t。

データをロードするときは、必要に応じてを使用して、各IPをアレイにスローしますrealloc()。正常な成長パターンを使用することを忘れないでください。割り当てられた長さを使い切るたびに2倍にするのが一般的であり、おそらくうまく機能します。

http://linux.die.net/man/3/qsortロード後、単純な呼び出しを使用して配列をソートします。

次に、を使用して配列をすばやく検索できますbsearch()。

これは標準関数のみを使用するため、コード的には非常に小さく、理解しやすく、すばやく記述できます。依存関係はなく、正常なライブラリを追跡したり、独自の高レベルのデータ構造を記述したりするために費やす時間もありません。しかし、二分探索を使用しているため、かなり高速になります。