初心者への GNU perf のススメ
Lynx Optimized Pages!
23592 accesses since 2001/07/27.
9 accesses per day.
[ TOP ]
一部から完全ハッシュ関数を作るツール gperf の使い方を知りたい、というリクエストが あったので、軽く説明してみようと思います。 (深く突っ込めないという話も。知ってることしか説明できないよねー(汗;))
ちなみに gperf は cperf-2.1a.tar.gz, gperf-3.0.3.tar.gz というパッケージになってます。gperf-2.7 以降は C++ がないとコンパイルできません。
パッケージのコンパイルについては割愛します。だって簡単なんだもん。
ハッシュが線形逐次検索に比べて速いことは周知です。完全ハッシュ関数は固定長のハッシュ表により ハッシュ値の計算コストを抑えてキーワードの探索を高速に行う関数です。普段使われる動的ハッシュに 対して静的ハッシュとも呼ばれます。
簡単な例を。入力した文字列が ID とマッチするかどうか調べるプログラムを作ってみましょう。
--- id.key --- AVG-FOE M.H Sato/2 Sharl UME20 anti-top nbkz oo -------------- ID 勝手に出してごめんなさい
このようなキーワードファイルを用意します。
先程のファイル id.key を入力ファイルとして
% gperf id.key
または
% gperf < id.key
とすると、標準出力に C のソースが出力されるので、リダイレクトして id.c とでもしておきます。
version 3.0 以降ではキャラクタセットが異なるとエラーを出すようになりました(id.c 参照)。
完全ハッシュ関数の関数名はデフォルトで in_word_set です。-N オプションで関数名を変更できます (-N name or --lookup-function-name=name)。プロトタイプ宣言は id.c を見てもらうとわかるように
const char *in_word_set(const char *str, unsigned int len);
です。version 2.1 では -a オプションにより len を int にすることができます。
実際の使用例は以下のようになります。
--- main.c ---
#include <stdio.h>
#include <string.h>
extern const char *in_word_set(char *, unsigned int);
void
main(int argc, char *argv[])
{
const char *p;
if (argc == 1)
return;
p = in_word_set(argv[1], strlen(argv[1]));
if (p == NULL)
printf("no match.\n");
else
printf("hit [%s]\n", p);
}
--------------
id.c とリンクしてください。
% cc main.c id.c % ./a.out aa no match. % ./a.out oo hit [oo] %
次の例を見てください。
--- asm.key --- add asl asr dec inc lsl lsr mov ret rol ror sub --------------- % gperf asm.key /* starting time is 14:59:48 */ Key link: "rol" = "lsr", with key set "lr". Some input keys have identical hash values, try different key positions or use option -D.
どうやら文字が重複している(アナグラムになっている)ので一意に決定できないようです。こういう場合は -D オプションを指定してください(と書いてある(汗;))。
% gperf -D asm.key
‘try different key positions’というのは…うまく説明できません。省略(汗;)。この場合は -k1,3,$ とか -k1,2,$ と指定すればいいんですけど…。この辺は試行錯誤してみてください。 すみません。(清く正しいシェルは $ をエスケープするのを忘れずに :-)
version 3.0 以降では -D をつけなくても自動的に計算してくれるようになりました。
とりあえずこれで gperf を使えるようになりました。(実用的かどうかは神のみぞ知る…)
ここからが普通の使い方です。
通常はキーワードとその属性(?)を構造体で格納して、キーワードの属性に対してアクションを行います。
gperf は文字列をキーワードとしてハッシュ表を作るので、かなり用途が限定されます。 逆引きできない、ということですね。
--- word.key ---
%{
/*
* a portion of GNU make keywords
*/
#include "word.h"
%}
struct OPE { char *name; int type; int args; };
%%
addprefix, F_ADDPREFIX, DYNAMIC
addsuffix, F_ADDSUFFIX, DYNAMIC
basename, F_BASENAME, MONAMIC
dir, F_DIR, MONAMIC
filter, F_FILTER, DYNAMIC
filter-out, F_FILTEROUT, DYNAMIC
findstring, F_FINDSTRING, DYNAMIC
firstword, F_FIRSTWORD, MONAMIC
foreach, F_FOREACH, TRINAMIC
join, F_JOIN, DYNAMIC
notdir, F_NOTDIR, MONAMIC
origin, F_ORIGIN, MONAMIC
patsubst, F_PATSUBST, TRINAMIC
shell, F_SHELL, MONAMIC
sort, F_SORT, MONAMIC
strip, F_STRIP, MONAMIC
subst, F_SUBST, TRINAMIC
suffix, F_SUFFIX, MONAMIC
wildcard, F_WILDCARD, MONAMIC
word, F_WORD, DYNAMIC
words, F_WORDS, MONAMIC
----------------
この例では word.h に define や enum などで定数を定義しておきます。この書式、yacc/bison の .y に似てますね。f?lex の .l にも似てるかも。
%{ と %} の間の行がソースに挿入されます。%} と %% の間の行が、構造体の宣言になります。%% 以降が 構造体の内容の羅列です。1 行に構造体 1 つぶんしか書いてはいけません。 キーワードは必ず先頭に書きます。それにあわせて構造体のメンバの型も決めてください。
ここで注意。デフォルトではキーワードに対するメンバ名が‘name’です。 メンバ名を変更したい、という時は -K で指定します(-K name or --slot-name=name)。
ex.)
struct MEMB { char *id; char *addr; char *tel; };
のとき gperf -K id ... となります。
キーワードから属性(この場合は構造体のメンバ)を得たいので、構造体へのポインタが返ってこないと 参照できませんね。
しかし、デフォルトではキーワードへのポインタを返すので、構造体へのポインタを返すように オプションで -p -t を指定します。 -pt と続けて書いてもかまいません。
% gperf -pt word.key > word.c
さて、word.c の中に構造体 OPE の定義が残っています。もし word.h の中で struct OPE を定義したり していると redefinition error が出ます。ヘッダを使い回す人は注意ですね。そういうときは -T を指定すると、構造体の宣言が出力されなくなります。
% gperf -ptT word.key > word.c
めでたく構造体へのポインタが返るようになりました(なりましたよね???)。この場合の in_word_set のプロトタイプ宣言は
struct OPE *in_word_set(const char *str, unsigned int len);
になります。あとは
struct OPE *p;
if ((p = in_word_set(key, strlen(key))) != NULL)
do_func(p->type, p->args);
などとして使いましょう。
構造体の初期化でコンパイラの警告が出る場合は -F ", 0, 0" とオプションで初期化するものを無理やり 指定するか、構造体宣言の前か後ろに
%define initializer-suffix ,0,0
と書いてあげると埋めてくれます。自動的に構造体宣言の中を解析してくれるわけじゃないですけど。%define を 使うときに空白を入れるとダメな感じなので -F を使ってquoteしてあげるといい感じのソースになります。
駆け足で説明してきましたが、けっこうな量になっちゃいました。でも、これだけ覚えておけば一応使う ことはできます。わたしもこのくらいしかわかりませんけど大丈夫ですし(汗;)。
もっと突っ込んで知りたい方は gperf.texinfo や付属の gperf.html を参照してください(汗;)。
(2005/10/29) gperfの吐くソースにgccが文句を言うを受けて構造体の初期化を追加。
(2003/08/09) version 3.0.1 に対応した内容に改変。
(2001/08/02) サンプルで使ったソースを見れるようにした。若干改変。
(2001/08/01) 休んでいる間に gperf-2.7.2.tar.gz が出ていたので更新。
(1998/05/08) gperf-2.7.tar.gz が独立パッケージに。
(1997/10/06) gperf の在処を追加。
(1997/05/16) はるか昔に書いたドキュメントを HTML にしてみました。今でもここに書いたくらいの知識しか持って ないし、これ以上の使い方をしてないので、この説明が役にたつ人もいるんじゃないかなぁ。 ツッコミもお待ちしております。
$Id: gperf.html,v 1.20 2008/02/05 06:17:14 sharl Exp sharl $