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; }