Provided by: manpages-ja-dev_0.5.0.0.20221215+dfsg-1_all 
名前
hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - ハッシュテーブルの管理
書式
#include <search.h>
int hcreate(size_t nel);
ENTRY *hsearch(ENTRY item, ACTION action);
void hdestroy(void);
#define _GNU_SOURCE /* feature_test_macros(7) 参照 */
#include <search.h>
int hcreate_r(size_t nel, struct hsearch_data *htab);
int hsearch_r(ENTRY item, ACTION action, ENTRY **retval,
struct hsearch_data *htab);
void hdestroy_r(struct hsearch_data *htab);
説明
hcreate(), hsearch(), hdestroy() の 3 つの関数を利用すると、キー (文字列) と対応するデー
タから構成される エントリーを格納できるハッシュ検索テーブルを作成、管理することができる。
これらの関数を使って、一度に使用できるのは一つのハッシュテーブルだけである。
hcreate_r(), hsearch_r(), hdestroy_r() の 3 つの関数はリエントラント版で、これらを利用す
ると、 一つのプログラムで同時に複数のハッシュテーブルを使うことができる。 最後の引数 htab
は関数の操作対象となるテーブルを示す構造体へのポインターである。 プログラマはこの構造体を
ブラックボックスとして扱うべきである (つまり、この構造体のフィールドに直接アクセスしたり変
更したり しないこと)。
最初に、 hcreate() 関数によってハッシュテーブルを作成しなければならない。 引数 nel でテー
ブルの最大エントリー数を指定する (この最大値は後で変更することはできないので、よく考えて選
択すること)。 作成されるハッシュテーブルの性能を向上させるために、 関数内部の実装によりこ
の値は増やされる場合もある。
hcreate_r() 関数は hcreate() と同じ動作をするが、構造体 *htab で示されるテーブルを対象と
して動作する。 htab が指し示す構造体は、 hcreate_r() を初めて呼び出す前に 0 で埋めておか
なければならない。
hdestroy() 関数は、 hcreate() で作成されたハッシュテーブルが占有していたメモリーを解放す
る。 ハッシュテーブルによって占有されていたメモリーを解放し、 新しいテーブルを作成できるよ
うにする。 hdestroy() を呼び出すと、その後は hcreate() を使って新しいハッシュテーブルを
作成することができる。 hdestroy_r() 関数は、同様の処理を、それ以前に hcreate_r() を使っ
て作成した *htab で示されるハッシュテーブルに対して実行する。
hsearch() 関数は、item と同じキーを持つ項目をハッシュテーブルから 検索し、項目が見つかっ
た場合にはその項目へのポインターを返す (「同じ」かどうかは strcmp(3) を使って判定する)。
引数 item は ENTRY 型であり、<search.h> の中で 以下のように定義されている。
typedef struct entry {
char *key;
void *data;
} ENTRY;
フィールド key は検索キーとなるヌル終端された文字列を指す。 フィールド data は、このキーに
対応するデータを指す。
検索が失敗した後の動作は、引数 action により決まる。 この引数には ENTER か FIND のいずれか
の値を指定しなければならない。 ENTER は item のコピーを挿入することを (関数の結果として新
しいハッシュテーブルエントリーへのポインターを返す)、 FIND は NULL を返すことを意味する
(action が FIND の場合、 data は無視される)。
hsearch_r() 関数は hsearch() と同様だが、 *htab で示されるハッシュテーブルに対して処理を
行う。 hsearch_r() 関数が hsearch() と異なるのは、見つかった項目へのポインターを、 関数
の結果としてではなく、 *retval に格納して返す点である。
返り値
hcreate() と hcreate_r() は、成功した場合 0 以外の値を返す。 エラーの場合 0 を返し、
errno にエラーの原因を示す値を設定する。
成功すると、 hsearch() は、ハッシュテーブル内のエントリーへのポインターを返す。 エラーの
場合、 hsearch() は NULL を返す。 エラーとなるのは、 action が ENTER でハッシュテーブルが
いっぱいの場合か、 action が FIND で item がハッシュテーブル内に 見つからない場合である。
hsearch_r() は、成功すると 0 以外を返し、エラーの場合 0 を返す。 エラーの場合、 これら二
つの関数は errno にエラーの原因を示す値を設定する。
エラー
hcreate_r() と hdestroy_r() は以下の理由で失敗する可能性がある。
EINVAL htab が NULL である。
hsearch() と hsearch_r() は以下の理由で失敗する可能性がある。
ENOMEM action が ENTER で、 key がテーブル内に見つからず、 テーブルに新しいエントリーを追
加する余地がなかった。
ESRCH action が FIND で、 key がテーブル内に見つからなかった。
POSIX.1 が規定しているのは、エラー ENOMEM だけである。
属性
この節で使用されている用語の説明については、 attributes(7) を参照。
┌──────────────────────────┬───────────────┬────────────────────────┐
│インターフェース │ 属性 │ 値 │
├──────────────────────────┼───────────────┼────────────────────────┤
│hcreate(), hsearch(), │ Thread safety │ MT-Unsafe race:hsearch │
│hdestroy() │ │ │
├──────────────────────────┼───────────────┼────────────────────────┤
│hcreate_r(), hsearch_r(), │ Thread safety │ MT-Safe race:htab │
│hdestroy_r() │ │ │
└──────────────────────────┴───────────────┴────────────────────────┘
準拠
関数 hcreate(), hsearch(), hdestroy() は SVr4 から導入されたもので、POSIX.1-2001 と
POSIX.1-2008 に記述されている。
関数 hcreate_r(), hsearch_r(), hdestroy_r() は GNU による拡張である。
注意
通常、ハッシュテーブルの実装は、衝突を最小限にするために テーブルに十分な空き領域がある場
合に効率がよくなる。 このため、普通は、 nel を、呼び出し側がテーブルに格納しようと思ってい
る エントリーの最大数より少なくとも 25% は大きな値にすべきである。
hdestroy() と hdestroy_r() は、ハッシュテーブルのエントリーの要素である key と data が指
すバッファーを解放しない (これができないのは、これらのバッファーが動的に割り当てられたのか
を 知ることができないからである)。 これらのバッファーを解放する必要がある場合、 プログラム
では、これらのバッファーを解放できるように管理用のデータ構造を 設けて、これを管理しなけれ
ばならない (解放が必要となる理由は、たいていは、プログラム自身と生存期間が同じ ハッシュ
テーブルを一つだけ作成するのではなく、そのプログラムでは複数の ハッシュテーブルを繰り返し
て作成したり破棄したりするからであろう)。
バグ
SVr4 と POSIX.1-2001 の規定では、 action は検索が失敗したときにだけ意味を持つとなってい
る。 よって、検索が成功した場合、action の値が ENTER でも 何もすべきではない。 (バージョン
2.3 より前の) libc と glibc の実装はこの規格に違反しており、 この状況で、指定された key に
対応する data が更新される。
ハッシュテーブルエントリーの追加はできるが、削除ができない。
例
次のプログラムは、ハッシュテーブルに 24 個の項目を挿入し、 それからそのうちのいくつかを表
示する。
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
static char *data[] = { "alpha", "bravo", "charlie", "delta",
"echo", "foxtrot", "golf", "hotel", "india", "juliet",
"kilo", "lima", "mike", "november", "oscar", "papa",
"quebec", "romeo", "sierra", "tango", "uniform",
"victor", "whisky", "x-ray", "yankee", "zulu"
};
int
main(void)
{
ENTRY e;
ENTRY *ep;
hcreate(30);
for (int i = 0; i < 24; i++) {
e.key = data[i];
/* データは、ポインターではなく、単なる整数値である。 */
e.data = (void *) i;
ep = hsearch(e, ENTER);
/* エラーは起こらないはずである。 */
if (ep == NULL) {
fprintf(stderr, "entry failed\n");
exit(EXIT_FAILURE);
}
}
for (int i = 22; i < 26; i++) {
/* テーブルにある 2 つのエントリーを表示し、
あとの 2 つがテーブルにないことを示す。 */
e.key = data[i];
ep = hsearch(e, FIND);
printf("%9.9s -> %9.9s:%d\n", e.key,
ep ? ep->key : "NULL", ep ? (int)(ep->data) : 0);
}
hdestroy();
exit(EXIT_SUCCESS);
}
関連項目
bsearch(3), lsearch(3), malloc(3), tsearch(3)
この文書について
この man ページは Linux man-pages プロジェクトのリリース 5.10 の一部である。プロジェクトの
説明とバグ報告に関する情報は https://www.kernel.org/doc/man-pages/ に書かれている。