How to write generics in C

by

C is barebones and doesn’t “support” generics, but it’s actually quite easy to implement with the tools we already have. There are many ways you can find them in action in the wild. Some of these are common:

  • Using Function-Like Macros
#define vector_push(vector, item) vector.buf[vector.idx++] = item;

Con: This will make everything inline and loosely typed.

void vector_push(Vector vec, void *item);

Con: You rely on type erasure to get generics, so you have to recompile everything to access them. You can also run in UB.

  • Dispatch specializations via function-like macro
#define DECLARE_VECTOR(type) \
  void vector_push(Vector##_##type, type item) {\
    // do stuff here \
    }

DECLARE_VECTOR(int)

Con: Everything is wrapped in a macro and can be autocomplete

The approach I recommend is not really new, but it is the method I have found best to use and works better with existing tooling. Since it doesn’t depend on type erasure and not everything is wrapped in macros.

professional:

  • type safe
  • No need to use pointers
  • Minimal use of macros
  • Can be duplicated by linkers
  • It can be kept entirely in a single file to reduce changes that trigger compilation of multiple files.

Shortcoming:

  • depends on macro trick
  • can be a little talkative

Getting generics through header instantiation

The way it works is that you instantiate specialization for a type by defining its type and possibly a suffix if that type is not a valid name for an identifier. To do this, we have to rely on a little macro trick, but other than that, everything is pretty straightforward. The header instantiation should look like this:

#define VEC_ITEM_TYPE long long
#define VEC_SUFFIX num
#include "vector.h"

with VEC_SUFFIX To be optional.

Once instantiated it will give you a vector_push_num Functions that you can use. To do this we need to be able to engage _num For our symbol names. because we make one G Function like macro.

#define G(name) name##_##VEC_ITEM_TYPE

Except it doesn’t work. You can’t extend and combine them like this. We need to first expand the definitions and then combine them, so we will rely on the following trick:

#define __G(name, type) name##_##type
#define _G(name, type) __G(name, type)
#define G(name) _G(name, VEC_ITEM_TYPE)

it works now! Now we can wrap our identifier names into a G macro so that they are the name got spoiled For the type they are.
We can use it to define our functions and structures like this: struct G(something), void G(do_something)(),

Enforcing type definition and allowing custom suffixes

#ifndef VEC_ITEM_TYPE
  #error VEC_ITEM_TYPE was not defined
#endif

#ifndef VEC_SUFFIX
  #define VEC_SUFFIX VEC_ITEM_TYPE
#endif

Now we can generate an error if VEC_ITEM_TYPE And we know that if this header is compiled it means we have a VEC_ITEM_TYPE Defined.

This fixes the incorrect usage of headers but what if we want to use something like long long Or atomic intThis won’t work. So we need to introduce a way to programmatically override suffixes added to functions. So we will give an introduction VEC_SUFFIX,

#ifndef VEC_ITEM_TYPE
  #error VEC_ITEM_TYPE was not defined
#endif

#ifndef VEC_SUFFIX
  #define VEC_SUFFIX VEC_ITEM_TYPE
#endif

#define __G(name, type) name##_##type
#define _G(name, type) __G(name, type)
#define G(name) _G(name, VEC_SUFFIX)

We are now free to implement our library. For example, here is a common vec_pop execution:

bool G(vec_pop)(G(vec_Vector) *vec, VEC_ITEM_TYPE *dest) {
   if (!vec->vec || vec->len <= 0 || vec->capacity <= 0) {
      return false;
   }

   vec->len--;
   if (dest) {
      *dest = vec->vec[vec->len];
   }
   G(vec_fit)(vec);
   return true;
}

As you can see, every time we call something common we have to include it in G So that it can be made unique and named properly.

elephant in the room

redeclaration error

You can try and use this implementation, but unless you only have one C file and nothing else, you may eventually encounter a redeclaration error, especially if you are using this common library. .c And .h files.

One possible solution is to make everything static But then you’ll end up copying everything across multiple translation units in your program.

The real improvement is to be able to choose when to forward the declaration and when to use the implementation:

#ifndef VEC_IMPLEMENTATION
  bool G(vec_pop)(G(vec_Vector) *vec, VEC_ITEM_TYPE *dest);
