Linux gperf 完美雜湊生成器：指令列參數解析、關鍵字查找與效能優化

編輯：關於C語言

一、gperf 是什麼？

GNU gperf 根據使用者提供的關鍵字集合，生成完美雜湊函數：無衝突、O(1) 查找、無需動態記憶體分配的靜態 C/C++ 程式碼。適用於編譯器關鍵字、保留字、命令列選項、協議指令碼等靜態集合。

二、安裝與基本用法

# 安裝
apt-get install gperf   # Debian/Ubuntu
yum install gperf       # RHEL/CentOS

# 基本流程
gperf -L C -t keywords.gperf > keywords.c
gcc -o myprog myprog.c keywords.c

三、.gperf 輸入檔案結構

%{
/* 前言：直接複製到生成碼頂部 */
#include 
#include 
%}

struct Keyword {        /* 定義結構體，欄位名任意 */
    const char *name;
    int id;
    /* 可加入更多欄位 */
};

%%
/* 關鍵字列表：每行一個，可附加結構體欄位值 */
"if",     IF_TOKEN
"else",   ELSE_TOKEN
"while",  WHILE_TOKEN
"for",    FOR_TOKEN
"return", RETURN_TOKEN
%%

/* 後言：複製到生成碼尾部，通常放 main 或測試碼 */
int main(int argc, char **argv) {
    const struct Keyword *kw;
    for (int i = 1; i < argc; i++) {
        kw = in_word_set(argv[i], strlen(argv[i]));
        if (kw)
            printf("Found: %s -> %d\n", kw->name, kw->id);
        else
            printf("Not a keyword: %s\n", argv[i]);
    }
    return 0;
}

四、關鍵命令列選項

選項	說明
`-L C` / `--language=C`	生成 C 程式碼 (預設)，也支援 C++, ANSI-C
`-t` / `--struct-type`	使用結構體輸出 (需在前言定義)，而非單純字串比對
`-k` / `--key-positions`	指定雜湊關鍵字位置 (如 `-k1,3,$` 取首、尾、第三字符)，手動優化
`-D` / `--duplicates`	允許重複關鍵字 (預設報錯)
`-i` / `--initial-assoc`	初始關聯值陣列大小 (預設自動)
`-j` / `--jump`	生成跳躍表而非 switch (大集合更快)
`-o` / `--output-file`	指定輸出檔名
`--ignore-case`	大小寫不敏感比對
`-S` / `--switch`	強制 switch 陳述式 (預設小集合)

五、完整實戰：命令列選項解析器

1. 定義 options.gperf

%{
#include 
#include 
#include 
%}

struct Option {
    const char *long_name;  // 如 "--help"
    char short_opt;         // 如 'h'
    int has_arg;            // 0=無參數, 1=必需, 2=可選
    const char *desc;
};

%%
"--help",        'h', 0, "Show help"
"--version",     'v', 0, "Show version"
"--input",       'i', 1, "Input file"
"--output",      'o', 1, "Output file"
"--verbose",     'V', 2, "Verbose mode"
%%

#include 

bool parse_args(int argc, char **argv, struct Config *cfg) {
    for (int i = 1; i < argc; i++) {
        const struct Option *opt = in_word_set(argv[i], strlen(argv[i]));
        if (!opt) {
            fprintf(stderr, "Unknown option: %s\n", argv[i]);
            return false;
        }
        switch (opt->short_opt) {
            case 'h': print_help(); exit(0);
            case 'v': print_version(); exit(0);
            case 'i': 
                if (i+1 >= argc) { fprintf(stderr, "%s needs argument\n", argv[i]); return false; }
                cfg->input = argv[++i]; break;
            case 'o':
                if (i+1 >= argc) { fprintf(stderr, "%s needs argument\n", argv[i]); return false; }
                cfg->output = argv[++i]; break;
            case 'V': cfg->verbose = true; break;
        }
    }
    return true;
}

2. 生成與編譯

gperf -L C -t options.gperf > options.c
gcc -o mytool main.c options.c

六、效能特性與優化建議

查找複雜度：嚴格 O(1)，最多 2 次字串比較 (雜湊碰撞極少)。
記憶體佔用：靜態陣列，約關鍵字總長度 + 索引表 (通常 < 2x 關鍵字大小)。
大小寫不敏感：--ignore-case 會將關鍵字與輸入同樣轉換，略增 CPU。
手動優化 -k：對於前綴相似關鍵字 (如 --input-file, --input-dir)，指定關鍵位置 -k2,$,3 可大幅減少比較次數。
-j (跳躍表) 適用於 >200 關鍵字，生成碼較大但查找更快。

七、gperf vs 替代方案

工具	類型	適用場景
gperf	靜態完美雜湊	編譯期已知、不變關鍵字集 (關鍵字、選項、指令)
CMPH	靜態最小完美雜湊	極大集合 (百萬級)、需最小記憶體
re2c	詞法分析器生成器	複雜 Token 匹配、正則表達式
unordered_map	動態雜湊表	執行期動態增減、非完美雜湊
trie/DAWG	前綴樹	自動完成、IP 路由、字典查找