名称

hcreate, hdestroy, hsearch — ハッシュ検索テーブルを管理する

ライブラリ

Standard C Library (libc, -lc)

書式

#include < search.h>

int
hcreate( size_t nel);

void
hdestroy( void);

ENTRY *
hsearch( ENTRY item, ACTION action);

解説

hcreate(), hdestroy() と hsearch() 関数は、ハッシュ検索テーブルを管理します。

hcreate() 関数は、テーブルのための十分な空間を割り付けます。また、アプリケーションは、 hsearch() が使用される前にそれが呼び出されることを保証するべきです。 nel 引数はテーブルが含んでいるべきエントリの最大の数の見積りです。この数は、ある数学的に好ましい状況を得るためにアルゴリズムによって上方へ調整されるかもしれません。

hdestroy() 関数は検索テーブルを処理します。また、 hcreate() への別の呼び出しが続くかもしれません。 hdestroy() への呼び出しの後に、データはもはやアクセス可能である考えることができません。 hdestroy() 関数は、キーに関連したデータアイテムではなく検索テーブル中の各比較キーのための free(3) を呼び出します。

hsearch() 関数は、ハッシュテーブル検索ルーチンです。それは、エントリが見つけることができる位置を示すハッシュテーブルへのポインタを返します。 item 引数は 2 つのポインタを含んでいる ( < search.h> ヘッダに定義された) タイプ ENTRY の構造体です。 item.key は、比較キー ( char *) を指します。そして、 item.data ( void *) はキーに関連する任意の他のデータを指します。 hsearch() によって使用される比較機能は strcmp(3) です。 action 引数はテーブルでそれを見つけることができない場合エントリの配置を示す列挙タイプ ACTION のメンバです。 ENTER は item が適切なポイントでテーブルに挿入されるべきであることを示します。 FIND は、エントリがなされてはならないことを示します。解決の失敗は NULL ポインタのリターンによって示されます。

( item.key として hsearch() に渡された) 比較キーは action が ENTER で hdestroy() が呼ばれる場合、 malloc(3) を使用して割り付けられなければなりません

戻り値

hcreate() 関数は、テーブルの作成に失敗し、グローバル変数 errno にエラーを示す値が設定されるなら、0 を返します。そうでなければ、0 以外の値が返されます。

hdestroy() 関数は、値を返しません。

action が FIND で、 item を見つけることができないか、あるいは、 action が ENTER でまた、テーブルが満杯のいずれかの場合は、 hsearch() 関数は NULL ポインタを返します。

使用例

次の例は 2 つの数が続く文字列を読み込み、複写を廃棄して、ハッシュテーブルにそれらを格納します。その後、文字列を読み込み、ハッシュテーブルに一致するエントリを見つけてそれを印刷します。

#include <stdio.h> 
#include <search.h> 
#include <string.h> 
#include <stdlib.h> 
 
struct info {   /* これはキー以外のテーブルに格納された */ 
 int age, room;  /* 情報です. */ 
}; 
 
#define NUM_EMPL 5000 /* 検索テーブルの要素の数. */ 
 
int 
main(void) 
{ 
 char str[BUFSIZ]; /* 文字列を読み込む空間 */ 
 struct info info_space[NUM_EMPL]; /* employee 情報を格納する空間. */ 
 struct info *info_ptr = info_space; /* info_space の次の空間. */ 
 ENTRY item; 
 ENTRY *found_item; /* テーブルで検索する名前. */ 
 char name_to_find[30]; 
 int i = 0; 
 
 /* テーブルの作成;エラーのチェックは実行されません. */ 
 (void) hcreate(NUM_EMPL); 
 
 while (scanf("%s%d%d", str, &info_ptr->age, 
     &info_ptr->room) != EOF && i++ < NUM_EMPL) { 
  /* 情報を構造体と項目の構造体に入れます. */ 
  item.key = strdup(str); 
  item.data = info_ptr; 
  info_ptr++; 
  /* 項目をテーブルに入れます. */ 
  (void) hsearch(item, ENTER); 
 } 
 
 /* アクセステーブル. */ 
 item.key = name_to_find; 
 while (scanf("%s", item.key) != EOF) { 
  if ((found_item = hsearch(item, FIND)) != NULL) { 
   /* 項目がテーブルにあるなら. */ 
   (void)printf("found %s, age = %d, room = %d\n", 
       found_item->key, 
       ((struct info *)found_item->data)->age, 
       ((struct info *)found_item->data)->room); 
  } else 
   (void)printf("no such employee %s\n", name_to_find); 
 } 
 hdestroy(); 
 return 0; 
}

エラー

hcreate() と hsearch() 関数は、次の場合に失敗します:

[ ENOMEM]

十分な記憶域空間が利用不可能です。

[ EINVAL]

テーブルは既に存在しています。

関連項目

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

規格

hcreate(), hdestroy() と hsearch() 関数は X/Open Portability Guide Issue 4, Version 2 (“XPG4.2”) に適合しています。

歴史

hcreate(), hdestroy() と hsearch() 関数は AT&T System V UNIX ではじめて登場しました。

バグ

インタフェースは、一度に 1 つのみのハッシュテーブルの使用を許します。