C 言語で辞書の実装

ISO C には、組み込みの辞書型は定義されていません。対象環境が POSIX の hsearch インターフェースを提供している場合、そのハッシュテーブル用ルーチンを使ってキーと値の組を保存・取得できます。以下の例では、テーブルを作成し、2つの項目を登録してから、存在するキーと存在しないキーを検索します。戻り値のポインターを確認した後、テーブルを解放します。ここで示すのは辞書の設計方法の一例です。

POSIX の hsearch ルーチンで C の辞書を実装する

hcreate、hsearch、hdestroy は <search.h> で宣言される POSIX ルーチンであり、ISO C ライブラリの関数ではありません。利用できるかどうかは対象の OS と C ライブラリによって異なるため、例を使う前に環境がこのインターフェースを提供していることを確認してください。hcreate と hsearch の POSIX 仕様で、インターフェースや要件を確認できます。この例が対象とする特定のプラットフォームやライブラリのバージョンは示されていません。

hcreate と hsearch でハッシュテーブルを作成し項目を追加する

hcreate を一度呼び出し、指定した容量のテーブルを作成します。成功すると 0 以外を返し、作成できない場合は 0 を返します。ENTRY は char * 型のキーと void * 型のデータポインターを保持します。hsearch には ENTRY と ACTION の値を渡します。ENTER は項目の登録、FIND は検索を要求します。成功時は項目へのポインターが返り、失敗時は NULL が返ります。

次の例を実行します。

このセクションのコードと表示されるラベルや出力は英語のままです。

#define _XOPEN_SOURCE 700
#include <search.h>
#include <stdio.h>

int main(void) {
    if (hcreate(4) == 0) {
        fputs("could not create table\n", stderr);
        return 1;
    }

    ENTRY item = {"language", "C"};
    if (hsearch(item, ENTER) == NULL) {
        fputs("could not insert language\n", stderr);
        hdestroy();
        return 1;
    }

    item.key = "standard";
    item.data = "POSIX";
    if (hsearch(item, ENTER) == NULL) {
        fputs("could not insert standard\n", stderr);
        hdestroy();
        return 1;
    }

    ENTRY query = {"language", NULL};
    ENTRY *found = hsearch(query, FIND);
    if (found == NULL) {
        puts("language: not found");
    } else {
        printf("language: %s\n", (char *)found->data);
    }

    query.key = "compiler";
    found = hsearch(query, FIND);
    if (found == NULL) {
        puts("compiler: not found");
    } else {
        printf("compiler: %s\n", (char *)found->data);
    }

    hdestroy();
    return 0;
}

language: C
compiler: not found

キーを検索し、見つからない場合に対処する

最初の FIND 呼び出しでは、プログラムが値 C とともに登録した language を検索します。2回目は登録していない compiler を検索します。どちらの場合も、プログラムは data を読む前に結果を確認するため、戻り値が NULL でも安全に「見つからない」場合を処理できます。本来存在するはずのキーの検索で NULL が返った場合も、例ではポインターを参照せずに結果を報告します。メッセージや戻り値の扱いは、用途に合わせて変更してください。

挿入を完了できない場合にも hsearch は NULL を返すため、処理を続ける前に各 ENTER の結果を確認します。例ではテーブルの作成や項目の登録に失敗したとき、stderr に診断メッセージを書き込み、すでに作成済みのテーブルを解放して、失敗を示すステータスを返します。各操作の直後に確認すれば、後続のコードでポインターを確かめてから項目を読むことができます。

変更されない出力例に表示される「compiler: not found」は英語のラベルです。日本語訳ではなく、例の中でも英語のままです。

テーブルを解放し、制限を把握する

テーブルを使い終えたら hdestroy を呼び出します。これはテーブルを解放しますが、項目が参照する動的に確保されたキーや値の領域は呼び出し側が管理します。それらのポインターを保持し、所有する領域は別途解放してください。この例では文字列リテラルを使っているため、そのような領域の解放は必要ありません。ここで示す POSIX インターフェースには、個々の項目を削除する操作がありません。テーブルを作成するときは十分な容量を選んでください。指定した容量は hcreate に渡しますが、この例で扱うインターフェースにはサイズ変更の操作もありません。