#else
  bool G(vec_pop)(G(vec_Vector) *vec, VEC_ITEM_TYPE *dest) {
     if (!vec->vec || vec->len <= 0 || vec->capacity <= 0) {
        return false;
     }

     vec->len--;
     if (dest) {
        *dest = vec->vec[vec->len];
     }
     G(vec_fit)(vec);
     return true;
  }
#endif

Then you can only include the headers in the header files

// included like any other header
#define VEC_ITEM_TYPE int
#include "vector.h"
#include 
#include

And then on your C files you can specify that you need an immediate implementation

#define VEC_IMPLEMENTATION
#define VEC_ITEM_TYPE int
#include "vector.h"

Side note: If you include the header in another header, you can still call #define VEC_IMPLEMENTION Without recompiling the file to get the implementation. Which is a nice side effect of this method, but in the end it can seem a bit implicit because it’s hidden in something else involved. It’s up to you what you like.

Example:

#define VEC_IMPLEMENTATION
#include "flag.h"

Multiple includes hereditary types

Since we are relying on preprocessor definitions to define our types. if we do:

#define VEC_ITEM_TYPE int
#include "vector.h"
#include "vector.h"

We will have a redefinition error, because both contain View VEC_ITEM_TYPE As intWe can fix this by adding undefined at the end of our normal vector header:

#undef VEC_ITEM_TYPE
#undef VEC_SUFFIX

This way we still get the “undeclared VEC_ITEM_TYPE” error if we re-include the vector and forget to tell it what type of instantiation we want.

Note: We do not define VEC_IMPLEMENTATION So that we can declare it once in our .c For convenience.

include guard

You may be wondering about the missing guard, but you don’t need to! The reason for this is that we actually want to be able to include the same header multiple times. Every time for a different type.

put everything together

The final header will look something like this:

#ifndef VEC_ITEM_TYPE
   #error VEC_ITEM_TYPE was not defined
#endif

#ifndef VEC_SUFFIX
   #define VEC_SUFFIX VEC_ITEM_TYPE
#endif

#define __G(name, type) name##_##type
#define _G(name, type) __G(name, type)
#define G(name) _G(name, VEC_SUFFIX)

#include 
#include 
#include 
#include 
#include 
#include 

typedef struct G(vec_vector) {
   size_t capacity;
   size_t len;
   VEC_ITEM_TYPE *vec;
} G(vec_Vector);

#ifndef VEC_IMPLEMENTATION

G(vec_Vector) * G(vec_new)(void);
bool G(vec_push)(G(vec_Vector) *vec, VEC_ITEM_TYPE item);

#else

// Initializes a new vector with items of sizeof(T)
G(vec_Vector) * G(vec_new)(void) {
   G(vec_Vector) *vector = malloc(sizeof(*vector));
   if (!vector) {
      return NULL;
   }

   *vector = (G(vec_Vector)) {
      .capacity = 0,
      .len = 0,
      .vec = NULL,
   };

   return vector;
}

// Resizes vector to fit length
bool G(vec_fit)(G(vec_Vector) *vec) {
   const size_t power = ceilf(log2f(vec->len + 1));
   const size_t new_capacity = sizeof(vec->vec[0]) * powf(2, power);

   if (new_capacity < vec->capacity || new_capacity > vec->capacity) {
      void *tmp = realloc(vec->vec, new_capacity);
      if (!tmp) {
         return false;
      }
      vec->vec = tmp;
      vec->capacity = new_capacity;
   }
   return true;
}

// Pushes a value to vector
bool G(vec_push)(G(vec_Vector) *vec, VEC_ITEM_TYPE item) {
   if (vec->len == 0 && vec->capacity == 0) {
      vec->vec = malloc(sizeof(vec->vec[0]));
      if (!vec->vec) {
         return false;
      }

      vec->vec[0] = item;
      vec->len = 1;
      vec->capacity = sizeof(vec->vec[0]);
      return true;
   }

   G(vec_fit)(vec);
   vec->vec[vec->len] = item;
   vec->len++;
   return true;
}

#endif
#undef VEC_ITEM_TYPE
#undef VEC_SUFFIX



Leave a Comment