目次


gperf を使って効率的に C/C++ コマンド・ラインを処理する

GNU perfect (gperf) ハッシュ関数生成プログラムによって、複雑な入力ストリングの処理作業が単純に

Comments

コマンド・ライン処理と gperf の必要性

コマンド・ライン処理は、ソフトウェア開発の中で歴史的に最もないがしろにされてきた領域の 1 つです。比較的複雑なソフトウェアであれば、ほとんどすべて何十ものコマンド・ライン・オプションを持っています。実際、ユーザー入力を処理するために何百行ものif-else 文がコーディングされることも珍しくありません。そうしたレガシー・コードを維持する作業は、たとえ経験豊かなプログラマーにとっても時間のかかる作業になってしまいます。そうした場合、大部分の C 開発者は、ANSI C ライブラリー関数 (strcmpstrcasecmpstrtok など) を適当に使った長々とした (そして多くの場合はネストした)if-else文に頼ることが普通です (リスト 1)。

リスト 1. C スタイルのコマンド・ライン処理
if (strtok(cmdstring, "+dumpdirectory"))
  {
  // code for printing help messages goes here
  }
else if (strtok(cmdstring, "+dumpfile"))
  {
  // code for printing version info goes here
  }

C++ 開発者は、おそらく ANSI C ベースの API (application program interface) の代わりに STL (Standard Template Library) のストリングを使うでしょう。それでも、ネストされた一連の if-else文から逃れることはできません。当然ながら、この方法はオプションの増加に対してスケーラブルではありません。N のオプションを持つ典型的なプログラム呼び出しの場合、コードは O(N2) 回の比較を行う羽目になります。高速に実行する、そして維持管理が容易なコードを生成するためには、コマンド・ライン・オプションを保存するハッシュ・テーブルを使い、そしてハッシュを使ってユーザーが指定する入力を検証した方が、はるかに賢明です。

ここに gperf が登場します。gperf は、有効なコマンド・ライン・オプションの事前定義リストと時間計算量が O(1) の参照関数から、ハッシュ・テーブルを生成します。従って、N のオプションを持つ典型的なプログラム呼び出しの場合、コードは O(N) [N*O(1)] 回の比較しか必要ありません。これはレガシー・コードに比べ、1 桁の改善です。

gperf の使用パターン

gperf は、ユーザーが提供するファイル (通常は .gperf という拡張子を持ちますが、必ずそうである必要はありません)、例えば commandoptions.gperf から一連のキーワードを読み取り、ハッシュ・テーブル用とハッシュ値計算用、そして参照メソッド用の C/C++ ソースを生成します。すべてのコードは標準出力に出力するように指示され、この標準出力をファイルにリダイレクトする必要があるため、次のようになります。

gperf  -L C++ command_line_options.gperf > perfecthash.hpp

注意: この -L オプションは gperf に対して、C++ のコードを生成するように命令しています。

gperf の入力ファイル・フォーマット

リスト 2 は gperf の入力ファイルの典型的なフォーマットを示しています。

リスト 2. gperf の入力ファイル・フォーマット
%{
/* C code that goes verbatim in output */
%}
declarations
%%
keywords
%%
functions

このフォーマットはいくつかの要素で構成されており、C コードのインクルード、宣言、キーワード、そして関数という要素があります。

C コードのインクルード

C コードのインクルードは、%{%} に囲まれたオプション・セクションです。この領域の中に書かれた C コードとコメントは、gperf が生成する出力ファイルにそのままコピーされます (GNU の flex ユーティリティーと bison ユーティリティーと似ていることに注目してください)。

宣言

宣言セクションもオプションです。-t オプションを使って gperf を呼び出すのでなければ、このセクションを完全に省略することができます。しかしこのオプションを有効にする場合には、宣言セクションの最後のコンポーネントは構造体でなければならず、その構造体の最初のフィールドは name と呼ばれる char* あるいはconst char* 識別子でなければなりません。

ただし、gperf の -K オプションを使うことで、最初のフィールドの name を変更することもできます。例えば、このフィールドを command_option という名前にしたい場合には、次のように gperf を呼び出します。

gperf -t -K command_option

リスト 3 は C コードのインクルード・セクションと宣言セクションを示しています。

リスト 3. C コードのインクルード・セクションと宣言セクション
%{
struct CommandOptionCode  {
  enum { 
      HELPVERBOSE = 1,
      ..., // more option codes here
      _64BIT = 5
   };
};
typedef struct CommandOptionCode CommandOptionCode;
%}
struct CommandOption
  {
  const char* command_option;
  int OptionCode;
  };
