low-level sub-allocation/alignment challenge

From: David Abrahams (abrahams_at_[hidden])
Date: 2000-08-23 23:09:30

Hi,

I'm trying to solve a seemingly simple problem that's turning out to be
harder than it looks. I'm hoping someone out there has the expertise to
help.

The goal is to portably sub-allocate a POD struct from larger blocks
obtained from malloc() without wasting space or invoking undefined behavior.
The POD struct ends with a variable-length array. Here is an example of what
the struct looks like:

struct Rule
{
    unsigned long cost;
    const void* action;
    const char* symbols[1]; // actually a variable-length array
};

I think I know how to calculate the amount of room needed to accomodate any
number of symbols in a Rule:
   offsetof(Rule, symbols) + n * sizeof(const char*)
ought to do the trick. The greater challenge is to figure out how many bytes
of padding (if any) are needed between the first Rule allocated and the next
one. The problem is that the byte following the last symbol in one Rule may
not be aligned properly for the next Rule. I realize that on most machines,
sizeof(unsigned long) == sizeof(void*) == sizeof(char*), so there will be no
problem, but remember I want a *portable* solution.

If you can solve that problem, it would be great to know (for curiosity's
sake, mostly) how to perfom the same trick when Rule is not strictly a
POD...

Thanks in advance,
Dave