C言語ハッシュテーブルuthashの使い方の詳細(ダウンロードリンク付)

15734 ワード
c
uthashの概要
  C言語自体にハッシュは存在しないが,ハッシュテーブルを使用する必要がある場合に自分でハッシュを構築することは非常に複雑である.したがって、オープンソースのサードパーティヘッダファイルを呼び出すことができます.これはヘッダファイル:uthash.hにすぎません.私たちがしなければならないのは、ヘッダファイルをあなたのプロジェクトにコピーし、#include“uthash.h”です.uthashはヘッダファイルのみなので、リンク可能なライブラリコードはありません.
  uthashを使用して追加、検索、削除は通常定数時間の操作であり、このハッシュの目標は簡潔で効率的である.約1000行のCがあります.マクロとして実装されているため、自動的にインラインされます. uthashには、チェーンテーブル、動的配列、文字列を主に提供する3つの追加のヘッダファイルも含まれています.utlist.hはC構造にリンクリストマクロを提供する.utarray.hマクロを使用して動的配列を実現します.utstring.hは基本的な動的文字列を実現する.  githubダウンロードリンク:https://github.com/troydhanso...
uthashの使用
構造体の定義
ここではidをインデックス値、すなわちキー値、nameをvalueとします.
#include "uthash.h"
struct my_struct {
    int id;                    /* key */
    char name[10];
    UT_hash_handle hh;         /* makes this structure hashable */
};
/*     NULL  */
struct my_struct *users = NULL;    /* important! initialize to NULL */

  注意:必ずUT_を含めるhash_handle hh;hhは初期化する必要はありません.任意の名前に名前を付けることができますが、一般的にはhhと名前を付けます.
追加
  HASH_ADD_INTは、intタイプ  HASH_の追加キー値を示しますADD_STRは、追加されたキー値が文字列タイプ  HASH_であることを示すADD_PTRは、追加されたキー値がポインタタイプ  HASH_であることを示すADDは、追加されたキー値が任意のタイプであってもよいことを示す
void add_user(int user_id, char *name) {
    struct my_struct *s;
    /*     ，      key                */
    HASH_FIND_INT(users, &user_id, s);  /* id already in the hash? */
    /*         ID    ，             。  ，            。*/
    if (s==NULL) {
      s = (struct my_struct *)malloc(sizeof *s);
      s->id = user_id;
      HASH_ADD_INT( users, id, s );  /* id: name of key field */
    }
    strcpy(s->name, name);
}

  HASH_ADD_INT関数では、最初のパラメータusersはハッシュテーブルであり、2番目のパラメータidはキーフィールドの名前である.最後のパラメータsは、追加する構造を指すポインタです.
検索
struct my_struct *find_user(int user_id) {
    struct my_struct *s;
    HASH_FIND_INT( users, &user_id, s );  /* s: output pointer */
    return s;
}

  上記コードでは、第1のパラメータusersはハッシュテーブルであり、第2のパラメータはuser_であるidのアドレス(必ずアドレスを渡す).最後のsは出力変数である.ハッシュ・テーブルで対応するキー値を見つけることができる場合、sは所与のキーの構造を返し、見つからない場合、sはNULLを返す.
置換
  HASH_REPLACEマクロはHASH_に等しいADDマクロ、HASH_REPLACEは、アイテム外の検索と削除を試みます.アイテムが見つかって削除された場合、そのアイテムのポインタが出力パラメータとして返されます.
void replace_user(HashHead *head, HashNode *newNode) {
    HashNode *oldNode = find_user(*head, newNode->id);
    if (oldNode)
        HASH_REPLACE_INT(*head, id, newNode, oldNode);
}

削除
ハッシュ・テーブルから構造を削除するには、そのポインタが必要です.(キーのみの場合は、構造ポインタを取得するためにHASH_FINDを先に実行します).
void delete_user(struct my_struct *user) {
    HASH_DEL(users, user);  /* user: pointer to deletee */
    free(user);             /* optional; it's up to you! */
}

  同様に、ここでusersはハッシュテーブルであり、userはハッシュから削除する構造を指すポインタである.
