Календарь на Апрель 2024 года: calendar2008.ru/2024/aprel/
Навигация
Главная »  Игры 

Использование 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 ." #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  #include  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 в вашем следующем проекте.



 

 Diablo 3. Третье погружение в дьявольщину.
 Рецензия: Gears of War 3. Шутер со стальными яйцами.
 Самоисполняемый phar как способ распространения веб-приложений.
 Обзор игры The Cursed Crusade.
 Высокие технологии мотивации.


Главная »  Игры 

© 2024 Team.Furia.Ru.
Частичное копирование материалов разрешено.