名前

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