CODEWITHSUNDEEP
c
username_4567
username_4567

Reputation: 4913

Array of structure with struct hack

Suppose I have structure in C like this

struct A {  
int len;  
char s[1];  
}

I want to have an array of above structure but char s[1] member of struct A can be of variable length. How can we do this? Even struct hack trick in C99 doesn't seem to work here. One solution is to have char * as a last member and do dynamic memory allocation, but I want all data of struct to be in contiguous locations as my implementation needs to be cache oblivious.

Upvotes: 1

Views: 423

Answers (3)

Tony Delroy
Tony Delroy

Reputation: 106226

In C, array indexing involves multiplying the base address by the compile-time-constant size of an individual element. For that reason, you can't use inbuilt array support directly with the "struct hack", as each s element will be allocated exactly the 1 byte you request, and indices further past the struct will access following S elements in the array (or go off the end completely, possibly crashing).

If you really need contiguous data for cache-access speed, you can pack it yourself, you can solve this (like most things) with an indirection... have a contiguous array of S*, and manually pack your data into another contiguous buffer (malloc() or stack-allocate enough memory for all your S objects including the real data size of all s[] members). Your performance may suffer (or your OS crash) if the int len elements aren't optimally (properly) aligned for your architecture, so you may need to manually pad between S instances.

S* index[100]               char data[10000];
(S*)(data)  --------------> S with 14-byte s[] using data[0]..[17]
(S*)(data + 20) -----\      2 byte padding so next S is 4-byte aligned
(S*)(data + 32) --\   \---> S with 7-byte s[] using data[20]..[30]
                   \        1 byte padding...
                    \-----> ...

Unfortunately, this is quite an inflexible data layout - you can't just grow the amount of data in an element's s member without schuffling all the other data out of the way and patching the index, but that's normal for arrays so if you were already considering using them then perhaps this will suit you. Another hassle is calculating the total size of S structs (including s[] and any padding) up front....

Upvotes: 1

Jonathan Leffler
Jonathan Leffler

Reputation: 754640

You can't have an array of variable size objects, so you can't have an array of structures using the struct hack. All the objects in an array must be the same size. And if they're all the same size, the size must be implied by the structure, so you won't be using the struct hack after all; there'll be a size other than 1 in the dimension of the array s in your structure (unless 1 is big enough for everything). The reason is that the storage location for a[i] (where a is the name of an array and i is an index into the array) must be computable as 'byte address of a plus (i times size of one object in array)'. So the size of the objects in the array (in this case, structures) must be known and fixed.

As an alternative, you can have an array of pointers to variable size objects; you simply have to arrange to allocate each object separately with the appropriate size, and save the pointer to that in the array.

Note that C99 does away with the 'struct hack' (which was never officially portable, though in practice it was) and introduces 'flexible array members' instead:

struct A {  
    int  len;  
    char data[];  
};

However, the advice above still applies.

Upvotes: 5

John3136
John3136

Reputation: 29266

If there is a maximum size for "s", you could use that instead of [1]. That keeps everything contiguous.

If you really don't want to use dynamic memory, then you can't do it with an array. You need your own "manager" that will use the struct hack trick on each member individually - but that means you can't do indexed lookups - you have to look at each element to see how big it is and jump the right number of bytes to the next element.

Upvotes: 1

Related Questions