C Struct Hack

This tip introduces struct hack and compares it with several implementation alternatives. A typical C struct hack is a struct whose last element is an array of size one.

struct Foo
{
  //..
  size_t size;
  // Better to use char array to be more portable, as discussed in comments.
  int data[1];
};

const size_t SIZE = 100;
Foo *p = (Foo*) malloc(sizeof(Foo) + sizeof(int) * (SIZE - 1));
p->size = SIZE;
for (int i = 0; i < p->size; ++i) p->data[i] = i;

The trick is to allocate more memory than sizeof (Foo), and make a Foo* point to it. The memory allocated is filled with a Foo object at the beginning, followed by an array of “dynamic” number of integers. You just reference the out-of-bounds part of the array such that you stay inside the memory actually allocated. That is, you can visit p->data[0] as well as p->data[1] and so on up until you hit the end of the memory you allocated. That said, you implement a flexible array member in C.

Why Not Use a Pointer?

struct Foo
{
  // ..
  size_t size;
  // data = (int*)malloc(sizeof(int) * 10);
  int *data;
};

The advantage of using an array is that you don’t have to allocate the memory elsewhere and make the pointer point to that. Thus there is no extra memory management. Furthermore, accesses to the memory will hit the memory cache (much) more likely because dynamically allocated block is contiguous.

What About an Array of Size Zero?

You can't. Defining an array of constant size zero is illegal.

struct Foo
{
  // ..
  size_t size;
  // Error: cannot allocate an array of constant size zero
  char data[0];
};

What About an int?

Yes, you can. But then you have to write more complex expression to access array elements. p->data[i] is more convenient and readable than (&p->data)[i], isn’t it?

struct Foo
{
  size_t size;
  int data;
};

// 1. operator-> has a higher precedence than operator&
// 2. it's illegal to say "p->data[i]" because array subscript
// operator[] can only be used with a pointer among all other
// build-in types. User-defined type can overload this operator
// though.
for (int i = 0; i < p->size; ++i) ((&p->data)[i]) = i;

Flexible Array Member

C99 has a new language feature called “flexible array member”. It’s quite similar to the struct hack except an empty bracket [].

struct Foo
{
  size_t size;
  int data[]; // FLA
};