%%

キーワード

キーワード・セクションは、キーワード (この場合は事前定義されたコマンド・ライン引数) を含みます。このセクションで、最初の列が番号記号 (#) で始まる各行はコメントです。キーワードは、コメントではない各行の最初のフィールドになければなりません。通常はchar*に関連付けられる文字列引用符は、ここではオプションです。また、フィールドを先行キーワードに続けることができますが、各フィールドをカンマで区切り、行の最後で終了する必要があります。これらのフィールドは、宣言セクションで提供された最後の構造体に直接対応します (リスト 4)。

リスト 4. キーワード・セクション
%%
+helpverbose, CommandOptionCode::HELPVERBOSE
+append_log, CommandOptionCode::APPEND_LOG
+compile, CommandOptionCode::COMPILE

最初のエントリーは、リスト 3 に示すように構造体 CommandOptionconst char* command_option フィールドを参照します。2 番目のエントリーは、同じ構造体の int OptionCode フィールドを参照します。では、ここでは実際に何が起きているのでしょう。実は、コマンド・ライン・オプションとそれらに関連する属性を保存するハッシュ・テーブルを、gperf 流に初期化しているのです。

関数

関数も、もう 1 つのオプション・セクションです。このセクションで、%% で始まりファイルの終わりにまで至るすべてのテキストは、生成されるファイルにそのままコピーされます。宣言セクションの場合と同じく、このセクションに有効な C/C++ コードを配置するのはユーザーの責任です。

gperf の出力

gperf は、事前定義された一連のキーワードのハッシュ値を計算し、そして同じこれらのキーワードを素早く参照します。このやり方に従って、gperf は hash()in_word_set() という 2 つの関数を出力します。前者はハッシュ値計算ルーチンであり、後者は参照に使われます。gperf の出力は、C あるいは C++ (どちらか指定した方) です。出力に C を指定した場合には、上記の名前を持つ 2 つの C 関数が生成されます。出力言語が C++ の場合には、gperf は Perfect_Hash という名前のクラスを生成します (このクラスはこれら 2 つのメソッドを含んでいます)。

注意: 生成されるクラス名を変更するためには -Z オプションを使います。

ハッシュ関数のプロトタイプは次の通りです。

unsigned int hash (const char *str, unsigned int len);

ここで、str はコマンド・ライン・オプションを表し、len はそのオプションの長さを表します。例えばコマンド・ライン引数が +helpverbose だったとすると、str+helpverbose であり、len12 です。

gperf が生成するハッシュの中で、in_word_set() は参照関数です。このルーチンのプロトタイプはユーザーが指定する -t オプションに依存します。もしこのオプションを指定しないと、コマンド・ストリングと関連付けられる構造体を処理するのではなく、そのユーザー専用のコマンド・ストリング (gperf が生成するハッシュにデータとして保存されます) を単純に処理することになります。

例えば、リスト 3 にはユーザー・コマンド引数に関連付けられた構造体 CommandOption がありますが、これが in_word_set() ルーチンが返すものです。このルーチンの名前は、-N オプションを使って変更することができます。このルーチンの引数は、先ほど説明した hash() 関数と似ています。

const struct CommandOption* in_word_set (const char *str, unsigned int len);

gperf の一般的なオプション

gperf は高度なカスタマイズが可能なツールであり、いくつかのオプションがあります。gperf のオンライン・マニュアル (下記の「参考文献」セクションのリンクを参照) は、gperf で利用できるすべてのオプションを説明しています。オプションには次のようなものがあります。

  • -L言語名: 指定されたプログラミング言語で出力を生成するように gperf に命令します。現在サポートされているオプションは次の通りです。
    • KR-C: この古いスタイルの K&R C は新旧いずれの C コンパイラーでもサポートされていますが、ANSI C 準拠の新しいコンパイラーは警告を出すかもしれず、場合によるとエラー・フラグを立てるかもしれません。
    • C: このオプションは C コードを生成しますが、一部の古い C コンパイラーを使う場合には、既存のソースに少し手を加えないとコンパイルできないかもしれません。
    • ANSI-C: このオプションは ANSI-C 準拠のコードを生成します。このコードは ANSI-C 準拠のコンパイラーまたは C++ コンパイラーでないとコンパイルできません。
    • C++:このオプションは C++ コードを生成します。
  • -N: このオプションで参照関数の名前を変更することができます。デフォルトは in_word_set() です。
  • -H: このオプションでハッシュ値計算ルーチンの名前を変えることができます。デフォルト名は hash() です。
  • -Z: このオプションは-L C++ オプションが指定されている場合に役立ちます。このオプションを使うと、in_word_set() 関数と hash() 関数を持つ、生成される C++ クラスの名前を指定することができます。デフォルト名は Perfect_Hash です。
  • -G: このオプションは静的なグローバル変数としてルックアップ・テーブルを生成します。(デフォルト動作のように) 参照関数の中にルックアップ・テーブルを生成して隠すことはしません。
  • -C: gperf は先ほど説明したようにルックアップ・テーブルを生成します。-C オプションは、const キーワードで宣言されるルックアップ・テーブルを作成します。そうすると、生成されるすべてのルックアップ・テーブルの内容は定数、つまり読み取り専用になります。多くのコンパイラーは、ルックアップ・テーブルを読み取り専用メモリーの中に置くことで、ルックアップ・テーブルを使用するコードをより効率的に生成することができます。
  • -D: このオプションは、重複した値をハッシュするキーワードを処理します。
  • -t: このオプションを使うとキーワード構造を含めることができます。
  • -K: このオプションを使うと、ユーザーはキーワード構造の中でキーワード・コンポーネントの名前を選択することができます。
  • -p: このオプションは、以前のリリースの gperf との互換性を保つためにサポートされています。以前のバージョンの場合、このオプションは、生成される関数 in_word_set() の戻り値をデフォルトのブール値 (つまり 0 または 1) から wordlist 配列へのポインター型に変更します。これが最も便利なのは、ユーザー定義の structs を許可する -t オプションが使われたときでした。最新リリースの gperf では、このオプションは必要なく、省略することができます。

gperf 内部の概要

静的検索セット (static search set) は、initializeinsertretrieve という操作を行う抽象データ型です。完全ハッシュ関数は、静的検索セットを時間と空間の両面から効率よく実装したものです。gperf は、ユーザーが提供するキーワード・リストから完全ハッシュ関数を構築する、完全ハッシュ関数生成プログラムです。gperf は、ユーザーが提供するn 要素のキーワード・リストを、k 要素のルックアップ・テーブルと次の 2 つの関数を含むソースコードに変換します。

  • hash: このルーチンは、キーワードを 0 から k - 1 の範囲に固有マッピングします (ここで k = n です)。もし k = n であれば、hash() は最小完全hash() 関数です。そうしたhash() 関数は、次の 2 つのプロパティーを持ちます。
    • perfect property: テーブルのエントリーを見つけるために O(1) 回、つまり、静的検索セット内でキーワード認識を行うために、最大で 1 回のストリング比較が必要です。
    • minimal property: キーワードを保存するために割り当てられているメモリーは、そのキーワードのセットにぴったりの大きさであり、それよりも大きいサイズではありません。
  • in_word_set: このルーチンは、ある特定のストリングがユーザーから提供されるリストに属するかどうかをhash() を使って判断します (最も一般的な場合では 1 つのストリング比較を使います)。

gperf 内部の実装は、キーワード・シグニチャー・リスト (Key_List) と関連値配列 (asso_values) という 2 つの内部データ構造を中心としています。ユーザーが指定する各キーワードと、その属性は、ユーザーが指定するファイルから読み取られ、Key_List と呼ばれるリンク・リストのノードとして保存されます。gperf が完全 hash() 関数を検索する際には、gperf は各キーワードの文字列のサブセットのみをキーと見なします。このサブセットは、キーワード・シグニチャー、あるいは keysig と呼ばれます。

関連値配列は hash() 関数内部で生成され、keysig 文字列を使って索引付けされます。gperf は、重複のないハッシュ値にすべてのnkeysig をマップする関連値構成を繰り返し検索します。完全 hash() 関数が作成されるのは、生成されたルックアップ・テーブルの固有の位置に各 keysig を割り当てる構成を gperf が発見した時です。作成された完全 hash() 関数は、0 から (k-1) までの範囲の符号なしの int 値を返します (k は最大キーワード・ハッシュ値 +1 です)。

k = n の場合には、最小完全 hash() 関数が作成されます。キーワードのハッシュ値は通常、そのキーワードの keysig の関連値をそのキーワードの長さと組み合わせることで計算されます。hash() 関数はデフォルトで、キーワードの最初のインデックスの位置の関連値プラスそのキーワードの最後のインデックスの位置の関連値を、そのキーワードの長さに加えます。例えば次のようになります。

hash_value = length + asso_values[(unsigned char)keyword[1]];

サンプル・プロジェクト

これまでに説明した概念を、小さなプロジェクトを使って説明しましょう。リスト 5 に示す gperf ファイルを考えてみてください。

リスト 5. command_options.gperf
%{
#include "command_options.h"
typedef struct CommandOptionCode CommandOptionCode;
%}
struct CommandOption
  {
  const char *Option;
  int OptionCode;
  };
%%
+helpverbose, CommandOptionCode::HELPVERBOSE
+password, CommandOptionCode::PASSWORD
+nocopyright, CommandOptionCode::NOCOPYRIGHT
+nolog, CommandOptionCode::NOLOG
+_64bit, CommandOptionCode::_64BIT

リスト 6 は、この gperf ファイルに含まれる command_options.h ヘッダーを示しています。

リスト 6. command_options.h ヘッダー
#ifndef __COMMANDOPTIONS_H
#define __COMMANDOPTIONS_H
struct CommandOptionCode 
  {
  enum 
    {
    HELPVERBOSE = 1,
    PASSWORD = 2,
    NOCOPYRIGHT = 3,
    NOLOG = 4,
    _64BIT = 5
    };
  };
#endif

gperf のコマンド・ラインは次のようになります。

gperf -CGD -N IsValidCommandLineOption -K Option -L C++ -t 
    command_line_options.gperf > perfecthash.hpp

perfecthash.hpp ファイルの一部として、ハッシュ・テーブルも生成されます。コマンド・ラインで -G オプションが指定されているため、ハッシュ・テーブルはグローバルなスコープで生成されます。gperf の呼び出しに -C オプションが使われたため、ハッシュ・テーブルは const 属性で定義されます。リスト 7 は、生成されたソースの詳細を示しています。

リスト 7. 生成された perfecthash.hpp
/* C++ code produced by gperf version 3.0.3 */
/* Command-line: 'C:\\gperf\\gperf.exe' -CGD -N IsValidCommandLineOption -K Option 
-L C++ -t command_line_options.gperf  */
/* Computed positions: -k'2' */

#if !((' ' == 32) && ('!' == 33) && ('"' == 34) && ('#' == 35) \
      && ('%' == 37) && ('&' == 38) && ('\'' == 39) && ('(' == 40) \
      && (')' == 41) && ('*' == 42) && ('+' == 43) && (',' == 44) \
      && ('-' == 45) && ('.' == 46) && ('/' == 47) && ('0' == 48) \
      && ('1' == 49) && ('2' == 50) && ('3' == 51) && ('4' == 52) \
      && ('5' == 53) && ('6' == 54) && ('7' == 55) && ('8' == 56) \
      && ('9' == 57) && (':' == 58) && (';' == 59) && ('<' == 60) \
      && ('=' == 61) && ('>' == 62) && ('?' == 63) && ('A' == 65) \
      && ('B' == 66) && ('C' == 67) && ('D' == 68) && ('E' == 69) \
      && ('F' == 70) && ('G' == 71) && ('H' == 72) && ('I' == 73) \
      && ('J' == 74) && ('K' == 75) && ('L' == 76) && ('M' == 77) \
      && ('N' == 78) && ('O' == 79) && ('P' == 80) && ('Q' == 81) \
      && ('R' == 82) && ('S' == 83) && ('T' == 84) && ('U' == 85) \
      && ('V' == 86) && ('W' == 87) && ('X' == 88) && ('Y' == 89) \
      && ('Z' == 90) && ('[' == 91) && ('\\' == 92) && (']' == 93) \
      && ('^' == 94) && ('_' == 95) && ('a' == 97) && ('b' == 98) \
      && ('c' == 99) && ('d' == 100) && ('e' == 101) && ('f' == 102) \
      && ('g' == 103) && ('h' == 104) && ('i' == 105) && ('j' == 106) \
      && ('k' == 107) && ('l' == 108) && ('m' == 109) && ('n' == 110) \
      && ('o' == 111) && ('p' == 112) && ('q' == 113) && ('r' == 114) \
      && ('s' == 115) && ('t' == 116) && ('u' == 117) && ('v' == 118) \
      && ('w' == 119) && ('x' == 120) && ('y' == 121) && ('z' == 122) \
      && ('{' == 123) && ('|' == 124) && ('}' == 125) && ('~' == 126))
