the magic of dispatch tables and dynamic arrays

Posted on Wed 29 November 2017 in code

I love C. Quite simply, I find it an incredibly fun language to program in. Even through all the weird, little Heisenbugs, the segmentation faults, the incredibly confusing linker errors, it is still my favorite programming language by far. You will hear a lot of bad press about C:

“There is no memory safety!”


“The typing system is dated and unreliable!”

maybe even

“The language makes it far too easy to shoot yourself in the foot!”

And granted, these criticisms are not without merit. C is a old language; the origins of C take place around 1971, when Dennis M. Ritchie of Bell Labs rewrote B as a language named NB, which he eventually refined into C. However, in my opinion the greatest sins commonly committed by C programmers is the tendency to snob the features and inventions of other languages, dismissing potentially useful constructs with an attitude of it being the “easy way out,” even when there is a great productivity boon to be had. Two of these constructs are the dynamic array and the dispatch table, both common in modern, dynamically typed languages.

The dynamic array is the simpler of the two concepts, and the most ubiquitous:

# instantiate an array containing `1, 2, 3`
my @array = qw/1 2 3/;

is a simple, contrived example of an array (or more pedantically, list,) of length 3 in Perl. Unlike C, if you want to change the length of the array, it would be as simple as:

# instantiate an array containing `1, 2, 3`
my @array = qw/1 2 3/;
# append `4` and `5`
push @array, 4;
push @array, 5;
# pop `5` off the end
pop @array;
# shift `1` off the beginning
shift @array;
# prepend `1`
unshift @array, 1;
# prints `1, 2, 3, 4`
print join ' ', @array;

and you now have an array of length 4 containing 1, 2, 3, 4.

Easy, right? A dispatch table is a slightly more complex beast, but really not all that complicated either. A dispatch table is simply a table of functions which you can refer to by index to call:

