Обработка параметров командной строки и необходимость gperf
Исторически обработка параметров командной строки является одной из областей разработки программного обеспечения, которым уделяется наименьшее внимание. Практически у любого более или менее сложного программного обеспечения существует множество параметров командной строки. На самом деле, нет ничего необычного в сотнях строк кода с операторами if-else, обрабатывающих вводимые пользователем данные, и поддержка такого кода становится очень трудоемкой даже для опытных программистов. В таких случаях большинство разработчиков на C предпочитают использовать длинные (и, зачастую, вложенные) операторы if-else, дополненные для удобства чтения функциями из библиотеки ANSI C, например, strcmp, strcasecmp и strtok, что видно из Листинга 1.
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, эти поля являются последней структурой секции объявлений.
%% +helpverbose, CommandOptionCode::HELPVERBOSE +append_log, CommandOptionCode::APPEND_LOG +compile, CommandOptionCode::COMPILE |
|
Как видно из Листинга 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.
#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 представлен сформированный исходный код.
/* 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).
#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 в вашем следующем проекте.