Използване на gperf за ефективна обработка на опциите на командния ред в C
Генераторът на идеални хеш функции на GNU (gperf) улеснява работата със сложни входни параметри
Работа с опциите на командния ред и необходимостта от gperf
В исторически план обработката на параметрите на командния ред е била една от областите на разработката на софтуер, която е получавала най-малко внимание. Почти всеки повече или по-малко сложен софтуер има много опции на командния ред. Всъщност не е необичайно да има стотици редове код if-else, обработващ въвеждане от потребителя, и поддържането на такъв код става много трудоемко дори за опитни програмисти. В такива случаи повечето C разработчици предпочитат да използват дълги (и често вложени) изрази if-else, разширени за четимост с функции от библиотеката ANSI C, като strcmp, strcasecmp и strtok, както е показано в листинг 1.
Листинг 1. Работа с опции на командния ред в стил C
Вместо ANSI C API, разработчикът на C++ най-вероятно ще използва низови функции от Standard Template Library (STL). Въпреки това, вложените последователности от оператори if-else не могат да бъдат избегнати и тук. Определено този подход не може да се нарече мащабируем с увеличаване на броя на параметрите. За да изпълни нормална програма с N параметъра, кодът трябва да извърши O(N 2 ) сравнения. За да създадете код, който е по-бърз за изпълнение и по-лесен за поддръжка, има смисъл да използвате хеш таблици за съхраняване на опциите на командния ред и впоследствие да използвате хеша за валидиране на въведеното от потребителя.
Тук в игратавлиза в gperf. Той създава хеш-таблица въз основа на предварително дефиниран списък с разрешени опции на командния ред, както и функция за търсене, която има O(1) времева сложност. По този начин, за да извика нормална програма с N параметъра, кодът трябва само да извършиO(N) [N*O(1)] сравнения, което означава подобрение на производителността с порядък в сравнение с нормалния код.
Характеристики на използването на gperf
Gperf чете набор от ключови думи от предоставен от потребителя файл (обикновено .gperf файл, въпреки че не е задължителен), като commandoptions.gperf, и генерира изходния код на C/C++ за хеш-таблицата, хеш-методите и търсенията. Кодът е насочен към стандартен изход, който може да бъде пренасочен към файл като този:
Забележка: Опцията -L казва на gperf да генерира C++ код.
gperf входен файлов формат
Листинг 2 показва формата на входния файл gperf.
Списък 2. Формат на входен файл gperf
Активиране на C код
реклами
В gperf обаче е възможно да промените името на първото поле с помощта на опцията -K. Например, ако искате да наименувате това поле command_option, извикайте gperf по следния начин:
Ключови думи
Листинг 4. Секция за ключови думи
Както можете да видите в списък 3, първият запис съответства на полето const char* command_option на структурата CommandOption; вторият запис се отнася до полето int OptionCode на същата структура. И така, какво всъщност се случва тук? Всъщност това е начинът, по който gperf инициализира хеш таблица, която ще съхранява опциите на командния ред и свързаните с тях атрибути.
gperf изходен файл
Gperf хешира предварително дефинираннабор от ключови думи и след това извършва бързо търсене на тези думи. Следвайки тази техника, gperf извежда две функции: hash() и in_word_set(). Първата е процедурата за хеширане, докато втората се използва за търсене. Изходният файл на gperf може да бъде C или C++, в зависимост от избраните от вас опции. Ако искате изходният файл да бъде на C, ще бъдат създадени две C функции с горните имена. Ако изходният файл е на C++, gperf създава клас Perfect_Hash, който съдържа тези два метода.
Забележка: За да промените името на генерирания клас, използвайте опцията -Z.
Прототипът на хеш функцията изглежда така:
където str представлява опцията на командния ред, а len е нейната дължина. Например за аргумента на командния ред +helpverbose, str ще бъде +helpverbose и len ще бъде 12.
Функцията за търсене на хеша, генериран от gperf, е in_word_set(). Прототипът за тази рутина зависи от опцията -t, която потребителят посочва. Ако не укажете тази опция, ще имате работа с дефинирани от потребителя опции на командния ред, съхранени в gperf хеша като данни, а не със структура, свързана с командния ред.
Например листинг 3 дефинира структура на CommandOption, която е свързана с персонализиран команден аргумент, който процедурата in_word_set() ще върне. Можете да промените името на процедурата с опцията -N. Аргументите на процедурата са подобни на описаните по-рано за функцията hash():
Основни опции на gperf
Gperf е силно конфигурируем инструмент, който приема няколко параметъра. Всички опции на gperf са документирани в онлайн препратката (вижте Ресурси за връзка), включително:
Преглед на вътрешната структура на gperf
Наборът за статично търсене е абстрактен тип данни с операции за инициализиране, вмъкване и извличане. Идеалните хеш функции са оптимизирани за времето и паметта реализации на статични набори за търсене. Gperf е перфектен генератор на хеш функции от списък с ключови думи, предоставени от потребителя. Gperf преобразува предоставен от потребителя списък с ключови думи отn елемента в изходен код, съдържащ справочна таблица отk елемента и две функции:
- хеш : Тази рутина създава уникални съвпадения между ключови думи и диапазона0 .. k - 1, където k = n. Ако k = n, hash() се счита за минималната идеална функция hash(). Тази функция hash() има две свойства:
- свойство идеалност : Търсенето на запис в таблица отнемаO(1) време, което означава, че е необходима една операция за сравнение на низове, за да се разпознае ключова дума в статичен набор за търсене.
- Минимално свойство: Паметта, разпределена за съхраняване на ключови думи, е достатъчна за съхраняване на набор от ключови думи и не повече.
Вътрешното внедряване на gperf е изградено около две структури от данни: списък с ключови ключове ( Key_List ) и масив от свързани стойности ( asso_values ). Всяка ключова дума и нейните параметри се четат от предоставен от потребителя файл и се съхраняват като възли в свързан Key_List. Като ключ при търсене на перфектната функцияhash() gperf разглежда само част от знаците на всяка ключова дума. Тази част се нарича подпис на ключова дума или keysig.
Масив от свързани стойности се генерира във функцията hash() и се индексира от символите на keysig. Gperf извършва итеративно търсене за конфигурация на свързана стойност, съответстваща на всичкиn keysig ключове с уникални хеш стойности. Когато gperf намери конфигурация, която задава уникалното местоположение на всеки keysig в генерираната справочна таблица, се създава идеалната функция hash(). Получената идеална функция hash() връща int стойност без знак в диапазона 0..(k-1), където k е максималната хеш стойност на ключовата дума +1.
В случай, когато k = n, се създава минимална идеална функция hash(). Хеш-стойността на ключова дума обикновено се изчислява чрез комбиниране на свързаните стойности на ключа keysig с неговата дължина. По подразбиране функцията hash() добавя свързаната стойност на първата индексна позиция на ключова дума и свързаната стойност на последната индексна позиция към нейната дължина, например:
Примерен проект
За да илюстрирате горния материал, помислете за малък проект. Вижте gperf файла, показан в листинг 5.
Списък 5. command_options.gperf
Листинг 6 показва заглавния файл command_options.h, включен във файла gperf.
Листинг 6. Заглавка на Command_options.h
Извикването на gperf от командния ред ще изглежда така:
Хеш таблицата се генерира във файла perfecthash.hpp. Тъй като опцията -G е зададена в командния ред, се генерира глобална хеш таблица. Тъй като опцията -C е посочена при извикването на gperf, хеш-таблицата се декларира с атрибута const. Листинг 7 показва генериранияизточник.
Листинг 7. Създаден perfecthash.hpp
И накрая, списък 8 показва основния изходен код.
Забележка: Списък 8 показва, че можете да намерите всяка опция на командния ред в даден списък с ключови думи за фиксиран период от време и следователно да предприемете необходимите стъпки за обработка на тази опция. Времевата сложност на IsValidCommandLineOption е O(1).
Листинг 8. gperf.cpp, дефиниращ входната точка на приложението
Бележки: Всички примери в тази статия са тествани с gperf версия 3.0.3. Ако използвате по-ранна версия, може да се наложи да посочите опцията -p при извикване.
Заключение
Помощната програма gperf е настроена да формира бързо идеалния хеш за малки до средни набори от данни. Но gperf има и други приложения. Всъщност това е най-добрият инструмент за работа с перфектни хешове за ключови думи в компилаторите на GNU, а най-новите подобрения също ви позволяват да работите с по-големи набори от данни. Опитайте да използвате gperf в следващия си проект.
Изтегляне на ресурси
Свързани теми
- Оригинална статия Използвайте gperf за ефективна обработка на командния ред на C/C++. (EN)
- Повече информация за работа с gperf можете да намерите в gperf онлайн справочника. (EN)
- Изтеглете gperf от уебсайта на GNU. (EN)
- Потребителите на Cygwin могат да изтеглят gperf пакета от SourceForge.(EN)
- Допълнителни ресурси за разработчици на Linux, включително уроци за Linux и любимите статии и уроци за Linux на нашите читатели през последния месец, могат да бъдат намерени в раздела за Linux на developerWorks.(EN)
- Използвайте пробни версии на софтуераIBM продукти, достъпни за изтегляне директно от developerWorks, в следващия ви проект за разработка на Linux. (EN)