Compile time вычисление хеша строки - C/C++

Есть проблема: необходимо на этапе компиляции вычислить хеш строки. Хеш-функция очень простая, например:

template<class charT>
unsigned hash(charT* str)
{
    unsigned h = 0;
    for(; *str; ++str)
        h = 5 * h + *str;
    return h;
}

Долго пытался реализовать нечто подобное вычислению факториала:

#include <iostream>
#include <iomanip>

template<unsigned n>
struct factorial
{
    enum { value = n * factorial<n-1>::value };
};

template<>
struct factorial<0>
{
    enum { value = 1 };
};

int main()
{
    std::cout << factorial<5>::value << std::endl;
    return 0;
}

С факторилом все понятно и ясно — в качестве параметра ordinal и проблем нет.
А вот с шаблоном, принимающим строку и вычисляющим ее хеш — ничего работающего (компилирующегося) в голову не пришло.

    unsigned h = hash<"test">::value;

Может кто сталкивался с такой проблемой? Или есть идеи?

Заранее спасибо!

Здравствуйте paul_shmakov, Вы писали:

PS>Есть проблема: необходимо на этапе компиляции вычислить хеш строки.

Зачем?

<< J 1.0 alpha 4 >>

Здравствуйте paul_shmakov, Вы писали:

[skip]

PS>С факторилом все понятно и ясно — в качестве параметра ordinal и проблем нет.
PS>А вот с шаблоном, принимающим строку и вычисляющим ее хеш — ничего работающего (компилирующегося) в голову не пришло.

PS>

PS>    unsigned h = hash<"test">::value;
PS>

PS>Может кто сталкивался с такой проблемой? Или есть идеи?

По идее — аргументом шаблона может служить константная строка с extern-связыванием:

#include <iostream.h>

extern "C" const char S1[] = "S1";
extern "C" const char S2[] = "S2";

template<const char *ARG>
class Str
{
  public:
    Str()
    {
      cout << ARG << endl;
    }
};

int main(int argc, char* argv[])
{
  Str<S1> s1;
  Str<S2> s2;
  return 0;
}

Вывод этой программы (MSVC6):

S1
S2

Ну а дальше действуй сообразно структуре хеш-функции.

Здравствуйте Геннадий Васильев, Вы писали:

PS>>А вот с шаблоном, принимающим строку и вычисляющим ее хеш — ничего работающего (компилирующегося) в голову не пришло.
<...>
ГВ>По идее — аргументом шаблона может служить константная строка с extern-связыванием:

Только вычислять значение хэша подобный шабон будет не во время компиляции, а во время выполнения, дискредитируя всю "идею"

<< J 1.0 alpha 4 >>

Здравствуйте Павел Кузнецов, Вы писали:

ПК>Здравствуйте paul_shmakov, Вы писали:

PS>>Есть проблема: необходимо на этапе компиляции вычислить хеш строки.

ПК>Зачем?

На самом деле это не так важно, но есть такая задача. Есть некая библиотека, "черный ящик" (т.е. ее внутренее устройство менять нельзя), интерфейс которой предоставляет набор сервисов. Вызов сервисов осуществляется передачей строки с именем сервиса:

    call_service("system\\database\\restart", ...);

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

    const unsigned hash_some_function = 0x23243412; // = get_hash("system\\database\\restart")
    call_service(hash_some_function, ...);

Тут и неудобство — вычислять хеш приходится "руками" отдельной программой и вставлять в код. Куда приятнее было бы написать:

    call_service(hash<"system\\database\\restart">(), ...);

Но даже не эта задача сподвигла к написанию вопроса. Просто стало очень интересно — возможно ли это реализовать? Мои мучения ни к чему пока не привели. Может кто-то сталкивался с подобной задачей?

Здравствуйте Павел Кузнецов, Вы писали:

ГВ>>По идее — аргументом шаблона может служить константная строка с extern-связыванием:

ПК>Только вычислять значение хэша подобный шабон будет не во время компиляции, а во время выполнения, дискредитируя всю "идею" :-)

