About gpref O(n2) --> O(1)

http://www.ibm.com/developerworks/cn/linux/l-gperf.html

命令行处理和 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 输入文件的典型格式。

清单 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

C++/STL 风格的初始化

C++/STL 风格的初始化就是创建一个 stl::map 并使用insert() 方法将它反复插入到映射中。相反，任何负责维护代码的人员必须对其进行调试，以找出每一个命令行选项进行初始化的确切位置，这在编写糟糕的代码中十分常见。Gperf 对此提供了更加整洁的界面。

第一个条目指 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++ 代码。
• -N：该选项允许用户修改查找函数的名称。默认名为 in_word_set()。
• -H：该选项允许用户修改散列例程的名称。默认名为 hash()。
• -Z：该选项在提供了 -L C++ 选项时使用。它允许用户指定所生成的 C++ 类的名称，该类包含 in_word_set() 和 hash() 函数。默认名为Perfect_Hash。
• -G：该选项将生成查找表并将其作为静态全局变量，而不是在查找函数内生成以隐藏该表（默认行为）。
• -C：前面讨论了 Gperf 将生成查找表。-C 选项将创建使用 const 关键字声明的查找表。所有生成的查找表中的内容都是常量 — 即只读形式。很多编译器通过将表放入只读内存中可以生成更高效的代码。
• -D：该选项将处理散列为重复值的关键字。
• -t：该选项允许包含关键字结构。
• -K：该选项允许用户选择关键字结构中的关键字组件的名称。
• -p：该选项可以与较早版本的 gperf 兼容。在早期版本中，它将生成的函数 in_word_set() 返回的默认布尔值（即 0 或 1 ）修改为 pointer to wordlist array 类型。这个选项非常有用，尤其是在使用 -t（允许使用用户定义的 structs）选项时。在最新版的 gperf 中并不要求使用该选项并且可以将其删除。

回页首

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

清单 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 选项，将在全局范围内生成散列表。因为使用 -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 <[e-mail]>."
#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 还可用于其他目的。事实上，可以在 GUN 编译器中使用它维护语言关键字的完美散列，其最新的功能使您能够操作更大的数据库。因此，可以考虑在您的下一个开发项目中使用 gperf。