Generic Containers in C: span

Martin Uecker, 2025-07-02


I will discuss generic containers in C. For similar ideas, see here and here.

A span type combines a pointer to an array with a length.

	static void sumup(span(int) my_span)
	{
	  int sum = 0;

	  for (int i  = 0; i < my_span.N; i++)
	    sum += span_access(int, &my_span, i);

	  printf("sum %d\n", sum);
	}
	

In C, one could define a span type such as the following.

	#define span(T) struct span_##T { size_t N; T (*data)[/* .N */]; }
	

This is type safe but does not do any bounds checking, but we will come back to this later. One problem is that you can't use this type twice as C would then traditionally interpret this as two different structure types which are not compatible. So the following does not work.

	span(int) foo(span(int x));
	

The traditional way to use such types is to forward declare them exactly once.

	#define span_name(T) span_## T
	#define span_decl(T) struct span_name(T) { size_t N; T (*data)[/* .N */]; }
	#define span(T) struct span_name(T)

	span_decl(int);

	span(int) foo(span(int) x) { /*...*/ }
	

This works quite well but is a bit annoying in larger programs, as it requires a single common declaration to be used which all parts of the program need to agree on. In C23 we changed the rules so that you can redeclare such types in the same scope, and also made two types of the same form compatible (N3037). With the new rules, one can simply inline the definition and write the following.

	#define span(T) struct span_ ## T { size_t N; T (*data)[/* .N */]; }

	span(int) foo(span(int) x) { /*...*/ }
	

There is one limitation with this design, which is that T needs to be an identifier and can not be an arbitrary type name. For example, if you want to have span into an array of pointers to C strings, one can not simply write the following.

	span(char *) my_span;
	

Instead, you have to first define a typedef name for such pointer.

	typedef const char *strp_t;
	span(strp_t) my_span
	

This is admittingly a bit annoying, and maybe we will fix this... On the other hand, it is also not that too terrible in practice, as the typedef is often desirable anyway. One can also redeclare typedef names where they are needed, so this does not create the same annoying requirement for having to maintain a single common declaration which we had before C23. Still, one would have to use a common naming scheme when one wants these types to be compatible later.

Bounds Safety

Ideally, the type of the pointer would be T (*data)[.N] so that the array (*data) has a known length. Ada and many other languages have such types. They are not exotic.

Until we get something like this in C, we can work around this by using an access macro that adds the length back to the array type.

	#define span2array(T, x) (*({ span(T) *_x = (x); (T(*)[_x->N])_x->data; }))
	

The code may look complicated at first glance, but it just casts the type of the data pointer to a pointer to an array with the right bound. Statement expressions are a common language extension, and are used here to avoid double evaluation of the argument (returning variably modified types required fixing some compilers bugs). I also apply the indirection operator to the result to make the result type be an array instead of a pointer to it, which I find a bit more convenient. In the following example you can see how it interoperates with a vector type and traditional (variable-length) C arrays (Godbolt link).

	static int array_sum(int N, int (*arr_ptr)[N])
	{
	  return N ? (*arr_ptr)[0] + array_sum(N - 1, &array_slice(*arr_ptr, 1, N)) : 0;
	}

	static int process(span(int) my_span)
	{
	  for (int i = 0; i < my_span.N; i++)
	    span_access(int, &my_span, i) *= 2;

	  auto arr_ptr = &span2array(int, &my_span);

	  return array_sum(_Countof *arr_ptr, arr_ptr);
	}

	int main()
	{
	  vec(int) *vec_ptr = vec_alloc(int);

	  for (int i = 0; i < 10; i++)
	    vec_push(int, &vec_ptr, i);

	  int sum = process(vec2span(int, vec_ptr));

	  printf("sum: %d\n", sum);

	  free(vec_ptr);
	}
	

The code is type safe and (with -fsanitize=bounds) also bounds safe, as long as you do not manipulate the members of the span type directly.

If you want, you can check out my experimental library where I am experimenting with these ideas: link. If you have ideas on how to do this better, let me know!