名前
hcreate, hdestroy, hsearch - ハッシュテーブルの管理
書式
#include <search.h>
int hcreate(size_t nel);
ENTRY *hsearch(ENTRY item, ACTION action);
void hdestroy(void);
#define _GNU_SOURCE
#include <search.h>
int hcreate_r(size_t nel, struct hsearch_data *tab);
int hsearch_r(ENTRY item, ACTION action, ENTRY **ret,
struct hsearch_data *tab);
void hdestroy_r(struct hsearch_data *tab);
説明
3 つの関数 hcreate(), hsearch(), hdestroy() を利用すると、ユーザはキーと任意のデータを関連づける (1 度に 1 つの) ハッシュテーブルを作成することができる。
最初に、関数 hcreate() によってテーブルを作成しなければならない。 引き数 nel は、テーブルのエントリー数の予想される最大値である。 関数 hcreate() は、作成されるハッシュテーブルの性能を向上させるために この値を増やす場合もある。
これに対応する hdestroy() 関数は、 ハッシュテーブルによって占有されていたメモリを解放し、 新しいテーブルを作成できるようにする。
引き数 item は ENTRY 型であり、これは <search.h> の中で typedef されており、次の要素を含んでいる:
typedef struct entry { char *key; void *data; } ENTRY;
フィールド key は、NULL 終端された文字列を指し、 サーチキーとなる。 フィールド data は、このキーに対応するデータを指す。 関数 hsearch() は、item と同じキーを持つ項目を ハッシュテーブルの中から探し、成功すればその項目へのポインタを返す (キーが「同じであるか」は strcmp(3) を使って決定される)。 探索が失敗した場合、引き数 action によって hsearch() の動作が決まる。 値 ENTER は item のコピーを挿入し、 値 FIND は NULL を返すことを意味する。
3 つの関数 hcreate_r(), hsearch_r(), hdestroy_r() はリエントラントな関数で、2 つ以上のテーブルを使用することができる。 最後の引き数はテーブルを識別するのに使われる。 これが指し示す構造体は、初めて hcreate_r() を呼び出す前に 0 にしておかなければならない。
返り値
ハッシュテーブル用のメモリが確保が失敗した場合、 hcreate() と hcreate_r() は 0 を返す。 成功した場合は 0 以外の値を返す。
hsearch() は、action が ENTER で ハッシュテーブルがいっぱいの場合、 または action が FIND で item がハッシュテーブル内に見つからない場合、 NULL を返す。
hsearch_r() は、action が ENTER で ハッシュテーブルがいっぱいの場合、0 を返す。 それ以外の場合は 0 以外の値を返す。
エラー
POSIX では以下のように記述している。
| ENOMEM | メモリが足りない。 |
| glibc の実装では以下の 2 つのエラーを返す。 | |
| ENOMEM | ENTER に設定された action で、 テーブルがいっぱいになった。 |
| ESRCH | action 引き数が FIND で、 かつ対応する要素がテーブルに見つからなかった。 |
準拠
関数 hcreate(), hsearch(), hdestroy() は SVr4 から導入されたもので、POSIX.1-2001 に記述されている。 関数 hcreate_r, hsearch_r, hdestroy_r は GNU の拡張である。
バグ
SVr4 と POSIX.1-2001 では、 action は検索が失敗したときにだけ意味を持つ。 よって検索が成功した場合、action の値が ENTER でも何もすべきではない。 この場合、libc と glibc の実装では key で与えられる data が更新される。
個々のハッシュテーブルエントリーを追加できるが、削除できない。
例
次のプログラムは、ハッシュテーブルに 24 個の項目を挿入し、
それからそのうちのいくつかを表示する。
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
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()
{
ENTRY e, *ep;
int i;
/* 小さなテーブルで開始して大きくする操作は、うまく動作しない。*/
hcreate(30);
for (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 (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);
}
exit(EXIT_SUCCESS);
}
関連項目
bsearch(3), lsearch(3), malloc(3), tsearch(3), feature_test_macros(7)