В том-то и дело :(

Здравствуйте paul_shmakov, Вы писали:

PS>Известно и документировано, что реализация call_service выполняет над этой строкой хеш-преобразование и дальше работает с значением хеша. Хеш функция также документирована, также предоставлен интерфейс для более быстрого вызова со стороны клиента:

PS>

PS>    const unsigned hash_some_function = 0x23243412; // = get_hash("system\\database\\restart")
PS>    call_service(hash_some_function, ...);
PS>

PS>Тут и неудобство — вычислять хеш приходится "руками" отдельной программой и вставлять в код. Куда приятнее было бы написать:

PS>

PS>    call_service(hash<"system\\database\\restart">(), ...);
PS>

а что мешает написать, скажем, так:

const unsigned hash_some_function = get_hash("system\\database\\restart");
call_service(hash_some_function, ...);

Пусть hash_some_function вычисляется один раз при инициализации программы? Или это тоже слишком медленно?

<< J 1.0 alpha 4 >>

Здравствуйте Павел Кузнецов, Вы писали:

ПК>а что мешает написать, скажем, так:

ПК>

ПК>const unsigned hash_some_function = get_hash("system\\database\\restart");
ПК>call_service(hash_some_function, ...);
ПК>

ПК>Пусть hash_some_function вычисляется один раз при инициализации программы? Или это тоже слишком медленно?

Да, было бы желательно вычислить хеш еще на этапе компиляции. Дело в том, что вызовы call_service осуществляют достаточно большое количество маленьких dll (плагинов), которые загружаются не при старте приложения, а только в момент обработки некоего события. У них задача — как можно быстрее отработать. Поэтому, собственно, даже и был введен дополнительный интерфейс функции call_service, принимающей хеш, а не строку.

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

Здравствуйте paul_shmakov, Вы писали:

ПК>>Пусть hash_some_function вычисляется один раз при инициализации программы? Или это тоже слишком медленно?

PS>Дело в том, что вызовы call_service осуществляют достаточно большое количество маленьких dll (плагинов), которые загружаются не при старте приложения, а только в момент обработки некоего события.

Подозреваю, что ничего этим выиграть особенно не получится: время загрузки, пусть даже маленькой, DLL несопоставимо со временем выполнения хэш-функции от строки. Разве что, этих строк в каждой DLL очень много... Профайлером пробовал?

PS>Но даже больше интересует не оптимизация по времени моего кода, а сама возможность (или невозможность) вычисления хеша на этапе компиляции. Уж больно мне нравится идея вычислений на этапе компиляции со строками в качестве пареметров, а тут и задача как раз подвернулась

Если уж так... Нет, непосредственно по строке нельзя, т.к. выражения со строками и массивами не являются константами времени компиляции. Можно примерно так:

template<char c1, char c2, char c3, char c4 /*, сколько их там надо*/>
class Hash
{
static const unsigned value = . . . ;
};

typedef Hash<'s', 'y', 's', 't', 'e', 'm', '\\',
'd', 'a', 't', 'a', 'b', 'a', 's', 'e', '\\',
'r', 'e', 's', 't', 'a', 'r', 't'> hash_some_function;

call_service(hash_some_function::value, ...);

Или того хуже, навернуть рекурсивные шаблоны для произвольной длины, но, имхо, все это того не стоит.

<< J 1.0 alpha 4 >>

Здравствуйте Павел Кузнецов, Вы писали:

ПК>Подозреваю, что ничего этим выиграть особенно не получится: время загрузки, пусть даже маленькой, DLL несопоставимо со временем выполнения хэш-функции от строки. Разве что, этих строк в каждой DLL очень много... Профайлером пробовал?

Я же говорю — меня не столько оптимизация этой задачи интересует, сколько сама возможность

ПК>Если уж так... Нет, непосредственно по строке нельзя, т.к. выражения со строками и массивами не являются константами времени компиляции. Можно примерно так:

ПК>template<char c1, char c2, char c3, char c4 /*, сколько их там надо*/>
ПК>class Hash
ПК>{
ПК> static const unsigned value = . . . ;
ПК>};

ПК>typedef Hash<'s', 'y', 's', 't', 'e', 'm', '\\',
ПК> 'd', 'a', 't', 'a', 'b', 'a', 's', 'e', '\\',
ПК> 'r', 'e', 's', 't', 'a', 'r', 't'> hash_some_function;

ПК>call_service(hash_some_function::value, ...);

ПК>Или того хуже, навернуть рекурсивные шаблоны для произвольной длины, но, имхо, все это того не стоит.

Вот и я ничего лучшего не придумал

А жаль, ведь хеш — это одно из приминений. Но все равно спасибо!

Здравствуйте paul_shmakov, Вы писали:

PS>Есть проблема: необходимо на этапе компиляции вычислить хеш строки. Хеш-функция очень простая, например:

Для этого можно написать скрипт, который будет вызываться перед компиляцией, который ищет в сорцах твою HASH функцию, ее аргумент передает в утилитку и результат вставляет вместо вызова твоей функции. Опытный линуксоид справится с этой задачей за час. У нас таким образом константные строчки с версией файла из VersionControl системы вставляются в код как const char*, а поределенная функция печатает их. Не так красиво, но работает.

Здравствуйте the_moon, Вы писали:

TM>Для этого можно написать скрипт, который будет вызываться перед компиляцией, который ищет в сорцах твою HASH функцию, ее аргумент передает в утилитку и результат вставляет вместо вызова твоей функции. Опытный линуксоид справится с этой задачей за час. У нас таким образом константные строчки с версией файла из VersionControl системы вставляются в код как const char*, а поределенная функция печатает их. Не так красиво, но работает.

Это все понятно, примерно так сейчас делаю. Но интерес представляет именно возможность/невозможность реализации средствами самого языка, с помощью шаблонов или еще как. Но, похоже, этого сделать нельзя

А было бы очень красиво. Вариант Павла Кузнецова (передача строки отдельными символами) — это не то.

Здравствуйте the_moon, Вы писали:

TM>Здравствуйте paul_shmakov, Вы писали:

PS>>Есть проблема: необходимо на этапе компиляции вычислить хеш строки. Хеш-функция очень простая, например:

TM>Для этого можно написать скрипт, который будет вызываться перед компиляцией, который ищет в сорцах твою HASH функцию, ее аргумент передает в утилитку и результат вставляет вместо вызова твоей функции. Опытный линуксоид справится с этой задачей за час. У нас таким образом константные строчки с версией файла из VersionControl системы вставляются в код как const char*, а поределенная функция печатает их. Не так красиво, но работает.

Зачем так мучаться, когда есть мощный С-препроцессор.
Ребятки из boost'a уже над этим поработали.
Если эта линка не поможет, то по крайней мере на мысли натолкнет.

http://www.boost.org/libs/preprocessor/doc/index.htm

Здравствуйте Sergeem, Вы писали:

S>Здравствуйте the_moon, Вы писали:

TM>>Здравствуйте paul_shmakov, Вы писали:

PS>>>Есть проблема: необходимо на этапе компиляции вычислить хеш строки. Хеш-функция очень простая, например:

TM>>Для этого можно написать скрипт, который будет вызываться перед компиляцией, который ищет в сорцах твою HASH функцию, ее аргумент передает в утилитку и результат вставляет вместо вызова твоей функции. Опытный линуксоид справится с этой задачей за час. У нас таким образом константные строчки с версией файла из VersionControl системы вставляются в код как const char*, а поределенная функция печатает их. Не так красиво, но работает.

S>Зачем так мучаться, когда есть мощный С-препроцессор.
S>Ребятки из boost'a уже над этим поработали.
S>Если эта линка не поможет, то по крайней мере на мысли натолкнет.

S>http://www.boost.org/libs/preprocessor/doc/index.htm

еще в догонку, но это уже через шаблоны:
http://www.mywikinet.com/mpl/

	От:	paul_shmakov
	Дата:	13.09.02 17:39
	Оценка:

	От:	Павел Кузнецов
	Дата:	14.09.02 15:13
	Оценка:

От:	Геннадий Васильев	http://www.livejournal.com/users/gesha_x
Дата:	14.09.02 22:43
Оценка:

	От:	Павел Кузнецов
	Дата:	15.09.02 08:09
	Оценка:

	От:	paul_shmakov
	Дата:	15.09.02 18:41
	Оценка:

	От:	the_moon
	Дата:	16.09.02 11:30
	Оценка:

	От:	Sergeem
	Дата:	18.09.02 15:05
	Оценка:

	От:	Sergeem
	Дата:	19.09.02 13:03
	Оценка:	10 (1)