名 前
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;
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.79 の 一 部 で あ る 。 プ ロ ジ ェ ク ト の 説 明 と バ グ 報 告 に 関 す る 情 報 は http://www.kernel.org/doc/man−pages/ に 書 か れ て い る 。