Generic Programming in C

How to do generic programming in C

2 minute read

Generic programming is an important idea in programming. In languages like Java and C++, it can be done easily. In this post, I show how to do it in plain old C.

We use the classic stack implementation. First, we implement an int version.

This is stack.h:

typedef struct {
  int *elems;
  int logLength;
  int allocLengh;
} stack;

void StackNew(stack *s);
void StackDispose(stack *s);
void StackPush(stack *s, int value);
int StackPop(stack *s);

This is stack.c:

#include "stack.h"
#include <stdio.h>
#include <stdlib.h>

void StackNew(stack *s) {
  s->logLength = 0;
  s->allocLengh = 4;
  s->elems = (int *)malloc(sizeof(int) * 4);
}

void StackDispose(stack *s) { free(s->elems); }

void StackPush(stack *s, int value) {
  if (s->logLength == s->allocLengh) {
    s->allocLengh *= 2;
    s->elems = (int *)realloc(s->elems, s->allocLengh * sizeof(int));
  }

  s->elems[s->logLength] = value;
  s->logLength++;
}

int StackPop(stack *s) {
  s->logLength--;
  return s->elems[s->logLength];
}

Now we make it generic.

Here is stack_gen.h:

typedef struct {
  void *elems;
  int elemSize;
  int logLength;
  int allocLength;
  void (*freefn)(void *);
} stack;

void StackNew(stack *s, int elemSize, void(*freefn)(void *));
void StackDispose(stack *s);
void StackPush(stack *s, void *elemAddr);
void StackPop(stack *s, void *elemAddr);

Here is stack-gen.c:

#include "stack_gen.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>

static void StackGrow(stack *s) {
  s->allocLength *= 2;
  s->elems = realloc(s->elems, s->allocLength * s->elemSize);
}

void StackNew(stack *s, int elemSize, void (*freefn)(void *)) {
  s->elemSize = elemSize;
  s->logLength = 0;
  s->allocLength = 4;
  s->elems = malloc(4 * elemSize);
  s->freefn = freefn;
  assert(s->elems != NULL);
}

void StackDispose(stack *s) {
  if (s->freefn != NULL) {
    for (int i = 0; i < s->logLength; ++i) {
      s->freefn((char *)s->elems + i * s->elemSize);
    }
  }
  free(s->elems);
}

void StackPush(stack *s, void *elemAddr) {
  if (s->logLength == s->allocLength) {
    StackGrow(s);
  }
  void *target = (char *)s->elems + s->logLength * s->elemSize;
  memcpy(target, elemAddr, s->elemSize);
  s->logLength++;
}

void StackPop(stack *s, void *elemAddr) {
  s->logLength--;
  void *source = (char *)s->elems + s->logLength * s->elemSize;
  memcpy(elemAddr, source, s->elemSize);
}

This is the code from the course Programming Paradigms (lecture 5 - 7) by Stanford. This post serves as a bookmark for me and I’m not gonna explain it better than the professor. So if you don’t understand, just watch the video, it is good material for learning C.