Generic Data Structures in C
See here for a final implementation if you don’t want to read all this.
Generic data structures in C typically have a pretty unfriendly API. They either rely on void pointers and erase type information, or resort to macros to provide a semblance of the templating system found in C++.
This post will look at constructing a macro-based vector in C with a focus on ease of use. We will use modern C11 features and ample compiler extensions to see where we can take this.
A Generic Vector
First, lets define our vector type. We’ll call it qvec because its
short and sweet.
#define qvec(T) \
struct qvec_##T { \
size_t cap, len; \
T data[]; \
}
We take a parameter T which will represent the type that is stored in our
vector. This will be templatized at compile-time, similar to how vector<T> is
in C++.
The data field is a flexible array
member
from C99.
Note: We will forgo error checking of malloc and realloc
for simplicity.
new
The new function should malloc enough memory for some initial members.
The size of the required storage will depend on the size of T. A possible
implementation could be
#define qvec_new(T, v) \
do { \
size_t initial_size = 16; \
v = malloc(sizeof(qvec(T)) + sizeof(T) * initial_size); \
v->cap = initial_size; \
v->len = 0; \
} while (0)
which we can use to initialize a vector of integers as
qvec(int) *v;
qvec_new(int, v);
The flexible array member allows us to get away with a single call to malloc
which is a minor nicety. Otherwise, this is a little underwhelming. The
separation of declaration and initialization is not ideal.
To make this a bit nicer, we can use statement expressions
which allow multiple statements to be evaluated and used as if they were an
expression. Our new definition for new would then be
#define qvec_new(T) \
({ \
const size_t initial_size = 16; \
struct qvec_##T *v = malloc(sizeof(qvec(T)) + sizeof(T) * initial_size); \
v->cap = initial_size; \
v->len = 0; \
v; \
})
which gives us the much more natural usage
qvec(int) *v = qvec_new(int);
Standard Functions
Lets now implement the common vector functions push, pop and at.
pop
pop doesn’t require any special knowledge of the type T so this is simply
#define qvec_pop(v) (v->data[--v->len])
at
at is slightly more interesting. When working with a C++ vector (or a
standard C array), the notation array[x] is an lvalue which can be
assigned to. It would be nice if our qvec has this property as well.
First, lets define the helper function
#define qvec_ref(v, i) (&v->data[i])
This returns an lvalue and so can be used with a pointer dereference. e.g.
*qvec_ref(v, i) = 5.
We can wrap this in another macro to hide this dereference
#define qvec_at(v, i) (*(qvec_ref(v, i)))
push
push presents a small problem. If we were to generate a standard
implementation
#define qvec_push(v, i) \
({ \
if (v->len >= v->cap) { \
v->cap *= 2; \
v = realloc(v, sizeof(?) + v->cap * sizeof(?)); \
} \
v->data[v->len++] = (i); \
})
we might be left wondering what to insert into the ? marked locations.
The second ? is less worrying. This should be sizeof(T). We could just pass
the type again, but doing it on every push is not ideal. In fact, we don’t need
any new information. Recall that the data field of qvec is of type T[].
Performing a dereference of this will give us the size of a single T, exactly
what we want!
The first ? is more bothersome. We are interested in determining the value of
sizeof(qvec(T)). We can’t use the data field here, since the T required
here is the actual typename used during initialization. This would be viable if
it were possible to generate a type name from an arbitrary variable but
unfortunately we cannot do this.
The way to get this size is first to realise that the data member in a qvec
doesn’t actually take up any space within the array, not even for a pointer.
We can confirm this by checking the following
struct {
char a, b;
char b[]
} foo;
printf("foo is %zu bytes\n", sizeof(foo));
which will print
foo is 2 bytes
Since this data doesn’t take any space, we can see that the other members
(len and cap) have a fixed type and therefore size, regardless of the type
of T.
We can separate the type of qvec into
#define qvec_base \
struct { \
size_t cap, len;\
}
#define qvec(T) \
struct qvec_##T { \
qvec_base; \
T data[]; \
}
This now allows us to query the size of the type-independent part of a qvec
while retaining access to all the members in the same way.
As an aside, we can define this using less macro-wizardry if we enable the
-fplan9-extensions option in GCC as documented here.
struct qvec_base {
size_t cap, len;
}
#define qvec(T) \
struct qvec_##T { \
struct qvec_base; \
T data[]; \
}
This allows embedding of existing struct definitions as an anonymous struct.
Now, finally, we can define our push function as:
#define qvec_push(v, i) \
({ \
if (v->len >= v->cap) { \
v->cap *= 2; \
v = realloc(v, sizeof(qvec_base) + v->cap * sizeof(*v->data)); \
} \
v->data[v->len++] = (i); \
})
free
Since we only use a single malloc to initialize the type, this is simply
#define qvec_free(v) free(v)
API so far
Lets see what this gives us so far
qvec(int) *iv = qvec_new(int);
qvec_push(iv, 5);
qvec_push(iv, 8);
printf("%d\n", qvec_at(iv, 0));
qvec_at(iv, 1) = 5;
qvec_free(iv);
and compared similar C++ vector usage
std::vector<int> iv;
iv.push_back(5);
iv.push_back(8);
printf("%d\n", iv[0]);
iv[1] = 5;
Looking okay, but lets go a bit further.
Extended Functions
Generic Printing
It is fairly common that we want to dump the values of a vector to see what is inside. If we wanted to write this for an integer vector, the following would work
#define qvec_int_print(v) \
({ \
printf("["); \
for (int i = 0; i < v->len; ++i) { \
printf("%d", v->data[i]); \
if (i + 1 < v->len) \
printf(", "); \
} \
printf("]\n"); \
})
which can be used as
qvec_print(iv); // [5, 5]
This is nice, but since it isn’t generic it has a limited use case. Fortunately for us, C11 brings some new interesting features to the table which we can use.
The C11 _Generic keyword allows rudimentary switching based on the type of
its input. Think of it just as a compile-time switch statement on types.
For example, we could construct a macro to print the name of a type
#define type_name(x) _Generic((x), int: "int", float: "float")
printf("This is a %s\n", type_name(5.0f));
printf("This is a %s\n", type_name(5));
which when run would output
This is a float
This is a int
We can use this to generate the appropriate printf format specifier for the
passed type.
#define GET_FMT_SPEC(x) _Generic((x), int: "%d", float: "%f", char*: "%s")
and modifying our print function
#define qvec_print(v) \
({ \
printf("["); \
for (int i = 0; i < v->len; ++i) { \
printf(GET_FMT_SPEC(v->data[i]), v->data[i]);\
if (i + 1 < v->len) \
printf(", "); \
} \
printf("]\n"); \
})
This would now work on an integer and float qvec type with no modifications.
Of course, we could extend GET_FMT_SPEC with whatever types we need.
You may recall that I mentioned that we could solve an earlier issue regarding
our push function if we could generate a type name from a variable. It seems
like the _Generic keyword would help is achieve this and indeed it does in
part. The problem is that it is evaluated after preprocessing, so we cannot use
its output as part of the preprocessor token concatenation process.
This is an easy mistake to make, since _Generic is seen pretty much solely
within macro definitions for obvious reasons. This isn’t required though,
the following being perfectly valid code.
int a;
float b;
printf("%s\n", _Generic(a, int: "a is an int", float: "a is a float"));
printf("%s\n", _Generic(b, int: "b is an int", float: "b is a float"));
Initializer Lists
Since C++11, vectors can now be initialized with initializer lists
std::vector<int> = {4, 5, 2, 3};
This is pretty nice. Let’s add something similar to our new function using
C99 variadic macros with a GCC extension
which allows an arbitrary name to be given for them.
#define QVEC_ALEN(a) (sizeof(a) / sizeof(*a))
#define qvec_new(T, xs...) \
({ \
const size_t initial_size = 16; \
const T _xs[] = {xs}; \
struct qvec_##T *v = malloc(sizeof(qvec(T)) + sizeof(T) * QVEC_ALEN(_xs));\
v->cap = initial_size; \
v->len = QVEC_ALEN(_xs); \
for (int i = 0; i < v->len; ++i) \
v->data[i] = _xs[i]; \
v; \
})
xs here collects all arguments except the first. We assign these to a
temporary array which allows us to work with the values, but also has the effect
of typechecking the values.
qvec(int) *v = qvec_new(int, 4, 5, 2, 3);
Complex Objects
Suppose we have the following type
typedef struct {
char *id;
bool is_tasty;
} Food;
We might try and utilize C99 struct initializers to perform the following
qvec(Food) *v = qvec_new(Food);
qvec_push(v, { .id = "apple", .is_tasty = true });
This however fails to compile. Under clang, we get the following error
qvec.c:103:34: error: too many arguments provided to function-like macro
invocation
qvec_push(v, { "apple", 1 });
^
qvec.c:42:9: note: macro 'qvec_push' defined here
#define qvec_push(v, i) \
^
qvec.c:103:5: note: cannot use initializer list at the beginning of a macro
argument
qvec_push(v, { "apple", 1 });
^ ~~~~~~~~~~~~~~~~~~~~
qvec.c:103:5: error: use of undeclared identifier 'qvec_push'
qvec_push(v, { "apple", 1 });
^
The reason this doesn’t work is that the C preprocessor is dumb. It doesn’t know
that this is a designated initializer because it doesn’t actually know anything
about the C language. Instead, it sees two arguments. The first being
{ .id = "apple" and the second .is_tasty = true }.
The can get around this is by using the previously mentioned variadic macros once
again. Using a similar technique to the previously extended new function.
#define qvec_push(v, xs...) \
({ \
const typeof(*v->data) _xs[] = {xs}; \
if (v->len + QVEC_ALEN(_xs) >= v->cap) { \
while (v->cap <= v->len + alen(_xs)) { \
v->cap = 2 * v->cap; \
} \
v = realloc(v, sizeof(qvec_base) + v->cap * sizeof(*v->data)); \
} \
for (int i = 0; i < QVEC_ALEN(_xs); ++i) { \
v->data[v->len++] = _xs[i]; \
} \
v; \
})
The reason variadic macros help here is that all macro arguments are gathered at once and treated as input to an array initializer. Even though individual arguments are not valid tokens, it doesn’t matter, since the full set of argments is.
Another thing to note is the use of the
typeof keyword. This
allows us to retrieve the type of an expression, which can be used to initialize
new types. The most common example of its usage is likely within a type-generic
swap macro.
#define swap(x, y) \
do { \
const typeof(x) _temp = y; \
y = x; \
x = _temp; \
} while (0)
Extensions, Extensions, Extensions
Our code is already filled with compiler-specific C extensions, so we may as well go overboard.
RAII
One of the better features of C++ is the ability to utilize RAII to run destructors on block exit. This reduces the chance that leaks occur within programs and just makes using complex types much more pleasant.
The
cleanup
variable attribute is a GCC extension which allows a user-defined cleanup
function to automatically run when the value goes out of scope.
This attribute takes one argument, a function of type void cleanup(T**) where
T is the type which this attribute is declared with.
Using this with our qvec, it may look like
static inline _qvec_free(void **qvec) { free(*qvec); }
int main(void)
{
qvec(int) __attribute__ ((cleanup(_qvec_free))) *qv = qvec_new(int);
// No qvec_free here!
}
This is a little verbose however, so lets define our own keyword which we can use instead.
#define raii __attribute__ ((cleanup(_qvec_free)))
int main(void)
{
raii qvec(int) *qv = qvec_new(int);
}
Note that an attribute doesn’t strictly need to be specified after the type definition.
This is nice, but if you had actually compiled the above you would get a number of type errors.
qvec.c: In function ‘main’:
qvec.c:13:12: warning: passing argument 1 of ‘_qvec_free’ from incompatible pointer type [-Wincompatible-pointer-types]
struct { \
^
qvec.c:26:40: note: in expansion of macro ‘qvec_base’
struct qvec_##T *v = malloc(sizeof(qvec_base) + sizeof(_xs)); \
^
qvec.c:94:25: note: in expansion of macro ‘qvec_new’
raii qvec(int) *v = qvec_new(int);
^
qvec.c:88:20: note: expected ‘void **’ but argument is of type ‘struct qvec_int **’
static inline void _qvec_free(void **qvec) { free(*qvec); }
The compiler complains because we are relying on an implicit cast to void. We
know this is actually valid however, since every qvec is going to use a
single call to free in order to release its memory.
As far as I’m aware, this requires a pragma at the callsite to disable this locally. This is quite inconvenient, and really loses out any usability that we may have gained from using this. The following will compile without warnings
int main(void)
{
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
raii qvec(int) *v = qvec_new(int, 5, 4, 3);
#pragma GCC diagnotic pop
}
At this stage though, remembering to just manually free seems like a saner choice.
Type Inference
One of the nice features of C++11 onwards is the revitalization of the auto
keyword. This now provides type inference which is very nice in a number of
circumstances.
If we look at our vector initialization
qvec(int) *v = qvec_new(int);
we clearly have a bit of redundancy. Unfortunately the C language doesn’t support
type inference… as part of the standard at least. An interesting extension is
the _auto_type keyword which
provides some limited type inference capabilities.
Since the auto keyword is practically useless, lets just redefine it
Redefining keywords is usually a very bad idea. Although, GCC will allow it.
#define auto __auto_type
auto iv = qvec_new(int);
Although yet again, our expectations differ to reality. This will not compile!
The reason for this is that previously we were relying on the inline struct
definition of qvec(T) that was declared on every initialization. Without this
declaration, our new auto keyword cannot find any struct which matches the
return type and must fail.
As an example, the following works fine
qvec(int) *a = qvec_new(int);
auto b = qvec_new(int);
because the qvec(int) declared the struct, so the next qvec return type can
be deduced correctly. This is simply an inherent limitation with the tools we
have. A simple solution would be simply forward declare our structs.
qvec(int);
int main(void)
{
auto a = qvec_new(int); // Ok!
}
But this is one extra line to type for each qvec type required!
Drawbacks
We have a pretty good set of functions associated with our qvec so far.
Usability is ok and we have a few of the more desirable features of C++ in our
hands within C.
Undoubtedly however, there are some inherent problems that we just can’t solve.
Complex Container Types
We can do the following in C++
std::vector<std::vector<std::vector<int>>> v;
To do this with our qvec the following is required
typedef qvec(int) qvec_int;
typedef qvec(qvec_int) qvec_qvec_int;
qvec(qvec_qvec_int) *v = qvec_new(qvec_qvec_int);
Recall back to our new implementation. We generate a struct with a name
qvec_##T where T is the type. Since this is concatenated to make an
identifier, the types must be comprised only of characters which can exist
within an identifier ([_0-9A-Za-z]). Any types which use other characters,
such as functions, pointers and even our own qvec types must have a typedef
before we can use them.
As an example, the following
qvec(char**);
expands to the invalid struct declaration
struct qvec_char** {
size_t cap, len;
char* data[];
};
Too Much Inlining
Since we are dealing with macros, every call is going to generate the same code
at the call site. This isn’t too big a deal with our qvec, since a vector is
inherently pretty simple, but if we wanted to use the same techniques to
construct a generic hashmap, for example, the code duplication would be much
worse.
This is where the generic containers which rely on simply generating the required functions for each type (see khash) definitely have the upper hand.
These approaches however do lose out a bit in terms of the expressiveness of the resulting API (which is our main focus here).
Which Names are Which?
Say we wanted to do the following contrived thing
void print(qvec(int) *v)
{
qvec_print(v);
}
int main(void)
{
qvec(int) *v = qvec_new(int, 1, 2, 3);
print(v);
}
This will spew our a mess of errors about anonymous structs. The reason being is
that the qvec(int) in the print parameter list is declaring a new anonymous
struct, and the two qvec(int) declarations are completely different
structures.
This can be worked around by doing a typedef at the start of your file and using this, but again at the cost of extra work for the programmer.
How about the following example. Will this qvec_new be aware of the type being
used within the Foo struct?
struct Foo {
qvec(int) *values;
};
void foo_init(Foo *v)
{
v->value = qvec_new(int);
}
int main(void)
{
struct Foo f;
foo_init(&f);
}
This in fact will work potentially to some surprise. Even though this does, it still highlights a pretty important problem. Even though the API is nice and appears easy to use, there are a number of naming issues that the user must be aware of, which greatly limits its usage as a just works type of structure.
A Final Look
#include "qvec.h"
typedef char* string;
typedef struct {
int x, y;
} Tuple;
int main(void)
{
qvec(string) *sv = qvec_new(string, "Who", "are", "you?");
qvec_print(sv);
qvec_at(sv, 2) = "we?";
qvec_print(sv);
qvec_free(sv);
qvec(int) *iv = qvec_new(int, 1, 2, 3, 4);
qvec_print(iv);
printf("%d\n", qvec_pop(iv));
qvec_free(iv);
qvec(Tuple) *tv = qvec_new(Tuple, { .x = 0, .y = 1 }, { 4, 2 }, { 5, 4 });
printf("%d\n", qvec_at(tv, 1).x);
printf("%d\n", qvec_at(tv, 2).x);
qvec_free(tv);
}
So would I recommend using this? Probably not. If you were insistent on
sticking with C however I think the best compromise would be to generate the
specific instantiations (similar to what khash
does). This gets rid of most of the problems specified here. Alternatively,
if performance and the type-safety isn’t a big deal, then a tried and tested
void* implementation would be good too.
At the end of the day though, the pragmatic solution would be to just use C++ if there are no reasons not to and call it a day. Especially if you are considering performing these types of C macro chicanery.