Last week, I blogged about table-driven development without creating relocations in memory. One of the comments I received indicated that the code was hard to read — I concurred, of course, as it is generated code.
Then Olivier looked at it and decided to have a go at making it entirely generated by the compiler, after being inspired by my C++0x initialisation of arrays. He posted another comment on my blog with the link to his code: http://paste.kde.org/100651/.
That was great! Now we could have the no-relocation table: instead of having pointers, we get the compiler to generate the offset table for us. I just didn’t like about two things in his code: one, his code uses a preprocessor macro so the string can be passed twice. The second was the need to write one long string with “\0″ ourselves.
So I decided to give it a go as well. I got most of what I needed, but was stuck on Friday. Talking to João this morning, he helped me solve my last problem — turns out all I needed was to add one &…
Here’s how you’d use this:
static constexpr auto table =
createStringTable("Hello", "World");
int main()
{
extern void foo(const char*);
foo(table[0]);
foo(table[1]);
// if you ever needed, this works too:
extern void foo(int);
foo(table.offset(0));
foo(table.offset(1));
foo(table.offset(2));
}
And here’s how it’s done (analysis after the break):
// same code as previous blog
template <int...> struct IndexList {};
template <typename IndexList, int Right> struct Append;
template <int... Left, int Right> struct Append<IndexList<Left...>, Right>
{ typedef IndexList<Left..., Right> Result; };
template <int N> struct Indexes
{
typedef typename Append<typename Indexes<N - 1>::Result,
N - 1>::Result Result;
};
template <> struct Indexes<0> { typedef IndexList<> Result; };
template <typename IndexList> struct DataContainer;
template <int... I> struct DataContainer<IndexList<I...> >
{
enum { N = sizeof...(I) };
char data[N + 1];
constexpr inline DataContainer(const char str[N + 1])
: data({ str[I]... }) {}
constexpr const char *charptr() const { return data; }
};
// new code starts here
template <typename... Args> struct StringTableStrings;
template <int N, typename... Tail>
struct StringTableStrings<const char[N], Tail...>
{
typedef typename Indexes<N - 1>::Result IndexList;
DataContainer<IndexList> data;
StringTableStrings<Tail...> tail;
constexpr StringTableStrings(const char data[N], Tail... t)
: data(data), tail(t...) {}
constexpr const char *charptr() const { return data.charptr(); }
};
template <int N> struct StringTableStrings<const char [N]>
{
DataContainer<typename Indexes<N - 1>::Result> data;
constexpr StringTableStrings(const char data[N]) : data(data) {}
constexpr const char *charptr() const { return data.charptr(); }
};
template <typename... Args> struct StringTableInts;
template <int N, typename... Tail>
struct StringTableInts<const char[N], Tail...>
{
int index;
StringTableInts<Tail...> tail;
constexpr StringTableInts(int previous)
: index(previous), tail(previous + N) {}
constexpr const int *intptr() const { return &index; }
};
template <> struct StringTableInts<>
{
int index;
constexpr StringTableInts(int) : index(-1) {}
};
template <typename... Args> struct StringTable
{
StringTableInts<Args...> intdata;
StringTableStrings<Args...> stringdata;
constexpr StringTable(Args... args)
: intdata(0), stringdata(args...) {}
int offset(int i) const
{ return intdata.intptr()[i]; }
const char *operator[](int i) const
{ return stringdata.charptr() + offset(i); }
};
template<typename... Args> constexpr
StringTable<Args...> createStringTable(Args &... args)
{
return StringTable<Args...>(args...);
}
Analysis
The first thing to point out is that the first 25 lines are the same as in the previous blog about C++0x array initialisation. I won’t explain what the code there does, so please refer to the previous blog for explanation.
The next class in this code is called StringTableStrings (lines 27-44). It is a variadic template class and the template arguments are supposed to be the char arrays. This is enforced by both partial template specialisations: the only possibility for the template type is a const char [N].
Note how this class is created as a chain of structures. We use the partial template specialisation to extract the first type out of the variadic template list — that is, from typename... Args to typename Head, typename... Tail — as well as constrain the first type to the only type we accept. I believe this is how most (if not all) implementations of the C++0x standard type std::tuple are done. In fact, if std::tuple<const char [6]> initialised properly, I’d use it.
The second partial template specialisation is used for the last element in the chain. The reason I simply didn’t write the specialisation for the empty list is 1 byte: if I had done that, the last element would still have a member of type StringTableStrings<>, which the standard requires to have a size of at least 1.
The next class is StringTableInts which is very similar in construction to StringTableStrings. However, instead of having as its payload member a char array, it has a single int. Note how the constructor is accomplished (lines 52-53):
constexpr StringTableInts(int previous)
: index(previous), tail(previous + N) {}
When we chain this constructor with itself, it will pass to the next level the sum of the sizes of each char array. The sum of the sizes of all previous strings is the offset of the next entry in the table. This creates our string table for us.
Unlike the previous class, this one uses the full specialisation to the empty list for the variadic template arguments. The empty list is used after the last entry to insert an offset of -1 (see line 60).
The main class in this example is StringTable (lines 63-74). This one is also variadic template class, but it is not implemented without template specialisations. Its two members are the integer table and the char array table. Its constructor (lines 67-68) initialises the integer table chaining with the value 0. It then defines two member functions:
int offset(int i) const
{ return intdata.intptr()[i]; }
const char *operator[](int i) const
{ return stringdata.charptr() + offset(i); }
The first one (offset) is actually a helper function to the second: it returns the offset for entry with index i. It does that by getting the address of the first integer and treating that as an array of integers.
The reason why the chaining of StringTableInts and StringTableStrings works as expected (or so I hope) is because both classes have standard layout, which is one of the two C++0x's deconstructions of C++98 POD definition. The other would be trivially-constructible, which these classes aren't. They do, however, have constexpr constructors, which will allow them to be in the .rodata section with GCC 4.7.
Finally, we have a template function called createStringTable declared on lines 76-80. All it does is return a StringTable<Args...> object with the same arguments that are passed to it. The reason it's there is so the compiler can guess the types from the arguments, without our having to spell them out in our code.
On line 77, the & is the reason why my code now works: without it, at least GCC expands the template arguments to the function as <const char*, const char *>, which won't work. With the ampersand, everything works great.
Further work
Also note an interesting thing: with this code, it's possible to have string tables not only of char, but trivially with other character types (char16_t, char32_t, wchar_t) as well as more complex types like QConstStringData<N>. That work is left as an exercise to the reader.
