Variable length structures

Assume that we want to define a uint_vector type, where:

• The length of different uint_vector instances can be different.
• The length of a particular uint_vector instance is fixed once it is created.

One possible approach is to use a variable length structure. Such a structure has its last field as an array, which (by playing tricks with malloc) can be of some creation-time defined length

	typedef struct uint_vector * uint_vector;

	struct uint_vector {
	  int		uiv_len;
	  unsigned	uiv_vecs[1];
	};

	#define deref_uint_vector(_v)	(_v)
	#define x_len_uint_vector(_v)	(deref_uint_vector(_v)->uiv_len)
	#define x_vecs_uint_vector(_v)	(deref_uint_vector(_v)->uiv_vec)
	#define x_vec_uint_vector(_v, _i) \
		(x_vecs_uint_vector(_v)[bounds(_i, x_len_uint_vector(_v))])

	uint_vector
	make_uint_vector(
		int	len
		)
	{
	  uint_vector	v = malloc( sizeof(struct uint_vector) +
				(len-1)*sizeof(unsigned) );
	  x_len_uint_vector(v) = len;
	  return v;
	}

Note the use of bounds() in x_vec_uint_vector(); it ensures that we never fall off the bottom of our variable length structure.

Using this code, the memory layout of some uint_vectors will be:

make_uint_vector(2)	make_uint_vector(3)
	_________		_________
	|   2   |		|   3   |
	|_______|		|_______|
	|       |		|       |
	|_______|		|_______|
	|       |		|       |
	|_______|		|_______|
				|       |
				|_______|

To manipulate the elements of the uint_vector, we define macro/functions get_uint_vector() and set_uint_vector().

	/* in header */
	unsigned (get_uint_vector)(const uint_vector, int i);
	unsigned (set_uint_vector)(uint_vector, int i, unsigned val);

	/* in implementation  header */
	#define get_uint_vector(_v,_i) \
		((void)0, x_vec_uint_vector(_v, _i))
	#define set_uint_vector(_v,_i,_n) \
		(x_vec_uint_vector(_v, _i) = (_n))

	/* in implementation */
	unsigned
	(get_uint_vector)(
		const uint_vector	vec,
		int			i
		)
	{
	  return get_uint_vector(vec, i);
	}

	unsigned
	(set_uint_vector)(
		uint_vector	vec,
		int		i,
		unsigned	val
		)
	{
	  return set_uint_vector(vec, i, val);
	}

This is a somewhat common idiom. To support it, we define two macros.

	#define xvalloc(_t1, _t2, _n) \
			((_t1*)malloc(sizeof(_t1) + ((_n)-1)*sizeof(_t2)))
	#define xvfree(_t1, _t2, _n, _p) \
			free(_p)

Using these macros we can rewrite make_uint_vector() as:

	uint_vector
	make_uint_vector(
		int	len
		)
	{
	  uint_vector	v = xvalloc(struct uint_vector, unsigned, len);
	  x_len_uint_vector(v) = len;
	  return v;
	}

Warning: Variable length structures are not ANSI compliant, and should be used cautiously. However, I have not come across a system where this will fail.

It is also possible to have a variable length structure with two variable length arrays, one at the bottom, and the other at the top. However, the accessor macros become a lot trickier.