リナックスコマンド

hsearchのヘルプ・マニュアル

日本語 英語

• help
• man

hsearch --help

man hsearch

HSEARCH(3) Linux Programmer’s Manual HSEARCH(3) 名前 hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - ハッシュ テーブルの管理 書式 #include int hcreate(size_t nel); ENTRY *hsearch(ENTRY item, ACTION action); void hdestroy(void); #define _GNU_SOURCE #include 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 型であり、 の中で以下のように定義されて いる。 typedef struct entry { char *key; void *data; } ENTRY; フィールド key は検索キーとなる NULL 終端された文字列を指す。フィールド data は、このキーに対応するデータを指す。 検 索 が 失敗した後の動作は、引き数 action により決まる。この引き数には ENTER か FIND のいずれかの値を指定しなければならない。 ENTER は item の コ ピーを挿入することを (関数の結果として新しいハッシュテーブルエントリ へのポインタを返す)、 FIND は NULL を返すことを意味する (action が FIND の場合、 data は無視される)。 hsearch_r() 関数は hsearch() と同様だが、 *htab で示されるハッシュテー ブルに対して処理を行う。 hsearch_r() 関数が hsearch() と異なるのは、 見 つかった項目へのポインタを、関数の結果としてではなく、 *retval に格納し て返す点である。 返り値 hcreate() と hcreate_r() は、成功した場合 0 以外の値を返し、エラーの 場 合 0 を返す。 成功すると、 hsearch() は、ハッシュテーブル内のエントリへのポインタを返 す。エラーの場合、 hsearch() は NULL を返す。エラーとなるのは、 action が ENTER でハッシュテーブルがいっぱいの場合か、 action が FIND で item がハッシュテーブル内に見つからない場合である。 hsearch_r() は、成功する と 0 以外を返し、エラーの場合 0 を返す。 エラー hcreate() と hcreate_r() は以下の理由で失敗する可能性がある。 EINVAL (hcreate_r()) htab が NULL である。 ENOMEM ENTER に設定された action で、テーブルがいっぱいになった。 ESRCH action 引き数が FIND で、かつ対応する要素がテーブルに見つからな かった。 hsearch() と hsearch_r() は以下の理由で失敗する可能性がある。 ENOMEM action が ENTER で、 key がテーブル内に見つからず、テーブルに 新 しいエントリを追加する余地がなかった。 ESRCH action が FIND で、 key がテーブル内に見つからなかった。 POSIX.1-2001 が規定しているのは、エラー ENOMEM だけである。 準拠 関 数 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 #include #include 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), feature_test_macros(7) GNU 2008-10-06 HSEARCH(3)

HSEARCH(3) Linux Programmer’s Manual HSEARCH(3) NAME hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - hash ta- ble management SYNOPSIS #include int hcreate(size_t nel); ENTRY *hsearch(ENTRY item, ACTION action); void hdestroy(void); #define _GNU_SOURCE #include 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); DESCRIPTION The three functions hcreate(), hsearch(), and hdestroy() allow the caller to create and manage a hash search table containing entries con- sisting of a key (a string) and associated data. Using these func- tions, only one hash table can be used at a time. The three functions hcreate_r(), hsearch_r(), hdestroy_r() are reen- trant versions that allow a program to use more than one hash search table at the same time. The last argument, htab, points to a structure that describes the table on which the function is to operate. The pro- grammer should treat this structure as opaque (i.e., do not attempt to directly access or modify the fields in this structure). First a hash table must be created using hcreate(). The argument nel specifies the maximum number of entries in the table. (This maximum cannot be changed later, so choose it wisely.) The implementation may adjust this value upward to improve the performance of the resulting hash table. The hcreate_r() function performs the same task as hcreate(), but for the table described by the structure *htab. The structure pointed to by htab must be zeroed before the first call to hcreate_r(). The function hdestroy() frees the memory occupied by the hash table that was created by hcreate(). After calling hdestroy() a new hash ta- ble can be created using hcreate(). The hdestroy_r() function performs the analogous task for a hash table described by *htab, which was pre- viously created using hcreate_r(). The hsearch() function searches the hash table for an item with the same key as item (where "the same" is determined using strcmp(3)), and if successful returns a pointer to it. The argument item is of type ENTRY, which is defined in as follows: typedef struct entry { char *key; void *data; } ENTRY; The field key points to a null-terminated string which is the search key. The field data points to data that is associated with that key. The argument action determines what hsearch() does after an unsuccess- ful search. This argument must either have the value ENTER, meaning insert a copy of item (and return a pointer to the new hash table entry as the function result), or the value FIND, meaning that NULL should be returned. (If action is FIND, then data is ignored.) The hsearch_r() function is like hsearch() but operates on the hash ta- ble described by *htab. The hsearch_r() function differs from hsearch() in that a pointer to the found item is returned in *retval, rather than as the function result. RETURN VALUE hcreate() and hcreate_r() return non-zero on success. They return 0 on error. On success, hsearch() returns a pointer to an entry in the hash table. hsearch() returns NULL on error, that is, if action is ENTER and the hash table is full, or action is FIND and item cannot be found in the hash table. hsearch_r() returns non-zero on success, and 0 on error. ERRORS hcreate() and hcreate_r() can fail for the following reasons: EINVAL (hcreate_r()) htab is NULL. ENOMEM Table full with action set to ENTER. ESRCH The action argument is FIND and no corresponding element is found in the table. hsearch() and hsearch_r() can fail for the following reasons: ENOMEM action was ENTER, key was not found in the table, and there was no room in the table to add a new entry. ESRCH action was FIND, and key was not found in the table. POSIX.1-2001 only specifies the ENOMEM error. CONFORMING TO The functions hcreate(), hsearch(), and hdestroy() are from SVr4, and are described in POSIX.1-2001. The functions hcreate_r(), hsearch_r(), and hdestroy_r() are GNU extensions. NOTES Hash table implementations are usually more efficient when the table contains enough free space to minimize collisions. Typically, this means that nel should be at least 25% larger than the maximum number of elements that the caller expects to store in the table. The hdestroy() and hdestroy_r() functions do not free the buffers pointed to by the key and data elements of the hash table entries. (It can’t do this because it doesn’t know whether these buffers were allo- cated dynamically.) If these buffers need to be freed (perhaps because the program is repeatedly creating and destroying hash tables, rather than creating a single table whose lifetime matches that of the pro- gram), then the program must maintain bookkeeping data structures that allow it to free them. BUGS SVr4 and POSIX.1-2001 specify that action is significant only for unsuccessful searches, so that an ENTER should not do anything for a successful search. In libc and glibc (before version 2.3), the imple- mentation violates the specification, updating the data for the given key in this case. Individual hash table entries can be added, but not deleted. EXAMPLE The following program inserts 24 items into a hash table, then prints some of them. #include #include #include 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, *ep; int i; hcreate(30); for (i = 0; i < 24; i++) { e.key = data[i]; /* data is just an integer, instead of a pointer to something */ e.data = (void *) i; ep = hsearch(e, ENTER); /* there should be no failures */ if (ep == NULL) { fprintf(stderr, "entry failed\n"); exit(EXIT_FAILURE); } } for (i = 22; i < 26; i++) { /* print two entries from the table, and show that two are not in the table */ 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); } SEE ALSO bsearch(3), lsearch(3), malloc(3), tsearch(3), feature_test_macros(7) COLOPHON This page is part of release 3.22 of the Linux man-pages project. A description of the project, and information about reporting bugs, can be found at http://www.kernel.org/doc/man-pages/. GNU 2008-10-06 HSEARCH(3)