Статическая табличка.

Здравствуйте. Я хочу сделать в программе на С статическую табличку для бинарного поиска данных. Табличку я формирую примерно так:

Код (Text):

1. unsigned int calc_hash(char const* s)
2. {
3.   // ...
4. }
5.  
6. typedef struct
7. {
8.   unsigned int hash;
9.   void* data;
10. } node;
11.  
12. int main()
13. {
14.   node table[] = { {calc_hash("abc"), "xyz"}, {..}, ..};
15. }

Поиск будет производиться по хешам node::hash. Хеши высчитывать compile-time, я так понимаю, не получится. Чтобы была возможность производить бинарный поиск по табличке необходимо её как-то упорядочить. Строить дерево в runtime'е не очень охота, т.к. все элементы таблицы известны на этапе компиляции. Можно, конечно, в runtime создать её, упорядочить и дальше работать с ней. Но мне хочется скинуть эту работу на компилятор, чтобы он в compile-time мне всё посчитал и сформировал табличку. Один из возможных вариантов - написать соответствующий bat скрипт.. Проблема в том, что всё это будет собираться под виндой, будь линух - можно было бы perl скрипт накатать. Писать на виндовом шеле не очень-то охота.

 

получится, если компилятор поддерживает constexpr из стандарта C++0x... можно на темплейтах, но тогда уже нужны будут темплейты с переменным числом параметров (тоже из C++0x) и строку придется задавать посимвольно, тк строка вроде как не может быть параметром шаблона...

про сортировку таблицы во времени компиляции - это сложно... можно попробовать на шаблонах сделать, но опять же без поддержки стандарта C++0x видимо не обойтись... либо делаете pre-build step, на котором формируете таблицу в си-файл, затем этот файл автоматом должен подключаться к сборке...

 

Програмка на языке "C".

То есть нужно програмку написать, которая будет запускаться во время компиляции и генерировать, например, хидер.

 

сами же вгоняете себя в бессмысленные рамки)

именно так... можно даже больше, написать интерпретатор своего декларированного языка, которому во время компиляции будет скармливаться файл с описанием таблицы, и уже интерпретатор будет генерировать си-файл... для этого можно использовать скажем XML-парсер (один любой из миллионов), или же написать свой парсер своего языка разметки с использованием того же GNU Bison, или Boost::Spirit, или ANTLR... в последнем кстати для целей создания собственного языка разметки есть даже целое IDE, написанное на джаве...

 

, не, не сам. Работа такая

 

srm

Ну почему же? Запишите табличку в виде:

Код (Text):

1. abc xyz
2. qwe asd
3. бла-бла-бла ...

После чего напишите препроцессор таблички:

Код (Text):

1. #include <stdio.h>
2. #include "my-hash-module.h"
3. int main () {
4.     char name[16], value[16];
5.     printf ("node table[] = {\n");
6.     while (!feof (stdin)) {
7.         scanf("%s%s", name, value);
8.         printf ("{0x%x, \"%s\"},\n", calc_hash(name), value);
9.     }
10.     printf ("};\n");
11.     return 0;
12. }

Из Makefile преобразуете табличку из исходного вида в C, складываете в файлик mytable.c. И последний штрих: в модуле main.c пишете так:

Код (Text):

1. int main ()
2. {
3.     node table[] =
4. #          include "mytable.c"
5. ;
6. /* ... */
7. }

Несколько уродливо, конечно, но это, хоть и простейший, но не единственный вариант. Можно вывести табличку в виде #define MY_TABLE {...}, и использовать в main макрос. Если очень хочется, то можно написать препроцессор для C, чтобы в main писать что-то типа:

Код (Text):

1. int main ()
2. {
3.     node table[] = %%{{"key1", "value1"} {"key2", "value2"} ... }%%;
4. }

Но такой препроцессор конечно же лучше писать уже не на C, а на Perl/Python/Ruby или другом языке в котором использование регекспов легко и приятно.

 

это не "compile-time", это - "custom build step")))

 

Rel

Нет, это, на самом то деле, демагогия. Никому ненужные теоретизирования в чисто практической задаче. Ведь как ни назови кодогенерацию, всё равно она будет происходить при выполнении команды make. И мне честно говоря без разницы, выполняется ли мною написанный код кодогенерации в контексте процесса компилятора, или форкается компилятором и выполняется как самостоятельный процесс, или форкается процессом make. Какая разница? Или вы видите какие-то принципиальные отличия, которые оправдывют неукоснительное следование терминологии, предложенной вами?

 

[off]r90, давайте флейм не будем разводить[/off]

 

srm

Сорри, не сдержался. Не выношу теоретиков от программирования.

 

А можно ли создать статическую табличку, например, такого вида:

Код (Text):

1. static int const N = 100;
2. static int const arr[] = {0, 1, 2, 3, ... N};

?

 

вот странный человек... в чем разница между #6 и:

зачем третий раз предлагать то, что уже было предложено дважды? еще чет ругается...

есть решения в лоб, а есть красивые решения... разница только в этом...

 

Жаль, что на форуме нет тега [off]xx[/off] или

Спойлер

xx

.

 

В голову приходит такая идея:

Код (Text):

1. template <int i_elem>
2. struct static_arr :
3.     static_arr<i_elem - 1>
4. {
5.     //static int const value = i_elem;
6.     int const value;
7.     static_arr<i_elem>() : value(i_elem) {}
8. };
9.  
10. template <>
11. struct static_arr<0>
12. {
13.     //static int const value = 0;
14.     int const value;
15.     static_arr<0>() : value(0) {}
16. };
17.  
18. int main()
19. {
20.     static static_arr<255> const arr;
21.     static_arr<0> const* p_zero = static_cast< static_arr<0> const* >(&arr);
22.     int const* p_arr = &p_zero->value;
23.     static int const val = arr.value;
24.  
25.     for (int i = 0; i < 256; ++ i)
26.     {
27.         std::cout << i << " = " << p_arr[i] << std::endl;
28.     }
29. }

 

только это си плюс плюс))) но вообще это почти то, что тебе нужно.. объяви только массив в структуре и сможен не разименовывать указатели...