Використання gperf для ефективної обробки параметрів командного рядка в C / C + + (исходники), Різне, Програмування, статті

Обробка параметрів командного рядка і необхідність 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, А len12.


Функцією пошуку в хеше, створеному 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


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



Внутрішня реалізація 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:gperfgperf.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 у вашому наступному проекті.


Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*