削除構造は、ハッシュテーブルから削除するだけでfreeではありません.いつ構造を解放するかの選択は完全に自分にかかっている.uthashは構造を解放しません
ループ削除
  HASH_ITERはマクロ定義であり,プログラム実行時にループに置き換えられる.
void delete_all() {
  struct my_struct *current_user, *tmp;

  HASH_ITER(hh, users, current_user, tmp) {
    HASH_DEL(users,current_user);  /* delete; users advances to next */
    free(current_user);            /* optional- if you want to free  */
  }
}

ハッシュ表のすべての要素を削除
  すべての項目を削除したいだけで、それらを解放したり、各要素のクリーンアップをしたりしない場合は、1回の操作でより効果的に行うことができます.
HASH_CLEAR(hh,users);

  の後、リストヘッダ(ここではusers)がNULLに設定されます.
ハッシュ表要素の個数の計算
unsigned int num_users;
num_users = HASH_COUNT(users);
printf("there are %u users
", num_users);

  usersがNULLの場合、HASH_COUNTは0を返します.
ハッシュ・テーブル内のすべてのアイテムを巡回
void print_users() {
    struct my_struct *s;

    for(s=users; s != NULL; s=s->hh.next) {
        printf("user id %d: name %s
", s->id, s->name);
    }
}

  は、任意の既知のアイテムからハッシュを後方反復するために使用できるhh.prevポインタもある.  hh.prevおよびhh.nextフィールドのため、ハッシュ内で前後に反復することができる.これらのポインタを繰り返すことで、ハッシュ内のすべてのアイテムにアクセスできます.したがって、ハッシュもデュアルチェーンテーブルです.
ハッシュ・テーブルのソート
HASH_SORT( users, name_sort );

2番目のパラメータは、比較関数を指すポインタです.2つのポインタパラメータ(比較する項目)を受け入れ、最初の項目が2番目の項目の前、等しい、または後に並べ替えられている場合は、ゼロ未満、ゼロ未満、またはゼロ以上のintを返さなければなりません.(これは、標準Cライブラリのstrcmpまたはqsortで使用される約束と同じです).
int sort_function(void *a, void *b) {
  /* compare a to b (cast a and b appropriately)
   * return (int) -1 if (a < b)
   * return (int)  0 if (a == b)
   * return (int)  1 if (a > b)
   */
}

  name_sortとid_sortの2つのソート関数の例.
int name_sort(struct my_struct *a, struct my_struct *b) {
    return strcmp(a->name,b->name);
}

int id_sort(struct my_struct *a, struct my_struct *b) {
    return (a->id - b->id);
}

void sort_by_name() {
    HASH_SORT(users, name_sort);
}

void sort_by_id() {
    HASH_SORT(users, id_sort);
}

完全なコード
#include    /* gets */
#include   /* atoi, malloc */
#include   /* strcpy */
#include "uthash.h"

struct my_struct {
    int id;                    /* key */
    char name[10];
    UT_hash_handle hh;         /* makes this structure hashable */
};

struct my_struct *users = NULL;

void add_user(int user_id, char *name) {
    struct my_struct *s;

    HASH_FIND_INT(users, &user_id, s);  /* id already in the hash? */
    if (s==NULL) {
      s = (struct my_struct *)malloc(sizeof *s);
      s->id = user_id;
      HASH_ADD_INT( users, id, s );  /* id: name of key field */
    }
    strcpy(s->name, name);
}

struct my_struct *find_user(int user_id) {
    struct my_struct *s;

    HASH_FIND_INT( users, &user_id, s );  /* s: output pointer */
    return s;
}

void delete_user(struct my_struct *user) {
    HASH_DEL(users, user);  /* user: pointer to deletee */
    free(user);
}

void delete_all() {
  struct my_struct *current_user, *tmp;

  HASH_ITER(hh, users, current_user, tmp) {
    HASH_DEL(users, current_user);  /* delete it (users advances to next) */
    free(current_user);             /* free it */
  }
}

void print_users() {
    struct my_struct *s;

    for(s=users; s != NULL; s=(struct my_struct*)(s->hh.next)) {
        printf("user id %d: name %s
", s->id, s->name);
    }
}

int name_sort(struct my_struct *a, struct my_struct *b) {
    return strcmp(a->name,b->name);
}

int id_sort(struct my_struct *a, struct my_struct *b) {
    return (a->id - b->id);
}

void sort_by_name() {
    HASH_SORT(users, name_sort);
}

void sort_by_id() {
    HASH_SORT(users, id_sort);
}

int main(int argc, char *argv[]) {
    char in[10];
    int id=1, running=1;
    struct my_struct *s;
    unsigned num_users;

    while (running) {
        printf(" 1. add user
");
        printf(" 2. add/rename user by id
");
        printf(" 3. find user
");
        printf(" 4. delete user
");
        printf(" 5. delete all users
");
        printf(" 6. sort items by name
");
        printf(" 7. sort items by id
");
        printf(" 8. print users
");
        printf(" 9. count users
");
        printf("10. quit
");
        gets(in);
        switch(atoi(in)) {
            case 1:
                printf("name?
");
                add_user(id++, gets(in));
                break;
            case 2:
                printf("id?
");
                gets(in); id = atoi(in);
                printf("name?
");
                add_user(id, gets(in));
                break;
            case 3:
                printf("id?
");
                s = find_user(atoi(gets(in)));
                printf("user: %s
", s ? s->name : "unknown");
                break;
            case 4:
                printf("id?
");
                s = find_user(atoi(gets(in)));
                if (s) delete_user(s);
                else printf("id unknown
");
                break;
            case 5:
                delete_all();
                break;
            case 6:
                sort_by_name();
                break;
            case 7:
                sort_by_id();
                break;
            case 8:
                print_users();
                break;
            case 9:
                num_users=HASH_COUNT(users);
                printf("there are %u users
", num_users);
                break;
            case 10:
                running=0;
                break;
        }
    }

    delete_all();  /* free any structures */
    return 0;
}

キー値の様々なタイプの例
整数キー値
 キー値が整数の場合、HASH_を使用できます.ADD_INTとHASH_FIND_INT.(HASH_DELETEやHASH_SORTなどの他の操作は、すべてのタイプのキーについて同じです).
文字列キー値
 キー値が文字列の場合、その関数を使用するには、構造体のキー値が文字列配列であるか文字列ポインタであるかによって異なります.この点が重要です.構造体のキー値が文字列配列の場合、HASH_を使用します.ADD_STR.キー値が文字列ポインタの場合HASH_を使用ADD_KEYPTR.次に、2つの例の参考を示します.
 構造体のキー値が文字列配列である場合
#include   /* strcpy */
#include   /* malloc */
#include    /* printf */
#include "uthash.h"

struct my_struct {
    char name[10];             /* key (string is WITHIN the structure) */
    int id;
    UT_hash_handle hh;         /* makes this structure hashable */
};


int main(int argc, char *argv[]) {
    const char *names[] = { "joe", "bob", "betty", NULL };
    struct my_struct *s, *tmp, *users = NULL;

    for (int i = 0; names[i]; ++i) {
        s = (struct my_struct *)malloc(sizeof *s);
        strcpy(s->name, names[i]);
        s->id = i;
        HASH_ADD_STR( users, name, s );
    }

    HASH_FIND_STR( users, "betty", s);
    if (s) printf("betty's id is %d
", s->id);

    /* free the hash table contents */
    HASH_ITER(hh, users, s, tmp) {
      HASH_DEL(users, s);
      free(s);
    }
    return 0;
}

 構造体のキー値が文字列ポインタである場合
#include   /* strcpy */
#include   /* malloc */
#include    /* printf */
#include "uthash.h"

struct my_struct {
    const char *name;          /* key */
    int id;
    UT_hash_handle hh;         /* makes this structure hashable */
};


int main(int argc, char *argv[]) {
    const char *names[] = { "joe", "bob", "betty", NULL };
    struct my_struct *s, *tmp, *users = NULL;

    for (int i = 0; names[i]; ++i) {
        s = (struct my_struct *)malloc(sizeof *s);
        s->name = names[i];
        s->id = i;
        HASH_ADD_KEYPTR( hh, users, s->name, strlen(s->name), s );
    }

    HASH_FIND_STR( users, "betty", s);
    if (s) printf("betty's id is %d
", s->id);

    /* free the hash table contents */
    HASH_ITER(hh, users, s, tmp) {
      HASH_DEL(users, s);
      free(s);
    }
    return 0;
}

ポインタキー値
#include 
#include 
#include "uthash.h"

typedef struct {
  void *key;
  int i;
  UT_hash_handle hh;
} el_t;

el_t *hash = NULL;
char *someaddr = NULL;

int main() {
  el_t *d;
  el_t *e = (el_t *)malloc(sizeof *e);
  if (!e) return -1;
  e->key = (void*)someaddr;
  e->i = 1;
  HASH_ADD_PTR(hash,key,e);
  HASH_FIND_PTR(hash, &someaddr, d);
  if (d) printf("found
");

  /* release memory */
  HASH_DEL(hash,e);
  free(e);
  return 0;
}

構造体キー値
 プロジェクトをハッシュまたは検索プロジェクトに追加する前に、構造体キー値の要素をクリアする必要があります.
#include 
#include 
#include "uthash.h"

typedef struct {
  char a;
  int b;
} record_key_t;

typedef struct {
    record_key_t key;
    /* ... other data ... */
    UT_hash_handle hh;
} record_t;

int main(int argc, char *argv[]) {
    record_t l, *p, *r, *tmp, *records = NULL;

    r = (record_t *)malloc(sizeof *r);
    /*       */
    memset(r, 0, sizeof *r);
    r->key.a = 'a';
    r->key.b = 1;
    HASH_ADD(hh, records, key, sizeof(record_key_t), r);

    memset(&l, 0, sizeof(record_t));
    l.key.a = 'a';
    l.key.b = 1;
    HASH_FIND(hh, records, &l.key, sizeof(record_key_t), p);

    if (p) printf("found %c %d
", p->key.a, p->key.b);

    HASH_ITER(hh, records, p, tmp) {
      HASH_DEL(records, p);
      free(p);
    }
    return 0;
}

共通マクロリファレンス
タイプマクロ
HASH_ADD_INT(head, keyfield_name, item_ptr)

HASH_REPLACE_INT(head, keyfiled_name, item_ptr,replaced_item_ptr)

HASH_FIND_INT(head, key_ptr, item_ptr)

HASH_ADD_STR(head, keyfield_name, item_ptr)

HASH_REPLACE_STR(head,keyfield_name, item_ptr, replaced_item_ptr)

HASH_FIND_STR(head, key_ptr, item_ptr)

HASH_ADD_PTR(head, keyfield_name, item_ptr)

HASH_REPLACE_PTR(head, keyfield_name, item_ptr, replaced_item_ptr)

HASH_FIND_PTR(head, key_ptr, item_ptr)

HASH_DEL(head, item_ptr)

HASH_SORT(head, cmp)

HASH_COUNT(head)

汎用マクロ
HASH_ADD(hh_name, head, keyfield_name, key_len, item_ptr)

HASH_ADD_BYHASHVALUE(hh_name, head, keyfield_name, key_len, hashv, item_ptr)

HASH_ADD_KEYPTR(hh_name, head, key_ptr, key_len, item_ptr)

HASH_ADD_KEYPTR_BYHASHVALUE(hh_name, head, key_ptr, key_len, hashv, item_ptr)

HASH_ADD_INORDER(hh_name, head, keyfield_name, key_len, item_ptr, cmp)

HASH_ADD_BYHASHVALUE_INORDER(hh_name, head, keyfield_name, key_len, hashv, item_ptr, cmp)

HASH_ADD_KEYPTR_INORDER(hh_name, head, key_ptr, key_len, item_ptr, cmp)

HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh_name, head, key_ptr, key_len, hashv, item_ptr, cmp)

HASH_REPLACE(hh_name, head, keyfield_name, key_len, item_ptr, replaced_item_ptr)

HASH_REPLACE_BYHASHVALUE(hh_name, head, keyfield_name, key_len, hashv, item_ptr, replaced_item_ptr)

HASH_REPLACE_INORDER(hh_name, head, keyfield_name, key_len, item_ptr, replaced_item_ptr, cmp)

HASH_REPLACE_BYHASHVALUE_INORDER(hh_name, head, keyfield_name, key_len, hashv, item_ptr, replaced_item_ptr, cmp)

HASH_FIND(hh_name, head, key_ptr, key_len, item_ptr)

HASH_FIND_BYHASHVALUE(hh_name, head, key_ptr, key_len, hashv, item_ptr)

HASH_DELETE(hh_name, head, item_ptr)

HASH_VALUE(key_ptr, key_len, hashv)

HASH_SRT(hh_name, head, cmp)

HASH_CNT(hh_name, head)

HASH_CLEAR(hh_name, head)

HASH_SELECT(dst_hh_name, dst_head, src_hh_name, src_head, condition)

HASH_ITER(hh_name, head, item_ptr, tmp_item_ptr)

HASH_OVERHEAD(hh_name, head)

パラメータの説明
  パラメータ説明  hh_name  UT_hash_handle構造のフィールドの名前.通称hh.
ハッシュの「ヘッダ」として使用される、構造ポインタ変数.この名前は、ハッシュに追加された最初のアイテムを指すためです.
  keyfield_name構造のキーフィールドの名前.(マルチフィールドキーの場合、これはキーの最初のフィールドです).マクロに詳しくない場合は、フィールド名をパラメータとして渡すのがおかしいようです.コメントを参照してください.
  key_lenキーフィールドの長さ(バイト単位).たとえば、整数キーはsizeof(int)であり、文字列キーはstrlen(key)である.(マルチフィールドキーについては、このコメントを参照してください.)
  key_ptr  対HASH_FINDは、ハッシュで検索するキーを指すポインタです(ポインタなので、ここで直接文字値を渡すことはできません).HASH_についてADD_KEYPTR、これは追加するアイテムのキーのアドレスです.
  hashv  が提供するキーのハッシュ値.これは...BYHASHVALUEマクロの入力パラメータ、はいの出力パラメータHASH_VALUE.同じキーを繰り返し検索する場合は、キャッシュのハッシュ値を再利用してパフォーマンスを最適化できます.
  item_ptrは、追加、削除、置換、または検索する構造のポインタ、または反復中の現在のポインタを指します.入力パラメータHASH_ですADD, HASH_DELETEとHASH_REPLACEマクロ、および出力パラメータHASH_FINDとHASH_ITER.(HASH_ITERが反復に使用される場合、tmp_item_ptrはitem_ptrの内部で使用されるタイプと同じ別の変数である).
  replace_item_ptr  HASH_用REPLACEマクロ.これは、置換されたアイテムを指す出力パラメータです(置換されていないアイテムはNULLに設定されます).
  cmp は比較関数のポインタを指し、この関数は2つのパラメータ(比較する項目を指すポインタ)を受け入れ、int値を返します.この値は、最初の項目が2番目の項目の前に、strcmpなどの後にソートされるかを指定します.
1つのパラメータの関数またはマクロ(構造を指す空のポインタであり、適切な構造タイプに強制的に変換する必要がある)を受け入れます.ターゲットハッシュに追加する構造を選択する場合は、関数またはマクロの値はゼロ以外の値にする必要があります.レイアウトの乱れの問題が発生した場合は、次のリンクで私のCSDNにアクセスできます.
**CSDN:[CSDN検索"埋め込み式とLinuxあれらの事"]
プロジェクトdeploy関連
ピーナッツ殻内ネットワーク貫通使用/三角関数