使用 gperf 實現高效的 C/C++ 命令行處理
一 簡介
GNU 的 gperf 工具是一種 “完美的” 散列函數，可以為用戶提供的一組特定字符串生成散列表、散列函數和查找函數的 C/C++ 代碼。通過本文學習如何使用 gperf 實現 C/C++ 代碼中高效的命令行處理。
二 命令行處理和 gperf 的作用
命令行處理一直以來都是軟件開發中最容易被忽視的領域。幾乎所有比較復雜的軟件都具有一些可用的命令行選項。事實上，大量 if-else語句經常被用來處理用戶輸入，因此維護這種遺留代碼相當費時，對資深程序員亦是如此。這種情形下，很多 C 開發人員通常使用冗長（通常都嵌套使用）的 if-else 語句，以及 ANSI C 庫函數，例如 strcmp、strcasecmp 和 strtok 作為補充，如清單 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 的應用程序編程接口，而是使用標準模板庫（Standard Template Library，STL）中的字符串。盡管如此，仍然無法避免使用嵌套的 if-else 序列語句。很明顯，隨著命令行選項不斷增加，這種方法缺乏可伸縮性。對于具有 N 個選項的典型程序調用，代碼最終執行 0（N2）比較。為了生成運行更加快捷并易于維護的代碼，使用散列表存儲命令行選項并使用散列驗證用戶指定的輸入，這種方法非常有幫助。
這就是 gperf 扮演的角色。它將從預定的有效命令行選項列表和時間復雜度為 O(1) 的查找函數中生成一個散列表。因此，對于具有 N 個選項的典型程序調用，代碼只需執行 O(N) [N*O(1)] 比較 — 這是對遺留代碼的巨大改進。
三 Gperf 使用模式
Gperf 將從用戶提供的文件中（通常使用 .gperf 作為擴展名，但不做強制要求）— 例如，commandoptions.gperf — 并針對散列表、散列和查找方法生成 C/C++ 源代碼。所有代碼被定向到標準輸出，然后必須重定向到類似下面的文件：
gperf -L C++ command_line_options.gperf > perfecthash.hpp
注意：-L 選項將指示 gperf 生成 C++ 代碼。
四 Gperf 輸入文件格式
清單 2 展示了 gperf 輸入文件的典型格式。
%{
/* C code that goes verbatim in output */
%}
declarations
%%
keywords
%%
functions
文件格式由若干元素組成：C 代碼內容、聲明、關鍵字和函數。
C 代碼內容
C 代碼內容是可選的，使用 %{ 和 %} 括起來。其中的 C 代碼和注釋將被全部復制到 gperf 生成的輸出文件中。（注意，此處類似于 GNU flex 和 bison 實用程序）。
聲明
聲明部分也是可選的；如果沒有使用 -t 選項調用 gperf，則完全可以忽略聲明部分。但是，如果啟用了這個選項，聲明部分中最后一個元素的第一個字段必須是使用 char* 或 const char* 標識符調用的名稱。
但是，通過使用 gperf 中的 -K 選項可以改寫第一個字段的名稱。例如，如果希望將該字段命名為 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
第一個條目指 CommandOption 結構的 const char* command_option 字段，如 清單 3所示；第二個條目指同一個結構中的 int OptionCode 字段。那么這里究竟有什么含義呢？事實上，這就是 gperf 初始化散列表的方式，其中存儲了命令行選項及其相關屬性。
函數
函數也是可選的部分。函數部分中所有以 %% 開頭并延伸到文件末尾的文本將全部復制到生成的文件中。和聲明部分一樣，用戶需要為函數部分提供有效的 C/C++ 代碼。
五 Gperf 輸出
Gperf 混編了一組預定義的關鍵字，然后對這些關鍵字執行快速查找。與此相似，gperf 輸出兩個函數：hash() 和 in_word_set()。前者是一個散列例程，而后者用于執行查找。Gperf 輸出可以是 C 語言，也可以是 C++ 語言 — 您可以指定為其中一種。如果將輸出指定為 C 語言，將生成兩個具有上述名稱的 C 函數。如果指定為 C++ 語言，gperf 將生成名為 Perfect_Hash 的類，該類包含兩種方法。
注意：可以使用 -Z 選項修改生成的類名。
散列函數的原型為：
unsigned int hash (const char *str, unsigned int len);
其中 str 表示命令行選項，而 len 表示其長度。例如，如果命令行參數為 +helpverbose，則 str 為 +helpverbose，len 為 12。
在 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 language-name：指示 gperf 使用指定的語言生成輸出。目前支持以下幾個選項：
KR-C：這種老式的 K&R C 可以得到新舊 C 編譯器的支持，但是新的符合 ANSI C 標準的編譯器可能會生成警告，或者，某些情況下甚至會生成標志錯誤。
C：該選項將生成 C 代碼，但是如果不對已有源代碼進行調整，則可能無法使用某些舊的 C 編譯器進行編譯。
ANSI-C：該選項生成符合 ANSI C 標準的代碼，只能使用符合 ANSI C 標準的編譯器或 C++ 編譯器進行編譯。
C++：該選項生成 C++ 代碼。
</li> -
-N：該選項允許用戶修改查找函數的名稱。默認名為 in_word_set()。
</li> -
-H：該選項允許用戶修改散列例程的名稱。默認名為 hash()。
</li> -
-Z：該選項在提供了 -L C++ 選項時使用。它允許用戶指定所生成的 C++ 類的名稱，該類包含 in_word_set() 和 hash() 函數。默認名為 Perfect_Hash。
</li> -
-G：該選項將生成查找表并將其作為靜態全局變量，而不是在查找函數內生成以隱藏該表（默認行為）。
</li> -
-C：前面討論了 Gperf 將生成查找表。-C 選項將創建使用 const 關鍵字聲明的查找表。所有生成的查找表中的內容都是常量 — 即只讀形式。很多編譯器通過將表放入只讀內存中可以生成更高效的代碼。
</li> -
-D：該選項將處理散列為重復值的關鍵字。
</li> -
-t：該選項允許包含關鍵字結構。
</li> -
-K：該選項允許用戶選擇關鍵字結構中的關鍵字組件的名稱。
</li> -
-p：該選項可以與較早版本的 gperf 兼容。在早期版本中，它將生成的函數 in_word_set() 返回的默認布爾值（即 0 或 1 ）修改為pointer to wordlist array 類型。這個選項非常有用，尤其是在使用 -t（允許使用用戶定義的 structs）選項時。在最新版的 gperf 中并不要求使用該選項并且可以將其刪除。
</li> </ol>七 Gperf 原理概述
靜態搜索集 是一種抽象數據類型，包含的操作包括 initialize、insert 和 retrieve。完美散列函數是一種在時間和空間方面都十分高效的靜態搜索集實現。Gperf 是一種完美散列函數生成器，它使用用戶提供的關鍵字列表構建完美散列函數。Gperf 將 n 個用戶提供的關鍵字元素列表轉換為包含 k 個元素查找表和兩個函數的源代碼：
hash：該例程將關鍵字惟一地映射到范圍 0 .. k - 1 中，其中 k = n。如果 k = n，hash() 被認為是最小完美 hash() 函數。這種 hash()函數具有兩個屬性：
perfect property：查找時間復雜度為 O(1) 的表條目 — 就是說，至多需要一個字符串比較執行靜態搜索集中的關鍵字識別。
minimal property：為存儲關鍵字而分配的最小內存。
in_word_set：該例程使用 hash() 確定某個字符串是否屬于用戶提供的列表，大多數情況下只使用一個字符串比較。
Gperf 的內部實現以兩個內部數據結構為核心： 關鍵字簽名（keyword signatures）列表（Key_List）和 關聯值（associated values）數組（asso_values）。所有用戶指定的關鍵字及其屬性將從用戶指定的文件中讀取，并存儲為鏈接列表中的一個節點（稱為 Key_List）。在搜索完美 hash() 函數時，gperf 只將每個關鍵字字符中的一部分作為搜索鍵。這部分字符被稱為關鍵字簽名 或 keysig。
關聯值數組在 hash() 函數內部生成，并使用 keysig 字符進行索引。Gperf 反復搜索某種關聯值配置，該配置將所有 nkeysig 映射到非重復的散列值。當 gperf 找到某種配置，并且該配置將每個 keysig 分配到生成的查找表中惟一位置時，將生成一個完美 hash() 函數。產生的完美 hash() 函數返回一個無符號的 int 值，范圍為 0..(k-1)，其中 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</pre>
清單 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</pre>
gperf 命令行如下所示：
gperf -CGD -N IsValidCommandLineOption -K Option -L C++ -t command_line_options.gperf > perfecthash.hpp
散列表作為 perfecthash.hpp 文件一部分生成。由于命令行中指定了 -G 選項，將在全局范圍內生成散列表。因為使用 -C 選項進行 gperf 調用，將使用 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; }</pre>
最后，清單 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; }</pre>
注意：本文中的所有示例都使用 gperf 版本 3.0.3 進行了測試。如果您使用的是早期的版本，則可能需要在命令行調用中使用 -p 選項。
九 結束語
gperf 實用程序可以為中小型數據庫快速生成完美散列。但是，gperf 還可用于其他目的。事實上，可以在 GUN 編譯器中使用它維護語言關鍵字的完美散列，其最新的功能使您能夠操作更大的數據庫。因此，可以考慮在您的下一個開發項目中使用 gperf。
原文地址：http://www.ibm.com/developerworks/cn/linux/l-gperf.html#resources