/* The character set is not based on ISO-646.  */
#error "gperf generated tables don't work with this execution character set. \
Please report a bug to <bug-gnu-gperf@gnu.org>."
#endif

#line 1 "command_line_options.gperf"

#include "command_options.h"

typedef struct CommandOptionCode CommandOptionCode;
#line 6 "command_line_options.gperf"
struct CommandOption
  {
  const char *Option;
  int OptionCode;
  };

#define TOTAL_KEYWORDS 5
#define MIN_WORD_LENGTH 6
#define MAX_WORD_LENGTH 12
#define MIN_HASH_VALUE 6
#define MAX_HASH_VALUE 17
/* maximum key range = 12, duplicates = 0 */

class Perfect_Hash
{
private:
  static inline unsigned int hash (const char *str, unsigned int len);
public:
  static const struct CommandOption *IsValidCommandLineOption (const char *str, 
                                                               unsigned int len);
};

inline unsigned int
Perfect_Hash::hash (register const char *str, register unsigned int len)
{
  static const unsigned char asso_values[] =
    {
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18,  0, 18, 18, 18, 18,
      18, 18, 18, 18,  5, 18, 18, 18, 18, 18,
       0, 18,  0, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
      18, 18, 18, 18, 18, 18
    };
  return len + asso_values[(unsigned char)str[1]];
}