# Define the table using one anonymous code-ref and one named code-ref
my %dispatch = (
    hi => sub {  return 'hello'; },
    bye => \&say_goodbye,

sub say_goodbye {
    return "goodbye";

# Fetch the code ref from the table, and invoke it
print $dispatch{hi}->();
print $dispatch{bye}->();

which will simply call the subroutines indexed by the entries “hi” and “bye”.

“Now this is all well and good, but this is Perl! I thought this post was about C?!” Ah, but it is! Although the code required to implement these constructs may not be quite the same, and a few semantics may be a bit different, it is indeed possible to implement these just as satisfactorily in C.

To implement a dynamic array data structure, since C is a statically typed language, you have to pick what kind of data this will be an array of. To keep things simple, I will be demonstrating using an int lists but I have just as easily applied this same technique to string lists, struct lists, and even void * lists.

A simple implementation in C would look something like this:

(This code depends only on the standard library; you are encouraged to compile and try it out yourself)

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

/* struct definition for dynamic array */
struct int_list {
    /* `size_t` members to keep track of current length and allocation size */
    size_t cnt, max;
    /* dynamically allocated array containing our data */
    int *list;

/* `malloc()` wrapper */
static inline void xmalloc(void *restrict ptr, size_t sz, char const *msg)
    /* sanity check */
    if (!ptr)
    /* allocate or die */
    if (!(*(void **)ptr = malloc(sz))) {
        fprintf(stderr, "%s", msg ? msg : "xrealloc()");

/* `calloc()` wrapper */
static inline void xcalloc(void *restrict ptr, size_t nmemb, size_t sz, char const *msg)
    /* sanity check */
    if (!ptr)
    /* allocate or die */
    if (!(*(void **)ptr = calloc(nmemb, sz))) {
        fprintf(stderr, "%s", msg ? msg : "xcalloc()");

/* `realloc()` wrapper */
static inline void xrealloc(void *restrict ptr, size_t sz, char const *msg)
    void *tmp;
    /* sanity check */
    if (!ptr)
    /* allocate or die */
    if (!(tmp = realloc(*(void **)ptr, sz))) {
        free(*(void **)ptr);
        fprintf(stderr, "%s", msg ? msg : "xrealloc()");
    *(void **)ptr = tmp;

/* initilization of our dynamic array */
static inline void array_init(struct int_list *restrict list_struct)
    /* initialize current length to `0` and current size to `1` */
    list_struct->cnt = 0;
    list_struct->max = 1;
    xcalloc(&list_struct->list, 1, sizeof *list_struct->list, "array_init()");

/* append an integer to our array */
static inline void array_append(struct int_list *restrict list_struct, int value)
    /* increment length */
    /* realloc if `cnt` reaches current size */
    if (list_struct->cnt >= list_struct->max) {
        /* check if size too large */
        if (list_struct->cnt > (SIZE_MAX / 2 - 1))
        /* reallocate double current size */
        list_struct->max <<= 1;
        xrealloc(&list_struct->list, sizeof *list_struct->list * list_struct->max, "array_append()");
    /* append the value */
    list_struct->list[list_struct->cnt - 1] = value;

int main(void)
    /* declare a dynamic array and initialize it */
    struct int_list dyn_arr;

    /* append `0, 1, 2, 3, 4` */
    for (size_t i = 0; i < 5; i++)
        array_append(&dyn_arr, i);

    /* print out the values */
    for (size_t i = 0; i < dyn_arr.cnt; i++)
        printf("%s[%zu] = %d\n", "dyn_arr", i, dyn_arr.list[i]);

    /* free our list now that we are done */

    return 0;

This may seem like more code than necessary, and it may well be, but doing your implementation in this manner allows you to easily reuse your code; say when you decide you want a list of strings (char *) instead of integers. All you have to do is a quick text substitution in a few places, and you have a fairly generic implementation that can be applied anywhere. In addition, since you allocate double the current size every time you call realloc(), you end up with an “amortized” dynamic array, which, in simple terms, means that when you append a value you end up only paying the cost of reallocation every power-of-two array length.

The wrapping of the allocation functions allows to to simplify your error checking, while keeping the code around your allocations clean and uncluttered. Reducing the work you do may seem lazy, but in fact it is the best way to keep your code bug-free; the less chance you have of eliding important, though tedious, tasks such as check the return of malloc(), the less chance of human error in general.

A dispatch table can also be implemented fairly easily in C using an array of function pointers. I recently used this data structure to vastly simplify the parsing of PGP packets, by have a dispatch table of constructor and destructor functions, which meant I could implement the parsing of a GnuPG key one packet at a time, and simply leave the other entries NULL until I got around to implementing them. Here is simplified version of my implementation.

(This snippet, unfortunately, is not compilable, but the full source can be found at alyptik/derpgp):

/* dispatch table forward declaration */
static size_t (*const dispatch_table[64][2])(PGP_PACKET *restrict);

/* function prototypes */
size_t parse_pubkey_packet(PGP_PACKET *restrict packet);
size_t parse_seckey_packet(PGP_PACKET *restrict packet);
size_t free_pubkey_packet(PGP_PACKET *restrict packet);
size_t free_seckey_packet(PGP_PACKET *restrict packet);

/* dispatch each packet to a parser */
size_t parse_pgp_packets(PGP_LIST *restrict pkts)
    size_t i;

    /* dispatch each packet to parsers */
    for (i = 0; i < pkts->cnt; i++) {
        /* get the type of the packet */
        int packet_type = TAGBITS(pkts->list[i].pheader);
        /* use the type as an index into the table of function pointers */
        size_t (*const parse_pkt)(PGP_PACKET *restrict) = dispatch_table[packet_type][0];
        if (parse_pkt)

    return i;

/* free list of packets */
static inline void free_pgp_list(PGP_LIST *restrict pkts)
    /* return if passed NULL pointers */
    if (!pkts || !pkts->list)
    for (size_t i = 0; i < pkts->cnt; i++) {
        /* get the type of the packet */
        int packet_type = TAGBITS(pkts->list[i].pheader);
        /* use the type as an index into the table of function pointers */
        size_t (*const cleanup_pkt)(PGP_PACKET *restrict) = dispatch_table[packet_type][1];
        if (cleanup_pkt)
    pkts->list = NULL;
    pkts->cnt = 0;
    pkts->max = 1;

/* static function pointer array indexed by packet tag number */
static size_t (*const dispatch_table[64][2])(PGP_PACKET *restrict) = {
    [TAG_RSRVD] = {0},
    [TAG_PKESESS] = {0},
    [TAG_SIG] = {0},
    [TAG_SKESESS] = {0},
    [TAG_OPSIG] = {0},
    [TAG_SECKEY] = {parse_seckey_packet, free_seckey_packet},
    [TAG_PUBKEY] = {parse_pubkey_packet, free_pubkey_packet},
    [TAG_SECSUBKEY] = {parse_seckey_packet, free_seckey_packet},
    [TAG_CDATA] = {0},
    [TAG_SEDATA] = {0},
    [TAG_MARKER] = {0},
    [TAG_LITDATA] = {0},
    [TAG_TRUST] = {0},
    [TAG_UID] = {0},
    [TAG_PUBSUBKEY] = {parse_pubkey_packet, free_pubkey_packet},
    [TAG_UATTR] = {0},
    [TAG_SEIPDATA] = {0},
    [TAG_MDCODE] = {0},
    [TAG_PRVT0] = {0},
    [TAG_PRVT1] = {0},
    [TAG_PRVT2] = {0},
    [TAG_PRVT3] = {0},

Just like that, I suddenly have a modular, reusable system for dispatching to the relevant constructor and destructor functions. I can implement them at whatever pace works for me, and leave the unimplemented entries NULL. This allows a simple if (ptr) { check inside of a for loop to suffice for dispatching to all of the implemented functions in my table; safely, correctly, and most important of all, easily. Keeping your code simple and too the point, decoupling and isolating as many part of your program as possible, and keeping an open mind are crucial if you want to keep you code maintainable by others as well as yourself.

Maybe you are an old, grizzled C veteran who cares not for all these fancy new languages, or maybe your aren't. Maybe C is a large part of your day-to-day career, or maybe you are just a C-hacker on the weekends. Regardless of your current relationship with C, it would be a grave mistake to ignore the innovations that other languages offer. It is an undisputed tautology that an open mind will always have an advantage over a closed one, and you will find that many useful data structures and algorithms from other programming languages are actually completely language-agnostic.

So give it a shot; who knows, learning a little Perl or Python may, in fact, end up being the best decision you ever made.