Использование gperf для эффективной обработки параметров командной строки в C/C++ (исходники)

Источник: IBM developerWorks Россия
Арпан Сен, Рахул Кардам

Обработка параметров командной строки и необходимость gperf

Исторически обработка параметров командной строки является одной из областей разработки программного обеспечения, которым уделяется наименьшее внимание. Практически у любого более или менее сложного программного обеспечения существует множество параметров командной строки. На самом деле, нет ничего необычного в сотнях строк кода с операторами if-else, обрабатывающих вводимые пользователем данные, и поддержка такого кода становится очень трудоемкой даже для опытных программистов. В таких случаях большинство разработчиков на C предпочитают использовать длинные (и, зачастую, вложенные) операторы if-else, дополненные для удобства чтения функциями из библиотеки ANSI C, например, strcmp, strcasecmp и strtok, что видно из Листинга 1.

Листинг 1. Обработка параметров командной строки в стиле C
                
if (strtok(cmdstring, "+dumpdirectory"))
  {
  // здесь идет код вывода справочных сообщений
  }
else if (strtok(cmdstring, "+dumpfile"))
  {
  // здесь идет код печати информации о версии
  }

Вместо программного интерфейса API из ANSI C разработчик C++, скорее всего, будет использовать строковые функции из стандартной библиотеки шаблонов (Standard Template Library, STL). Однако же, и здесь не уйти от вложенных последовательностей операторов if-else. Определенно, такой подход нельзя назвать масштабируемым с ростом количества параметров. Для запуска обычной программы с N параметрами, код должен будет выполнить O(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, который выводится без изменений */
%}
объявления
%%
ключевые слова
%%
функции

Формат состоит из нескольких элементов: включение кода C, объявления, ключевые слова и функции.

Включение кода C

Включение кода C представляет собой необязательную секцию, заключенную между %{ и %}. Код C и комментарии, приведенные в этой секции, копируются в выходной файл, генерируемый gperf, без изменений. (Обратите внимание на схожесть с утилитами GNU flex и bison.)

Объявления

Секция объявлений также необязательна; вы можете полностью опустить ее содержимое, если не будете вызывать gperf с параметром -t. Однако если вы включите этот параметр, последним компонентом раздела объявлений должна быть структура, первым полем которой должен быть идентификатор name типа char* или const char*.

Впрочем, в gperf существует возможность изменения названия первого поля путем использования параметра -K. Например, если вы желаете назвать это поле command_option , вызывайте gperf следующим образом:

gperf -t -K command_option

В Листинге 3 представлены разделы включения кода C и объявлений.

Листинг 3. Секции включения кода C и объявлений
                
%{
struct CommandOptionCode  {
  enum { 
      HELPVERBOSE = 1,
      ..., // здесь указываются дополнительные параметры
      _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 предоставляет значительно более понятный интерфейс.

Как видно из Листинга 3, первая запись соответствует полю const char* command_option структуры CommandOption; вторая запись ссылается на поле 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 описаны в онлайновом справочнике (смотри ссылку в разделе Ресурсы), в их число входят:

  • -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: Этот параметр полезен вместе с выбором значения C++ параметра -L. Он позволяет указать название создаваемого класса C++, в котором будут создаваться функции in_word_set() и hash(). По умолчанию класс называется Perfect_Hash.
  • -G: Этот параметр создает таблицу поиска как статическую глобальную переменную, не скрывая ее внутри функции поиска (поведение по умолчанию).
  • -C: Gperf создает таблицы поиска указанным выше способом. Параметр -C создает таблицы поиска, объявляемые с ключевым словом const; содержимое всех создаваемых таблиц поиска является константой, то есть доступно только для чтения. Многие компиляторы могут создавать более эффективный код, размещая таблицы в памяти только для чтения.
  • -D: Этот параметр обрабатывает ключевые слова с дублирующимися значениями хеша.
  • -t: Этот параметр позволяет добавлять структуру ключевых слов.
  • -K: Эта функция позволяет пользователю выбирать название компонента ключевого слова в структуре ключевых слов.
  • -p: Этот параметр сохранен для обеспечения совместимости с предыдущими версиями gperf. В этих версиях он изменял возвращаемое булево значение (то есть 0 или 1) функции in_word_set() на тип pointer to wordlist array. Это было полезно при указании параметра -t, который позволял пользователям создавать structs. В последних версиях gperf этот параметр не нужен и может быть опущен.

Обзор внутренней структуры gperf

Статическое поисковое множество (Static search set) представляет собой абстрактный тип данных с операциями initialize, insert и retrieve. Функции идеального хеша являются оптимизированными по времени и занимаемой памяти реализациями статических поисковых множеств. Gperf - это генератор идеальных хеш-функций из списка ключевых слов, предоставляемых пользователем. Gperf переводит список ключевых слов из n элементов, предоставляемый пользователем, в исходный код, содержащий поисковую таблицу из k элементов и две функции:

  • hash: Эта процедура создает уникальные соответствия между ключевым словами и диапазоном 0 .. k - 1, где k = n. Если k = n, hash() считается минимальной идеальной функцией hash(). У этой функции hash() есть два свойства:
    • свойство идеальности: Поиск записи таблицы занимает O(1) времени, то есть для распознавания ключевого слова в статическом поисковом множестве требуется одна операция строкового сравнения.
    • Свойство минимальности: Памяти, выделяемой для хранения ключевых слов, достаточно для хранения набора ключевых слов, и не более того.
  • in_word_set: Эта процедура использует hash() для определения того, принадлежит ли определенная строка к списку, предоставленному пользователем, используя в большинстве случаев одну операцию строкового сравнения.

Внутренняя реализация gperf построена на двух структурах данных: списке ключей ключевых слов (Key_List) и массиве связанных значений (asso_values). Каждое ключевое слово и его параметры считываются из файла, предоставляемого пользователем, и сохраняются как узлы в связанном списке Key_List. В качестве ключа при поиске для идеальной функции hash() gperf рассматривает только часть символов каждого ключевого слова. Эта часть называется ключом ключевого слова (keyword signature) , или keysig.

Массив связанных значений генерируется в функции hash() и индексируется по символам keysig. Gperf выполняет многократный поиск конфигурации связанных значений, устанавливающей соответствие между всеми n ключами keysig и уникальными значениями хеша. Когда gperf находит конфигурацию, устанавливающую уникальное место расположения каждого ключа keysig в создаваемой таблице поиска, создается идеальная функция hash(). Получившаяся идеальная функция hash() возвращает значение unsigned int, лежащее в диапазоне 0..( k -1), где k - максимальное значение хеша ключевого слова +1.

В случае, когда k = n, создается минимальная идеальная функция hash(). Значение хеша ключевого слова обычно рассчитывается путем сочетания связанных значений ключа keysig с его длиной. По умолчанию функция hash() добавляет связанное значение первой позиции индекса ключевого слова и связанное значение последней позиции индекса к его длине, например:

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

Пример проекта

Чтобы проиллюстрировать изложенный выше материал, рассмотрим небольшой проект. Посмотрите на файл gperf, приведенный в Листинге 5.

Листинг 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 показан файл заголовка command_options.h, включаемый в файл gperf.

Листинг 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 также есть другие области применения. Фактически, это лучший инструмент для работы с идеальными хешами для ключевых слов в компиляторах GNU, а последние усовершенствования также позволяют вам работать с более крупными массивами данных. Попробуйте использовать gperf в вашем следующем проекте.


Страница сайта http://test.interface.ru
Оригинал находится по адресу http://test.interface.ru/home.asp?artId=8664