static const struct CommandOption wordlist[] =
  {
#line 15 "command_line_options.gperf"
    {"+nolog", CommandOptionCode::NOLOG},
#line 16 "command_line_options.gperf"
    {"+_64bit", CommandOptionCode::_64BIT},
#line 13 "command_line_options.gperf"
    {"+password", CommandOptionCode::PASSWORD},
#line 14 "command_line_options.gperf"
    {"+nocopyright", CommandOptionCode::NOCOPYRIGHT},
#line 12 "command_line_options.gperf"
    {"+helpverbose", CommandOptionCode::HELPVERBOSE}
  };

static const signed char lookup[] =
  {
    -1, -1, -1, -1, -1, -1,  0,  1, -1,  2, -1, -1,  3, -1,
    -1, -1, -1,  4
  };

const struct CommandOption *
Perfect_Hash::IsValidCommandLineOption (register const char *str, 
                                        register unsigned int len)
{
  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)
    {
      register int key = hash (str, len);

      if (key <= MAX_HASH_VALUE && key >= 0)
        {
          register int index = lookup[key];

          if (index >= 0)
            {
              register const char *s = wordlist[index].Option;

              if (*str == *s && !strcmp (str + 1, s + 1))
                return &wordlist[index];
            }
        }
    }
  return 0;
}

