Strange variable array declaration

Question

Reading the implementation of this skip list I came across this piece of code:

typedef struct nodeStructure{ keyType key; valueType value; node forward[1]; /* variable sized array of forward pointers */ }; 

It seems to me that forward[1] denotes an array of one element. And the comment calls it a variable-size array.

Am I misunderstanding something or is it just a mistake in the source I'm reading?

Answer 1

This is a common trick for older C compilers (prior to C99): the compilers allowed you to cast elements at the end of the forward declared length when this is the last element of the struct ; you could malloc get enough memory for additional node elements, for example:

 nodeStructure *ptr = malloc(sizeof(nodeStructure)+4*sizeof(node)); for (int i = 0 ; i != 5 ; i++) { // The fifth element is part of the struct ptr->forward[i] = ... } free(ptr); 

The trick allows you to embed arrays with a variable size in the structure without separate dynamic allocation. An alternative solution would be to declare node *forward , but then you would need malloc and free separately from nodeStructure , without having to double the number of malloc and potentially increase memory fragmentation:

Here is what this fragment would look like without hacking:

 typedef struct nodeStructure{ keyType key; valueType value; node *forward; }; nodeStructure *ptr = malloc(sizeof(nodeStructure)); ptr->forward = malloc(5*sizeof(node)); for (int i = 0 ; i != 5 ; i++) { ptr->forward[i] = ... } free(ptr->forward); free(ptr); 

EDIT (in response to Adam Rosenfield's comments): C99 allows you to define arrays without size, for example: node forward[]; This is called a flexible member of the array; it is defined in section 6.7.2.1.16 of the C99 standard.

Answer 2

It is called struct hack. This is an old form of flex element introduced in C99.

This has been used in the past to mimic an array of variables in the last member of a structure, but it is not a strictly conformal construction in C.

Answer 3

This is a programming paradigm in C that you will see sometimes. When distributing the structure, you will allocate sizeof (struct nodeStructure + numNodes * sizeof (node)).

This allows you to have several nodes forward for the structure, although it is only announced that it is. This is a bit ugly hack, but it works.

Usually, when you do this, the name "count" or something else will also be stored, so that you know how many additional entries are after the node.

Answer 4

The implementation of the data structure is most likely written against the C90 standard, in which there were no elements of the flexible array (added on C99). At that time, it was customary to use an array of 1 or even 0 size (*) at the end of the structure to allow access to a dynamically variable number of elements.

The comment should not be interpreted as a value of a variable length array in the style of C99; in addition, in C99, the idiomatic and standard-consistent definition for the forward member will be node forward[]; . A type of type struct nodeStructure with such an element is then called an incomplete type. You can define a pointer to it, but you cannot define a variable of this type or take its size, all operations that are allowed by node forward[0] or node forward[1] , although these operations may not correspond to the programmer's intention.

(*) 0-dimensional arrays are forbidden by the standard, but GCC accepted them as an extension for this particular use.