Cの汎用ハッシュテーブル

Question

Cで一般的なハッシュテーブルを作成しようとしています。いくつかの実装を読み、いくつかのアプローチがありました。

最初はこのようなマクロを使用することです：http://attractivechaos.awardspace.com/khash.h.html

をそして第​​二には、このような2つのボイドポインタと構造体を使用することです：私はこのアプローチを伝えることができるものから、

struct hashmap_entry 
{ 
    void *key; 
    void *value; 
}; 

ではありませんこれは、マップの各エントリに、格納されるデータ型に関係なく、キーと値の少なくとも2つの割り当てが必要であることを意味します。 （それは正しいですか？）

私は、マクロルートを使わずに汎用性を保つための適切な方法を見つけることができませんでした。誰か助けてくれるヒントや例がありますか？

Answer 1

Cには一般的なデータ型がありません。そのため、実際には余分な割り当てや、void*のキャストはできません。あなたはすぐに正しいデータ関数/構造体を生成するためにマクロを使うことができますが、マクロも避けようとしています。

あなたはあなたのアイデアを少なくとも1つ放棄する必要があります。

あなたのような何かに割り当てることによって、余分な配分せず、一般的なデータ構造を持つことができます：一度に

size_t key_len; 
size_t val_len; 
char key[]; 
char val[]; 

をし、その後、ボイドポインタのいずれかを配って、各特定のタイプのためのAPIを追加。

あなたが処理するために必要な種類の数が限られている場合は別の方法として、あなたはまた、右のいずれかで値にタグを付けることができるようになりました各項目が含まれています

size_t key_len; 
size_t val_len; 
int val_type; 
char key[]; 
char val[]; 

いますが、少なくともAPIでの要求されたタイプが正しいタイプであることを確認してください。

それ以外の場合は、すべてを汎用的にするために、マクロを使用するか、言語を変更する必要があります。

Answer 2

Cは、それにもかかわらず、あなたがこのような何かをしたい場合、あなたが直接必要なものを提供していません：

あなたのハッシュテーブルは、二重リンクリストの固定サイズの配列であり、アイテムが常に割り当てられていることをOKであることを想像してみて/アプリケーション層で破壊される。これらの条件は、すべてのケースで機能するわけではありませんが、多くの場合、そのようになります。あなたはハッシュテーブルのロジックを実装する必要があり、これらの機能には

struct HashItemCore 
{ 
    HashItemCore *m_prev; 
    HashItemCore *m_next; 
}; 

struct HashTable 
{ 
    HashItemCore m_data[256]; // This is actually array of circled 
            // double linked lists. 
    int  (*GetHashValue)(HashItemCore *item); 
    bool (*CompareItems)(HashItemCore *item1, HashItemCore *item2); 
    void (*ReleaseItem)(HashItemCore *item); 
}; 

void InitHash(HashTable *table) 
{ 
    // Ensure that user provided the callbacks. 
    assert(table->GetHashValue != NULL && table->CompareItems != NULL && table->ReleaseItem != NULL); 

    // Init all double linked lists. Pointers of empty list should point to themselves. 
    for (int i=0; i<256; ++i) 
     table->m_data.m_prev = table->m_data.m_next = table->m_data+i; 
} 

void AddToHash(HashTable *table, void *item); 
void *GetFromHash(HashTable *table, void *item); 
.... 
void *ClearHash(HashTable *table); 

：次に、あなたは機能やprotototypesのこれらのデータ構造やスケッチを持っています。働いている間、彼らはスロットのインデックスを見つけるために、そして項目が同一であるかどうかを見つけるためにユーザ定義のコールバックを呼び出すでしょう。このテーブルのユーザは、彼らが使用するタイプのすべてのペアのために、独自の構造やコールバック関数を定義する必要があり

：項目は無効と周りに渡されますので、

struct HashItemK1V1 
{ 
    HashItemCore m_core; 
    K1 key; 
    V1 value; 
}; 

int CalcHashK1V1(void *p) 
{ 
    HashItemK1V1 *param = (HashItemK1V1*)p; 
    // App code. 
} 

bool CompareK1V1(void *p1, void *p2) 
{ 
    HashItemK1V1 *param1 = (HashItemK1V1*)p1; 
    HashItemK1V1 *param2 = (HashItemK1V1*)p2; 
    // App code. 
} 

void FreeK1V1(void *p) 
{ 
    HashItemK1V1 *param = (HashItemK1V1*)p; 
    // App code if needed. 
    free(p); 
} 

このアプローチでは、型の安全性を提供することはありませんすべてのアプリケーション構造がHashItemCoreメンバで始まるものと仮定するポインタ。これは多種多様な手作りのものです。これは完璧ではないかもしれませんが、これはうまくいくでしょう。

私はテンプレートを使用してこのアプローチをC++で実装しました。しかし、あなたがC++のすべての想像を取り除くならば、要するに、私が上で述べたこととまったく同じになるでしょう。私は複数のプロジェクトでテーブルを使いましたが、それは魅力的でした。

Answer 3

Cの一般ハッシュテーブルは悪い考えです。

• これらの関数がインライン化することができないので、遅い関数ポインタを、必要とするニート実装（一般的なケースは、少なくとも2つの関数呼び出しホップ当たり必要があります：一つはハッシュ値といずれかを計算します最終的には、比較のために）
• あなたは
  • に手動
  • コードを書いたり、コードジェネレータ
  を使用していますいずれかの関数のインライン化を可能にするには
  • またはマクロ。これは厄介な

IIRCを得ることができ、Linuxカーネルが作成し、維持するために、マクロを使用しています（の一部？）をそのハッシュテーブルを。