C 言語で辞書の実装
この記事では、C 言語で辞書を実装する方法について複数のメソッドを紹介します。
hcreate、hsearch、hdestroy を用いて C 言語で辞書機能を実装する
一般に、C 標準ライブラリには組み込みの辞書データ構造は含まれていないが、POSIX 標準では辞書機能を実装するために利用できるハッシュテーブル管理ルーチンが規定されています。すなわち、hcreate、hsearch、hdestroy はハッシュテーブルを作成し、そこにアイテムを挿入し、テーブル内のアイテムを検索し、データ構造全体を解放するといった機能を提供します。実装されている機能は最低限のものであるが、多くの問題を解決することができます。
最初に、hcreate 関数を呼び出して、与えられた最大要素数のハッシュテーブルを作成する必要があるが、これは唯一の引数として渡されます。容量は hcreate 呼び出しの後では変更できないことに注意してほしい。テーブルが作成されると、hsearch 関数を呼び出して項目を追加することができます。最初の引数は ENTRY 型で、キーには char*、対応するデータには void* の struct として定義されます。2つ目のパラメータは ACTION 型で、基本的には FIND と ENTER の 2つの要素からなる enum です。後者の値は、テーブルに対してどのような操作を行うかを示すために用いられます。
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
static char *companies[] = {"Intel", "AMD", "ARM", "Apple",
"Marvell", "Qualcomm", "IBM", "Nvidia"};
static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
"ThunderX2", "Kryo", "z15", "Ampere"};
int main(void) {
ENTRY e;
ENTRY *ep;
const size_t capacity = sizeof companies / sizeof companies[0];
hcreate(capacity);
for (size_t i = 0; i < capacity - 2; i++) {
e.key = companies[i];
e.data = (void *)uarch[i];
ep = hsearch(e, ENTER);
if (ep == NULL) {
fprintf(stderr, "entry failed\n");
exit(EXIT_FAILURE);
}
}
e.key = "Intel";
ep = hsearch(e, FIND);
printf("%s -> %s\n", e.key, (char *)ep->data);
hdestroy();
exit(EXIT_SUCCESS);
}
出力：
Intel -> Willow Cove
コードの例では、キーと値のペアを明確なテキストで表現していますが、ユーザーはハッシュアルゴリズムを用いてキーを作成し、それをテーブルに格納することができます。この例では、単純な繰り返しを使って 6つの項目をテーブルに追加し、最後の 2つの要素をスキップしています。しかし、次の for ループでは、元の配列からすべての項目を取得し、対応するデータを表示します。
関数 hdestroy はハッシュテーブルのメモリを解放するために使われるが、通常はユーザが作成する ENTRY オブジェクトのバッファは解放されません。したがって、これらのオブジェクトのポインタがダイナミックメモリを指している場合、呼び出し元はそれらのハンドルを保持し、プログラム終了前に解放する責任があります。個々のエントリはテーブルから削除できないことに注意してください。
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
static char *companies[] = {"Intel", "AMD", "ARM", "Apple",
"Marvell", "Qualcomm", "IBM", "Nvidia"};
static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
"ThunderX2", "Kryo", "z15", "Ampere"};
int main(void) {
ENTRY e;
ENTRY *ep;
const size_t capacity = sizeof companies / sizeof companies[0];
hcreate(capacity);
for (size_t i = 0; i < capacity - 2; i++) {
e.key = companies[i];
e.data = (void *)uarch[i];
ep = hsearch(e, ENTER);
if (ep == NULL) {
fprintf(stderr, "entry failed\n");
exit(EXIT_FAILURE);
}
}
for (size_t i = 0; i < capacity; i++) {
e.key = companies[i];
ep = hsearch(e, FIND);
ep ? printf("%s -> %s\n", e.key, (char *)ep->data)
: printf("%s -> %s\n", e.key, "Entry not found");
}
hdestroy();
exit(EXIT_SUCCESS);
}
出力：
Intel -> Willow Cove
AMD -> Zen 3
ARM -> A78
Apple -> A14
Marvell -> ThunderX2
Qualcomm -> Kryo
IBM -> Entry not found
Nvidia -> Entry not found
