Trailing Array Idiom

Question

What is Trailing Array Idiom ?

P.S : Googling this term gives The vectors are implemented using the trailing array idiom, thus they are not resizeable without changing the address of the vector object itself.

As others have commented on some answers below, you'd have better luck searching for _flexible array member_. — ninjalj, Nov 20 '10 at 12:25
Note that, by strict definition, this invokes _UB_: http://stackoverflow.com/questions/3711233/is-the-struct-hack-technically-undefined-behavior — sbi, Nov 20 '10 at 15:57

Fred Foo · Accepted Answer · 2010-11-20T09:33:54.150

10

If you mean the trailing array idiom mentioned in the GCC source code (where your quote comes from), it seems to refer to the old C trick to implement a dynamic array:

typedef struct {
    /* header */
    size_t nelems;

    /* actual array */
    int a[1];
} IntVector;

where an array would be created with

IntVector *make_intvector(size_t n)
{
    IntVector *v = malloc(sizeof(IntVector) + sizeof(int) * (n-1));
    if (v != NULL)
        v->nelems = n;
    return v;
}

edited Nov 20 '10 at 09:33

answered Nov 20 '10 at 09:25

Fred Foo

355,277
75
744
836

3

If it is referring to that, the more common term is the [struct hack](http://stackoverflow.com/q/3711233/168225). – Georg Fritzsche Nov 20 '10 at 09:32
@Georg: I dont think(although I am not sure) it is referring to that otherwise the term (as you've mentioned) `struct hack` would have been used in place of `Trailing array idiom`. – Prasoon Saurav Nov 20 '10 at 09:38
@Prasoon: The author might have just used a different term, would not be the first time someone did that. "Struct hack" sounds a bit informal anyway. – Georg Fritzsche Nov 20 '10 at 09:43
@Prasoon, this comment gives it away: "This means you cannot have variables or fields of vector type -- always use a pointer to a vector. The one exception is the final field of a structure, which could be a vector type." I admit I've never heard it being called "trailing array idiom" either, but it makes some sense. – Fred Foo Nov 20 '10 at 09:48
@larsmans : Yes it does make sense. Accepted your answer. `:)` – Prasoon Saurav Nov 20 '10 at 09:50
1

@Georg Fritzsche: Ironically, the term "struct hack" appears in the standard. – aib Nov 20 '10 at 10:18
@aib only in the index to point to the standard terminology: 'struct hack, *see* flexible array member' – Pete Kirkham Nov 20 '10 at 10:37
Am I the only one to find this "flexibility" extremely disconcerting. This gently violates any use of `sizeof`... – Matthieu M. Nov 20 '10 at 14:58
@Matthieu M.: like it or not, this is quite a common idiom in C (with at least three different names). I've seen it in operating system code, in libraries and now in GCC. – Fred Foo Nov 20 '10 at 23:35

score 1 · Answer 2 · answered Nov 20 '10 at 09:24

It seems to refer to arrays in structs, which may have a variable array-size. See:

http://blogs.msdn.com/b/oldnewthing/archive/2004/08/26/220873.aspx and http://sourceware.org/gdb/current/onlinedocs/gdbint/Support-Libraries.html

Another tip, if you google for an expression put the expression in "" like "trailing array" this will give you more specific results. Google knows about trailing arrays.

score 1 · Answer 3 · answered Nov 20 '10 at 09:29

I think what is meant is:

struct foo {
  ... some data members, maybe the length of bar ...
  char bar[]; /* last member of foo, char is just an example */
};

It is used by allocating with malloc(sizeof(struct foo)+LEN), where LEN is the desired length of bar. This way only one malloc is needed. The [] can only be used with the last struct member.

And, as fas as I understand the GCC doc, struct foo can also only be (reasonably) used as last member of another struct, because the storage size is not fixed -- or as pointer.

This is called a "flexible array member" and is in the C99 standard (§6.7.2.1P16). — aib, Nov 20 '10 at 10:25

Trailing Array Idiom

3 Answers3