highly professional scums

В природе есть масса отличных инструментов, которые мало кто использует. Очередной раз применив в бою один из таких, решил начать про них рассказывать. Сегодня на повестке программа с обманчивым именем gperf – GNU is not Unix, and gperf is not a performance profiler.

gperf это генератор идеальных хеш-функций. Идеальность заключается в том, что в хеш таблице не будет ни одной коллизии, те. поиск ключа стоит примерно одно строковое сравнение (иногда меньше). На входе gperf хочет тупой список ключевых слов, для которых строится хеш:

[code lang="cpp"]
struct month { char *name; int number; int days; int leap_days; };
%%
january, 1, 31, 31
february, 2, 28, 29
march, 3, 31, 31
april, 4, 30, 30
may, 5, 31, 31
june, 6, 30, 30
july, 7, 31, 31
august, 8, 31, 31
september, 9, 30, 30
october, 10, 31, 31
november, 11, 30, 30
december, 12, 31, 31
[/code]

На выходе несложной команды gperf -t sample.p –output-file sample.c получается вот такое (код слегка очищен от #if для простоты восприятия):

[code lang="cpp"]
struct month { char *name; int number; int days; int leap_days; };

#define TOTAL_KEYWORDS 12
#define MIN_WORD_LENGTH 3
#define MAX_WORD_LENGTH 9
#define MIN_HASH_VALUE 3
#define MAX_HASH_VALUE 18

static unsigned int hash ( const char * str, int len )
{
static unsigned char asso_values[] =
{
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 5, 5, 5,
0, 19, 5, 0, 19, 19, 0, 19, 10, 0,
0, 5, 0, 19, 0, 0, 0, 19, 0, 19,
19, 0, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19
};
return len + asso_values[(unsigned char)str[2]] + asso_values[(unsigned char)str[0]];
}

struct month * in_word_set ( const char * str, int len )
{
static struct month wordlist[] =
{
{""}, {""}, {""},
{"may", 5, 31, 31},
{"june", 6, 30, 30},
{"march", 3, 31, 31},
{""},
{"january", 1, 31, 31},
{"november", 11, 30, 30},
{"september", 9, 30, 30},
{"april", 4, 30, 30},
{"august", 8, 31, 31},
{"october", 10, 31, 31},
{"december", 12, 31, 31},
{"july", 7, 31, 31},
{""}, {""}, {""},
{"february", 2, 28, 29}
};

if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)
{
register int key = hash (str, len);

if (key <= MAX_HASH_VALUE && key >= 0)
{
register const char *s = wordlist[key].name;

if (*str == *s && !strcmp (str + 1, s + 1))
return &wordlist[key];
}
}
return 0;
}
[/code]

Основная радость в мега-быстром вычислении хеш-функции и ровно одном сравнении строк в “худшем” случае, когда ключ таки найден. Разумеется, есть всякие опции для контроля над выходным файлом: задание языка (можно генерировать функции, можно C++ класс); задание имен и видимости функций; поддержка ключей с нулевыми байтами внутри (!); контроль за размером таблицы (обмен размера таблицы на время поиска); итп. Применимо, понятно, для случаев, когда набор ключей фиксирован и известен заранее – для абсолютно случайных данных идеальный хеш не построить. Для всяческих текстовых парсеров, где больше десятка ключевых слов, самое то.