limitusus’s diary

主に技術のことを書きます

hcreate_rなどを使ってみた

現在作成中のプログラムでハッシュ表を使いたいなーと思っていたらPOSIX, GNU拡張に存在するらしい、ということで調べてみました。

もちろん基本はman hcreateを読むことですね。
今回は複数のハッシュ表を使う必要があるので、GNU拡張のhcreate_rなどのreentrant版を使う必要があります。

int hcreate_r(size_t nel, struct hsearch_data *tab);

3 つの関数 hcreate_r(), hsearch_r(), hdestroy_r() はリエントラントな関数で、2 つ以上のテーブルを使用することができる。最後の引き数はテーブルを識別するのに使われる。これが指し示す構造体は、初めて hcreate_r() を呼び出す前に 0 にしておかなければならない。

ところがこのreentrant版の用例はman pageには載っていません。実は使い方がよくわかりませんでした。
最初は

struct hsearch_data* tab;

などを最終引数に付けていて、hcreate_rの時点で見事に失敗しました。
次に

struct hsearch_data tab;

で最終引数は&tabにしました。ところがこれでもhcreate_rが0を返してきました(失敗を示しています)。

manpageにはtabに関して「0にしておかなければらならない」とかかれています。意味がよくわからなかったので最初に前者で

struct hsearch_data* tab = 0;

など、「意味ないよなあ・・・」とか思いながら失敗していました。

で、実際にやるべきことはこう。(2008/12/31 id:hayamiz の指摘により修正。こっちの方が短いし、将来構造体が変更されてもコード修正が不要になるので良いですね)

  /** 修正後 */
  struct hsearch_data tab;
  /* INITIALIZE */
  memset(&tab, 0, sizeof(tab));
  ret = hcreate_r(INIT_TABLE_SIZE, &tab);
  /** これは旧バージョン */
  struct hsearch_data tab;
  /* INITIALIZE */
  tab.size = 0;
  tab.filled = 0;
  tab.table = NULL;
  ret = hcreate_r(INIT_TABLE_SIZE, &tab);

実は私が読んでいたmanpage(Ubuntuのパッケージなのですが)は古いものでした(2003/11/28版)。新しいmanpage(現時点で2008/10/06版)はJM Projectで公開されています。man hcreate
ここでは少し表現が変わっています。

int hcreate_r(size_t nel, struct hsearch_data *htab);

hcreate_r() 関数は hcreate() と同じ動作をするが、構造体 *htab で示されるテーブルを対象として動作する。 htab が指し示す構造体は、 hcreate_r() を初めて呼び出す前に 0 で埋めておかなければならない。

(これは解決してから知った記述です。)

追記に実際に動かしてテストした、hcreate_r,hsearch_r関数の使用例を示します。基本的な動作はmanpageにあったhcreate,hsearchの動作と同じです。

また私の環境で/usr/include/search.hを読んだのですがどこにも

# ifdef _GNU_SOURCE

なる表現は見受けられず、

# ifdef __USE_GNU

こんなのばっかりだったので定数__USE_GNUを定義しています。

/*
** hash.c - Sample Program for using hcreate_r, hsearch_r
** Made by Limit
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* for memset() */
#include <errno.h>
#define __USE_GNU /* for reentrant functions hsearch_r etc. */
#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"
};

#define INIT_TABLE_SIZE ((size_t) 128)

int main(void) {
  ENTRY e;
  ENTRY* search_result;
  int ret;
  int i;
  struct hsearch_data tab;
  /* INITIALIZE */
  memset(&tab, 0, sizeof(tab));
  /* tab.size = 0;
  tab.filled = 0;
  tab.table = NULL; */
  ret = hcreate_r(INIT_TABLE_SIZE, &tab);
  if(!ret) { /* これはかなり引っかかった */
    if(errno == ENOMEM) { /* ここには引っかからなかった */
      printf("NOMEM\n");
    }
    printf("ERROR\n");
    return 0;
  }
  /* REGISTER DATA */
  for(i = 0; i < 24; i++) {
    e.key = data[i];
    e.data = (void*)i;
    ret = hsearch_r(e, ENTER, &search_result, &tab);
    if(ret == 0) {
      printf("Hash table is full\n");
      return 0;
    }
    printf("Registered %s:%d\n", e.key, (int)e.data);
  }
  /* SEARCH TEST: WILL HIT */
  for (i = 22; i < 24; i++) {
    e.key = data[i];
    ret = hsearch_r(e, FIND, &search_result, &tab);
    printf("%s : %s:%d\n", e.key,
           ret ? search_result->key : "NULL", ret ? (int)(search_result->data) : 0);
  }
  /* SEARCH TEST: NO HIT */
  e.key = data[24];
  ret = hsearch_r(e, FIND, &search_result, &tab);
  printf("%s : %s:%d\n", e.key,
         ret ? search_result->key : "NULL", ret ? (int)(search_result->data) : 0);
  
  return 0;
}