hsearch - ライブラリコールの説明 - Linux コマンド集 一覧表

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(1);
          }
      }
      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);
      }
      return 0;
    }

  bsearch (3),   lsearch (3),   malloc (3),   tsearch (3)