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-2001
が規定しているのは、エラー
ENOMEM だけである。
マルチスレッディング (pthreads(7) 参照)¶
関数
hcreate(),
hsearch(),
hdestroy()
はテーブルを格納するのにグローバル空間を使用する。そのため、これらの関数はスレッドセーフではない。
関数
hcreate_r(),
hsearch_r(),
hdestroy_r()
はスレッドセーフである。
関数
hcreate(),
hsearch(),
hdestroy() は
SVr4
から導入されたもので、POSIX.1-2001
に記述されている。
関数
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()
{
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);
}
hdestroy();
exit(EXIT_SUCCESS);
}
関連項目¶
bsearch(3),
lsearch(3),
malloc(3),
tsearch(3)
この文書について¶
この man ページは Linux
man-pages
プロジェクトのリリース
3.65 の一部
である。プロジェクトの説明とバグ報告に関する情報は
http://www.kernel.org/doc/man-pages/
に書かれている。