最後に、リスト 8 はメインのソース・リストを示しています。

注意: リスト 8 は、許容されるコマンド・ライン・オプションのキーワードの指定されたリスト内で、コマンド・ライン・オプションを一定時間で参照でき、そして適切な手段でそのオプションを処理できることを示しています。IsValidCommandLineOption は参照時間計算量 O(1) を持っています。

リスト 8. アプリケーションへのエントリー・ポイントを定義する gperf.cpp
#include "command_options.h"
#include "perfecthash.hpp"
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[])
  {
  string cmdLineOption = argv[1]; // First command line argument
  const CommandOption* option = 
    Perfect_Hash::IsValidCommandLineOption(cmdLineOption.c_str(), 
       cmdLineOption.length());
  switch (option->OptionCode)
    {
    case CommandOptionCode::HELPVERBOSE :
      cout << "Application specific detailed help goes here"; break;
    default: break;
    }
  return 0;
  }

注意: この記事のサンプルはすべて、gperf バージョン 3.0.3 を使ってテストされています。これ以前のバージョンを使う場合には、コマンド・ライン呼び出しの一部として -p オプションを使う必要があるかもしれません。

まとめ

gperf ユーティリティーは、小規模から中規模のデータセットに対して完全ハッシュ関数を素早く生成するように調整されています。しかし gperf は、他にも応用ができます。実際、gperf はGNU コンパイラーでの言語キーワード用の完全ハッシュ関数を維持管理する最適なツールであり、また最近では大規模なデータセットも処理できるように改善されています。gperf を、皆さんの次期開発プロジェクトの一部として利用することを検討してみてください。


ダウンロード可能なリソース


関連トピック


コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=253246
ArticleTitle=gperf を使って効率的に C/C++ コマンド・ラインを処理する
publish-date=07252007